diff options
Diffstat (limited to '')
-rw-r--r-- | src/3rdparty/2geom/include/2geom/intervaltree/interval_tree.h | 126 |
1 files changed, 126 insertions, 0 deletions
diff --git a/src/3rdparty/2geom/include/2geom/intervaltree/interval_tree.h b/src/3rdparty/2geom/include/2geom/intervaltree/interval_tree.h new file mode 100644 index 0000000..85f91f9 --- /dev/null +++ b/src/3rdparty/2geom/include/2geom/intervaltree/interval_tree.h @@ -0,0 +1,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 + + + |