/*                    COPYRIGHT NOTICE This material was developed by Christos Faloutsos and King-Ip Linat the University of Maryland, College Park, Department of Computer Science.Permission is granted to copy this software, to redistribute iton a nonprofit basis, and to use it for any purpose, subject tothe following restrictions and understandings. 1. Any copy made of this software must include this copyright noticein full. 2. All materials developed as a consequence of the use of thissoftware shall duly acknowledge such use, in accordance with the usualstandards of acknowledging credit in academic research. 3. The authors have made no warranty or representation that theoperation of this software will be error-free or suitable for anyapplication, and they are under under no obligation to provide anyservices, by way of maintenance, update, or otherwise.  The softwareis an experimental prototype offered on an as-is basis. 4. Redistribution for profit requires the express, written permissionof the authors. */// Author : $Author$// Date : $Date$// Id : $Id$// $Id: node.C,v 1.3 1996/04/18 21:50:24 kilin Exp kilin $ // Please change sig_dim to active_dim#include <iostream.h>#include <assert.h>#include <stdlib.h>#include <fstream.h>#include "TVdefine.h"#include "TVconstants.h"#include "TVvector.h"#include "TVrectangle.h"//#include "TVrectangle.h"#include "TVelement.h"#include "TVsimbuf.h"#include "TVnode.h"#include "TVutil.h"#include "TVsplit.h"#include "TVreinsert.h"extern Storage *globstorage;TVNodehandle::TVNodehandle(){   ptr = NULL;   pagenum = -1;}TVNodehandle::TVNodehandle(Internal_TVNode& n){  ptr = (TVNode *)&n;  pagenum = globstorage->newpage();}TVNodehandle::TVNodehandle(TVNode* n){  ptr = n;  pagenum = globstorage->newpage();}TVNodehandle::TVNodehandle(Leaf_TVNode& n){  ptr = (TVNode *)&n;  pagenum = globstorage->newpage();}TVNodehandle::TVNodehandle(const TVNodehandle& nh){  ptr = nh.ptr;  pagenum = nh.pagenum;}TVNodehandle& TVNodehandle::operator=(const TVNodehandle& nh){  ptr = nh.ptr;  pagenum = nh.pagenum;  return *this;}// return the size of the handle (not the node)// Assume all pointer have the same sizeint TVNodehandle::bytes() const{   return sizeof(TVNode *);}TVNode* TVNodehandle::fetch() const{   globstorage->fetch(pagenum);   return ptr;}// return FALSE when write failint TVNodehandle::write() const{   if (pagenum > -1)      globstorage->writepage(pagenum);   return TRUE;}TVNodehandle& TVNodehandle::assign(Internal_TVNode& n){   ptr = (TVNode *)&n;   pagenum = globstorage->newpage();   return *this;}TVNodehandle& TVNodehandle::assign(Leaf_TVNode& d){   ptr = (TVNode *)&d;   pagenum = globstorage->newpage();   return *this;}TVNodehandle& TVNodehandle::assign(TVNode* d){   ptr = d;   pagenum = globstorage->newpage();   return *this;}int TVNodehandle::null() const{   return !ptr;}TVNodehandle& TVNodehandle::setnull(){  ptr = NULL;  if (pagenum > 0)     {       globstorage->clearpage(pagenum);       pagenum = -1;     }  return *this;}void TVNodehandle::clearpage(){  globstorage->clearpage(pagenum);}ostream& operator<<(ostream& os, const TVNodehandle& nh){   if (nh.ptr)      os <<  "TVNode ptr : " << nh.ptr;   os << "  Page number : " << nh.pagenum;   return os;}TVNode::TVNode(){   count = 0;   max_count = 0;}TVNode::TVNode(int maxc){   count = 0;   max_count = maxc;}TVNode::TVNode(const TVNode &n){   count = n.count;   max_count = n.max_count;}TVNode::~TVNode(){}TVNode& TVNode::operator=(const TVNode& n){   count = n.count;   max_count = n.max_count;   return *this;}int TVNode::MaxCount(){   return max_count;}int TVNode::GetCount(){   return count;}void TVNode::WriteToDisk(){  // increase statistics}Internal_TVNode::Internal_TVNode(){   level = -1;   entry = NULL;}Internal_TVNode::Internal_TVNode(int l, int maxc) : TVNode(maxc){   level = l;   entry = NULL;   entry = new TVBranch[maxc];}Internal_TVNode::Internal_TVNode(const Internal_TVNode &n){   count = n.count;   max_count = n.max_count;   level = n.level;   entry = new TVBranch[n.max_count];   for (int i = 0; i < n.count; i++)     entry[i] = n.entry[i];}Internal_TVNode::~Internal_TVNode(){   if (max_count > 0)      {         for (int j = 0; j < count ; j++)             entry[j].TVBranch::~TVBranch();         delete [] entry;      }}Internal_TVNode& Internal_TVNode::Reinit(){   if (max_count > 0)      {         for (int j = 0; j < count ; j++)             entry[j].TVBranch::~TVBranch();         delete [] entry;      }   entry = new TVBranch[max_count];   count = 0;   return *this;}Internal_TVNode& Internal_TVNode::operator=(const Internal_TVNode& n){   if (max_count > 0)      {         for (int j = 0; j < count ; j++)             entry[j].TVBranch::~TVBranch();         delete [] entry;      }   count = n.count;   max_count = n.max_count;   level = n.level;   entry = new TVBranch[n.max_count];   for (int i = 0; i < n.count; i++)     entry[i] = n.entry[i];   return *this;}int Internal_TVNode::TVNodeType() const{  return INTERNAL_NODE;}int Internal_TVNode::Size() const{  int bsize=0;  for (int i=0; i < count; i++)      bsize += entry[i].Size();  return sizeof(count) + sizeof(max_count) + sizeof(level) + bsize;}int Internal_TVNode::GetLevel(){  return level;}int Internal_TVNode::ParentOfLeaf(){   return level == PARENT_OF_LEAF;}TVNodeEntry Internal_TVNode::Fetch(int i) const{  assert (i < max_count);  TVNodeEntry f(entry[i]);  return f;}int Internal_TVNode::Put(const TVBranch& b, int pagesize){   int result;// cout << "B.size, Size : " << b.Size() << ", " << Size() << "\n";   if (b.Size() + Size() <= pagesize)      {         if (count >= max_count)            {               // current array not big enough, create new one               TVBranch *newentry = new TVBranch[max_count * 2];               max_count = max_count * 2;               for (int i = 0; i < count ; i++)                   newentry[i] = entry[i];               newentry[count++] = b;               delete [] entry;               entry = newentry;            }         else            {              entry[count++] = b;              result = NODE_NOT_FULL;            }      }   else      result = NODE_FULL;   return result;}int Internal_TVNode::Remove(int bno, float min_fill_percent){   assert((bno < count) && (bno >= 0));   assert(min_fill_percent > 0);   entry[bno] = entry[count - 1];   if (--(count) < min_fill_percent * max_count / 100.0)      return(NODE_EMPTY);   else      return(NODE_NOT_EMPTY);}TVRectangle Internal_TVNode::MinBound(int sig_dim){   TVRectangle *darray = new TVRectangle[count];   for (int i = 0; i < count; i++)       darray[i] = entry[i].GetBound();   delete [] darray;   return (MinBoundTVRectangle(darray, count, sig_dim));}int Internal_TVNode::FixSize(){   return sizeof(int) * 3;}// Redistribute the nodes from the split return entriesInternal_TVNode& Internal_TVNode::ReDistribute(SplitReturn& sret, TVBranch *barray, int pagesize){  Reinit();    if (sret.newnode)    delete [] sret.newnode;  if (sret.parts > 1)     sret.newnode = new TVNode*[sret.parts - 1];  for (int i = 0; i < sret.parts - 1; i++)     sret.newnode[i] = new Internal_TVNode(level, max(max_count, CONSERVE_MAX_BRANCH_FACTOR));  for (int j = 0; j < sret.entrycount; j++)     {	if (sret.distribute[j])	    sret.newnode[sret.distribute[j] - 1]->Put(barray[j], pagesize);        else	   Put(barray[j], pagesize);     }  return *this;      }SplitReturn Internal_TVNode::Split(const TVBranch &b, const TVNodehandle& thishandle, int pagesize, float min_fill_percent, int sig_dim){ // cout << "----------\n";// cout << "Splitting :\n";// for (int xyy = 0; xyy < count; xyy++)//    cout << xyy << "  " << entry[xyy].GetBound() << endl;//cout << "new   " << b << endl;   SplitReturn sret(count + 1);   TVBranch *barray = new TVBranch[count + 1];   int i = 0;   for (; i < count; i++)          barray[i] = entry[i];   barray[count] = b;   // The splitting algorithm   SplitTVBranchAlg(sret, barray, FixSize(), pagesize, min_fill_percent, sig_dim);               // Rebuilt the nodes   ReDistribute(sret, barray, pagesize);//cout << "SplitReturn : " << sret.bound[0] << "  " << sret.bound[1] << endl;   thishandle.write();   delete [] barray;   return sret;}SplitReturn Internal_TVNode::Split(const Leaf_Element &e, const TVNodehandle& nh, VCOM_TYPE (*gfeat)(int, char*), int pagesize, float min_fill_percent, int sig_dim){  assert(0);  SplitReturn srt(1);  return srt;}void Internal_TVNode::SetReInsert(const Leaf_Element& b, ReInsertClass& ric, const TVNodehandle& nh, float reinsert_percent, int pagesize, float min_fill_percent, int sig_dim){  assert(0);}int sort_ricarray(const void *ric1, const void *ric2){   int out1;   float d1, d2;   TVector v1, v2;   d1 =  ((ReInsertCal *)ric1)->distance;   d2 =  ((ReInsertCal *)ric2)->distance;   out1 = (abs(d1 - d2) < abs(PRECISION * d1)) && (abs(d1 - d2) < abs(PRECISION * d2));   if (!(out1))      {      if ((d1 - d2) > 0)         return(1);      else         return(-1);      }   v1 =  ((ReInsertCal *)ric1)->ne.GetTVector();   v2 =  ((ReInsertCal *)ric2)->ne.GetTVector();   if (v1 < v2)      out1 = -1 ;   else      out1 = (v1 > v2);   return out1;}void Internal_TVNode::SetReInsert(const TVBranch& b, ReInsertClass& ric, const TVNodehandle& thishandle, float reinsert_percent, int pagesize, float min_fill_percent, int sig_dim){   TVNodeEntry *narray = new TVNodeEntry[count + 1];   TVBranch *barray = new TVBranch[count + 1];   TVRectangle *darray = new TVRectangle[count + 1];   ReInsertCal *ricarray = new ReInsertCal[count + 1];   ReInsertCal swap;   int total_branch = count + 1;   int cursize, requiresize;   TVRectangle bound;   int i;   for (i = 0; i < count; i++)      {         // need to do this, because TVNodeEntry have only pointers         barray[i] = entry[i];         ricarray[i].ne.Put(barray[i]);         darray[i] = barray[i].GetBound();      }   bound = MinBoundTVRectangle(darray, count, sig_dim);   barray[count] = b;   ricarray[count].ne.Put(barray[count]);   for (i = 0;  i < count; i++)      {        ricarray[i].distance = bound.GetCenter().Distance(barray[i].GetBound().GetCenter().ProjectFront(bound.GetCenter().GetDim()));      }   ricarray[count].distance = bound.GetCenter().Distance(b.GetBound().GetCenter().ProjectFront(bound.GetCenter().GetDim()));   qsort(ricarray, total_branch, sizeof(ReInsertCal), sort_ricarray);   int reinsert_size = 0;   int flag = TRUE;   i = count;   cursize = Size() + b.Size();   requiresize = (int)(pagesize * (100 - reinsert_percent) / 100);   while (cursize > requiresize)     {       cursize -= ricarray[i--].ne.u.b->Size();     }   if (cursize < (pagesize * min_fill_percent) / 100)      {        cursize +=  ricarray[++i].ne.u.b->Size();        if (cursize > pagesize)           {             // encounter a large element             swap = ricarray[i];             ricarray[i] = ricarray[0];             ricarray[0] = swap;             cursize = Size() + b.Size();             while (cursize > requiresize)               {                  cursize -= ricarray[i--].ne.u.b->Size();               }           }      }  // 0..i is to keep, reinsert others  int j;