#include <stdio.h>
#include <stdlib.h>
#define NDAT 10000000
#define DIM 3
class Obj
{
public:
int val[DIM];
int rank[DIM];
int idx;
int flag;
int flag2;
class Obj *next;
class Obj *prev;
};
Obj *oHead=NULL;
void AddObj(Obj *o)
{
o->prev=NULL;
o->next=oHead;
if(oHead)oHead->prev = o;
oHead=o;
}
void DelObj(Obj *o)
{
o->flag = 0;
if(o->prev)o->prev->next=o->next;
if(o->next)o->next->prev=o->prev;
if(oHead ==o) oHead = o->next;
}
Obj objs[NDAT];
#define DELMAX (NDAT/10)
Obj *dellist[DELMAX];
int ndel;
int ncomp=0;
int akillb(Obj *a, Obj *b)
{
int i;
ncomp++;
for(i=0;i<DIM;i++)if((a->val[i]) < (b->val[i])) return 0;
return 1;
}
int main(int argc, char **argv)
{
int i;
for(i=0;i<NDAT;i++)
{
Obj *o = &objs[i];
o->idx = i;
int k;
for(k=0;k<DIM;k++) o->val[k] = (rand()>>8)%10000;
o->flag=1;
}
for(i=0;i<NDAT;i++)
{
Obj *o = &objs[i];
int d;
Obj *o2;
ndel=0;
for(o2=oHead;o2!=NULL;o2=o2->next)
{
if(akillb(o,o2))
{
dellist[ndel++]=o2;
}
}
if(ndel)
{
int j;
for(j=0;j<ndel;j++)
{
Obj *oo = dellist[j];
DelObj(oo);
}
}
else
{
for(o2=oHead;o2!=NULL;o2=o2->next)
{
if(akillb(o2,o))
{
o->flag = 0;
o=NULL;
break;
}
}
}
if(o!=NULL)
{
AddObj(o);
}
}
int nlist=0;
Obj *o2;
for(o2=oHead; o2!=NULL; o2=o2->next)
{
nlist++;
}
printf("#total %d %d compare %d\n", nlist, NDAT, ncomp);
}