ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GIntervalTree.hh
(Generate patch)
# Line 1 | Line 1
1   #ifndef GINTERVALTREE_HH_
2   #define GINTERVALTREE_HH_
3  
4 #include "GBase.h"
4   #include <limits>
5 + #include "GBase.h"
6   #include "GVec.hh"
7 + using namespace std;
8 +
9   //#include <sstream>
10   //#include <vector>
11   //#include <string>
# Line 121 | Line 123
123   // your changes didn't mess anything up.
124   // #define CHECK_INTERVAL_TREE_ASSUMPTIONS 1
125  
126 < template<typename T, typename N> IntervalTree<T,N>::Node::Node() {
126 > template<typename T, typename N> IntervalTree<T,N>::Node::Node()
127 >  : //value_ (value__),
128 >    key(numeric_limits<N>::min()),
129 >    high_(numeric_limits<N>::min()),
130 >    maxHigh(numeric_limits<N>::min()),
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   template<typename T, typename N>
# Line 150 | Line 165
165   template<typename T, typename N>
166   IntervalTree<T,N>::IntervalTree() : nodes(64, true)
167   {
168 +  currentParent = 0;
169    nil = new IntervalTree<T,N>::Node();
170    nil->left = nil->right = nil->parent = nil;
171    nil->color = BLACK;
172 <  nil->key = nil->high_ = nil->maxHigh = std::numeric_limits<N>::min();
172 >  nil->key = nil->high_ = nil->maxHigh = numeric_limits<N>::min();
173    nodes.Add(nil); //index 0
174    nil->n_idx = nil->left_n_idx = nil->right_n_idx = nil->parent_n_idx = 0;
175    root = new IntervalTree<T,N>::Node();
176    root->parent = root->left = root->right = nil;
177    root->parent_n_idx = root->left_n_idx = root->right_n_idx = 0;
178    root->n_idx = nodes.Add(root);
179 <  root->key = root->high_ = root->maxHigh = std::numeric_limits<N>::max();
179 >  root->key = root->high_ = root->maxHigh = numeric_limits<N>::max();
180    root->color=BLACK;
181  
182    /* the following are used for the fetch function */
# Line 174 | Line 190
190    nil = new IntervalTree<T,N>::Node();
191    nil->left = nil->right = nil->parent = nil;
192    nil->color = BLACK;
193 <  nil->key = nil->high_ = nil->maxHigh = std::numeric_limits<N>::min();
193 >  nil->key = nil->high_ = nil->maxHigh = numeric_limits<N>::min();
194    nodes.Add(nil); //index 0
195    nil->n_idx = nil->left_n_idx = nil->right_n_idx = nil->parent_n_idx = 0;
196    root = new IntervalTree<T,N>::Node(); //root is index 1
197    root->parent = root->left = root->right = nil;
198    root->parent_n_idx = root->left_n_idx = root->right_n_idx = 0;
199    root->n_idx = nodes.Add(root);
200 <  root->key = root->high_ = root->maxHigh = std::numeric_limits<N>::max();
200 >  root->key = root->high_ = root->maxHigh = numeric_limits<N>::max();
201    root->color=BLACK;
202  
203    // neeeded by the fetch function
# Line 251 | Line 267
267   #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS
268    check();
269   #elif defined(DEBUG_ASSERT)
270 <  if (nil->maxHigh!=std::numeric_limits<N>::min())
271 <      GError("Error: nil->maxHigh != std::numeric_limits<N>::min() in ITLeftRotate!\n");
270 >  if (nil->maxHigh!=numeric_limits<N>::min())
271 >      GError("Error: nil->maxHigh != numeric_limits<N>::min() in ITLeftRotate!\n");
272   #endif
273   }
274  
# Line 311 | Line 327
327   #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS
328    check();
329   #elif defined(DEBUG_ASSERT)
330 <  if (nil->maxHigh!=std::numeric_limits<N>::min())
331 <        GError("Error: nil->maxHigh != std::numeric_limits<N>::min() in ITRightRotate!\n");
330 >  if (nil->maxHigh!=numeric_limits<N>::min())
331 >        GError("Error: nil->maxHigh != numeric_limits<N>::min() in ITRightRotate!\n");
332   #endif
333   }
334  
# Line 358 | Line 374
374  
375  
376   #if defined(DEBUG_ASSERT)
377 <  if (nil->maxHigh!=std::numeric_limits<N>::min())
378 <        GError("Error: nil->maxHigh != std::numeric_limits<N>::min() in ITTreeInsertHelp!\n");
377 >  if (nil->maxHigh!=numeric_limits<N>::min())
378 >        GError("Error: nil->maxHigh != numeric_limits<N>::min() in ITTreeInsertHelp!\n");
379   #endif
380   }
381  
# Line 468 | Line 484
484    check();
485   #elif defined(DEBUG_ASSERT)
486    if (root->color != RED) GError("Error: root not red in ITTreeInsert\n");
487 <  if (nil->maxHigh!=std::numeric_limits<N>::min())
488 <         GError("Error: nil->maxHigh != std::numeric_limits<N>::min() in ITTreeInsert\n");
487 >  if (nil->maxHigh!=numeric_limits<N>::min())
488 >         GError("Error: nil->maxHigh != numeric_limits<N>::min() in ITTreeInsert\n");
489   #endif
490   }
491  
# Line 714 | Line 730
730    check();
731   #elif defined(DEBUG_ASSERT)
732    if (nil->color != BLACK) GError("Error: nil not black in ITDeleteFixUp\n");
733 <  if (nil->maxHigh!=std::numeric_limits<N>::min())
734 <         GError("Error: nil->maxHigh != std::numeric_limits<N>::min() in ITDeleteFixUp\n");
733 >  if (nil->maxHigh!=numeric_limits<N>::min())
734 >         GError("Error: nil->maxHigh != numeric_limits<N>::min() in ITDeleteFixUp\n");
735   #endif
736   }
737  
# Line 760 | Line 776
776   #endif
777      /* y is the node to splice out and x is its child */
778    
779 <    y->maxHigh = std::numeric_limits<N>::min();
779 >    y->maxHigh = numeric_limits<N>::min();
780      y->left=z->left;
781      y->right=z->right;
782      y->parent=z->parent;
# Line 781 | Line 797
797      check();
798   #elif defined(DEBUG_ASSERT)
799      if (nil->color != BLACK) GError("Error: nil not black in ITDelete\n!");
800 <    if (nil->maxHigh!=std::numeric_limits<N>::min())
801 <        GError("Error: nil->maxHigh != std::numeric_limits<N>::min() in ITDelete\n");
800 >    if (nil->maxHigh!=numeric_limits<N>::min())
801 >        GError("Error: nil->maxHigh != numeric_limits<N>::min() in ITDelete\n");
802   #endif
803    } else {
804      FixUpMaxHigh(x->parent);
# Line 792 | Line 808
808      check();
809   #elif defined(DEBUG_ASSERT)
810      if (nil->color != BLACK) GError("Error: nil not black in ITDelete\n");
811 <    if (nil->maxHigh!=std::numeric_limits<N>::min())
812 <        GError("Error: nil->maxHigh != std::numeric_limits<N>::min() in ITDelete\n");
811 >    if (nil->maxHigh!=numeric_limits<N>::min())
812 >        GError("Error: nil->maxHigh != numeric_limits<N>::min() in ITDelete\n");
813   #endif
814    }
815    return returnValue;

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines