tvnode.c

TV-tree的c实现源码

  for (j = count; j > i; j--)
      ric.Add(ricarray[j].ne, level);

  Reinit();
  for (j = 0; j <= i; j++)
     Put(*ricarray[j].ne.u.b, pagesize);
  thishandle.write();
   delete [] narray;
   delete [] barray;
   delete [] darray;
   delete [] ricarray;
}
 

ostream& operator<< (ostream& os, const Internal_TVNode& n)
{
   os << "Level : " << n.level << "  Max fan-out : " <<  n.max_count << "  Current count : " << n.count << "   Size " << n.Size();
   for (int i = 0; i < n.count ; i++)
       os << "\nTVBranch " << i <<  "  " << n.entry[i];
   return os;
}

ostream& operator<< (ostream& os, const Internal_TVNode*& n)
{
   os << "Level : " << n->level << "  Max fan-out : " <<  n->max_count << "  Current count : " << n->count << "   Size " << n->Size();
   for (int i = 0; i < n->count ; i++)
       os << "\nTVBranch " << i <<  "  " << n->entry[i];
   return os;
}









// Code for leaf node

Leaf_TVNode::Leaf_TVNode()
{
   entry = NULL;
}

Leaf_TVNode::Leaf_TVNode(int maxc) : TVNode(maxc)
{
   entry = new Leaf_Element[maxc];
}


Leaf_TVNode::Leaf_TVNode(const Leaf_TVNode &n)
{
   count = n.count;
   max_count = n.max_count;
   entry = new Leaf_Element[n.max_count];
   for (int i = 0; i < n.count; i++)
     entry[i] = n.entry[i];
}

Leaf_TVNode::~Leaf_TVNode()
{
   delete [] entry;
}

Leaf_TVNode& Leaf_TVNode::Reinit()
{
   delete [] entry;
   entry = new Leaf_Element[max_count];
   count = 0;
   return *this;
}

Leaf_TVNode& Leaf_TVNode::operator=(const Leaf_TVNode& n)
{
   if (max_count > 0)
      delete [] entry;
   count = n.count;
   max_count = n.max_count;
   entry = new Leaf_Element[n.max_count];
   for (int i = 0; i < n.count; i++)
     entry[i] = n.entry[i];
   return *this;
}

int Leaf_TVNode::TVNodeType() const
{
  return LEAF_NODE;
}

int Leaf_TVNode::Size() const
{
  int bsize=0;

  for (int i=0; i < count; i++)
      bsize += entry[i].Size();
  return sizeof(count) + sizeof(max_count) +  bsize;
}

int Leaf_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);
}

TVNodeEntry Leaf_TVNode::Fetch(int i) const
{
  assert (i < max_count);

  TVNodeEntry f(entry[i]);

  return f;
}

int Leaf_TVNode::Put(const Leaf_Element& b, int pagesize)
{
   int result;
   if (b.Size() + Size() <= pagesize)
      {
         if (count >= max_count)
            {
               // current array not big enough, create new one
               Leaf_Element *newentry = new Leaf_Element[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;
}

TVRectangle Leaf_TVNode::MinBound(VCOM_TYPE (*gfeat)(int, char*), int sig_dim)
{
   TVector *varray = new TVector[count];
   int exec_count = 0;
   TVRectangle d;

   for (int i = 0; i < count; i++)
       varray[i] = entry[i].GetTVector();
   d = MinBoundTVRectangle(varray, count, sig_dim);
   while ((d.GetRadius() < PRECISION) && (exec_count < NO_OF_FEATURES))
       {
           for (int i = 0; i < count; i++)
               varray[i] = entry[i].GetTVector(varray[i].GetDim() + sig_dim, gfeat);
           d = MinBoundTVRectangle(varray, count, sig_dim);
           exec_count++;
       }
   delete [] varray;
   return d;
}

int Leaf_TVNode::FixSize()
{
   return sizeof(int) * 2;
}

// Redistribute the nodes from the split return entries
Leaf_TVNode& Leaf_TVNode::ReDistribute(SplitReturn& sret, Leaf_Element *larray, 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 Leaf_TVNode(max(max_count, CONSERVE_MAX_ELEMENT_FACTOR));

  for (int j = 0; j < sret.entrycount; j++)
     {
	if (sret.distribute[j])
	    sret.newnode[sret.distribute[j] - 1]->Put(larray[j], pagesize);
        else
	   Put(larray[j], pagesize);
     }

  return *this;      
}

SplitReturn Leaf_TVNode::Split(const TVBranch &b, const TVNodehandle& nh, int pagesize, float min_fill_percent, int sig_dim)
{
   assert(0);
   SplitReturn sret(1);
   return sret;
}

SplitReturn Leaf_TVNode::Split(const Leaf_Element &e, const TVNodehandle& nh, VCOM_TYPE (*gfeat)(int, char*), int pagesize, float min_fill_percent, int sig_dim)
{
//cout << "----------\n";
//cout << "Splitting :\n" << *this << endl;
//cout << e << endl;
   SplitReturn sret(count + 1);
   Leaf_Element *larray = new Leaf_Element[count + 1];
   int i = 0;

   for (; i < count; i++)
          larray[i] = entry[i];

   larray[count] = e;

   // The splitting algorithm
   SplitLeafAlg(sret, larray, gfeat, Leaf_TVNode::FixSize(), pagesize, min_fill_percent, sig_dim);
            
   // Rebuilt the nodes

   ReDistribute(sret, larray, pagesize);

//cout << "SplitReturn : " << sret.bound[0] << "  " << sret.bound[1] << endl;
   nh.write();
   delete [] larray;
   return sret;

}

// Code for removing item from a node to be reinserted somewhere else

void Leaf_TVNode::SetReInsert(const TVBranch& b, ReInsertClass& ric, const TVNodehandle& nh, float reinsert_percent, int pagesize, float min_fill_percent, int sig_dim)
{
  assert(0);
}

void Leaf_TVNode::SetReInsert(const Leaf_Element& le, ReInsertClass& ric, const TVNodehandle& nh, float reinsert_percent, int pagesize, float min_fill_percent, int sig_dim)
{

//cout << "SetReInsert\n";
   TVNodeEntry *narray = new TVNodeEntry[count + 1];
   Leaf_Element *larray = new Leaf_Element[count + 1];
   TVector *varray = new TVector[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
         larray[i] = entry[i];
         ricarray[i].ne.Put(larray[i]);
         varray[i] = ricarray[i].ne.GetTVector();
      }
   bound = MinBoundTVRectangle(varray, count, sig_dim);
   larray[count] = le;
   ricarray[count].ne.Put(larray[count]);
   for (i = 0;  i < total_branch ; i++)
      {
        int d = bound.GetCenter().GetDim();
        ricarray[i].distance = bound.GetCenter().Distance(larray[i].GetTVector().ProjectFront(d));
      }
/*
cout << "---- SetReInsert ----- " << endl;
cout << "Bound : " << bound << endl;
for (i = 0; i < total_branch; i++)
    cout << "Entry : " << i << ") " << ricarray[i].ne << "\t\t" << ricarray[i].distance << end
l;
*/
   qsort(ricarray, total_branch, sizeof(ReInsertCal), sort_ricarray);
/*
cout << "-- sorted --" << endl;
for (i = 0; i < total_branch; i++)
    cout << "Entry : " << i << ") " << ricarray[i].ne << "\t\t" << ricarray[i].distance << end
l;
cout << "---------------------" << endl;
*/

   int reinsert_size = 0;
   int flag = TRUE;

   i = count;
   cursize = Size() + le.Size();
   requiresize = (int)(pagesize * (100 - reinsert_percent) / 100);
   while (cursize > requiresize)
     {
       cursize -= ricarray[i--].ne.u.e->Size();
     }
   if (cursize < (pagesize * min_fill_percent) / 100)
      {
        cursize +=  ricarray[++i].ne.u.e->Size();
        if (cursize > pagesize)
           {
             // encounter a large element
             swap = ricarray[i];
             ricarray[i] = ricarray[0];
             ricarray[0] = swap;
             cursize = Size() + le.Size();
             while (cursize > requiresize)
                  cursize -= ricarray[i--].ne.u.e->Size();
           }
      }

  // 0..i is to keep, reinsert others
  int j;

  for (j = count; j > i; j--)
      ric.Add(ricarray[j].ne, 0);

  Reinit();
  for (j = 0; j <= i; j++)
     Put(*(ricarray[j].ne.u.e), pagesize);

  nh.write();

  delete [] narray;
  delete [] larray;
  delete [] varray;
  delete [] ricarray;
}

ostream& operator<< (ostream& os, const Leaf_TVNode& n)
{
   os << "Max fan-out : " <<  n.max_count << "  Current count : " << n.count << "   Size " <<
n.Size() << "\n";
   if (n.count > 0)
      os << n.entry[0];
   for (int i = 1; i < n.count ; i++)
       os <<  " / " << n.entry[i];
   return os;
}

ostream& Leaf_TVNode::PrintLeaf(ostream& os,  void (*PrintData)(ostream&, char *), int oneperline)
{
   os << "Max fan-out : " <<  max_count << "  Current count : " << count << "   Size " << Size() << "\n";
   if (count > 0)
      {
	os << "Data : ";
	PrintData(os, entry[0]());
	os << " (" << entry[0].GetTVector().GetDim() << ")";
	os << entry[0].GetTVector();
      }
   for (int i = 1; i < count ; i++)
       {
          os <<  (oneperline ? "\nData : " : " / ");
	  PrintData(os, entry[i]());
	  os << " (" << entry[i].GetTVector().GetDim() << ")";
	  os << entry[i].GetTVector();
       }
   return os;
}

// Info to be passed back from the split routine 

SplitReturn::SplitReturn(int ent)
{
  entrycount = ent;
  distribute = new int[ent];  
  parts = 0;
  newnode = NULL;
  bound = NULL;
}


SplitReturn::SplitReturn(const SplitReturn& s)
{
  entrycount = s.entrycount;
  distribute = new int[entrycount];
  for (int i = 0; i < entrycount; i++)
       distribute[i] = s.distribute[i];
  parts = s.parts;
  if (parts)
     {
	if (s.newnode)
	  {
             newnode = new TVNode*[parts - 1]; 
	     for (int j = 0; j < parts - 1; j++)
	        newnode[j] = s.newnode[j];
          }
	else
	  newnode = NULL;
	if (s.bound)
	 {
             bound = new TVRectangle[parts]; 
	     for (int j = 0; j < parts ; j++)
	        bound[j] = s.bound[j];
	 }
	else
	  bound = NULL;
     }
}

SplitReturn::~SplitReturn() 
{
  delete [] distribute;
  delete [] newnode;
  delete [] bound;
}

SplitReturn& SplitReturn::operator=(const SplitReturn& s)
{
  if (entrycount != s.entrycount)
     {
	 if (distribute)
	     delete [] distribute;
         entrycount = s.entrycount;
         distribute = new int[entrycount];
     }
  for (int i = 0; i < entrycount; i++)
       distribute[i] = s.distribute[i];
  if (parts != s.parts)
     {
        if (newnode)
	   delete [] newnode;
        if (bound)
	   delete [] bound;
       parts = s.parts;
       if (parts > 1)
          newnode = new TVNode*[parts - 1]; 
       else
	  newnode = NULL;
       if (parts)
          bound = new TVRectangle[parts]; 
       else
	  bound = NULL;
     }
  if (parts)
     {
	if (s.newnode)
	  {
	     for (int j = 0; j < parts - 1; j++)
	        newnode[j] = s.newnode[j];
          }
	else
	  newnode = NULL;
	if (s.bound)
	 {
	     for (int j = 0; j < parts ; j++)
	        bound[j] = s.bound[j];
	 }
	else
	  bound = NULL;
     }
  return *this;
}

int SplitReturn::HasBound()
{
  return (bound != NULL);
}


// TVNode iterator

TVNodeIter::TVNodeIter()
{
  n = NULL;
  count = -1;
}

TVNodeIter::TVNodeIter(TVNode *ni)
{
  n = ni;
  count = 0;
}


TVNodeIter::TVNodeIter(TVNode& ni)
{
  n = &ni;
  count = 0;
}

TVNodeIter::TVNodeIter(const TVNodeIter& nit)
{
  n = nit.n;
  count = nit.count;
}

int TVNodeIter::GetLastIterInd()
{
  return count - 1;
}

TVNodeEntry TVNodeIter::Iter()
{
  TVNodeEntry f;
  if (count >= n->GetCount())
     f.ftype = not_defined;
  else
     f = n->Fetch(count++);
  return f;
}


void TVNodeIter::Reset()
{
  count = 0;
}

int TVNodeIter::Count()
{
   return n->GetCount();
}