#include <stdio.h>
#include <stdlib.h>
#include "isort.h"
#define NDAT 100000
#define DIM 10
class Obj
{
public:
BtNode *bn[DIM];
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];
Btree *bt[DIM];
#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<DIM;i++) bt[i] = new Btree();
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;
int rank_max=-999, rank_min=NDAT*2, dim_max, dim_min;
for(d=0;d<DIM;d++)
{
BtNode *bn = bt[d]->Insert(o->val[d], (void *)o);
o->rank[d]= bn->rank;
o->bn[d]=bn;
if(bn->rank > rank_max)
{
rank_max=bn->rank;
dim_max=d;
}
if(bn->rank < rank_min)
{
rank_min=bn->rank;
dim_min=d;
}
}
BtNode *bn0 = o->bn[dim_min];
BtNode *bn;
ndel=0;
for(bn=bt[dim_min]->Head; bn!=bn0; bn = bn->next)
{
Obj *o2 = (Obj *)(bn->ptr);
if(akillb(o,o2))
{
dellist[ndel++]=o2;
}
}
if(ndel)
{
int j;
for(j=0;j<ndel;j++)
{
Obj *o2 = dellist[j];
int d;
for(d=0;d<DIM;d++)
{
BtNode *n = bt[d]->Delete(o2->bn[d]);
if(n!=NULL)
{
Obj *o3 = (Obj *)(n->ptr);
o3->bn[d] = n;
}
}
DelObj(o2);
}
}
else
{
bn0 = o->bn[dim_max];
for(bn=bt[dim_max]->Tail; bn!=bn0; bn = bn->prev)
{
Obj *o2 = (Obj *)(bn->ptr);
if(akillb(o2,o))
{
int d;
for(d=0;d<DIM;d++)
{
BtNode *n = bt[d]->Delete(o->bn[d]);
if(n!=NULL)
{
Obj *o3 = (Obj *)(n->ptr);
o3->bn[d] = n;
}
}
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);
#if 0
#endif
}