#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <float.h>
#include <math.h>

#include "rtree.h"

#define  METHODS  1

typedef struct _RTREEPARTITION
{
 int   partition[MAXCARD+1];
 int   total;
 int   minfill;
 int   taken[MAXCARD+1];
 int   count[2];
 RTREEMBR cover[2];
 REALTYPE area[2];
} RTREEPARTITION;

typedef struct _RTREENODE
{
 int count;
 int level;
 RTREEBRANCH  branch[MAXCARD];
}RTREENODE;

typedef struct _RTREELISTNODE
{
     struct _RTREELISTNODE *next;
     RTREENODE  *node;
}RTREELISTNODE;

typedef struct _RTREEROOT
{
 RTREENODE*  root_node;
 
 RTREEBRANCH  BranchBuf[MAXCARD+1];
 int    BranchCount;
 RTREEMBR  CoverSplit;
 REALTYPE  CoverSplitArea;
 RTREEPARTITION Partitions[METHODS];

 PFNRTreeSearchCallback  pfnCallback;
} RTREEROOT;

#define BIG_NUM (FLT_MAX/4.0)

#define INVALID_RECT(x) ((x)->bound[0] > (x)->bound[DIMS_NUMB])

#ifndef MIN
 #define MIN(a, b) ((a) < (b) ? (a) : (b))
#endif
#ifndef MAX
 #define MAX(a, b) ((a) > (b) ? (a) : (b))
#endif

int NODECARD = MAXCARD;
int LEAFCARD = MAXCARD;

#define MINNODEFILL (NODECARD / 2)
#define MINLEAFFILL (LEAFCARD / 2)

#define MAXKIDS(n) ((n)->level > 0 ? NODECARD : LEAFCARD)
#define MINFILL(n) ((n)->level > 0 ? MINNODEFILL : MINLEAFFILL)

static int set_max(int *which, int new_max){
 if(2 > new_max || new_max > MAXCARD)
  return 0;
 *which = new_max;
 return 1;
}
static int RTreeSetNodeMax(int new_max) { return set_max(&NODECARD, new_max); }
static int RTreeSetLeafMax(int new_max) { return set_max(&LEAFCARD, new_max); }
static int RTreeGetNodeMax(void) { return NODECARD; }
static int RTreeGetLeafMax(void) { return LEAFCARD; }

static void _RTreeGetBranches(HRTREEROOT root, RTREENODE *node, RTREEBRANCH *br)
{
 int i;

 assert(node && br);
 
 for (i=0; i<MAXKIDS(node); i++)
 {
  assert(node->branch[i].child);
  root->BranchBuf[i] = node->branch[i];
 }

 root->BranchBuf[MAXKIDS(node)] = *br;
 root->BranchCount = MAXKIDS(node) + 1;

 root->CoverSplit = root->BranchBuf[0].mbr;

 for (i=1; i<MAXKIDS(node)+1; i++)
 {
  root->CoverSplit = RTreeCombineRect(&root->CoverSplit, &root->BranchBuf[i].mbr);
 }

 root->CoverSplitArea = RTreeRectSphericalVolume(&root->CoverSplit);
 RTreeInitNode(node);
}

static void _RTreeClassify(HRTREEROOT root, int i, int group, RTREEPARTITION *p)
{
 assert(p);
 assert(!p->taken[i]);

 p->partition[i] = group;
 p->taken[i] = TRUE;

 if (p->count[group] == 0)
  p->cover[group] = root->BranchBuf[i].mbr;
 else
  p->cover[group] = RTreeCombineRect(&root->BranchBuf[i].mbr, &p->cover[group]);
 
 p->area[group] = RTreeRectSphericalVolume(&p->cover[group]);
 p->count[group]++;
}

static void _RTreePickSeeds(HRTREEROOT root, RTREEPARTITION *p)
{
 int i, j, seed0=0, seed1=0;
 REALTYPE worst, waste, area[MAXCARD+1];

 for (i=0; i<p->total; i++)
  area[i] = RTreeRectSphericalVolume(&root->BranchBuf[i].mbr);
 
 worst = -root->CoverSplitArea - 1;
 
 for (i=0; i<p->total-1; i++)
 {
  for (j=i+1; j<p->total; j++)
  {
   RTREEMBR one_rect;
   one_rect = RTreeCombineRect(&root->BranchBuf[i].mbr, &root->BranchBuf[j].mbr);
   waste = RTreeRectSphericalVolume(&one_rect) - area[i] - area[j];
   if (waste > worst)
   {
    worst = waste;
    seed0 = i;
    seed1 = j;
   }
  }
 }
 _RTreeClassify(root, seed0, 0, p);
 _RTreeClassify(root, seed1, 1, p);
}
static void _RTreeLoadNodes(HRTREEROOT root, RTREENODE *n, RTREENODE *q, RTREEPARTITION *p)
{
 int i;
 assert(n && q && p);

 for (i=0; i<p->total; i++)
 {
  assert(p->partition[i] == 0 || p->partition[i] == 1);
  if (p->partition[i] == 0)
   RTreeAddBranch(root, &root->BranchBuf[i], n, NULL);
  else if (p->partition[i] == 1)
   RTreeAddBranch(root, &root->BranchBuf[i], q, NULL);
 }
}

static void _RTreeInitPart( RTREEPARTITION *p, int maxrects, int minfill)
{
 int i;
 assert(p);

 p->count[0] = p->count[1] = 0;
 p->cover[0] = p->cover[1] = RTreeNullRect();
 p->area[0] = p->area[1] = (REALTYPE)0;
 p->total = maxrects;
 p->minfill = minfill;
 for (i=0; i<maxrects; i++)
 {
  p->taken[i] = FALSE;
  p->partition[i] = -1;
 }
}

static void _RTreePrintPart(HRTREEROOT root, RTREEPARTITION *p)
{
 int i;
 assert(p);
 
 fprintf (stdout, "\npartition:\n");
 for (i=0; i<p->total; i++)
 {
  fprintf (stdout, "%3d\t", i);
 }
 fprintf (stdout, "\n");
 for (i=0; i<p->total; i++)
 {
  if (p->taken[i])
   fprintf (stdout, "  t\t");
  else
   fprintf (stdout, "\t");
 }
 fprintf (stdout, "\n");
 for (i=0; i<p->total; i++)
 {
  fprintf (stdout, "%3d\t", p->partition[i]);
 }
 fprintf (stdout, "\n");

 fprintf (stdout, "count[0] = %d  area = %f\n", p->count[0], p->area[0]);
 fprintf (stdout, "count[1] = %d  area = %f\n", p->count[1], p->area[1]);
 if (p->area[0] + p->area[1] > 0)
 {
  fprintf (stdout, "total area = %f  effectiveness = %3.2f\n", 
   p->area[0] + p->area[1], (float)root->CoverSplitArea / (p->area[0] + p->area[1]));
 }
 fprintf (stdout, "cover[0]:\n");
 RTreePrintRect(&p->cover[0], 0);

 fprintf (stdout, "cover[1]:\n");
 RTreePrintRect(&p->cover[1], 0);
}
static void _RTreeMethodZero(HRTREEROOT root, RTREEPARTITION *p, int minfill )
{
 int i;
 REALTYPE biggestDiff;
 int group, chosen=0, betterGroup=0;
 assert(p);

 _RTreeInitPart(p, root->BranchCount, minfill);
 _RTreePickSeeds(root, p);

 while (p->count[0] + p->count[1] < p->total && 
  p->count[0] < p->total - p->minfill && 
  p->count[1] < p->total - p->minfill)
 {
  biggestDiff = (REALTYPE)-1.;
  for (i=0; i<p->total; i++)
  {
   if (!p->taken[i])
   {
    RTREEMBR *r, rect_0, rect_1;
    REALTYPE growth0, growth1, diff;
    r = &root->BranchBuf[i].mbr;
    rect_0 = RTreeCombineRect(r, &p->cover[0]);
    rect_1 = RTreeCombineRect(r, &p->cover[1]);
    growth0 = RTreeRectSphericalVolume(&rect_0) - p->area[0]; 
    growth1 = RTreeRectSphericalVolume(&rect_1) - p->area[1];
    diff = growth1 - growth0;
    if (diff >= 0)
     group = 0;
    else
    {
     group = 1;
     diff = -diff;
    }
    if (diff > biggestDiff)
    {
     biggestDiff = diff;
     chosen = i;
     betterGroup = group;
    }
    else if (diff==biggestDiff && p->count[group]<p->count[betterGroup])
    {
     chosen = i;
     betterGroup = group;
    }
   }
  }
  _RTreeClassify(root, chosen, betterGroup, p);
 }
 if (p->count[0] + p->count[1] < p->total)
 {
  if (p->count[0] >= p->total - p->minfill)
   group = 1;
  else
   group = 0;
  
  for (i=0; i<p->total; i++)
  {
   if (!p->taken[i])
    _RTreeClassify(root, i, group, p);
  }
 }
 assert(p->count[0] + p->count[1] == p->total);
 assert(p->count[0] >= p->minfill && p->count[1] >= p->minfill);
}

static void _RTreeInitBranch( RTREEBRANCH *br )
{
 RTreeInitRect(&(br->mbr));
 br->child = NULL;
}

static void _RTreePrintBranch( RTREEBRANCH *br, int depth )
{
 RTreePrintRect(&(br->mbr), depth);
 RTreePrintNode(br->child, depth);
}

static int _RTreeInsertRect(HRTREEROOT root, RTREEMBR *mbr, void* tid,  RTREENODE *node, RTREENODE **new_node, int level)
{
 int i;
 RTREEBRANCH b;
 RTREENODE *n2;

 assert(mbr && node && new_node);
 assert(level >= 0 && level <= node->level);

 if (node->level > level)
 {
  i = RTreePickBranch(mbr, node);
  if (!_RTreeInsertRect(root, mbr, tid, node->branch[i].child, &n2, level))
  {
   node->branch[i].mbr = RTreeCombineRect(mbr, &(node->branch[i].mbr));
   return 0;
  }
  
  node->branch[i].mbr = RTreeNodeCover(node->branch[i].child);
  b.child = n2;
  b.mbr = RTreeNodeCover(n2);

  return RTreeAddBranch(root, &b, node, new_node);
 } 
 else if (node->level == level) 
 {
  b.mbr = *mbr;

#pragma warning(push) 
#pragma warning( disable : 4312 )
  b.child = ( RTREENODE *) tid;
#pragma warning(pop)

  return RTreeAddBranch(root, &b, node, new_node);
 }
 assert (FALSE);
 return 0;
}

static RTREELISTNODE * _RTreeNewListNode(void)
{
 return (RTREELISTNODE *) malloc(sizeof(RTREELISTNODE));
}

static void _RTreeFreeListNode(RTREELISTNODE *p)
{
 free(p);
}

static void _RTreeReInsert(RTREENODE *node, RTREELISTNODE **ne)
{
 RTREELISTNODE *ln = _RTreeNewListNode();
 ln->node = node;
 ln->next = *ne;
 *ne = ln;
}

static int _RTreeDeleteRect( RTREEMBR *mbr, void* tid, RTREENODE *node, RTREELISTNODE **ee)
{
 int i;

 assert(mbr && node && ee);
 assert(node->level >= 0);

 if (node->level > 0)  
 {
  for (i = 0; i < NODECARD; i++)
  {
   if (node->branch[i].child && RTreeOverlap( mbr, &(node->branch[i].mbr )))
   {
    if (!_RTreeDeleteRect( mbr, tid, node->branch[i].child, ee ))
    {
     if (node->branch[i].child->count >= MINNODEFILL) 
      node->branch[i].mbr = RTreeNodeCover( node->branch[i].child );
     else{ 
      _RTreeReInsert(node->branch[i].child, ee);
      RTreeDisconnectBranch(node, i);
     }
     return 0;
    }
   }
  }
  return 1;
 }

#pragma warning(push)
#pragma warning( disable : 4312 )

 for (i = 0; i < LEAFCARD; i++)
 {
  if ( node->branch[i].child && node->branch[i].child == (RTREENODE *) tid )
  {
   RTreeDisconnectBranch( node, i );
   return 0;
  }

 }
#pragma warning(pop)

 return 1;
}

static void _RTreeTabIn(int depth)
{
 int i;
 for(i=0; i<depth; i++){
 }
}


static int _RTreeSearchRect( RTREENODE *node, RTREEMBR *mbr, PFNRTreeSearchCallback pfnSHCB, void* pfnParam)
{
 int hitCount = 0;
 int i;

 assert(node && mbr);
 assert(node->level >= 0);
 
 if (node->level > 0)
 {
  for (i=0; i<NODECARD; i++){
   if (node->branch[i].child && RTreeOverlap(mbr, &node->branch[i].mbr))
    hitCount += _RTreeSearchRect(node->branch[i].child, mbr, pfnSHCB, pfnParam);
  }
 }
 else 
 {
#pragma warning(push)
#pragma warning( disable : 4311 )
  for (i=0; i<LEAFCARD; i++)
  {
   if (node->branch[i].child && RTreeOverlap(mbr, &node->branch[i].mbr))
   {
    hitCount++;
    if(pfnSHCB && ! pfnSHCB((void*)node->branch[i].child, pfnParam) )
     return hitCount; 

   }
  }
#pragma warning(pop)
 }
 return hitCount;
}

 void RTreeInitRect( RTREEMBR *mbr)
{
 int i;
 for (i=0; i<SIDES_NUMB; i++)
  mbr->bound[i] = (REALTYPE) 0;
}

 RTREEMBR RTreeNullRect(void)
{
 RTREEMBR mbr;
 int i;

 mbr.bound[0] = (REALTYPE) 1;
 mbr.bound[DIMS_NUMB] = (REALTYPE)-1;
 for (i=1; i<DIMS_NUMB; i++)
  mbr.bound[i] = mbr.bound[i+DIMS_NUMB] = (REALTYPE) 0;
 return mbr;
}

 void RTreePrintRect( RTREEMBR *mbr, int depth)
{
 int i;
 
 _RTreeTabIn(depth);
 fprintf (stdout, "mbr:\n");
 for (i = 0; i < DIMS_NUMB; i++) 
 {
  _RTreeTabIn(depth+1);
  fprintf (stdout, "%f\t%f\n", mbr->bound[i], mbr->bound[i + DIMS_NUMB]);
 }
}


 REALTYPE RTreeRectArea( RTREEMBR *mbr )
{
 if (INVALID_RECT(mbr))
  return (REALTYPE) 0;

 return (mbr->bound[DIMS_NUMB] - mbr->bound[0]) * (mbr->bound[DIMS_NUMB+1] - mbr->bound[1]);
}


 REALTYPE RTreeRectVolume( RTREEMBR *mbr )
{
 int i;
 REALTYPE vol = (REALTYPE) 1;

 if (INVALID_RECT(mbr))
  return (REALTYPE) 0;

 for(i=0; i<DIMS_NUMB; i++)
  vol *= (mbr->bound[i+DIMS_NUMB] - mbr->bound[i]);
 assert(vol >= 0.0);
 return vol;
}

const double UnitSphereVolumes[] = {
 0.000000,  
 2.000000,  
 3.141593,  
 4.188790,  
 4.934802,
 5.263789,
 5.167713,  
 4.724766, 
 4.058712,  
 3.298509,  
 2.550164, 
 1.884104,  
 1.335263, 
 0.910629,  
 0.599265,  /* dimension  14 */
 0.381443,  
 0.235331,  
 0.140981,  /* dimension  17 */
 0.082146,  
 0.046622,  
 0.025807,  /* dimension  20 */
};

#if DIMS_NUMB > 20
 #error "not enough precomputed sphere volumes"
#endif

#define UnitSphereVolume UnitSphereVolumes[DIMS_NUMB]

 REALTYPE RTreeRectSphericalVolume( RTREEMBR *mbr )
{
 int i;
 double sum_of_squares=0, radius;

 if (INVALID_RECT(mbr))
  return (REALTYPE) 0;
 
 for (i=0; i<DIMS_NUMB; i++) {
  double half_extent = (mbr->bound[i+DIMS_NUMB] - mbr->bound[i]) / 2;
  sum_of_squares += half_extent * half_extent;
 }
 radius = sqrt(sum_of_squares);
 return (REALTYPE)(pow(radius, DIMS_NUMB) * UnitSphereVolume);
}

 REALTYPE RTreeRectSurfaceArea( RTREEMBR *mbr )
{
 int i, j;
 REALTYPE sum = (REALTYPE) 0;

 if (INVALID_RECT(mbr))
  return (REALTYPE) 0;

 for (i=0; i<DIMS_NUMB; i++) {
  REALTYPE face_area = (REALTYPE)1;
  for (j=0; j<DIMS_NUMB; j++)

   if(i != j) {
    REALTYPE j_extent = mbr->bound[j+DIMS_NUMB] - mbr->bound[j];
    face_area *= j_extent;
   }
   sum += face_area;
 }
 return 2 * sum;
}

 RTREEMBR RTreeCombineRect( RTREEMBR *rc1, RTREEMBR *rc2 )
{
 int i, j;
 RTREEMBR new_rect;

 assert(rc1 && rc2);

 if (INVALID_RECT(rc1))
  return *rc2;

 if (INVALID_RECT(rc2))
  return *rc1;

 for (i = 0; i < DIMS_NUMB; i++)
 {
  new_rect.bound[i] = MIN(rc1->bound[i], rc2->bound[i]);
  j = i + DIMS_NUMB;
  new_rect.bound[j] = MAX(rc1->bound[j], rc2->bound[j]);
 }
 return new_rect;
}

 int RTreeOverlap( RTREEMBR *rc1, RTREEMBR *rc2)
{
 int i, j;
 assert(rc1 && rc2);

 for (i=0; i<DIMS_NUMB; i++)
 {
  j = i + DIMS_NUMB; 

  if (rc1->bound[i] > rc2->bound[j] || rc2->bound[i] > rc1->bound[j])
   return FALSE;
 }
 return TRUE;
}

 int RTreeContained( RTREEMBR *r, RTREEMBR *s)
{
 int i, j, result;
 assert(r && s);

 if (INVALID_RECT(r))
  return TRUE;

 if (INVALID_RECT(s))
  return FALSE;

 result = TRUE;
 for (i = 0; i < DIMS_NUMB; i++)
 {
  j = i + DIMS_NUMB; 
  result = result && r->bound[i] >= s->bound[i] && r->bound[j] <= s->bound[j];
 }
 return result;
}

void RTreeSplitNode(HRTREEROOT root, RTREENODE *node, RTREEBRANCH *br, RTREENODE **new_node)
{
 RTREEPARTITION *p;
 int level;
 assert(node && br);

 level = node->level;
 _RTreeGetBranches(root, node, br);
 p = &root->Partitions[0];
 _RTreeMethodZero(root, p, (level>0 ? MINNODEFILL : MINLEAFFILL));
 *new_node = RTreeNewNode();
 (*new_node)->level = node->level = level;
 _RTreeLoadNodes(root, node, *new_node, p);

 assert(node->count+(*new_node)->count == p->total);
}
void RTreeInitNode( RTREENODE *node )
{
 int i;
 node->count = 0;
 node->level = -1;
 for (i = 0; i < MAXCARD; i++)
  _RTreeInitBranch(&(node->branch[i]));
}
RTREENODE *RTreeNewNode(void)
{
 RTREENODE *node = (RTREENODE*) malloc(sizeof(RTREENODE));
 assert(node);
 RTreeInitNode(node);
 return node;
}

void RTreeFreeNode( RTREENODE *node )
{
 assert(node);
 free(node);
}
 void RTreePrintNode( RTREENODE *node, int depth )
{
 int i;
 assert(node);

 _RTreeTabIn(depth);
 fprintf (stdout, "node");

 if (node->level == 0)
  fprintf (stdout, " LEAF");
 else if (node->level > 0)
  fprintf (stdout, " NONLEAF");
 else
  fprintf (stdout, " TYPE=?");

#pragma warning(push) /* C4311 */
#pragma warning( disable : 4311 )
 fprintf (stdout, "  level=%d  count=%d  address=%o\n", node->level, node->count, (unsigned int) node);

 for (i=0; i<node->count; i++)
 {
  if(node->level == 0) {
   fprintf (stdout, "\t%ld: data = %ld\n", i, (unsigned int)node->branch[i].child);
  }
  else {
   _RTreeTabIn(depth);
   fprintf (stdout, "branch %d\n", i);
   _RTreePrintBranch(&node->branch[i], depth+1);
  }
 }
#pragma warning(pop)
}

 RTREEMBR RTreeNodeCover( RTREENODE *node )
{
 int i, first_time=1;
 RTREEMBR mbr;
 assert(node);

 RTreeInitRect(&mbr);

 for (i = 0; i < MAXKIDS(node); i++)
 {
  if (node->branch[i].child)
  {
   if (first_time)
   {
    mbr = node->branch[i].mbr;
    first_time = 0;
   }
   else
    mbr = RTreeCombineRect(&mbr, &(node->branch[i].mbr));
  }
 }
 return mbr;
}

 int RTreePickBranch( RTREEMBR *mbr, RTREENODE *node)
{
 RTREEMBR *r;
 int i, first_time = 1;
 REALTYPE increase, bestIncr=(REALTYPE)-1, area, bestArea=0;
 int best=0;
 RTREEMBR tmp_rect;
 assert(mbr && node);

 for (i=0; i<MAXKIDS(node); i++)
 {
  if (node->branch[i].child)
  {
   r = &node->branch[i].mbr;
   area = RTreeRectSphericalVolume(r);
   tmp_rect = RTreeCombineRect(mbr, r);
   increase = RTreeRectSphericalVolume(&tmp_rect) - area;
   if (increase < bestIncr || first_time)
   {
    best = i;
    bestArea = area;
    bestIncr = increase;
    first_time = 0;
   }
   else if (increase == bestIncr && area < bestArea)
   {
    best = i;
    bestArea = area;
    bestIncr = increase;
   }
  }
 }
 return best;
}

 int RTreeAddBranch(HRTREEROOT root, RTREEBRANCH *br, RTREENODE *node, RTREENODE **new_node)
{
 int i;
 assert(br && node);
 
 if (node->count < MAXKIDS(node))
 {
  for (i = 0; i < MAXKIDS(node); i++)
  {
   if (node->branch[i].child == NULL)
   {
    node->branch[i] = *br;
    node->count++;
    break;
   }
  }
  return 0;
 }
 
 assert(new_node);
 RTreeSplitNode(root, node, br, new_node);
 
 return 1;
}
 void RTreeDisconnectBranch( RTREENODE *node, int i )
{
 assert(node && i>=0 && i<MAXKIDS(node));
 assert(node->branch[i].child);

 _RTreeInitBranch(&(node->branch[i]));
 node->count--;
}

 void RTreeDestroyNode ( RTREENODE *node )
{
 int i;

 if (node->level > 0) 
 {
  for ( i = 0; i < NODECARD; i++) 
  {
   if ( node->branch[i].child ) 
    RTreeDestroyNode ( node->branch[i].child );
  }
 }

 RTreeFreeNode( node );
}
HRTREEROOT RTreeCreate(PFNRTreeSearchCallback  pfnSearchCallback)
{
 RTREEROOT * root = (RTREEROOT*) malloc(sizeof(RTREEROOT));
 assert(root);
 root->root_node = RTreeNewNode();
 assert(root->root_node);
 root->root_node->level = 0;
 root->pfnCallback = pfnSearchCallback;
 return root;
}

void RTreeDestroy(HRTREEROOT root)
{
 RTreeDestroyNode (root->root_node);
 root->root_node = 0;
 free(root);
}

int RTreeSearch(HRTREEROOT root, RTREEMBR *mbr, void* pfnSearchCallbackParam)
{
 return  _RTreeSearchRect(root->root_node, mbr, root->pfnCallback, pfnSearchCallbackParam);
}

int RTreeInsert(HRTREEROOT root, RTREEMBR *mbr, void* tid, int level)
{
#ifdef _DEBUG
 int i;
#endif

 RTREENODE *newroot;
 RTREENODE *newnode;
 RTREEBRANCH b;
 
 assert(mbr && root);
 assert(level >= 0 && level <= root->root_node->level);

#ifdef _DEBUG
 for (i=0; i<DIMS_NUMB; i++) 
  assert(mbr->bound[i] <= mbr->bound[DIMS_NUMB+i]);
#endif

 if (_RTreeInsertRect(root, mbr, tid, root->root_node, &newnode, level))  
 {
  newroot = RTreeNewNode();  
  newroot->level = root->root_node->level + 1;
  b.mbr = RTreeNodeCover(root->root_node);
  b.child = root->root_node;
  RTreeAddBranch(root, &b, newroot, NULL);
  b.mbr = RTreeNodeCover(newnode);
  b.child = newnode;
  RTreeAddBranch(root, &b, newroot, NULL);
  root->root_node = newroot;
  
  return 1;
 }

 return 0;
}

int RTreeDelete(HRTREEROOT root, RTREEMBR *mbr, void* tid)
{
 int  i;
 RTREENODE  *tmp_nptr = NULL;
 RTREELISTNODE *reInsertList = NULL;
 RTREELISTNODE *e;

 assert(mbr && root && root->root_node);
 
 if (!_RTreeDeleteRect(mbr, tid, root->root_node, &reInsertList))
 {

  while (reInsertList)
  {
   tmp_nptr = reInsertList->node;

#pragma warning(push)
#pragma warning( disable : 4311 )
   for (i = 0; i < MAXKIDS(tmp_nptr); i++)
   {
    if (tmp_nptr->branch[i].child)
    {
     RTreeInsert(root, &(tmp_nptr->branch[i].mbr), (void*)tmp_nptr->branch[i].child, tmp_nptr->level);
    }
   }
#pragma warning(pop)
   e = reInsertList;
   reInsertList = reInsertList->next;
   RTreeFreeNode(e->node);
   _RTreeFreeListNode(e);
  }
  if (root->root_node->count == 1 && root->root_node->level > 0)
  {
   for (i = 0; i < NODECARD; i++)
   {
    tmp_nptr = root->root_node->branch[i].child;
    if(tmp_nptr)
     break;
   }
   assert(tmp_nptr);
   RTreeFreeNode(root->root_node);
   root->root_node = tmp_nptr;
  }
  return 0;
 }
 return 1;
}

#ifndef  RTREE_H_INCLUDED
#define  RTREE_H_INCLUDED

#ifdef __cplusplus
extern "C" {
#endif


#define  PAGE_SIZE    512
#define  DIMS_NUMB    2      
#define  SIDES_NUMB   2*DIMS_NUMB

typedef double REALTYPE;


#ifndef  TRUE
#define  TRUE  1
#define  FALSE 0
#endif


typedef struct _RTREEMBR
{
 REALTYPE bound[SIDES_NUMB]; 
}RTREEMBR;

typedef struct _RTREEBRANCH
{  
 RTREEMBR mbr;
 struct _RTREENODE *child; 
}RTREEBRANCH;


#define MAXCARD (int)((PAGE_SIZE-(2*sizeof(int))) / sizeof(RTREEBRANCH))

typedef struct _RTREENODE*  HRTREENODE;
typedef struct _RTREEROOT*  HRTREEROOT;


typedef int (*PFNRTreeSearchCallback)(void* data_id, void* pfnParam);


void RTreeInitRect( RTREEMBR *mbr);

RTREEMBR RTreeNullRect(void);


void RTreePrintRect( RTREEMBR *mbr, int depth );

REALTYPE RTreeRectArea( RTREEMBR *mbr );


REALTYPE RTreeRectVolume( RTREEMBR *mbr );

REALTYPE RTreeRectSphericalVolume( RTREEMBR *mbr );

REALTYPE RTreeRectSurfaceArea( RTREEMBR *mbr );


RTREEMBR RTreeCombineRect( RTREEMBR *rc1, RTREEMBR *rc2 );


int RTreeOverlap( RTREEMBR *rc1, RTREEMBR *rc2);


int RTreeContained( RTREEMBR *r, RTREEMBR *s);

void RTreeSplitNode(HRTREEROOT root, HRTREENODE node, RTREEBRANCH *br, HRTREENODE *new_node);


void RTreeInitNode( HRTREENODE node );


HRTREENODE RTreeNewNode(void);

void RTreeFreeNode( HRTREENODE node );


void RTreePrintNode( HRTREENODE node, int depth );


RTREEMBR RTreeNodeCover( HRTREENODE node );

int RTreePickBranch( RTREEMBR *mbr, HRTREENODE node);


int RTreeAddBranch(HRTREEROOT root, RTREEBRANCH *br, HRTREENODE node, HRTREENODE *new_node);


void RTreeDisconnectBranch( HRTREENODE node, int i );



void RTreeDestroyNode ( HRTREENODE node );


HRTREEROOT RTreeCreate(PFNRTreeSearchCallback  pfnSearchCallback);


void RTreeDestroy(HRTREEROOT root);


int RTreeSearch(HRTREEROOT root, RTREEMBR *mbr, void* pfnSearchCallbackParam);


int RTreeInsert(HRTREEROOT root, RTREEMBR *data_mbr, void* data_id, int level);


int RTreeDelete(HRTREEROOT root, RTREEMBR *data_mbr, void* data_id);


#ifdef __cplusplus
}
#endif

#endif 

#include <stdio.h>
#include "rtree.h"

RTREEMBR mbrs[] = {
    { {0, 0, 2, 2} },  /* xmin, ymin, zmin, xmax, ymax, zmax (for 3 dimensional RTree) */
    { {5, 5, 7, 7} },
    { {8, 5, 9, 6} },
	{ {4, 2, 6, 4} },
	{ {6, 3, 8, 5} },
    { {7, 1, 9, 2} }
};


int nmbr = sizeof(mbrs) / sizeof(mbrs[0]);
RTREEMBR search_mbr = {
 {6, 4, 10, 6} 
};

int MySearchCallback(int id, void* arg) 
{

 fprintf (stdout, "Searched data id: %d\n", id);
 return 1; /* 继续 */
}

int main()
{ 
    HRTREEROOT root = RTreeCreate(MySearchCallback);
    
 int i, nhits;
     
 fprintf (stdout, "nmbr = %d\n", nmbr);
    

 for(i=0; i<nmbr; i++){
  RTreeInsert(root, &mbrs[i],   /* mbr被插入 */
      (void*)(i+1),  /* i+1 mbr ID,ID必须永远是零 */
      0    /* 这意味着添加从根总是零 */
     );
 }

    nhits = RTreeSearch(root, &search_mbr, MySearchCallback);
 fprintf (stdout, "Search resulted is %d hits before delete 1\n", nhits);
    
 /* delete first shape: 1 */
 fprintf (stdout, "delete id=3 from tree\n");
 i = RTreeDelete(root, &mbrs[1], (void*)2);

 nhits = RTreeSearch(root, &search_mbr, MySearchCallback);
 fprintf (stdout, "Search resulted is %d hits after delete 1\n", nhits);

 RTreeDestroy (root);
    return 0;
}