quickhvolume.c

/* 
 * 
 * Copyright (c) Year(s), 2013, Luis M. S. Russo and Alexandre 
 * P. Francisco / KDBIO / INESC-ID, <qhv@kdbio.inesc-id.pt> 
 *  
 * Any published media that is related with to use of the distributed 
 * software, or derived software, must contain a reference to "Extending 
 * quick hypervolume. Luís M. S. Russo, Alexandre P. Francisco: 
 * J. Heuristics 22(3): 245-271 (2016)".
 *  
 * Permission to use, copy, modify, and/or distribute this software for 
 * any purpose with or without fee is hereby granted, provided that the 
 * above copyright notice and this permission notice appear in all 
 * copies. 
 *  
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL 
 * WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED 
 * WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE 
 * AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL 
 * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR 
 * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER 
 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 
 * PERFORMANCE OF THIS SOFTWARE. 
 * 
 */

#include <pthread.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <float.h>
#include <strings.h>
#include <sys/types.h>  /* basic system data types */
#include <limits.h>     /* PIPE_BUF */
#include "unionFilter.h"
#include "quickhvolume.h"
#include "constants.h"
#include "HSO.h"
#include "subsets.h"
#include "division.h"
#include "splitter.h"
#include "macros.h"
#include "inexclusion.h"
#include "tpool.h"


void openBox(toolBox* b)
{
#warning TODO: There should be a better solution to the initUnion problem.

  b->spt.uD.size = 0; /* This was hidden in a static variable. */
  initUnion(NPOINTS, &(b->spt.uD));                 
  initSplitter(&(b->spt));
}

void closeBox(toolBox* b)
{
  destroySplitter(&(b->spt));
}

int   priority(taskData* d)
{
  return d->n;
}

void jobCopy(jobData* dst, jobData* src)
{
  int i;

  dst->n = src->n;
  memcpy(&(dst->PS[0]), &(src->PS[0]), (src->n)*sizeof(point));

  i = 0;
  while(i < src->n)
    {
      dst->r[i] = 0;
      i++;
    }
}

void taskCopy(taskData* dst, taskData* src)
{
  int i;

  memcpy(dst, src, offsetof(struct taskData, idx));
  memcpy(&(dst->idx[0]), &(src->idx[0]), (src->n)*sizeof(int));

  i = 0;
  while(i < src->n)
    {
      dst->r[i] = 0;
      i++;
    }
}

void merge(jobData* dst, taskData* src)
{
  int i;

  i = 0;
  while(i < src->n)
    {
      dst->r[src->idx[i]] += src->r[i];
      i++;
    }
}

void  publish(int jid, jobData* jd)
{
  int i;

  i = 0;
  while(i < jd->n)
    {
      printf("Ex[%d] = %1.10f\t", i, jd->r[i]);
      i++;
    }
  printf("\n");
}

/* global variables */

/* file scope macro definitions */

/* file scope type declarations */

/* file scope variables */

/* file scope functions declarations */

static void quickHVolumeR(toolBox* b, taskData* d, const jobData* jd);

static void drop(int* idx, int* n, int j);

static sureInline(void) swapD(double* r, int n, int j);

/* file scope functions */

static sureInline(void) swapD(double* r, int n, int j)
{
  double t;
  
  t = r[n];
  r[n] = r[j];
  r[j] = t;
}

static void drop(int* idx, int* n, int j)
{
  (*n)--;
  idx[j] = idx[*n];
}

void quickHVolumeS(toolBox* b, taskData* d, const jobData* jd)
{
  point p;                      
  point pp;                     
  double tp[3];                 
  if(d->n < N)
  /* if(1 == d->n) */
    {  
      switch(d->n)
        {
        case 1:             
          intercept(&p, &(d->o), &(jd->PS[d->idx[0]]));
          d->r[0] += HV(&(d->z), &p);
          break;
        case 2:             
          intercept(&p, &(d->o), &(jd->PS[d->idx[0]]));
          tp[0] = HV(&(d->z), &p);

          intercept(&pp, &(d->o), &(jd->PS[d->idx[1]]));
          tp[1] = HV(&(d->z), &pp);

          intercept(&p, &p, &pp); 
          tp[2] = HV(&(d->z), &p);

          d->r[0] += tp[0] - tp[2];  
          d->r[1] += tp[1] - tp[2];  
          break;

        default:
          exInExClusion(&(d->z), &(d->o), d->n, d->idx, jd->PS, d->r, &(b->iex));
          break;
        }
    }
  else 
    {
      quickHVolumeR(b, d, jd);
    }
}

/* paper: 1 */
static void quickHVolumeR(toolBox* b, taskData* d, const jobData* jd)
{
  double hv;                    
  division di;                  
  int i, j, k;                  
  point p;                      
  point pp;                     
  point ppp;                    
  double max;                   
  int* nidx;                    
  taskData ld;                  
  int lidx[NPOINTS];            
  point* A[3];                  

  k = 0;
  A[0] = &(d->o);
  A[1] = &ppp;
  A[2] = &p;
  while(k < 2)                  
    {
      max = -DBL_MAX;               
      i = k;
      while(i < d->n)
        {
          intercept(&pp, &(d->o), &(jd->PS[d->idx[i]]));
          hv = objective(&(d->z), &pp, &(d->o));
          if(hv > max)
            {                       
              max = hv;
              j = i;
            }
          i++;
        }
      intercept(A[k+1], A[k], &(jd->PS[d->idx[j]]));
      swap(d->idx, k, j);          
      swapD(d->r, k, j);           
      k++;
    }

  /* d->r += HV(&(d->z), &p); */

  i = 0;
  while(i < d->n)
    {
      intercept(&pp, &(d->o), &(jd->PS[d->idx[i]]));
      push(d->idx[i], classify(&p, &pp), &(b->spt));
      i++;
    }
  di = newDivision(&(jd->PS[0]), &(d->o), &p, &(b->spt));

  ld.o = d->o;
  ld.z = d->z;
  ld.n = d->n;
  memcpy(ld.idx, d->idx, (d->n)*sizeof(int));
  memcpy(ld.r, d->r, (d->n)*sizeof(double));

  i = 0;
  while(i < d->n)
    {
      lidx[d->idx[i]] = i;         
      i++;
    }

  while(hasNext(di))
    {
      nidx = next(di, &j, &(d->n));
      memcpy(d->idx, nidx, (d->n)*sizeof(int));
      projectZero(&(d->z), &p, j, &(ld.z));
      projectOne(&(d->o), &p, j, &(ld.o));
      memset(d->r, 0, sizeof(double)*d->n);

      prun(d, d->n >= N);

      i = 0;
      while(i < d->n)
        {
          ld.r[lidx[d->idx[i]]] += d->r[i];
          i++;
        }
#warning DONE. Regrouping is OK.
    }
  freeDivision(&di);

  d->o = ld.o;
  d->z = ld.z;
  d->n = ld.n;
  memcpy(d->idx, ld.idx, (d->n)*sizeof(int));
  memcpy(d->r, ld.r, (d->n)*sizeof(double));
}
/* paper: 0 */

/* public functions */

/* ------------------------------------------------------ */