ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GIntervalTree.h
Revision: 264
Committed: Mon Aug 27 18:21:11 2012 UTC (7 years, 1 month ago) by gpertea
File size: 3299 byte(s)
Log Message:
minor refactoring etc

Line File contents
1 #ifndef GINTERVALTREE_H_
2 #define GINTERVALTREE_H_
3
4 #include "templatestack.h"
5 #include "GBase.h"
6 #include <math.h>
7
8 // The interval_tree.h and interval_tree.cc files contain code for
9 // interval trees implemented using red-black-trees as described in
10 // the book _Introduction_To_Algorithms_ by Cormen, Leisserson,
11 // and Rivest.
12
13 /*
14 #ifndef MAX_INT
15 #define MAX_INT INT_MAX // some architechturs define INT_MAX not MAX_INT
16 #endif
17 */
18 // The Interval class is an Abstract Base Class. This means that no
19 // instance of the Interval class can exist. Only classes which
20 // inherit from the Interval class can exist. Furthermore any class
21 // which inherits from the Interval class must define the member
22 // functions GetLowPoint and GetHighPoint.
23 //
24 // The GetLowPoint should return the lowest point of the interval and
25 // the GetHighPoint should return the highest point of the interval.
26
27 class IntervalTree;
28
29 class Interval {
30 public:
31 Interval();
32 virtual ~Interval();
33 virtual int GetLowPoint() const = 0;
34 virtual int GetHighPoint() const = 0;
35 virtual void Print() const;
36 };
37
38 class IntervalTreeNode {
39 friend class IntervalTree;
40 public:
41 void Print(IntervalTreeNode*,
42 IntervalTreeNode*) const;
43 IntervalTreeNode();
44 IntervalTreeNode(Interval *);
45 ~IntervalTreeNode();
46 protected:
47 Interval * storedInterval;
48 int key;
49 int high;
50 int maxHigh;
51 int red; /* if red=0 then the node is black */
52 IntervalTreeNode * left;
53 IntervalTreeNode * right;
54 IntervalTreeNode * parent;
55 };
56
57 struct it_recursion_node {
58 public:
59 /* this structure stores the information needed when we take the */
60 /* right branch in searching for intervals but possibly come back */
61 /* and check the left branch as well. */
62
63 IntervalTreeNode * start_node;
64 unsigned int parentIndex;
65 int tryRightBranch;
66 } ;
67
68
69 class IntervalTree {
70 public:
71 IntervalTree();
72 ~IntervalTree();
73 void Print() const;
74 Interval * DeleteNode(IntervalTreeNode *);
75 IntervalTreeNode * Insert(Interval *);
76 IntervalTreeNode * GetPredecessorOf(IntervalTreeNode *) const;
77 IntervalTreeNode * GetSuccessorOf(IntervalTreeNode *) const;
78 TemplateStack<void *> * Enumerate(int low, int high) ;
79 void CheckAssumptions() const;
80 protected:
81 /* A sentinel is used for root and for nil. These sentinels are */
82 /* created when ITTreeCreate is caled. root->left should always */
83 /* point to the node which is the root of the tree. nil points to a */
84 /* node which should always be black but has aribtrary children and */
85 /* parent and no key or info. The point of using these sentinels is so */
86 /* that the root and nil nodes do not require special cases in the code */
87 IntervalTreeNode * root;
88 IntervalTreeNode * nil;
89 void LeftRotate(IntervalTreeNode *);
90 void RightRotate(IntervalTreeNode *);
91 void TreeInsertHelp(IntervalTreeNode *);
92 void TreePrintHelper(IntervalTreeNode *) const;
93 void FixUpMaxHigh(IntervalTreeNode *);
94 void DeleteFixUp(IntervalTreeNode *);
95 void CheckMaxHighFields(IntervalTreeNode *) const;
96 int CheckMaxHighFieldsHelper(IntervalTreeNode * y,
97 const int currentHigh,
98 int match) const;
99 private:
100 unsigned int recursionNodeStackSize;
101 it_recursion_node * recursionNodeStack;
102 unsigned int currentParent;
103 unsigned int recursionNodeStackTop;
104 };
105
106
107 #endif