ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GIntervalTree.hh
(Generate patch)
# Line 18 | Line 18
18  
19   // T = type of data associated with each interval is stored in a <T>
20  
21 <
22 < template<typename T, typename N=int32_t>
23 < class IntervalTree {
21 > template<typename T, typename N=int32_t> class IntervalTree {
22   public:
23    enum color_t {BLACK, RED};
24  
# Line 39 | Line 37
37      N key;
38      N high_;
39      N maxHigh;
40 +    int n_idx; //location in IntervalTree::nodes array
41 +    int left_n_idx; // left node index in nodes array
42 +    int right_n_idx; // right node index in nodes array
43 +    int parent_n_idx;  //parent node index in nodes array
44      color_t color;
45      Node * left;
46      Node * right;
47      Node * parent;
48 <  };
48 >  }; //Node
49  
50    struct it_recursion_node {
51      /*  this structure stores the information needed when we take the */
# Line 52 | Line 54
54      it_recursion_node(Node *start_node_=NULL,
55          size_t parentIndex_=0,
56          bool tryRightBranch_=false)
57 <      : start_node (start_node_),
58 <        parentIndex (parentIndex_),
59 <        tryRightBranch (tryRightBranch_) {}
57 >    : start_node (start_node_),
58 >      parentIndex (parentIndex_),
59 >      tryRightBranch (tryRightBranch_) {}
60  
61      Node * start_node;
62      size_t parentIndex;
# Line 62 | Line 64
64    };
65  
66    IntervalTree();
67 +  IntervalTree(FILE* f); //create by deserialization from file
68 +
69    ~IntervalTree();
70 +
71 +  void fileStore(FILE* f); //write the tree into a file
72    //std::string str() const;
73    void remove(N, N, GVec<T>&);
74    template <class F> void remove(N, N, const F&, GVec<T>&);
# Line 85 | Line 91
91    /*  node which should always be black but has aribtrary children and */
92    /*  parent and no key or info.  The point of using these sentinels is so */
93    /*  that the root and nil nodes do not require special cases in the code */
94 +  GPVec<Node> nodes; //store all the tree nodes for easy de/serialization
95    Node * root;
96    Node * nil;
97  
# Line 120 | Line 127
127    : value_ (value__),
128      key(lowPoint),
129      high_(highPoint),
130 <    maxHigh(highPoint)
130 >    maxHigh(highPoint),
131 >    n_idx(-1), //location in IntervalTree::nodes array
132 >    left_n_idx(0), // left node index in nodes array
133 >    right_n_idx(0), // right node index in nodes array
134 >    parent_n_idx(0),  //parent node index in nodes array
135 >    color(BLACK),
136 >    left(NULL),
137 >    right(NULL),
138 >    parent(NULL)
139 >
140   {
141   }
142  
# Line 130 | Line 146
146   }
147  
148   template<typename T, typename N>
149 < IntervalTree<T,N>::IntervalTree()
149 > IntervalTree<T,N>::IntervalTree() : nodes(64, true)
150   {
151    nil = new IntervalTree<T,N>::Node();
152    nil->left = nil->right = nil->parent = nil;
153    nil->color = BLACK;
154    nil->key = nil->high_ = nil->maxHigh = std::numeric_limits<N>::min();
155 <  
155 >  nodes.Add(nil); //index 0
156 >  nil->n_idx = nil->left_n_idx = nil->right_n_idx = nil->parent_n_idx = 0;
157    root = new IntervalTree<T,N>::Node();
158    root->parent = root->left = root->right = nil;
159 +  root->parent_n_idx = root->left_n_idx = root->right_n_idx = 0;
160 +  root->n_idx = nodes.Add(root);
161    root->key = root->high_ = root->maxHigh = std::numeric_limits<N>::max();
162    root->color=BLACK;
163  
164    /* the following are used for the fetch function */
146 –  //recursionNodeStack.push_back(IntervalTree<T,N>::it_recursion_node());
165    recursionNodeStack.Push(IntervalTree<T,N>::it_recursion_node());
166   }
167   /*
# Line 387 | Line 405
405    TreeInsertHelp(x);
406    FixUpMaxHigh(x->parent);
407    newNode = x;
408 +  newNode->n_idx = nodes.Add(newNode);
409    x->color=RED;
410    while(x->parent->color == RED) { /* use sentinel instead of checking for root */
411      if (x->parent == x->parent->parent->left) {
# Line 426 | Line 445
445      }
446    }
447    root->left->color=BLACK;
448 +  //update new node link indexes
449 +  newNode->left_n_idx = newNode->left->n_idx;
450 +  newNode->right_n_idx = newNode->right->n_idx;
451 +  newNode->parent_n_idx = newNode->parent->n_idx;
452    return(newNode);
453  
454   #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS
# Line 550 | Line 573
573  
574   template<typename T, typename N>
575   IntervalTree<T,N>::~IntervalTree() {
576 <
576 >  nodes.Clear(); //this should also free all allocated nodes
577 >  /*
578    IntervalTree<T,N>::Node * x = root->left;
579    GVec<IntervalTree<T,N>::Node *> stuffToFree;
580  
# Line 563 | Line 587
587      }
588      delete x;
589      while( stuffToFree.notEmpty() ) {
566 –      //x = stuffToFree.back();
567 –      //stuffToFree.pop_back();
590        x = stuffToFree.Pop();
591        if (x->left != nil) {
592          stuffToFree.Push(x->left);
# Line 577 | Line 599
599    }
600    delete nil;
601    delete root;
602 +  */
603   }
604  
605  
# Line 772 | Line 795
795    for (typename GVec<IntervalTree<T,N>::Node*>::const_iterator
796        i=got.begin(); i!=got.end(); ++i)
797    {
798 <    removed.push_back((*i)->value());
798 >    removed.Push((*i)->value());
799      remove(*i);
800    }
801   }
# Line 786 | Line 809
809        i=got.begin(); i!=got.end(); ++i)
810    {
811      if (removeFunctor((*i)->value(), (*i)->low(), (*i)->high())) {
812 <      removed.push_back((*i)->value());
812 >      removed.Push((*i)->value());
813        remove(*i);
814      }
815    }
# Line 800 | Line 823
823    for (typename GVec<IntervalTree<T,N>::Node*>::const_iterator
824        i=got.begin(); i!=got.end(); ++i)
825    {
826 <    removed.push_back((*i)->value());
826 >    removed.Push((*i)->value());
827      remove(*i);
828    }
829   }
# Line 818 | Line 841
841        i=got.begin(); i!=got.end(); ++i)
842    {
843      if (removeFunctor((*i)->value(), (*i)->low(), (*i)->high())) {
844 <      removed.push_back((*i)->value());
844 >      removed.Push((*i)->value());
845        remove(*i);
846      }
847    }
# Line 951 | Line 974
974  
975    while(stuffToDo) {
976      if (Overlap(low,high,x->key,x->high_) ) {
977 <      enumResultStack.push_back(x);
977 >      enumResultStack.Push(x);
978        recursionNodeStack[currentParent].tryRightBranch=true;
979      }
980      if(x->left->maxHigh >= low) { // implies x != nil
981 <      recursionNodeStack.push_back(IntervalTree<T,N>::it_recursion_node());
982 <      recursionNodeStack.back().start_node = x;
983 <      recursionNodeStack.back().tryRightBranch = false;
984 <      recursionNodeStack.back().parentIndex = currentParent;
985 <      currentParent = recursionNodeStack.size()-1;
981 >      recursionNodeStack.Push(IntervalTree<T,N>::it_recursion_node());
982 >      recursionNodeStack.Last().start_node = x;
983 >      recursionNodeStack.Last().tryRightBranch = false;
984 >      recursionNodeStack.Last().parentIndex = currentParent;
985 >      currentParent = recursionNodeStack.Count()-1;
986        x = x->left;
987      } else {
988        x = x->right;
989      }
990      stuffToDo = (x != nil);
991 <    while( (!stuffToDo) && (recursionNodeStack.size() > 1) ) {
992 <        IntervalTree<T,N>::it_recursion_node back = recursionNodeStack.back();
970 <        recursionNodeStack.pop_back();
991 >    while( (!stuffToDo) && (recursionNodeStack.Count() > 1) ) {
992 >        IntervalTree<T,N>::it_recursion_node back = recursionNodeStack.Pop();
993  
994          if(back.tryRightBranch) {
995            x=back.start_node->right;
# Line 999 | Line 1021
1021  
1022    while(stuffToDo) {
1023      if (Contain(low,high,x->key,x->high_) ) {
1024 <      enumResultStack.push_back(x->value());
1024 >      enumResultStack.Push(x->value());
1025        recursionNodeStack[currentParent].tryRightBranch=true;
1026      }
1027      if(x->left->maxHigh >= low) { // implies x != nil
1028 <      recursionNodeStack.push_back(IntervalTree<T,N>::it_recursion_node());
1029 <      recursionNodeStack.back().start_node = x;
1030 <      recursionNodeStack.back().tryRightBranch = false;
1031 <      recursionNodeStack.back().parentIndex = currentParent;
1032 <      currentParent = recursionNodeStack.size()-1;
1028 >      recursionNodeStack.Push(IntervalTree<T,N>::it_recursion_node());
1029 >      recursionNodeStack.Last().start_node = x;
1030 >      recursionNodeStack.Last().tryRightBranch = false;
1031 >      recursionNodeStack.Last().parentIndex = currentParent;
1032 >      currentParent = recursionNodeStack.Count()-1;
1033        x = x->left;
1034      } else {
1035        x = x->right;
1036      }
1037      stuffToDo = (x != nil);
1038      while( (!stuffToDo) && (recursionNodeStack.size() > 1) ) {
1039 <        IntervalTree<T,N>::it_recursion_node back = recursionNodeStack.back();
1018 <        recursionNodeStack.pop_back();
1039 >        IntervalTree<T,N>::it_recursion_node back = recursionNodeStack.Pop();
1040  
1041          if(back.tryRightBranch) {
1042            x=back.start_node->right;
# Line 1050 | Line 1071
1071  
1072    while(stuffToDo) {
1073      if (Contain(low,high,x->key,x->high_) ) {
1074 <      //enumResultStack.push_back(x);
1054 <      enumResultStack.Add(x);
1074 >      enumResultStack.Push(x);
1075        recursionNodeStack[currentParent].tryRightBranch=true;
1076      }
1077      if(x->left->maxHigh >= low) { // implies x != nil
1078 <      //recursionNodeStack.push_back(IntervalTree<T,N>::it_recursion_node());
1059 <      recursionNodeStack.Add(IntervalTree<T,N>::it_recursion_node());
1060 <      //recursionNodeStack.back().start_node = x;
1078 >      recursionNodeStack.Push(IntervalTree<T,N>::it_recursion_node());
1079        recursionNodeStack.Last().start_node = x;
1080        recursionNodeStack.Last().tryRightBranch = false;
1081        recursionNodeStack.Last().parentIndex = currentParent;
# Line 1068 | Line 1086
1086      }
1087      stuffToDo = (x != nil);
1088      while( (!stuffToDo) && (recursionNodeStack.size() > 1) ) {
1089 <        IntervalTree<T,N>::it_recursion_node back = recursionNodeStack.back();
1072 <        recursionNodeStack.pop_back();
1089 >        IntervalTree<T,N>::it_recursion_node back = recursionNodeStack.Pop();
1090  
1091          if(back.tryRightBranch) {
1092            x=back.start_node->right;
# Line 1101 | Line 1118
1118    return match;
1119   }
1120  
1104 –          
1121  
1122   /* Make sure the maxHigh fields for everything makes sense. *
1123   * If something is wrong, print a warning and exit */

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines