multi-dimensional data comparison: using sort list

#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;
};

//simple list
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];// = new Btree();

#define DELMAX (NDAT/10)
Obj *dellist[DELMAX];
int ndel;

int ncomp=0; //count calls
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();

    // Init data
    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;
    }

    //begin insert
    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++)
	{
	    // insert
	    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;
	    }
	}

	// check min_rank
	BtNode *bn0 = o->bn[dim_min];
	BtNode *bn;
	ndel=0;

	// new entry o kills o2 in the current list?

	for(bn=bt[dim_min]->Head; bn!=bn0; bn = bn->next)
	{
	    Obj *o2 = (Obj *)(bn->ptr);
	    if(akillb(o,o2))
	    {
		//printf("new Kill old happen\n");
		dellist[ndel++]=o2;
	    }
	}

	//new entry kills
	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;
		    }
		}//d

		DelObj(o2);
	    }//delete
	}
	else
	{
	    bn0 = o->bn[dim_max];
	    // Old kill new
	    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;
			}
		    }//d
		    o->flag = 0;
		    o=NULL;
		    break;
		}
	    }// loop old
	}// else

	if(o!=NULL)
	{
	    AddObj(o);
	    //printf("#Adding %d\n",i);
	}
    }//i

    // loop list
    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
    // begin check;
    for(i=0;i<NDAT;i++)
    {
	Obj *o = &objs[i];
	o->flag2=1;
    }

    int j;
    for(i=0;i<NDAT;i++)
    {
	Obj *o = &objs[i];
	for(j=i+1;j<NDAT;j++)
	{
	    Obj *o2 = &objs[j];
	    if(akillb(o,o2))o2->flag2=0;
	    if(akillb(o2,o))o->flag2=0;
	}
    }

    for(i=0;i<NDAT;i++)
    {
	Obj *o = &objs[i];
	if(o->flag != o->flag2)printf("#Error flag \n");
    }
#endif

}