1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
#ifndef E_INTERVAL_TREE
#define E_INTERVAL_TREE
// From Emin Martinian, licenced LGPL and MPL with permission
#include <vector>
#include <math.h>
#include <limits>
#include <iostream>
using std::vector;
// The interval_tree.h and interval_tree.cc files contain code for
// interval trees implemented using red-black-trees as described in
// the book _Introduction_To_Algorithms_ by Cormen, Leisserson,
// and Rivest.
// CONVENTIONS:
// Function names: Each word in a function name begins with
// a capital letter. An example funcntion name is
// CreateRedTree(a,b,c). Furthermore, each function name
// should begin with a capital letter to easily distinguish
// them from variables.
//
// Variable names: Each word in a variable name begins with
// a capital letter EXCEPT the first letter of the variable
// name. For example, int newLongInt. Global variables have
// names beginning with "g". An example of a global
// variable name is gNewtonsConstant.
#ifndef MAX_INT
#define MAX_INT INT_MAX // some architechturs define INT_MAX not MAX_INT
#endif
// The Interval class is an Abstract Base Class. This means that no
// instance of the Interval class can exist. Only classes which
// inherit from the Interval class can exist. Furthermore any class
// which inherits from the Interval class must define the member
// functions GetLowPoint and GetHighPoint.
//
// The GetLowPoint should return the lowest point of the interval and
// the GetHighPoint should return the highest point of the interval.
class Interval {
public:
Interval();
virtual ~Interval();
virtual int GetLowPoint() const = 0;
virtual int GetHighPoint() const = 0;
virtual void Print() const;
};
class IntervalTreeNode {
friend class IntervalTree;
public:
void Print(IntervalTreeNode*,
IntervalTreeNode*) const;
IntervalTreeNode();
IntervalTreeNode(Interval *);
~IntervalTreeNode();
protected:
Interval * storedInterval;
int key;
int high;
int maxHigh;
bool red; /* if red=0 then the node is black */
IntervalTreeNode * left;
IntervalTreeNode * right;
IntervalTreeNode * parent;
};
struct it_recursion_node {
public:
/* this structure stores the information needed when we take the */
/* right branch in searching for intervals but possibly come back */
/* and check the left branch as well. */
IntervalTreeNode * start_node;
unsigned int parentIndex;
bool tryRightBranch;
} ;
class IntervalTree {
public:
IntervalTree();
~IntervalTree();
void Print() const;
Interval * DeleteNode(IntervalTreeNode *);
IntervalTreeNode * Insert(Interval *);
IntervalTreeNode * GetPredecessorOf(IntervalTreeNode *) const;
IntervalTreeNode * GetSuccessorOf(IntervalTreeNode *) const;
vector<void *> Enumerate(int low, int high) ;
void CheckAssumptions() const;
protected:
/* A sentinel is used for root and for nil. These sentinels are */
/* created when ITTreeCreate is caled. root->left should always */
/* point to the node which is the root of the tree. nil points to a */
/* node which should always be black but has arbitrary children and */
/* parent and no key or info. The point of using these sentinels is so */
/* that the root and nil nodes do not require special cases in the code */
IntervalTreeNode * root;
IntervalTreeNode * nil;
void LeftRotate(IntervalTreeNode *);
void RightRotate(IntervalTreeNode *);
void TreeInsertHelp(IntervalTreeNode *);
void TreePrintHelper(IntervalTreeNode *) const;
void FixUpMaxHigh(IntervalTreeNode *);
void DeleteFixUp(IntervalTreeNode *);
void CheckMaxHighFields(IntervalTreeNode *) const;
int CheckMaxHighFieldsHelper(IntervalTreeNode * y,
const int currentHigh,
int match) const;
private:
unsigned int recursionNodeStackSize;
it_recursion_node * recursionNodeStack;
unsigned int currentParent;
unsigned int recursionNodeStackTop;
};
#endif
|
