/*                    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: reinsert.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 "TVreinsert.h"// reinsertnodeReInsertTVNode::ReInsertTVNode(){  next = NULL;}FRType ReInsertTVNode::Type(){  return not_defined;}// Reinsertnode for elementsReInsertTVNode_element::ReInsertTVNode_element(){  next = NULL;}ReInsertTVNode_element::ReInsertTVNode_element(const ReInsertTVNode_element& ric){   entry = ric.entry;   next = ric.next;}ReInsertTVNode_element::~ReInsertTVNode_element(){}ReInsertTVNode_element& ReInsertTVNode_element::operator=(const ReInsertTVNode_element& ric){   entry = ric.entry;   next = ric.next;   return *this;}FRType ReInsertTVNode_element::Type(){  return is_leafele;}void ReInsertTVNode_element::Put(TVNodeEntry& ne){   assert(ne.Type() == is_leafele);   entry = *ne.u.e;}void ReInsertTVNode_element::Put(const Leaf_Element& le){   entry = le;}Leaf_Element ReInsertTVNode_element::Get_element(){  return entry;}// Reinsert node for branchReInsertTVNode_branch::ReInsertTVNode_branch(){  next = NULL;}ReInsertTVNode_branch::ReInsertTVNode_branch(const ReInsertTVNode_branch& ric){   entry = ric.entry;   next = ric.next;}ReInsertTVNode_branch::~ReInsertTVNode_branch(){}ReInsertTVNode_branch& ReInsertTVNode_branch::operator=(const ReInsertTVNode_branch& ric){   entry = ric.entry;   next = ric.next;   return *this;}FRType ReInsertTVNode_branch::Type(){  return is_branch;}void ReInsertTVNode_branch::Put(TVNodeEntry& ne){   assert(ne.Type() == is_branch);   entry = *ne.u.b;}void ReInsertTVNode_branch::Put(const TVBranch& b){   entry = b;}TVBranch ReInsertTVNode_branch::Get_branch(){  return entry;}// A stack for the elements to be reinsertedReInsertStack::ReInsertStack(){   head.next =  NULL;}ReInsertStack::~ReInsertStack(){    while (head.next)      {        ReInsertTVNode *current = head.next;        head.next = head.next->next;        delete current;      }}void ReInsertStack::Push(const TVNodeEntry& ne){   ReInsertTVNode *rin;   if (ne.Type() == is_branch)      {        rin =  new ReInsertTVNode_branch;        rin->Put(*ne.u.b);      }   else      {        rin =  new ReInsertTVNode_element;        rin->Put(*ne.u.e);      }   rin->next = head.next;   head.next = rin;}void ReInsertStack::Push(const Leaf_Element& le){   ReInsertTVNode *rin =  new ReInsertTVNode_element;   rin->Put(le);   rin->next = head.next;   head.next = rin;}void ReInsertStack::Push(const TVBranch& b){   ReInsertTVNode *rin =  new ReInsertTVNode_branch;   rin->Put(b);   rin->next = head.next;   head.next = rin;}Leaf_Element ReInsertStack::Pop_element(){   Leaf_Element result;   if ((head.next) && (head.next->Type() == is_leafele))      {        result = head.next->Get_element();        ReInsertTVNode* freenode = head.next;        head.next = head.next->next;//	((ReInsertTVNode_element *)freenode)->ReInsertTVNode_element::~ReInsertTVNode_element();        delete freenode;      }   return result;}TVBranch ReInsertStack::Pop_branch(){   TVBranch result;   if ((head.next) && (head.next->Type() == is_branch))      {        result = head.next->Get_branch();        ReInsertTVNode* freenode = head.next;        head.next = head.next->next;        delete freenode;      }   return result;}Leaf_Element ReInsertStack::Top_element(){   Leaf_Element result;   if ((head.next) && (head.next->Type() == is_leafele))        result = head.next->Get_element();   return result;}TVBranch ReInsertStack::Top_branch(){   TVBranch result;   if ((head.next) && (head.next->Type() == is_branch))        result = head.next->Get_branch();   return result;}FRType ReInsertStack::Top_type(){  return head.next->Type();}int ReInsertStack::NonEmpty(){  return (head.next != NULL);}ostream& operator<< (ostream& os, const ReInsertStack& ris){   ReInsertTVNode *current = ris.head.next;   if (!(current))      cout << "Empty stack  ";   while (current)      {        if (current->Type() == is_leafele)           cout << current->Get_element() << "\n";        else if (current->Type() == is_branch)                cout << current->Get_branch() << "\n";             else cout << "Oops!  ";        current = current->next;      }   return os;}// Reinsert classReInsertClass::ReInsertClass(int height){   assert (height >= 0);   no_of_levels = height;   havereinserted = new int[no_of_levels];   reinsertst = new ReInsertStack[no_of_levels];   for (int i = 0; i < no_of_levels; i++)       havereinserted[i] = 0;}ReInsertClass::~ReInsertClass(){   for (int i = 0; i < no_of_levels; i++)       reinsertst[i].ReInsertStack::~ReInsertStack();   delete [] reinsertst;   delete [] havereinserted;}ReInsertClass::ReInsertClass(const ReInsertClass& ric){  no_of_levels = ric.no_of_levels;  reinsertst = new ReInsertStack[no_of_levels];  havereinserted = new int [no_of_levels];  for (int i = 0; i < no_of_levels; i++)      {         reinsertst[i] = ric.reinsertst[i];         havereinserted[i] = ric.havereinserted[i];      }}ReInsertClass& ReInsertClass::operator=(const ReInsertClass& ric){  no_of_levels = ric.no_of_levels;  reinsertst = new ReInsertStack[no_of_levels];  havereinserted = new int [no_of_levels];  for (int i = 0; i < no_of_levels; i++)      {         reinsertst[i] = ric.reinsertst[i];         havereinserted[i] = ric.havereinserted[i];      }  return *this;}void ReInsertClass::Add(const TVNodeEntry& ne, const int level){   assert(level < no_of_levels);   reinsertst[level].Push(ne);}void ReInsertClass::Add(const Leaf_Element& le, const int level){   assert(level < no_of_levels);   reinsertst[level].Push(le);}void ReInsertClass::Add(const TVBranch& b, const int level){   assert(level < no_of_levels);   reinsertst[level].Push(b);}FRType ReInsertClass::Top_type(const int level){   assert(level < no_of_levels);   return reinsertst[level].Top_type();}Leaf_Element ReInsertClass::Pop_element(const int level){   assert(level < no_of_levels);   assert(reinsertst[level].Top_type() == is_leafele);   return reinsertst[level].Pop_element();}TVBranch ReInsertClass::Pop_branch(const int level){   assert(level < no_of_levels);   assert(reinsertst[level].Top_type() == is_branch);   return reinsertst[level].Pop_branch();}Leaf_Element ReInsertClass::Top_element(const int level){   assert(level < no_of_levels);   assert(reinsertst[level].Top_type() == is_leafele);   return reinsertst[level].Top_element();}TVBranch ReInsertClass::Top_branch(const int level){   assert(level < no_of_levels);   assert(reinsertst[level].Top_type() == is_branch);   return reinsertst[level].Top_branch();}int ReInsertClass::NonEmpty(int level){   assert(level < no_of_levels);   return reinsertst[level].NonEmpty();}int ReInsertClass::NonEmpty(){   int i = 0;   for (; (i < no_of_levels) && !(reinsertst[i].NonEmpty()); i++)	;   return (i < no_of_levels);}ostream& operator<< (ostream& os, const ReInsertClass& ric){   for (int i = 0; i < ric.no_of_levels; i++)      {        cout << "Level " << i << "  :  ";        cout << ric.reinsertst[i];      }   return os;}// Use for calculating where to reinsertReInsertCal::ReInsertCal(){   distance = 0.0;}ReInsertCal::ReInsertCal(const ReInsertCal& ric){  ne = ric.ne;  distance = ric.distance;}ReInsertCal& ReInsertCal::operator=(const ReInsertCal& ric){  ne = ric.ne;  distance = ric.distance;  return *this;}