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, 2 months ago) by gpertea
File size: 3299 byte(s)
Log Message:
minor refactoring etc

Line User Rev File contents
1 gpertea 2 #ifndef GINTERVALTREE_H_
2     #define GINTERVALTREE_H_
3    
4 gpertea 171 #include "templatestack.h"
5     #include "GBase.h"
6     #include <math.h>
7 gpertea 2
8 gpertea 171 // 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 gpertea 2
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 gpertea 171 // the GetHighPoint should return the highest point of the interval.
26 gpertea 2
27 gpertea 264 class IntervalTree;
28    
29 gpertea 2 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 gpertea 171 int CheckMaxHighFieldsHelper(IntervalTreeNode * y,
97 gpertea 2 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