ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GIntervalTree.h
Revision: 2
Committed: Mon Mar 22 22:03:27 2010 UTC (9 years, 6 months ago) by gpertea
File size: 3284 byte(s)
Log Message:
added my gclib source files

Line File contents
1 #ifndef GINTERVALTREE_H_
2 #define GINTERVALTREE_H_
3
4 #include"templatestack.h"
5 #include<math.h>
6 #include<limits.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 Interval {
28 public:
29 Interval();
30 virtual ~Interval();
31 virtual int GetLowPoint() const = 0;
32 virtual int GetHighPoint() const = 0;
33 virtual void Print() const;
34 };
35
36 class IntervalTreeNode {
37 friend class IntervalTree;
38 public:
39 void Print(IntervalTreeNode*,
40 IntervalTreeNode*) const;
41 IntervalTreeNode();
42 IntervalTreeNode(Interval *);
43 ~IntervalTreeNode();
44 protected:
45 Interval * storedInterval;
46 int key;
47 int high;
48 int maxHigh;
49 int red; /* if red=0 then the node is black */
50 IntervalTreeNode * left;
51 IntervalTreeNode * right;
52 IntervalTreeNode * parent;
53 };
54
55 struct it_recursion_node {
56 public:
57 /* this structure stores the information needed when we take the */
58 /* right branch in searching for intervals but possibly come back */
59 /* and check the left branch as well. */
60
61 IntervalTreeNode * start_node;
62 unsigned int parentIndex;
63 int tryRightBranch;
64 } ;
65
66
67 class IntervalTree {
68 public:
69 IntervalTree();
70 ~IntervalTree();
71 void Print() const;
72 Interval * DeleteNode(IntervalTreeNode *);
73 IntervalTreeNode * Insert(Interval *);
74 IntervalTreeNode * GetPredecessorOf(IntervalTreeNode *) const;
75 IntervalTreeNode * GetSuccessorOf(IntervalTreeNode *) const;
76 TemplateStack<void *> * Enumerate(int low, int high) ;
77 void CheckAssumptions() const;
78 protected:
79 /* A sentinel is used for root and for nil. These sentinels are */
80 /* created when ITTreeCreate is caled. root->left should always */
81 /* point to the node which is the root of the tree. nil points to a */
82 /* node which should always be black but has aribtrary children and */
83 /* parent and no key or info. The point of using these sentinels is so */
84 /* that the root and nil nodes do not require special cases in the code */
85 IntervalTreeNode * root;
86 IntervalTreeNode * nil;
87 void LeftRotate(IntervalTreeNode *);
88 void RightRotate(IntervalTreeNode *);
89 void TreeInsertHelp(IntervalTreeNode *);
90 void TreePrintHelper(IntervalTreeNode *) const;
91 void FixUpMaxHigh(IntervalTreeNode *);
92 void DeleteFixUp(IntervalTreeNode *);
93 void CheckMaxHighFields(IntervalTreeNode *) const;
94 int CheckMaxHighFieldsHelper(IntervalTreeNode * y,
95 const int currentHigh,
96 int match) const;
97 private:
98 unsigned int recursionNodeStackSize;
99 it_recursion_node * recursionNodeStack;
100 unsigned int currentParent;
101 unsigned int recursionNodeStackTop;
102 };
103
104
105 #endif