ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GIntervalTree.h
Revision: 171
Committed: Tue Feb 14 22:36:26 2012 UTC (7 years, 4 months ago) by gpertea
File size: 3278 byte(s)
Log Message:
wip fqtrim

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     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 gpertea 171 int CheckMaxHighFieldsHelper(IntervalTreeNode * y,
95 gpertea 2 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