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)
{
  dst->n = src->n;
  memcpy(&(dst->PS[0]), &(src->PS[0]), (src->n)*sizeof(point));
  dst->r = 0; /* Start at partial value 0 */
}

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

  dst->r = 0; /* Do not copy results */
}

void merge(jobData* dst, taskData* src)
{
  dst->r += src->r;
}

void  publish(int jid, jobData* jd)
{
  printf("%1.10f\n", jd->r);
}

/* 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);

/* file scope functions */

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;                     
  if(d->n < N)
  /* if(1 == d->n) */
    {  
      switch(d->n)
        {
        case 1:             
          intercept(&p, &(d->o), &(jd->PS[d->idx[0]]));
          d->r += HV(&(d->z), &p);
          break;
        case 2:             
          intercept(&p, &(d->o), &(jd->PS[d->idx[0]]));
          d->r += HV(&(d->z), &p);
          intercept(&pp, &(d->o), &(jd->PS[d->idx[1]]));
          d->r += HV(&(d->z), &pp);
          intercept(&p, &p, &pp); 
          d->r -= HV(&(d->z), &p);
          break;
        default:
          d->r += InExClusion(&(d->z), &(d->o), d->n, d->idx, jd->PS, &(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;                     
  point p;                      
  point pp;                     
  double max;                   
  int* nidx;                    
  taskData ld;                  
  max = -DBL_MAX;               
  i = 0;
  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(&p, &(d->o), &(jd->PS[d->idx[j]]));
  d->r += HV(&(d->z), &p);
  drop(d->idx, &(d->n), j);

  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;

  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));

      prun(d, d->n >= N);
      /* prun(d, ld.n+1 >= jd->n);              /\**< Recursive call to quickHyperVolume *\/ */
    }

  freeDivision(&di);
}
/* paper: 0 */

/* public functions */

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