summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--MySpace/collection.h343
-rw-r--r--font_service/collection.h343
-rw-r--r--meta2/collection.h343
-rw-r--r--meta2/common.cpp4
-rw-r--r--meta2/meta2.cpp22
-rw-r--r--meta2/version.h2
-rw-r--r--ping/collection.h343
7 files changed, 1218 insertions, 182 deletions
diff --git a/MySpace/collection.h b/MySpace/collection.h
index 2c69216..d0570f4 100644
--- a/MySpace/collection.h
+++ b/MySpace/collection.h
@@ -7,8 +7,8 @@ public:
Collection(): count(0) {}
virtual void clear() = 0;
- virtual void add(T &val) = 0;
- virtual const bool remove(T &val) = 0;
+ virtual void add(const T &val) = 0;
+ virtual const bool remove(const T &val) = 0;
const unsigned long size() const {return count;}
};
@@ -17,7 +17,7 @@ template<class T> class Node {
public:
T val;
- Node(T &v): val(v) {}
+ Node(const T &v): val(v) {}
virtual ~Node() {}
};
@@ -25,7 +25,7 @@ template<class T> class ListNode: public Node<T> {
public:
ListNode<T> *next, *prev;
- ListNode(T &v): Node<T>(v), next(0), prev(0) {}
+ ListNode(const T &v): Node<T>(v), next(0), prev(0) {}
virtual ~ListNode() {
if(next) next->prev = prev;
if(prev) prev->next = next;
@@ -87,7 +87,7 @@ public:
Collection<T>::count++;
}
- virtual void add(T &val) {
+ virtual void add(const T &val) {
ListNode<T> *n = new ListNode<T>(val);
n->prev = tail;
if(tail) tail->next = n;
@@ -96,7 +96,7 @@ public:
Collection<T>::count++;
}
- virtual const bool remove(T &val) {
+ virtual const bool remove(const T &val) {
ListNode<T> *n = head;
while(n) {
if(n->val == val) {
@@ -192,7 +192,7 @@ public:
virtual Iterator start() const {return Iterator(ar, Collection<T>::count, 0);}
- virtual void add(T &val) {
+ virtual void add(const T &val) {
if(Collection<T>::count == limit) {
limit += increment;
ar = (T *)realloc(ar, limit * sizeof(T));
@@ -207,7 +207,7 @@ public:
}
}
- virtual const bool remove(T &val) {
+ virtual const bool remove(const T &val) {
for(unsigned long i = 0; i < Collection<T>::count; i++) {
if(ar[i] == val) {
memmove(ar + i, ar + i + 1, (Collection<T>::count - i) * sizeof(T));
@@ -226,7 +226,7 @@ public:
return true;
}
- virtual const bool insert(T &val, const unsigned long index) {
+ virtual const bool insert(const T &val, const unsigned long index) {
if(index > Collection<T>::count) return false;
if(Collection<T>::count == limit) {
@@ -275,7 +275,7 @@ public:
return false;
}
- virtual void push(T &val) {
+ virtual void push(const T &val) {
add(val);
}
};
@@ -285,7 +285,7 @@ public:
SortedDynamicArray(unsigned long init = 0, unsigned long inc = 1): DynamicArray<T>(init, inc) {}
virtual ~SortedDynamicArray() {}
- const bool get_index(T &val, unsigned long &index) {
+ const bool get_index(const T &val, unsigned long &index) {
unsigned long low = 0;
unsigned long high = Collection<T>::count-1;
@@ -306,7 +306,7 @@ public:
return false;
}
- virtual void add(T &val) {
+ virtual void add(const T &val) {
unsigned long index;
get_index(val, index);
insert(val, index);
@@ -317,7 +317,7 @@ template<class T> class TreeNode: public Node<T> {
public:
TreeNode<T> *parent, *left, *right;
- TreeNode(T &v, TreeNode<T> *par): Node<T>(v), parent(par), left(0), right(0) {}
+ TreeNode(const T &v, TreeNode<T> *par): Node<T>(v), parent(par), left(0), right(0) {}
virtual ~TreeNode() {
if(parent) {
if(parent->left == this) parent->left = 0;
@@ -326,18 +326,18 @@ public:
}
};
-template<class T> class BinaryTree: public Collection<T> {
+template<class T, class N = TreeNode<T> > class BinaryTree: public Collection<T> {
protected:
- TreeNode<T> *root;
+ N *root;
- TreeNode<T> *delete_node(TreeNode<T> *n) {
+ virtual void delete_node(N *n) {
if(n->left && n->right) {
- TreeNode<T> *minmax = n->left;
+ N *minmax = n->left;
while(minmax->right) minmax = minmax->right;
n->val = minmax->val;
delete_node(minmax);
- return n;
+ return;
} else if(n->right) {
if(n->parent) {
if(n->parent->left == n) n->parent->left = n->right;
@@ -357,11 +357,10 @@ protected:
}
delete n;
Collection<T>::count--;
- return 0;
}
- void insert_node(TreeNode<T> *n) {
- TreeNode<T> *current = root, *parent = 0;
+ virtual void insert_node(N *n) {
+ N *current = root, *parent = 0;
while(current) {
parent = current;
if(n->val < current->val)
@@ -373,39 +372,38 @@ protected:
if(parent) {
if(n->val < parent->val) {
parent->left = n;
- n->parent = parent;
} else {
parent->right = n;
- n->parent = parent;
}
} else
root = n;
+ n->parent = parent;
Collection<T>::count++;
}
public:
class Iterator {
- friend class BinaryTree<T>;
+ friend class BinaryTree<T, N>;
protected:
class EvalNode {
public:
bool evaluate;
- TreeNode<T> *node;
+ N *node;
EvalNode(): evaluate(false), node(0) {}
- EvalNode(const bool eval, TreeNode<T> *n): evaluate(eval), node(n) {}
+ EvalNode(const bool eval, N *n): evaluate(eval), node(n) {}
const bool operator==(const EvalNode &other) const {return node == other.node;}
EvalNode &operator=(const EvalNode &other) {evaluate = other.evaluate; node = other.node; return *this;}
};
- TreeNode<T> *n;
+ N *n;
LinkedList<EvalNode> stack;
- Iterator(TreeNode<T> *start): n(0) {
+ Iterator(N *start): n(0) {
if(start) {
stack.push(EvalNode(true, start));
next();
@@ -446,7 +444,7 @@ public:
}
virtual void clear() {
- TreeNode<T> *current = root, *parent = 0;
+ N *current = root, *parent = 0;
while(current) {
if(current->left) current = current->left;
else if(current->right) current = current->right;
@@ -461,13 +459,13 @@ public:
Collection<T>::count = 0;
}
- void add(T &val) {
- TreeNode<T> *n = new TreeNode<T>(val, 0);
+ void add(const T &val) {
+ N *n = new N(val, 0);
insert_node(n);
}
- const bool remove(T &val) {
- TreeNode<T> *current = root;
+ const bool remove(const T &val) {
+ N *current = root;
while(current) {
if(current->val == val)
break;
@@ -485,8 +483,8 @@ public:
return false;
}
- const bool contains(T &val) const {
- TreeNode<T> *current = root;
+ const bool contains(const T &val) const {
+ N *current = root;
while(current) {
if(current->val == val)
break;
@@ -502,6 +500,259 @@ public:
Iterator start() const {return Iterator(root);}
};
+#define RED 1
+#define BLACK 0
+
+// thanks to wikipedia (http://en.wikipedia.org/wiki/Red_black_tree)
+template<class T> class ColouredTreeNode: public Node<T> {
+public:
+ ColouredTreeNode<T> *parent, *left, *right;
+ char color;
+
+ ColouredTreeNode(const T &v, ColouredTreeNode<T> *par): Node<T>(v), parent(par), left(0), right(0), color(BLACK) {}
+ virtual ~ColouredTreeNode() {
+ if(parent) {
+ if(parent->left == this) parent->left = 0;
+ if(parent->right == this)parent->right = 0;
+ }
+ }
+};
+
+template<class T, class N = ColouredTreeNode<T> > class RedBlackTree: public BinaryTree<T, N> {
+protected:
+ N *grandparent(N *n) {
+ if (n && n->parent)
+ return n->parent->parent;
+ else
+ return NULL;
+ }
+ N *uncle(N *n) {
+ if(grandparent(n)) {
+ if (n->parent == grandparent(n)->left)
+ return grandparent(n)->right;
+ else
+ return grandparent(n)->left;
+ } else
+ return NULL;
+ }
+ N *sibling(N *n) {
+ if(n->parent) {
+ if (n == n->parent->left)
+ return n->parent->right;
+ else
+ return n->parent->left;
+ } else
+ return NULL;
+ }
+ bool is_leaf(N *n) {
+ return n == 0;
+ }
+
+ void replace_node(N *o, N *n) {
+ n->parent = o->parent;
+ if(n->parent) {
+ if(n->parent->left == o) n->parent->left = n;
+ else if(n->parent->right == o) n->parent->right = n;
+ } else
+ root = n;
+ }
+
+ void rotate_left(N *n) {
+ N *p = n->right;
+ N *q = n;
+
+ q->right = p->left;
+ if(q->right) q->right->parent = q;
+ p->left = q;
+ p->parent = q->parent;
+ q->parent = p;
+ if(p->parent) {
+ if(p->parent->left == q) p->parent->left = p;
+ else if(p->parent->right == q) p->parent->right = p;
+ } else
+ root = p;
+ }
+ void rotate_right(N *n) {
+ N *p = n->left;
+ N *q = n;
+
+ q->left = p->right;
+ if(q->left) q->left->parent = q;
+ p->right = q;
+ p->parent = q->parent;
+ q->parent = p;
+ if(p->parent) {
+ if(p->parent->left == q) p->parent->left = p;
+ else if(p->parent->right == q) p->parent->right = p;
+ } else
+ root = p;
+ }
+
+ void insert_case1(N *n) {
+ if (n->parent == NULL)
+ n->color = BLACK;
+ else
+ insert_case2(n);
+ }
+ void insert_case2(N *n) {
+ if (n->parent->color == BLACK)
+ return; /* Tree is still valid */
+ else
+ insert_case3(n);
+ }
+ void insert_case3(N *n) {
+ if (uncle(n) != NULL && uncle(n)->color == RED) {
+ n->parent->color = BLACK;
+ uncle(n)->color = BLACK;
+ grandparent(n)->color = RED;
+ insert_case1(grandparent(n));
+ } else
+ insert_case4(n);
+ }
+ void insert_case4(N *n) {
+ if (n == n->parent->right && n->parent == grandparent(n)->left) {
+ rotate_left(n->parent);
+ n = n->left;
+ } else if (n == n->parent->left && n->parent == grandparent(n)->right) {
+ rotate_right(n->parent);
+ n = n->right;
+ }
+ insert_case5(n);
+ }
+ void insert_case5(N *n) {
+ n->parent->color = BLACK;
+ grandparent(n)->color = RED;
+ if (n == n->parent->left && n->parent == grandparent(n)->left) {
+ rotate_right(grandparent(n));
+ } else {
+ /* Here, n == n->parent->right && n->parent == grandparent(n)->right */
+ rotate_left(grandparent(n));
+ }
+ }
+
+ void delete_case0(N *n) {
+ /* Precondition: n has at most one non-null child */
+ N *child = is_leaf(n->right) ? n->left : n->right;
+ if(child) replace_node(n, child);
+ if (n->color == BLACK) {
+ if(child) {
+ if (child->color == RED)
+ child->color = BLACK;
+ else
+ delete_case1(child);
+ } else
+ delete_case1(n);
+ }
+ if(root == n) root = 0;
+ delete n;
+ Collection<T>::count--;
+ }
+ void delete_case1(N *n) {
+ if (n->parent == NULL)
+ return;
+ else
+ delete_case2(n);
+ }
+ void delete_case2(N *n) {
+ if (sibling(n) && sibling(n)->color == RED) {
+ n->parent->color = RED;
+ sibling(n)->color = BLACK;
+ if (n == n->parent->left)
+ rotate_left(n->parent);
+ else
+ rotate_right(n->parent);
+ }
+ delete_case3(n);
+ }
+ void delete_case3(N *n) {
+ if (n->parent->color == BLACK &&
+ sibling(n) &&
+ sibling(n)->color == BLACK &&
+ (sibling(n)->left == 0 || sibling(n)->left->color == BLACK) &&
+ (sibling(n)->right == 0 || sibling(n)->right->color == BLACK))
+ {
+ sibling(n)->color = RED;
+ delete_case1(n->parent);
+ } else
+ delete_case4(n);
+ }
+ void delete_case4(N *n) {
+ if (n->parent->color == RED &&
+ sibling(n) &&
+ sibling(n)->color == BLACK &&
+ (sibling(n)->left == 0 || sibling(n)->left->color == BLACK) &&
+ (sibling(n)->right == 0 || sibling(n)->right->color == BLACK))
+ {
+ sibling(n)->color = RED;
+ n->parent->color = BLACK;
+ } else
+ delete_case5(n);
+ }
+ void delete_case5(N *n) {
+ if (n == n->parent->left &&
+ sibling(n) &&
+ sibling(n)->color == BLACK &&
+ sibling(n)->left &&
+ sibling(n)->left->color == RED &&
+ (sibling(n)->right == 0 || sibling(n)->right->color == BLACK))
+ {
+ sibling(n)->color = RED;
+ sibling(n)->left->color = BLACK;
+ rotate_right(sibling(n));
+ } else if (n == n->parent->right &&
+ sibling(n) &&
+ sibling(n)->color == BLACK &&
+ sibling(n)->right &&
+ sibling(n)->right->color == RED &&
+ (sibling(n)->left == 0 || sibling(n)->left->color == BLACK))
+ {
+ sibling(n)->color = RED;
+ sibling(n)->right->color = BLACK;
+ rotate_left(sibling(n));
+ }
+ delete_case6(n);
+ }
+ void delete_case6(N *n) {
+ sibling(n)->color = n->parent->color;
+ n->parent->color = BLACK;
+ if (n == n->parent->left) {
+ /* Here, sibling(n)->right->color == RED */
+ sibling(n)->right->color = BLACK;
+ rotate_left(n->parent);
+ } else {
+ /* Here, sibling(n)->left->color == RED */
+ sibling(n)->left->color = BLACK;
+ rotate_right(n->parent);
+ }
+ }
+
+ N *get_predecessor(N *n) {
+ N *minmax = n->left;
+ while(minmax->right) minmax = minmax->right;
+ return minmax;
+ }
+
+ virtual void insert_node(N *n) {
+ BinaryTree<T, N>::insert_node(n);
+ n->color = RED;
+
+ insert_case1(n);
+ }
+
+ virtual void delete_node(N *n) {
+ if(n->left && n->right) {
+ N *predecessor = get_predecessor(n);
+ n->val = predecessor->val;
+ delete_case0(predecessor);
+ } else
+ delete_case0(n);
+ }
+
+public:
+ RedBlackTree(): BinaryTree< T, N >() {}
+ virtual ~RedBlackTree() {}
+};
+
template<class A, class B> class Pair {
public:
A first;
@@ -509,7 +760,7 @@ public:
Pair(const A &f): first(f) {}
Pair(const A &f, const B &s): first(f), second(s) {}
- Pair(Pair<A,B> &other): first(other.first), second(other.second) {}
+ Pair(const Pair<A,B> &other): first(other.first), second(other.second) {}
virtual ~Pair() {}
const bool operator<(const Pair<A,B> &other) const {return first < other.first;}
@@ -517,11 +768,12 @@ public:
Pair<A,B> &operator=(const Pair<A,B> &other) {first = other.first; second = other.second; return *this;}
};
-template<class A, class B> class Map: public BinaryTree< Pair< A, B > > {
+//template<class A, class B, class N = TreeNode<Pair<A, B> > > class Map: public BinaryTree< Pair< A, B >, N > {
+template<class A, class B, class N = ColouredTreeNode<Pair<A, B> > > class Map: public RedBlackTree< Pair< A, B >, N > {
protected:
- TreeNode<Pair< A, B > > *find(A &key) const {
- TreeNode<Pair< A, B > > *n = BinaryTree< Pair< A, B > >::root;
+ N *find(A &key) const {
+ N *n = root;
while(n) {
if(n->val.first == key)
return n;
@@ -534,7 +786,8 @@ protected:
return 0;
}
public:
- Map(): BinaryTree< Pair<A,B> >() {}
+ //Map(): BinaryTree< Pair<A,B>, N >() {}
+ Map(): RedBlackTree< Pair<A,B>, N >() {}
virtual ~Map() {}
void put(A &key, B &value) {
@@ -542,7 +795,7 @@ public:
}
const bool get(A &key, B &val) const {
- const TreeNode<Pair< A, B > > *n = find(key);
+ const N *n = find(key);
if(n) {
val = n->val.second;
return true;
@@ -551,19 +804,19 @@ public:
}
B &operator[](A &key) {
- TreeNode<Pair< A, B > > *n = find(key);
+ N *n = find(key);
if(n)
return n->val.second;
else {
Pair< A, B > p(key);
- TreeNode<Pair< A, B > > *n = new TreeNode<Pair< A, B > >(p, 0);
+ N *n = new N(p, 0);
insert_node(n);
return n->val.second;
}
}
virtual const bool exists(A &key) const {
- const TreeNode<Pair< A, B > > *n = find(key);
+ const N *n = find(key);
if(n) {
return true;
} else
@@ -571,7 +824,7 @@ public:
}
virtual const bool remove(A &key) {
- TreeNode<Pair< A, B > > *n = find(key);
+ N *n = find(key);
if(n) {
delete_node(n);
return true;
diff --git a/font_service/collection.h b/font_service/collection.h
index 2c69216..d0570f4 100644
--- a/font_service/collection.h
+++ b/font_service/collection.h
@@ -7,8 +7,8 @@ public:
Collection(): count(0) {}
virtual void clear() = 0;
- virtual void add(T &val) = 0;
- virtual const bool remove(T &val) = 0;
+ virtual void add(const T &val) = 0;
+ virtual const bool remove(const T &val) = 0;
const unsigned long size() const {return count;}
};
@@ -17,7 +17,7 @@ template<class T> class Node {
public:
T val;
- Node(T &v): val(v) {}
+ Node(const T &v): val(v) {}
virtual ~Node() {}
};
@@ -25,7 +25,7 @@ template<class T> class ListNode: public Node<T> {
public:
ListNode<T> *next, *prev;
- ListNode(T &v): Node<T>(v), next(0), prev(0) {}
+ ListNode(const T &v): Node<T>(v), next(0), prev(0) {}
virtual ~ListNode() {
if(next) next->prev = prev;
if(prev) prev->next = next;
@@ -87,7 +87,7 @@ public:
Collection<T>::count++;
}
- virtual void add(T &val) {
+ virtual void add(const T &val) {
ListNode<T> *n = new ListNode<T>(val);
n->prev = tail;
if(tail) tail->next = n;
@@ -96,7 +96,7 @@ public:
Collection<T>::count++;
}
- virtual const bool remove(T &val) {
+ virtual const bool remove(const T &val) {
ListNode<T> *n = head;
while(n) {
if(n->val == val) {
@@ -192,7 +192,7 @@ public:
virtual Iterator start() const {return Iterator(ar, Collection<T>::count, 0);}
- virtual void add(T &val) {
+ virtual void add(const T &val) {
if(Collection<T>::count == limit) {
limit += increment;
ar = (T *)realloc(ar, limit * sizeof(T));
@@ -207,7 +207,7 @@ public:
}
}
- virtual const bool remove(T &val) {
+ virtual const bool remove(const T &val) {
for(unsigned long i = 0; i < Collection<T>::count; i++) {
if(ar[i] == val) {
memmove(ar + i, ar + i + 1, (Collection<T>::count - i) * sizeof(T));
@@ -226,7 +226,7 @@ public:
return true;
}
- virtual const bool insert(T &val, const unsigned long index) {
+ virtual const bool insert(const T &val, const unsigned long index) {
if(index > Collection<T>::count) return false;
if(Collection<T>::count == limit) {
@@ -275,7 +275,7 @@ public:
return false;
}
- virtual void push(T &val) {
+ virtual void push(const T &val) {
add(val);
}
};
@@ -285,7 +285,7 @@ public:
SortedDynamicArray(unsigned long init = 0, unsigned long inc = 1): DynamicArray<T>(init, inc) {}
virtual ~SortedDynamicArray() {}
- const bool get_index(T &val, unsigned long &index) {
+ const bool get_index(const T &val, unsigned long &index) {
unsigned long low = 0;
unsigned long high = Collection<T>::count-1;
@@ -306,7 +306,7 @@ public:
return false;
}
- virtual void add(T &val) {
+ virtual void add(const T &val) {
unsigned long index;
get_index(val, index);
insert(val, index);
@@ -317,7 +317,7 @@ template<class T> class TreeNode: public Node<T> {
public:
TreeNode<T> *parent, *left, *right;
- TreeNode(T &v, TreeNode<T> *par): Node<T>(v), parent(par), left(0), right(0) {}
+ TreeNode(const T &v, TreeNode<T> *par): Node<T>(v), parent(par), left(0), right(0) {}
virtual ~TreeNode() {
if(parent) {
if(parent->left == this) parent->left = 0;
@@ -326,18 +326,18 @@ public:
}
};
-template<class T> class BinaryTree: public Collection<T> {
+template<class T, class N = TreeNode<T> > class BinaryTree: public Collection<T> {
protected:
- TreeNode<T> *root;
+ N *root;
- TreeNode<T> *delete_node(TreeNode<T> *n) {
+ virtual void delete_node(N *n) {
if(n->left && n->right) {
- TreeNode<T> *minmax = n->left;
+ N *minmax = n->left;
while(minmax->right) minmax = minmax->right;
n->val = minmax->val;
delete_node(minmax);
- return n;
+ return;
} else if(n->right) {
if(n->parent) {
if(n->parent->left == n) n->parent->left = n->right;
@@ -357,11 +357,10 @@ protected:
}
delete n;
Collection<T>::count--;
- return 0;
}
- void insert_node(TreeNode<T> *n) {
- TreeNode<T> *current = root, *parent = 0;
+ virtual void insert_node(N *n) {
+ N *current = root, *parent = 0;
while(current) {
parent = current;
if(n->val < current->val)
@@ -373,39 +372,38 @@ protected:
if(parent) {
if(n->val < parent->val) {
parent->left = n;
- n->parent = parent;
} else {
parent->right = n;
- n->parent = parent;
}
} else
root = n;
+ n->parent = parent;
Collection<T>::count++;
}
public:
class Iterator {
- friend class BinaryTree<T>;
+ friend class BinaryTree<T, N>;
protected:
class EvalNode {
public:
bool evaluate;
- TreeNode<T> *node;
+ N *node;
EvalNode(): evaluate(false), node(0) {}
- EvalNode(const bool eval, TreeNode<T> *n): evaluate(eval), node(n) {}
+ EvalNode(const bool eval, N *n): evaluate(eval), node(n) {}
const bool operator==(const EvalNode &other) const {return node == other.node;}
EvalNode &operator=(const EvalNode &other) {evaluate = other.evaluate; node = other.node; return *this;}
};
- TreeNode<T> *n;
+ N *n;
LinkedList<EvalNode> stack;
- Iterator(TreeNode<T> *start): n(0) {
+ Iterator(N *start): n(0) {
if(start) {
stack.push(EvalNode(true, start));
next();
@@ -446,7 +444,7 @@ public:
}
virtual void clear() {
- TreeNode<T> *current = root, *parent = 0;
+ N *current = root, *parent = 0;
while(current) {
if(current->left) current = current->left;
else if(current->right) current = current->right;
@@ -461,13 +459,13 @@ public:
Collection<T>::count = 0;
}
- void add(T &val) {
- TreeNode<T> *n = new TreeNode<T>(val, 0);
+ void add(const T &val) {
+ N *n = new N(val, 0);
insert_node(n);
}
- const bool remove(T &val) {
- TreeNode<T> *current = root;
+ const bool remove(const T &val) {
+ N *current = root;
while(current) {
if(current->val == val)
break;
@@ -485,8 +483,8 @@ public:
return false;
}
- const bool contains(T &val) const {
- TreeNode<T> *current = root;
+ const bool contains(const T &val) const {
+ N *current = root;
while(current) {
if(current->val == val)
break;
@@ -502,6 +500,259 @@ public:
Iterator start() const {return Iterator(root);}
};
+#define RED 1
+#define BLACK 0
+
+// thanks to wikipedia (http://en.wikipedia.org/wiki/Red_black_tree)
+template<class T> class ColouredTreeNode: public Node<T> {
+public:
+ ColouredTreeNode<T> *parent, *left, *right;
+ char color;
+
+ ColouredTreeNode(const T &v, ColouredTreeNode<T> *par): Node<T>(v), parent(par), left(0), right(0), color(BLACK) {}
+ virtual ~ColouredTreeNode() {
+ if(parent) {
+ if(parent->left == this) parent->left = 0;
+ if(parent->right == this)parent->right = 0;
+ }
+ }
+};
+
+template<class T, class N = ColouredTreeNode<T> > class RedBlackTree: public BinaryTree<T, N> {
+protected:
+ N *grandparent(N *n) {
+ if (n && n->parent)
+ return n->parent->parent;
+ else
+ return NULL;
+ }
+ N *uncle(N *n) {
+ if(grandparent(n)) {
+ if (n->parent == grandparent(n)->left)
+ return grandparent(n)->right;
+ else
+ return grandparent(n)->left;
+ } else
+ return NULL;
+ }
+ N *sibling(N *n) {
+ if(n->parent) {
+ if (n == n->parent->left)
+ return n->parent->right;
+ else
+ return n->parent->left;
+ } else
+ return NULL;
+ }
+ bool is_leaf(N *n) {
+ return n == 0;
+ }
+
+ void replace_node(N *o, N *n) {
+ n->parent = o->parent;
+ if(n->parent) {
+ if(n->parent->left == o) n->parent->left = n;
+ else if(n->parent->right == o) n->parent->right = n;
+ } else
+ root = n;
+ }
+
+ void rotate_left(N *n) {
+ N *p = n->right;
+ N *q = n;
+
+ q->right = p->left;
+ if(q->right) q->right->parent = q;
+ p->left = q;
+ p->parent = q->parent;
+ q->parent = p;
+ if(p->parent) {
+ if(p->parent->left == q) p->parent->left = p;
+ else if(p->parent->right == q) p->parent->right = p;
+ } else
+ root = p;
+ }
+ void rotate_right(N *n) {
+ N *p = n->left;
+ N *q = n;
+
+ q->left = p->right;
+ if(q->left) q->left->parent = q;
+ p->right = q;
+ p->parent = q->parent;
+ q->parent = p;
+ if(p->parent) {
+ if(p->parent->left == q) p->parent->left = p;
+ else if(p->parent->right == q) p->parent->right = p;
+ } else
+ root = p;
+ }
+
+ void insert_case1(N *n) {
+ if (n->parent == NULL)
+ n->color = BLACK;
+ else
+ insert_case2(n);
+ }
+ void insert_case2(N *n) {
+ if (n->parent->color == BLACK)
+ return; /* Tree is still valid */
+ else
+ insert_case3(n);
+ }
+ void insert_case3(N *n) {
+ if (uncle(n) != NULL && uncle(n)->color == RED) {
+ n->parent->color = BLACK;
+ uncle(n)->color = BLACK;
+ grandparent(n)->color = RED;
+ insert_case1(grandparent(n));
+ } else
+ insert_case4(n);
+ }
+ void insert_case4(N *n) {
+ if (n == n->parent->right && n->parent == grandparent(n)->left) {
+ rotate_left(n->parent);
+ n = n->left;
+ } else if (n == n->parent->left && n->parent == grandparent(n)->right) {
+ rotate_right(n->parent);
+ n = n->right;
+ }
+ insert_case5(n);
+ }
+ void insert_case5(N *n) {
+ n->parent->color = BLACK;
+ grandparent(n)->color = RED;
+ if (n == n->parent->left && n->parent == grandparent(n)->left) {
+ rotate_right(grandparent(n));
+ } else {
+ /* Here, n == n->parent->right && n->parent == grandparent(n)->right */
+ rotate_left(grandparent(n));
+ }
+ }
+
+ void delete_case0(N *n) {
+ /* Precondition: n has at most one non-null child */
+ N *child = is_leaf(n->right) ? n->left : n->right;
+ if(child) replace_node(n, child);
+ if (n->color == BLACK) {
+ if(child) {
+ if (child->color == RED)
+ child->color = BLACK;
+ else
+ delete_case1(child);
+ } else
+ delete_case1(n);
+ }
+ if(root == n) root = 0;
+ delete n;
+ Collection<T>::count--;
+ }
+ void delete_case1(N *n) {
+ if (n->parent == NULL)
+ return;
+ else
+ delete_case2(n);
+ }
+ void delete_case2(N *n) {
+ if (sibling(n) && sibling(n)->color == RED) {
+ n->parent->color = RED;
+ sibling(n)->color = BLACK;
+ if (n == n->parent->left)
+ rotate_left(n->parent);
+ else
+ rotate_right(n->parent);
+ }
+ delete_case3(n);
+ }
+ void delete_case3(N *n) {
+ if (n->parent->color == BLACK &&
+ sibling(n) &&
+ sibling(n)->color == BLACK &&
+ (sibling(n)->left == 0 || sibling(n)->left->color == BLACK) &&
+ (sibling(n)->right == 0 || sibling(n)->right->color == BLACK))
+ {
+ sibling(n)->color = RED;
+ delete_case1(n->parent);
+ } else
+ delete_case4(n);
+ }
+ void delete_case4(N *n) {
+ if (n->parent->color == RED &&
+ sibling(n) &&
+ sibling(n)->color == BLACK &&
+ (sibling(n)->left == 0 || sibling(n)->left->color == BLACK) &&
+ (sibling(n)->right == 0 || sibling(n)->right->color == BLACK))
+ {
+ sibling(n)->color = RED;
+ n->parent->color = BLACK;
+ } else
+ delete_case5(n);
+ }
+ void delete_case5(N *n) {
+ if (n == n->parent->left &&
+ sibling(n) &&
+ sibling(n)->color == BLACK &&
+ sibling(n)->left &&
+ sibling(n)->left->color == RED &&
+ (sibling(n)->right == 0 || sibling(n)->right->color == BLACK))
+ {
+ sibling(n)->color = RED;
+ sibling(n)->left->color = BLACK;
+ rotate_right(sibling(n));
+ } else if (n == n->parent->right &&
+ sibling(n) &&
+ sibling(n)->color == BLACK &&
+ sibling(n)->right &&
+ sibling(n)->right->color == RED &&
+ (sibling(n)->left == 0 || sibling(n)->left->color == BLACK))
+ {
+ sibling(n)->color = RED;
+ sibling(n)->right->color = BLACK;
+ rotate_left(sibling(n));
+ }
+ delete_case6(n);
+ }
+ void delete_case6(N *n) {
+ sibling(n)->color = n->parent->color;
+ n->parent->color = BLACK;
+ if (n == n->parent->left) {
+ /* Here, sibling(n)->right->color == RED */
+ sibling(n)->right->color = BLACK;
+ rotate_left(n->parent);
+ } else {
+ /* Here, sibling(n)->left->color == RED */
+ sibling(n)->left->color = BLACK;
+ rotate_right(n->parent);
+ }
+ }
+
+ N *get_predecessor(N *n) {
+ N *minmax = n->left;
+ while(minmax->right) minmax = minmax->right;
+ return minmax;
+ }
+
+ virtual void insert_node(N *n) {
+ BinaryTree<T, N>::insert_node(n);
+ n->color = RED;
+
+ insert_case1(n);
+ }
+
+ virtual void delete_node(N *n) {
+ if(n->left && n->right) {
+ N *predecessor = get_predecessor(n);
+ n->val = predecessor->val;
+ delete_case0(predecessor);
+ } else
+ delete_case0(n);
+ }
+
+public:
+ RedBlackTree(): BinaryTree< T, N >() {}
+ virtual ~RedBlackTree() {}
+};
+
template<class A, class B> class Pair {
public:
A first;
@@ -509,7 +760,7 @@ public:
Pair(const A &f): first(f) {}
Pair(const A &f, const B &s): first(f), second(s) {}
- Pair(Pair<A,B> &other): first(other.first), second(other.second) {}
+ Pair(const Pair<A,B> &other): first(other.first), second(other.second) {}
virtual ~Pair() {}
const bool operator<(const Pair<A,B> &other) const {return first < other.first;}
@@ -517,11 +768,12 @@ public:
Pair<A,B> &operator=(const Pair<A,B> &other) {first = other.first; second = other.second; return *this;}
};
-template<class A, class B> class Map: public BinaryTree< Pair< A, B > > {
+//template<class A, class B, class N = TreeNode<Pair<A, B> > > class Map: public BinaryTree< Pair< A, B >, N > {
+template<class A, class B, class N = ColouredTreeNode<Pair<A, B> > > class Map: public RedBlackTree< Pair< A, B >, N > {
protected:
- TreeNode<Pair< A, B > > *find(A &key) const {
- TreeNode<Pair< A, B > > *n = BinaryTree< Pair< A, B > >::root;
+ N *find(A &key) const {
+ N *n = root;
while(n) {
if(n->val.first == key)
return n;
@@ -534,7 +786,8 @@ protected:
return 0;
}
public:
- Map(): BinaryTree< Pair<A,B> >() {}
+ //Map(): BinaryTree< Pair<A,B>, N >() {}
+ Map(): RedBlackTree< Pair<A,B>, N >() {}
virtual ~Map() {}
void put(A &key, B &value) {
@@ -542,7 +795,7 @@ public:
}
const bool get(A &key, B &val) const {
- const TreeNode<Pair< A, B > > *n = find(key);
+ const N *n = find(key);
if(n) {
val = n->val.second;
return true;
@@ -551,19 +804,19 @@ public:
}
B &operator[](A &key) {
- TreeNode<Pair< A, B > > *n = find(key);
+ N *n = find(key);
if(n)
return n->val.second;
else {
Pair< A, B > p(key);
- TreeNode<Pair< A, B > > *n = new TreeNode<Pair< A, B > >(p, 0);
+ N *n = new N(p, 0);
insert_node(n);
return n->val.second;
}
}
virtual const bool exists(A &key) const {
- const TreeNode<Pair< A, B > > *n = find(key);
+ const N *n = find(key);
if(n) {
return true;
} else
@@ -571,7 +824,7 @@ public:
}
virtual const bool remove(A &key) {
- TreeNode<Pair< A, B > > *n = find(key);
+ N *n = find(key);
if(n) {
delete_node(n);
return true;
diff --git a/meta2/collection.h b/meta2/collection.h
index 2c69216..d0570f4 100644
--- a/meta2/collection.h
+++ b/meta2/collection.h
@@ -7,8 +7,8 @@ public:
Collection(): count(0) {}
virtual void clear() = 0;
- virtual void add(T &val) = 0;
- virtual const bool remove(T &val) = 0;
+ virtual void add(const T &val) = 0;
+ virtual const bool remove(const T &val) = 0;
const unsigned long size() const {return count;}
};
@@ -17,7 +17,7 @@ template<class T> class Node {
public:
T val;
- Node(T &v): val(v) {}
+ Node(const T &v): val(v) {}
virtual ~Node() {}
};
@@ -25,7 +25,7 @@ template<class T> class ListNode: public Node<T> {
public:
ListNode<T> *next, *prev;
- ListNode(T &v): Node<T>(v), next(0), prev(0) {}
+ ListNode(const T &v): Node<T>(v), next(0), prev(0) {}
virtual ~ListNode() {
if(next) next->prev = prev;
if(prev) prev->next = next;
@@ -87,7 +87,7 @@ public:
Collection<T>::count++;
}
- virtual void add(T &val) {
+ virtual void add(const T &val) {
ListNode<T> *n = new ListNode<T>(val);
n->prev = tail;
if(tail) tail->next = n;
@@ -96,7 +96,7 @@ public:
Collection<T>::count++;
}
- virtual const bool remove(T &val) {
+ virtual const bool remove(const T &val) {
ListNode<T> *n = head;
while(n) {
if(n->val == val) {
@@ -192,7 +192,7 @@ public:
virtual Iterator start() const {return Iterator(ar, Collection<T>::count, 0);}
- virtual void add(T &val) {
+ virtual void add(const T &val) {
if(Collection<T>::count == limit) {
limit += increment;
ar = (T *)realloc(ar, limit * sizeof(T));
@@ -207,7 +207,7 @@ public:
}
}
- virtual const bool remove(T &val) {
+ virtual const bool remove(const T &val) {
for(unsigned long i = 0; i < Collection<T>::count; i++) {
if(ar[i] == val) {
memmove(ar + i, ar + i + 1, (Collection<T>::count - i) * sizeof(T));
@@ -226,7 +226,7 @@ public:
return true;
}
- virtual const bool insert(T &val, const unsigned long index) {
+ virtual const bool insert(const T &val, const unsigned long index) {
if(index > Collection<T>::count) return false;
if(Collection<T>::count == limit) {
@@ -275,7 +275,7 @@ public:
return false;
}
- virtual void push(T &val) {
+ virtual void push(const T &val) {
add(val);
}
};
@@ -285,7 +285,7 @@ public:
SortedDynamicArray(unsigned long init = 0, unsigned long inc = 1): DynamicArray<T>(init, inc) {}
virtual ~SortedDynamicArray() {}
- const bool get_index(T &val, unsigned long &index) {
+ const bool get_index(const T &val, unsigned long &index) {
unsigned long low = 0;
unsigned long high = Collection<T>::count-1;
@@ -306,7 +306,7 @@ public:
return false;
}
- virtual void add(T &val) {
+ virtual void add(const T &val) {
unsigned long index;
get_index(val, index);
insert(val, index);
@@ -317,7 +317,7 @@ template<class T> class TreeNode: public Node<T> {
public:
TreeNode<T> *parent, *left, *right;
- TreeNode(T &v, TreeNode<T> *par): Node<T>(v), parent(par), left(0), right(0) {}
+ TreeNode(const T &v, TreeNode<T> *par): Node<T>(v), parent(par), left(0), right(0) {}
virtual ~TreeNode() {
if(parent) {
if(parent->left == this) parent->left = 0;
@@ -326,18 +326,18 @@ public:
}
};
-template<class T> class BinaryTree: public Collection<T> {
+template<class T, class N = TreeNode<T> > class BinaryTree: public Collection<T> {
protected:
- TreeNode<T> *root;
+ N *root;
- TreeNode<T> *delete_node(TreeNode<T> *n) {
+ virtual void delete_node(N *n) {
if(n->left && n->right) {
- TreeNode<T> *minmax = n->left;
+ N *minmax = n->left;
while(minmax->right) minmax = minmax->right;
n->val = minmax->val;
delete_node(minmax);
- return n;
+ return;
} else if(n->right) {
if(n->parent) {
if(n->parent->left == n) n->parent->left = n->right;
@@ -357,11 +357,10 @@ protected:
}
delete n;
Collection<T>::count--;
- return 0;
}
- void insert_node(TreeNode<T> *n) {
- TreeNode<T> *current = root, *parent = 0;
+ virtual void insert_node(N *n) {
+ N *current = root, *parent = 0;
while(current) {
parent = current;
if(n->val < current->val)
@@ -373,39 +372,38 @@ protected:
if(parent) {
if(n->val < parent->val) {
parent->left = n;
- n->parent = parent;
} else {
parent->right = n;
- n->parent = parent;
}
} else
root = n;
+ n->parent = parent;
Collection<T>::count++;
}
public:
class Iterator {
- friend class BinaryTree<T>;
+ friend class BinaryTree<T, N>;
protected:
class EvalNode {
public:
bool evaluate;
- TreeNode<T> *node;
+ N *node;
EvalNode(): evaluate(false), node(0) {}
- EvalNode(const bool eval, TreeNode<T> *n): evaluate(eval), node(n) {}
+ EvalNode(const bool eval, N *n): evaluate(eval), node(n) {}
const bool operator==(const EvalNode &other) const {return node == other.node;}
EvalNode &operator=(const EvalNode &other) {evaluate = other.evaluate; node = other.node; return *this;}
};
- TreeNode<T> *n;
+ N *n;
LinkedList<EvalNode> stack;
- Iterator(TreeNode<T> *start): n(0) {
+ Iterator(N *start): n(0) {
if(start) {
stack.push(EvalNode(true, start));
next();
@@ -446,7 +444,7 @@ public:
}
virtual void clear() {
- TreeNode<T> *current = root, *parent = 0;
+ N *current = root, *parent = 0;
while(current) {
if(current->left) current = current->left;
else if(current->right) current = current->right;
@@ -461,13 +459,13 @@ public:
Collection<T>::count = 0;
}
- void add(T &val) {
- TreeNode<T> *n = new TreeNode<T>(val, 0);
+ void add(const T &val) {
+ N *n = new N(val, 0);
insert_node(n);
}
- const bool remove(T &val) {
- TreeNode<T> *current = root;
+ const bool remove(const T &val) {
+ N *current = root;
while(current) {
if(current->val == val)
break;
@@ -485,8 +483,8 @@ public:
return false;
}
- const bool contains(T &val) const {
- TreeNode<T> *current = root;
+ const bool contains(const T &val) const {
+ N *current = root;
while(current) {
if(current->val == val)
break;
@@ -502,6 +500,259 @@ public:
Iterator start() const {return Iterator(root);}
};
+#define RED 1
+#define BLACK 0
+
+// thanks to wikipedia (http://en.wikipedia.org/wiki/Red_black_tree)
+template<class T> class ColouredTreeNode: public Node<T> {
+public:
+ ColouredTreeNode<T> *parent, *left, *right;
+ char color;
+
+ ColouredTreeNode(const T &v, ColouredTreeNode<T> *par): Node<T>(v), parent(par), left(0), right(0), color(BLACK) {}
+ virtual ~ColouredTreeNode() {
+ if(parent) {
+ if(parent->left == this) parent->left = 0;
+ if(parent->right == this)parent->right = 0;
+ }
+ }
+};
+
+template<class T, class N = ColouredTreeNode<T> > class RedBlackTree: public BinaryTree<T, N> {
+protected:
+ N *grandparent(N *n) {
+ if (n && n->parent)
+ return n->parent->parent;
+ else
+ return NULL;
+ }
+ N *uncle(N *n) {
+ if(grandparent(n)) {
+ if (n->parent == grandparent(n)->left)
+ return grandparent(n)->right;
+ else
+ return grandparent(n)->left;
+ } else
+ return NULL;
+ }
+ N *sibling(N *n) {
+ if(n->parent) {
+ if (n == n->parent->left)
+ return n->parent->right;
+ else
+ return n->parent->left;
+ } else
+ return NULL;
+ }
+ bool is_leaf(N *n) {
+ return n == 0;
+ }
+
+ void replace_node(N *o, N *n) {
+ n->parent = o->parent;
+ if(n->parent) {
+ if(n->parent->left == o) n->parent->left = n;
+ else if(n->parent->right == o) n->parent->right = n;
+ } else
+ root = n;
+ }
+
+ void rotate_left(N *n) {
+ N *p = n->right;
+ N *q = n;
+
+ q->right = p->left;
+ if(q->right) q->right->parent = q;
+ p->left = q;
+ p->parent = q->parent;
+ q->parent = p;
+ if(p->parent) {
+ if(p->parent->left == q) p->parent->left = p;
+ else if(p->parent->right == q) p->parent->right = p;
+ } else
+ root = p;
+ }
+ void rotate_right(N *n) {
+ N *p = n->left;
+ N *q = n;
+
+ q->left = p->right;
+ if(q->left) q->left->parent = q;
+ p->right = q;
+ p->parent = q->parent;
+ q->parent = p;
+ if(p->parent) {
+ if(p->parent->left == q) p->parent->left = p;
+ else if(p->parent->right == q) p->parent->right = p;
+ } else
+ root = p;
+ }
+
+ void insert_case1(N *n) {
+ if (n->parent == NULL)
+ n->color = BLACK;
+ else
+ insert_case2(n);
+ }
+ void insert_case2(N *n) {
+ if (n->parent->color == BLACK)
+ return; /* Tree is still valid */
+ else
+ insert_case3(n);
+ }
+ void insert_case3(N *n) {
+ if (uncle(n) != NULL && uncle(n)->color == RED) {
+ n->parent->color = BLACK;
+ uncle(n)->color = BLACK;
+ grandparent(n)->color = RED;
+ insert_case1(grandparent(n));
+ } else
+ insert_case4(n);
+ }
+ void insert_case4(N *n) {
+ if (n == n->parent->right && n->parent == grandparent(n)->left) {
+ rotate_left(n->parent);
+ n = n->left;
+ } else if (n == n->parent->left && n->parent == grandparent(n)->right) {
+ rotate_right(n->parent);
+ n = n->right;
+ }
+ insert_case5(n);
+ }
+ void insert_case5(N *n) {
+ n->parent->color = BLACK;
+ grandparent(n)->color = RED;
+ if (n == n->parent->left && n->parent == grandparent(n)->left) {
+ rotate_right(grandparent(n));
+ } else {
+ /* Here, n == n->parent->right && n->parent == grandparent(n)->right */
+ rotate_left(grandparent(n));
+ }
+ }
+
+ void delete_case0(N *n) {
+ /* Precondition: n has at most one non-null child */
+ N *child = is_leaf(n->right) ? n->left : n->right;
+ if(child) replace_node(n, child);
+ if (n->color == BLACK) {
+ if(child) {
+ if (child->color == RED)
+ child->color = BLACK;
+ else
+ delete_case1(child);
+ } else
+ delete_case1(n);
+ }
+ if(root == n) root = 0;
+ delete n;
+ Collection<T>::count--;
+ }
+ void delete_case1(N *n) {
+ if (n->parent == NULL)
+ return;
+ else
+ delete_case2(n);
+ }
+ void delete_case2(N *n) {
+ if (sibling(n) && sibling(n)->color == RED) {
+ n->parent->color = RED;
+ sibling(n)->color = BLACK;
+ if (n == n->parent->left)
+ rotate_left(n->parent);
+ else
+ rotate_right(n->parent);
+ }
+ delete_case3(n);
+ }
+ void delete_case3(N *n) {
+ if (n->parent->color == BLACK &&
+ sibling(n) &&
+ sibling(n)->color == BLACK &&
+ (sibling(n)->left == 0 || sibling(n)->left->color == BLACK) &&
+ (sibling(n)->right == 0 || sibling(n)->right->color == BLACK))
+ {
+ sibling(n)->color = RED;
+ delete_case1(n->parent);
+ } else
+ delete_case4(n);
+ }
+ void delete_case4(N *n) {
+ if (n->parent->color == RED &&
+ sibling(n) &&
+ sibling(n)->color == BLACK &&
+ (sibling(n)->left == 0 || sibling(n)->left->color == BLACK) &&
+ (sibling(n)->right == 0 || sibling(n)->right->color == BLACK))
+ {
+ sibling(n)->color = RED;
+ n->parent->color = BLACK;
+ } else
+ delete_case5(n);
+ }
+ void delete_case5(N *n) {
+ if (n == n->parent->left &&
+ sibling(n) &&
+ sibling(n)->color == BLACK &&
+ sibling(n)->left &&
+ sibling(n)->left->color == RED &&
+ (sibling(n)->right == 0 || sibling(n)->right->color == BLACK))
+ {
+ sibling(n)->color = RED;
+ sibling(n)->left->color = BLACK;
+ rotate_right(sibling(n));
+ } else if (n == n->parent->right &&
+ sibling(n) &&
+ sibling(n)->color == BLACK &&
+ sibling(n)->right &&
+ sibling(n)->right->color == RED &&
+ (sibling(n)->left == 0 || sibling(n)->left->color == BLACK))
+ {
+ sibling(n)->color = RED;
+ sibling(n)->right->color = BLACK;
+ rotate_left(sibling(n));
+ }
+ delete_case6(n);
+ }
+ void delete_case6(N *n) {
+ sibling(n)->color = n->parent->color;
+ n->parent->color = BLACK;
+ if (n == n->parent->left) {
+ /* Here, sibling(n)->right->color == RED */
+ sibling(n)->right->color = BLACK;
+ rotate_left(n->parent);
+ } else {
+ /* Here, sibling(n)->left->color == RED */
+ sibling(n)->left->color = BLACK;
+ rotate_right(n->parent);
+ }
+ }
+
+ N *get_predecessor(N *n) {
+ N *minmax = n->left;
+ while(minmax->right) minmax = minmax->right;
+ return minmax;
+ }
+
+ virtual void insert_node(N *n) {
+ BinaryTree<T, N>::insert_node(n);
+ n->color = RED;
+
+ insert_case1(n);
+ }
+
+ virtual void delete_node(N *n) {
+ if(n->left && n->right) {
+ N *predecessor = get_predecessor(n);
+ n->val = predecessor->val;
+ delete_case0(predecessor);
+ } else
+ delete_case0(n);
+ }
+
+public:
+ RedBlackTree(): BinaryTree< T, N >() {}
+ virtual ~RedBlackTree() {}
+};
+
template<class A, class B> class Pair {
public:
A first;
@@ -509,7 +760,7 @@ public:
Pair(const A &f): first(f) {}
Pair(const A &f, const B &s): first(f), second(s) {}
- Pair(Pair<A,B> &other): first(other.first), second(other.second) {}
+ Pair(const Pair<A,B> &other): first(other.first), second(other.second) {}
virtual ~Pair() {}
const bool operator<(const Pair<A,B> &other) const {return first < other.first;}
@@ -517,11 +768,12 @@ public:
Pair<A,B> &operator=(const Pair<A,B> &other) {first = other.first; second = other.second; return *this;}
};
-template<class A, class B> class Map: public BinaryTree< Pair< A, B > > {
+//template<class A, class B, class N = TreeNode<Pair<A, B> > > class Map: public BinaryTree< Pair< A, B >, N > {
+template<class A, class B, class N = ColouredTreeNode<Pair<A, B> > > class Map: public RedBlackTree< Pair< A, B >, N > {
protected:
- TreeNode<Pair< A, B > > *find(A &key) const {
- TreeNode<Pair< A, B > > *n = BinaryTree< Pair< A, B > >::root;
+ N *find(A &key) const {
+ N *n = root;
while(n) {
if(n->val.first == key)
return n;
@@ -534,7 +786,8 @@ protected:
return 0;
}
public:
- Map(): BinaryTree< Pair<A,B> >() {}
+ //Map(): BinaryTree< Pair<A,B>, N >() {}
+ Map(): RedBlackTree< Pair<A,B>, N >() {}
virtual ~Map() {}
void put(A &key, B &value) {
@@ -542,7 +795,7 @@ public:
}
const bool get(A &key, B &val) const {
- const TreeNode<Pair< A, B > > *n = find(key);
+ const N *n = find(key);
if(n) {
val = n->val.second;
return true;
@@ -551,19 +804,19 @@ public:
}
B &operator[](A &key) {
- TreeNode<Pair< A, B > > *n = find(key);
+ N *n = find(key);
if(n)
return n->val.second;
else {
Pair< A, B > p(key);
- TreeNode<Pair< A, B > > *n = new TreeNode<Pair< A, B > >(p, 0);
+ N *n = new N(p, 0);
insert_node(n);
return n->val.second;
}
}
virtual const bool exists(A &key) const {
- const TreeNode<Pair< A, B > > *n = find(key);
+ const N *n = find(key);
if(n) {
return true;
} else
@@ -571,7 +824,7 @@ public:
}
virtual const bool remove(A &key) {
- TreeNode<Pair< A, B > > *n = find(key);
+ N *n = find(key);
if(n) {
delete_node(n);
return true;
diff --git a/meta2/common.cpp b/meta2/common.cpp
index fe22092..17418fd 100644
--- a/meta2/common.cpp
+++ b/meta2/common.cpp
@@ -5,7 +5,11 @@ bool ContactHandle::operator==(const ContactHandle &other) const {
}
bool ContactHandle::operator<(const ContactHandle &other) const {
+ // these don't work, 'cause the comparison is not constant
//return CallService(MS_CLIST_CONTACTSCOMPARE, (WPARAM)hContact, (LPARAM)other.handle()) < 0;
+ //return _tcscmp(ContactName(hContact), ContactName(other.handle()));
+
+ // will produce a *very* unbalanced binary tree (metaMap) when contacts are added in order of handle - which they most likely are
return hContact < other.handle();
}
diff --git a/meta2/meta2.cpp b/meta2/meta2.cpp
index d4effe5..3eff626 100644
--- a/meta2/meta2.cpp
+++ b/meta2/meta2.cpp
@@ -92,13 +92,33 @@ int ModulesLoaded(WPARAM wParam, LPARAM lParam) {
HANDLE hModulesLoaded;
extern "C" __declspec (dllexport) int Load(PLUGINLINK *link) {
-
pluginLink=link;
DuplicateHandle( GetCurrentProcess(), GetCurrentThread(), GetCurrentProcess(), &metaMainThread, THREAD_SET_CONTEXT, FALSE, 0 );
mir_getMMI(&mmi);
mir_getUTFI(&utfi);
+ RedBlackTree<int> test;
+ test.add(1);
+ test.add(-3);
+ test.add(15);
+ test.add(4);
+ test.add(2);
+ test.add(-1);
+ char buff[256];
+ for(RedBlackTree<int>::Iterator i = test.start(); i.has_val(); i.next()) {
+ mir_snprintf(buff, 256, "%d", i.val());
+ PUShowMessage(buff, SM_NOTIFY);
+ }
+
+ test.remove(-1);
+ test.remove(2);
+ for(RedBlackTree<int>::Iterator i2 = test.start(); i2.has_val(); i2.next()) {
+ mir_snprintf(buff, 256, "%d", i2.val());
+ PUShowMessage(buff, SM_NOTIFY);
+ }
+
+
InitOptions();
InitPriorities();
diff --git a/meta2/version.h b/meta2/version.h
index 3c62707..1ef5862 100644
--- a/meta2/version.h
+++ b/meta2/version.h
@@ -5,7 +5,7 @@
#define __MAJOR_VERSION 0
#define __MINOR_VERSION 0
#define __RELEASE_NUM 0
-#define __BUILD_NUM 7
+#define __BUILD_NUM 8
#define __FILEVERSION_STRING __MAJOR_VERSION,__MINOR_VERSION,__RELEASE_NUM,__BUILD_NUM
#define __FILEVERSION_STRING_DOTS __MAJOR_VERSION.__MINOR_VERSION.__RELEASE_NUM.__BUILD_NUM
diff --git a/ping/collection.h b/ping/collection.h
index 2c69216..d0570f4 100644
--- a/ping/collection.h
+++ b/ping/collection.h
@@ -7,8 +7,8 @@ public:
Collection(): count(0) {}
virtual void clear() = 0;
- virtual void add(T &val) = 0;
- virtual const bool remove(T &val) = 0;
+ virtual void add(const T &val) = 0;
+ virtual const bool remove(const T &val) = 0;
const unsigned long size() const {return count;}
};
@@ -17,7 +17,7 @@ template<class T> class Node {
public:
T val;
- Node(T &v): val(v) {}
+ Node(const T &v): val(v) {}
virtual ~Node() {}
};
@@ -25,7 +25,7 @@ template<class T> class ListNode: public Node<T> {
public:
ListNode<T> *next, *prev;
- ListNode(T &v): Node<T>(v), next(0), prev(0) {}
+ ListNode(const T &v): Node<T>(v), next(0), prev(0) {}
virtual ~ListNode() {
if(next) next->prev = prev;
if(prev) prev->next = next;
@@ -87,7 +87,7 @@ public:
Collection<T>::count++;
}
- virtual void add(T &val) {
+ virtual void add(const T &val) {
ListNode<T> *n = new ListNode<T>(val);
n->prev = tail;
if(tail) tail->next = n;
@@ -96,7 +96,7 @@ public:
Collection<T>::count++;
}
- virtual const bool remove(T &val) {
+ virtual const bool remove(const T &val) {
ListNode<T> *n = head;
while(n) {
if(n->val == val) {
@@ -192,7 +192,7 @@ public:
virtual Iterator start() const {return Iterator(ar, Collection<T>::count, 0);}
- virtual void add(T &val) {
+ virtual void add(const T &val) {
if(Collection<T>::count == limit) {
limit += increment;
ar = (T *)realloc(ar, limit * sizeof(T));
@@ -207,7 +207,7 @@ public:
}
}
- virtual const bool remove(T &val) {
+ virtual const bool remove(const T &val) {
for(unsigned long i = 0; i < Collection<T>::count; i++) {
if(ar[i] == val) {
memmove(ar + i, ar + i + 1, (Collection<T>::count - i) * sizeof(T));
@@ -226,7 +226,7 @@ public:
return true;
}
- virtual const bool insert(T &val, const unsigned long index) {
+ virtual const bool insert(const T &val, const unsigned long index) {
if(index > Collection<T>::count) return false;
if(Collection<T>::count == limit) {
@@ -275,7 +275,7 @@ public:
return false;
}
- virtual void push(T &val) {
+ virtual void push(const T &val) {
add(val);
}
};
@@ -285,7 +285,7 @@ public:
SortedDynamicArray(unsigned long init = 0, unsigned long inc = 1): DynamicArray<T>(init, inc) {}
virtual ~SortedDynamicArray() {}
- const bool get_index(T &val, unsigned long &index) {
+ const bool get_index(const T &val, unsigned long &index) {
unsigned long low = 0;
unsigned long high = Collection<T>::count-1;
@@ -306,7 +306,7 @@ public:
return false;
}
- virtual void add(T &val) {
+ virtual void add(const T &val) {
unsigned long index;
get_index(val, index);
insert(val, index);
@@ -317,7 +317,7 @@ template<class T> class TreeNode: public Node<T> {
public:
TreeNode<T> *parent, *left, *right;
- TreeNode(T &v, TreeNode<T> *par): Node<T>(v), parent(par), left(0), right(0) {}
+ TreeNode(const T &v, TreeNode<T> *par): Node<T>(v), parent(par), left(0), right(0) {}
virtual ~TreeNode() {
if(parent) {
if(parent->left == this) parent->left = 0;
@@ -326,18 +326,18 @@ public:
}
};
-template<class T> class BinaryTree: public Collection<T> {
+template<class T, class N = TreeNode<T> > class BinaryTree: public Collection<T> {
protected:
- TreeNode<T> *root;
+ N *root;
- TreeNode<T> *delete_node(TreeNode<T> *n) {
+ virtual void delete_node(N *n) {
if(n->left && n->right) {
- TreeNode<T> *minmax = n->left;
+ N *minmax = n->left;
while(minmax->right) minmax = minmax->right;
n->val = minmax->val;
delete_node(minmax);
- return n;
+ return;
} else if(n->right) {
if(n->parent) {
if(n->parent->left == n) n->parent->left = n->right;
@@ -357,11 +357,10 @@ protected:
}
delete n;
Collection<T>::count--;
- return 0;
}
- void insert_node(TreeNode<T> *n) {
- TreeNode<T> *current = root, *parent = 0;
+ virtual void insert_node(N *n) {
+ N *current = root, *parent = 0;
while(current) {
parent = current;
if(n->val < current->val)
@@ -373,39 +372,38 @@ protected:
if(parent) {
if(n->val < parent->val) {
parent->left = n;
- n->parent = parent;
} else {
parent->right = n;
- n->parent = parent;
}
} else
root = n;
+ n->parent = parent;
Collection<T>::count++;
}
public:
class Iterator {
- friend class BinaryTree<T>;
+ friend class BinaryTree<T, N>;
protected:
class EvalNode {
public:
bool evaluate;
- TreeNode<T> *node;
+ N *node;
EvalNode(): evaluate(false), node(0) {}
- EvalNode(const bool eval, TreeNode<T> *n): evaluate(eval), node(n) {}
+ EvalNode(const bool eval, N *n): evaluate(eval), node(n) {}
const bool operator==(const EvalNode &other) const {return node == other.node;}
EvalNode &operator=(const EvalNode &other) {evaluate = other.evaluate; node = other.node; return *this;}
};
- TreeNode<T> *n;
+ N *n;
LinkedList<EvalNode> stack;
- Iterator(TreeNode<T> *start): n(0) {
+ Iterator(N *start): n(0) {
if(start) {
stack.push(EvalNode(true, start));
next();
@@ -446,7 +444,7 @@ public:
}
virtual void clear() {
- TreeNode<T> *current = root, *parent = 0;
+ N *current = root, *parent = 0;
while(current) {
if(current->left) current = current->left;
else if(current->right) current = current->right;
@@ -461,13 +459,13 @@ public:
Collection<T>::count = 0;
}
- void add(T &val) {
- TreeNode<T> *n = new TreeNode<T>(val, 0);
+ void add(const T &val) {
+ N *n = new N(val, 0);
insert_node(n);
}
- const bool remove(T &val) {
- TreeNode<T> *current = root;
+ const bool remove(const T &val) {
+ N *current = root;
while(current) {
if(current->val == val)
break;
@@ -485,8 +483,8 @@ public:
return false;
}
- const bool contains(T &val) const {
- TreeNode<T> *current = root;
+ const bool contains(const T &val) const {
+ N *current = root;
while(current) {
if(current->val == val)
break;
@@ -502,6 +500,259 @@ public:
Iterator start() const {return Iterator(root);}
};
+#define RED 1
+#define BLACK 0
+
+// thanks to wikipedia (http://en.wikipedia.org/wiki/Red_black_tree)
+template<class T> class ColouredTreeNode: public Node<T> {
+public:
+ ColouredTreeNode<T> *parent, *left, *right;
+ char color;
+
+ ColouredTreeNode(const T &v, ColouredTreeNode<T> *par): Node<T>(v), parent(par), left(0), right(0), color(BLACK) {}
+ virtual ~ColouredTreeNode() {
+ if(parent) {
+ if(parent->left == this) parent->left = 0;
+ if(parent->right == this)parent->right = 0;
+ }
+ }
+};
+
+template<class T, class N = ColouredTreeNode<T> > class RedBlackTree: public BinaryTree<T, N> {
+protected:
+ N *grandparent(N *n) {
+ if (n && n->parent)
+ return n->parent->parent;
+ else
+ return NULL;
+ }
+ N *uncle(N *n) {
+ if(grandparent(n)) {
+ if (n->parent == grandparent(n)->left)
+ return grandparent(n)->right;
+ else
+ return grandparent(n)->left;
+ } else
+ return NULL;
+ }
+ N *sibling(N *n) {
+ if(n->parent) {
+ if (n == n->parent->left)
+ return n->parent->right;
+ else
+ return n->parent->left;
+ } else
+ return NULL;
+ }
+ bool is_leaf(N *n) {
+ return n == 0;
+ }
+
+ void replace_node(N *o, N *n) {
+ n->parent = o->parent;
+ if(n->parent) {
+ if(n->parent->left == o) n->parent->left = n;
+ else if(n->parent->right == o) n->parent->right = n;
+ } else
+ root = n;
+ }
+
+ void rotate_left(N *n) {
+ N *p = n->right;
+ N *q = n;
+
+ q->right = p->left;
+ if(q->right) q->right->parent = q;
+ p->left = q;
+ p->parent = q->parent;
+ q->parent = p;
+ if(p->parent) {
+ if(p->parent->left == q) p->parent->left = p;
+ else if(p->parent->right == q) p->parent->right = p;
+ } else
+ root = p;
+ }
+ void rotate_right(N *n) {
+ N *p = n->left;
+ N *q = n;
+
+ q->left = p->right;
+ if(q->left) q->left->parent = q;
+ p->right = q;
+ p->parent = q->parent;
+ q->parent = p;
+ if(p->parent) {
+ if(p->parent->left == q) p->parent->left = p;
+ else if(p->parent->right == q) p->parent->right = p;
+ } else
+ root = p;
+ }
+
+ void insert_case1(N *n) {
+ if (n->parent == NULL)
+ n->color = BLACK;
+ else
+ insert_case2(n);
+ }
+ void insert_case2(N *n) {
+ if (n->parent->color == BLACK)
+ return; /* Tree is still valid */
+ else
+ insert_case3(n);
+ }
+ void insert_case3(N *n) {
+ if (uncle(n) != NULL && uncle(n)->color == RED) {
+ n->parent->color = BLACK;
+ uncle(n)->color = BLACK;
+ grandparent(n)->color = RED;
+ insert_case1(grandparent(n));
+ } else
+ insert_case4(n);
+ }
+ void insert_case4(N *n) {
+ if (n == n->parent->right && n->parent == grandparent(n)->left) {
+ rotate_left(n->parent);
+ n = n->left;
+ } else if (n == n->parent->left && n->parent == grandparent(n)->right) {
+ rotate_right(n->parent);
+ n = n->right;
+ }
+ insert_case5(n);
+ }
+ void insert_case5(N *n) {
+ n->parent->color = BLACK;
+ grandparent(n)->color = RED;
+ if (n == n->parent->left && n->parent == grandparent(n)->left) {
+ rotate_right(grandparent(n));
+ } else {
+ /* Here, n == n->parent->right && n->parent == grandparent(n)->right */
+ rotate_left(grandparent(n));
+ }
+ }
+
+ void delete_case0(N *n) {
+ /* Precondition: n has at most one non-null child */
+ N *child = is_leaf(n->right) ? n->left : n->right;
+ if(child) replace_node(n, child);
+ if (n->color == BLACK) {
+ if(child) {
+ if (child->color == RED)
+ child->color = BLACK;
+ else
+ delete_case1(child);
+ } else
+ delete_case1(n);
+ }
+ if(root == n) root = 0;
+ delete n;
+ Collection<T>::count--;
+ }
+ void delete_case1(N *n) {
+ if (n->parent == NULL)
+ return;
+ else
+ delete_case2(n);
+ }
+ void delete_case2(N *n) {
+ if (sibling(n) && sibling(n)->color == RED) {
+ n->parent->color = RED;
+ sibling(n)->color = BLACK;
+ if (n == n->parent->left)
+ rotate_left(n->parent);
+ else
+ rotate_right(n->parent);
+ }
+ delete_case3(n);
+ }
+ void delete_case3(N *n) {
+ if (n->parent->color == BLACK &&
+ sibling(n) &&
+ sibling(n)->color == BLACK &&
+ (sibling(n)->left == 0 || sibling(n)->left->color == BLACK) &&
+ (sibling(n)->right == 0 || sibling(n)->right->color == BLACK))
+ {
+ sibling(n)->color = RED;
+ delete_case1(n->parent);
+ } else
+ delete_case4(n);
+ }
+ void delete_case4(N *n) {
+ if (n->parent->color == RED &&
+ sibling(n) &&
+ sibling(n)->color == BLACK &&
+ (sibling(n)->left == 0 || sibling(n)->left->color == BLACK) &&
+ (sibling(n)->right == 0 || sibling(n)->right->color == BLACK))
+ {
+ sibling(n)->color = RED;
+ n->parent->color = BLACK;
+ } else
+ delete_case5(n);
+ }
+ void delete_case5(N *n) {
+ if (n == n->parent->left &&
+ sibling(n) &&
+ sibling(n)->color == BLACK &&
+ sibling(n)->left &&
+ sibling(n)->left->color == RED &&
+ (sibling(n)->right == 0 || sibling(n)->right->color == BLACK))
+ {
+ sibling(n)->color = RED;
+ sibling(n)->left->color = BLACK;
+ rotate_right(sibling(n));
+ } else if (n == n->parent->right &&
+ sibling(n) &&
+ sibling(n)->color == BLACK &&
+ sibling(n)->right &&
+ sibling(n)->right->color == RED &&
+ (sibling(n)->left == 0 || sibling(n)->left->color == BLACK))
+ {
+ sibling(n)->color = RED;
+ sibling(n)->right->color = BLACK;
+ rotate_left(sibling(n));
+ }
+ delete_case6(n);
+ }
+ void delete_case6(N *n) {
+ sibling(n)->color = n->parent->color;
+ n->parent->color = BLACK;
+ if (n == n->parent->left) {
+ /* Here, sibling(n)->right->color == RED */
+ sibling(n)->right->color = BLACK;
+ rotate_left(n->parent);
+ } else {
+ /* Here, sibling(n)->left->color == RED */
+ sibling(n)->left->color = BLACK;
+ rotate_right(n->parent);
+ }
+ }
+
+ N *get_predecessor(N *n) {
+ N *minmax = n->left;
+ while(minmax->right) minmax = minmax->right;
+ return minmax;
+ }
+
+ virtual void insert_node(N *n) {
+ BinaryTree<T, N>::insert_node(n);
+ n->color = RED;
+
+ insert_case1(n);
+ }
+
+ virtual void delete_node(N *n) {
+ if(n->left && n->right) {
+ N *predecessor = get_predecessor(n);
+ n->val = predecessor->val;
+ delete_case0(predecessor);
+ } else
+ delete_case0(n);
+ }
+
+public:
+ RedBlackTree(): BinaryTree< T, N >() {}
+ virtual ~RedBlackTree() {}
+};
+
template<class A, class B> class Pair {
public:
A first;
@@ -509,7 +760,7 @@ public:
Pair(const A &f): first(f) {}
Pair(const A &f, const B &s): first(f), second(s) {}
- Pair(Pair<A,B> &other): first(other.first), second(other.second) {}
+ Pair(const Pair<A,B> &other): first(other.first), second(other.second) {}
virtual ~Pair() {}
const bool operator<(const Pair<A,B> &other) const {return first < other.first;}
@@ -517,11 +768,12 @@ public:
Pair<A,B> &operator=(const Pair<A,B> &other) {first = other.first; second = other.second; return *this;}
};
-template<class A, class B> class Map: public BinaryTree< Pair< A, B > > {
+//template<class A, class B, class N = TreeNode<Pair<A, B> > > class Map: public BinaryTree< Pair< A, B >, N > {
+template<class A, class B, class N = ColouredTreeNode<Pair<A, B> > > class Map: public RedBlackTree< Pair< A, B >, N > {
protected:
- TreeNode<Pair< A, B > > *find(A &key) const {
- TreeNode<Pair< A, B > > *n = BinaryTree< Pair< A, B > >::root;
+ N *find(A &key) const {
+ N *n = root;
while(n) {
if(n->val.first == key)
return n;
@@ -534,7 +786,8 @@ protected:
return 0;
}
public:
- Map(): BinaryTree< Pair<A,B> >() {}
+ //Map(): BinaryTree< Pair<A,B>, N >() {}
+ Map(): RedBlackTree< Pair<A,B>, N >() {}
virtual ~Map() {}
void put(A &key, B &value) {
@@ -542,7 +795,7 @@ public:
}
const bool get(A &key, B &val) const {
- const TreeNode<Pair< A, B > > *n = find(key);
+ const N *n = find(key);
if(n) {
val = n->val.second;
return true;
@@ -551,19 +804,19 @@ public:
}
B &operator[](A &key) {
- TreeNode<Pair< A, B > > *n = find(key);
+ N *n = find(key);
if(n)
return n->val.second;
else {
Pair< A, B > p(key);
- TreeNode<Pair< A, B > > *n = new TreeNode<Pair< A, B > >(p, 0);
+ N *n = new N(p, 0);
insert_node(n);
return n->val.second;
}
}
virtual const bool exists(A &key) const {
- const TreeNode<Pair< A, B > > *n = find(key);
+ const N *n = find(key);
if(n) {
return true;
} else
@@ -571,7 +824,7 @@ public:
}
virtual const bool remove(A &key) {
- TreeNode<Pair< A, B > > *n = find(key);
+ N *n = find(key);
if(n) {
delete_node(n);
return true;
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-08 13:16:16 +0000