dominant.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 <assert.h>
#include <stdio.h>
#include "dominant.h"
#include "point.h"

/*** global variables *************************************/
#define NPs 1001

/* static point PTS[NPs] __attribute__ ((aligned (CLS))); */
    
/*** file scope macro definitions *************************/

/*** file scope type declarations *************************/
    
/*** file scope variables *********************************/

/*** file scope functions declarations ********************/

/*** public functions declarations ************************/

/*** file scope functions *********************************/

static sureInline(void) swap(int* a, int* b);

/* static int isDominated(point* PS, int* idx, int n, int j, int exclude); */

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

static sureInline(void) swap(int* a, int* b)
{
  int t;

  t = *a;
  *a = *b;
  *b = t;
}

/*** public functions *************************************/

int dominant(point* PS, int* idx, int n, 
             point *o, 
             point *p,
             int hypoct,
             int exclude,
             struct dominantData* dod
             )
{
  point *PTS;
  int i;                        
  int j;
  int k;                        
  int R;                        
  /* static point newo; */
  point newo;

  int* localidx;                
  PTS = dod->PTS;
  localidx = dod->localidx;

  /* static int localidx[NPs];     /\**< A local ordering of points *\/ */
  /* int localidx[NPs];     /\**< A local ordering of points *\/ */

  /* printf("o: %.2f %.2f %.2f\n", o->x[0], o->x[1], o->x[2]); */
  /* printf("p: %.2f %.2f %.2f\n", p->x[0], p->x[1], p->x[2]); */
  /* printf("hypoct: %x\n", hypoct); */

  assert(n < NPs);

  /* if(n > 100) */
  /*   printf("Big dominat\n"); */

  projectOne(&newo, p, hypoct, o);
  /* printf("newo: %.2f %.2f %.2f\n", newo.x[0], newo.x[1], newo.x[2]); */
  i = 0;
  while(i < n)
    {
      /* printf("Initial %d : %.2f %.2f %.2f \t", idx[i], PS[idx[i]].x[0], PS[idx[i]].x[1], PS[idx[i]].x[2]); */
      intercept(&(PTS[i]), &newo, &(PS[idx[i]]));
      /* printf("Projected %d : %.2f %.2f %.2f\n", idx[i], PTS[i].x[0], PTS[i].x[1], PTS[i].x[2]); */
      
      i++;
    }

  k = n;
  i = n;
  while(i > 0)
    {
      i--;

      R = 0;
      j = n;
      while(!R && j > k)
        {
          j--;
          R = (classify(&(PTS[localidx[j]]), &(PTS[i])) & ~exclude) == 0;
        }
      
      if(R == 0)               
        {
          k--;
          localidx[k] = i;
        }
    }

  /* printf("Initial pass %d points \t", n-k); */
  /* j = k; */
  /* while(j < n) */
  /*   { */
  /*     printf("%.2f %.2f %.2f \t", PTS[localidx[j]].x[0], PTS[localidx[j]].x[1], PTS[localidx[j]].x[2]); */
  /*     j++; */
  /*   } */
  /* printf("\n"); */

  while(k < n)
    {
      R = 0;
      j = 0;
      while(!R && j < i)
        {
          R = (classify(&(PTS[localidx[j]]), &(PTS[localidx[k]])) & ~exclude) == 0;
          j++;
        }
      
      if(R == 0)               
        {
          localidx[i] = localidx[k];
          i++;
        }
      k++;
    }

  j = 0;
  while(j < i)
    {
      swap(&idx[j], &idx[localidx[j]]);
      j++;
    }

  /* printf("Second pass %d points \t", i); */
  /* j = 0; */
  /* while(j < i) */
  /*   { */
  /*     printf("%.2f %.2f %.2f \t", PTS[localidx[j]].x[0], PTS[localidx[j]].x[1], PTS[localidx[j]].x[2]); */
  /*     j++; */
  /*   } */
  /* printf("\n"); */


  /* printf("First %d points \t", i); */
  /* j = 0; */
  /* while(j < n) */
  /*   { */
  /*     printf("point %d : %.2f %.2f %.2f \t", idx[j], PS[idx[j]].x[0], PS[idx[j]].x[1], PS[idx[j]].x[2]); */
  /*     j++; */
  /*   } */
  /* printf("\n"); */

  return i;
}