From c33fc11c302b8a477acb6770ee2b187d822629a5 Mon Sep 17 00:00:00 2001
From: sje <sje@4f64403b-2f21-0410-a795-97e2b3489a10>
Date: Tue, 30 Oct 2007 05:10:11 +0000
Subject: fix collection.h to build under mingw

git-svn-id: https://server.scottellis.com.au/svn/mim_plugs@375 4f64403b-2f21-0410-a795-97e2b3489a10
---
 message_notify/collection.h | 834 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 834 insertions(+)
 create mode 100644 message_notify/collection.h

(limited to 'message_notify/collection.h')

diff --git a/message_notify/collection.h b/message_notify/collection.h
new file mode 100644
index 0000000..f8709e3
--- /dev/null
+++ b/message_notify/collection.h
@@ -0,0 +1,834 @@
+#include <malloc.h>
+
+template<class T> class Collection {
+protected:
+	unsigned long count;
+public:
+	Collection(): count(0) {}
+
+	virtual void clear() = 0;
+	virtual void add(const T &val) = 0;
+	virtual const bool remove(const T &val) = 0;
+
+	const unsigned long size() const {return count;}
+};
+
+template<class T> class Node {
+public:
+	T val;
+
+	Node(const T &v): val(v) {}
+	virtual ~Node() {}
+};
+
+template<class T> class ListNode: public Node<T> {
+public:
+	ListNode<T> *next, *prev;
+
+	ListNode(const T &v): Node<T>(v), next(0), prev(0) {}
+	virtual ~ListNode() {
+		if(next) next->prev = prev;
+		if(prev) prev->next = next;			
+	}
+};
+
+template<class T> class LinkedList: public Collection<T> {
+protected:
+	ListNode<T> *head, *tail;
+
+public:
+	class Iterator {
+		friend class LinkedList<T>;
+	protected:
+		ListNode<T> *n;
+		Iterator(ListNode<T> *start): n(start) {}
+	public:
+		Iterator(const Iterator &other): n(other.n) {}
+
+		virtual T &val() {return n->val;}
+		virtual void next() {if(n) n = n->next;}
+		virtual void prev() {if(n) n = n->prev;}
+		virtual const bool has_val() {return (n ? true : false); }
+	};
+
+	LinkedList(): Collection<T>(), head(0), tail(0) {};
+	LinkedList(const LinkedList<T> &other): Collection<T>(), head(0), tail(0) {
+		for(Iterator i = other.start(); i.has_val(); i.next())
+			add(i.val());
+	}
+	virtual ~LinkedList() {clear();}
+
+	LinkedList<T> &operator=(const LinkedList<T> &other) {
+		clear();
+		for(Iterator i = other.start(); i.has_val(); i.next())
+			add(i.val());
+		return *this;
+	}
+
+	virtual void clear() {
+		ListNode<T> *n;
+		while(head) {
+			n = head;
+			head = head->next;
+			delete n;
+		}
+		tail = 0;
+		Collection<T>::count = 0;
+	}
+
+	virtual Iterator start() const {return Iterator(head);}
+
+	virtual void add_front(T &val) {
+		ListNode<T> *n = new ListNode<T>(val);
+		n->next = head;
+		if(head) head->prev = n;
+		head = n;
+		if(!tail) tail = n;
+		Collection<T>::count++;
+	}
+
+	virtual void add(const T &val) {
+		ListNode<T> *n = new ListNode<T>(val);
+		n->prev = tail;
+		if(tail) tail->next = n;
+		tail = n;
+		if(!head) head = n;
+		Collection<T>::count++;
+	}
+
+	virtual const bool remove(const T &val) {
+		ListNode<T> *n = head;
+		while(n) {
+			if(n->val == val) {
+				if(n == head) head = head->next;
+				if(n == tail) tail = tail->prev;
+				
+				delete n;
+				Collection<T>::count--;
+				return true;
+			} else
+				n = n->next;
+		}
+
+		return false;
+	}
+
+	virtual const bool contains(T &val) const {
+		ListNode<T> *n = head;
+		while(n) {
+			if(n->val == val) {
+				return true;
+			} else
+				n = n->next;
+		}
+
+		return false;
+	}
+
+	// queue/stack functions
+	// stack - use push/pop
+	// queue - use push_back/pop
+	virtual void push(T val) {
+		add_front(val);
+	}
+
+	virtual void push_back(T &val) {
+		add(val);
+	}
+
+	virtual const bool pop(T &val) {
+		if(!head) return false;
+
+		ListNode<T> *n = head;
+		if(head) {
+			head = head->next;
+			if(n == tail) tail = 0;
+			val = n->val;
+			delete n;
+			Collection<T>::count--;
+			return true;
+		} else
+			return false;
+	}
+};
+
+template<class T> class DynamicArray: public Collection<T> {
+protected:
+	T *ar;
+
+	unsigned long initial, limit, increment;
+
+public:
+	class Iterator {
+		friend class DynamicArray<T>;
+	protected:
+		T *ar;
+		unsigned long count;
+		unsigned long pos;
+		Iterator(T *a, const int c, unsigned long p): ar(a), count(c), pos(p) {}
+	public:
+		Iterator(const Iterator &other): ar(other.ar), count(other.count), pos(other.pos) {}
+
+		virtual T &val() {return ar[pos];}
+		virtual void next() {pos++;}
+		virtual void prev() {pos--;}
+		virtual const bool has_val() {return pos < count; }
+	};
+
+	DynamicArray(unsigned long init = 0, unsigned long inc = 1): Collection<T>(), ar(0), initial(init), limit(init), increment(inc) {
+		if(limit) ar = (T *)malloc(limit * sizeof(T));
+	}
+	virtual ~DynamicArray() {if(ar) free(ar);}
+
+	virtual void clear() {
+		Collection<T>::count = 0;
+		limit = initial;
+		if(limit) ar = (T *)realloc(ar, limit * sizeof(T));
+		else {
+			free(ar);
+			ar = 0;
+		}
+	}
+
+	virtual Iterator start() const {return Iterator(ar, Collection<T>::count, 0);}
+
+	virtual void add(const T &val) {
+		if(Collection<T>::count == limit) {
+			limit += increment;
+			ar = (T *)realloc(ar, limit * sizeof(T));
+			ar[Collection<T>::count++] = val;
+		} else
+			ar[Collection<T>::count++] = val;
+	}
+
+	virtual void add_all(DynamicArray<T> &other) {
+		for(Iterator i = other.start(); i.has_val(); i.next()) {
+			add(i.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));
+				Collection<T>::count--;
+				return true;
+			}
+		}
+		return false;
+	}
+
+	virtual const bool remove(const unsigned long index) {
+		if(index >= Collection<T>::count) return false;
+
+		memmove(ar + index, ar + index + 1, (Collection<T>::count - index) * sizeof(T));
+		Collection<T>::count--;
+		return true;
+	}
+
+	virtual const bool insert(const T &val, const unsigned long index) {
+		if(index > Collection<T>::count) return false;
+
+		if(Collection<T>::count == limit) {
+			limit += increment;
+			ar = (T *)realloc(ar, limit * sizeof(T));
+		}
+
+		if(index < Collection<T>::count)
+			memmove(ar + index + 1, ar + index, (Collection<T>::count - index) * sizeof(T));
+		
+		ar[index] = val;
+		Collection<T>::count++;
+		return true;
+	}
+
+	virtual T &operator[](const int index) {
+		return ar[index];
+	}
+
+	const bool index_of(const T &val, unsigned long &index) const {
+		for(int i = 0; i < Collection<T>::count; i++) {
+			if(ar[index] == val) {
+				index = i;
+				return true;
+			}
+		}
+		return false;
+	}
+
+	const int index_of(const T &val) const {
+		for(int i = 0; i < Collection<T>::count; i++) {
+			if(ar[i] == val) {
+				return i;
+			}
+		}
+		return -1;
+	}
+
+	// stack functions
+	virtual const bool pop(T &val) {
+		if(Collection<T>::count) {
+			val = ar[Collection<T>::count -1];
+			remove(Collection<T>::count -1);
+			return true;
+		}
+		return false;
+	}
+
+	virtual void push(const T &val) {
+		add(val);
+	}
+};
+
+template<class T> class SortedDynamicArray: public DynamicArray<T> {
+public:
+	SortedDynamicArray(unsigned long init = 0, unsigned long inc = 1): DynamicArray<T>(init, inc) {}
+	virtual ~SortedDynamicArray() {}
+
+	const bool get_index(const T &val, unsigned long &index) {
+		unsigned long low  = 0;
+		unsigned long high = Collection<T>::count-1;
+
+		while( high < Collection<T>::count && low <= high )
+		{  
+			unsigned long i = ( low+high )/2;
+			if ( DynamicArray<T>::ar[i] == val )
+			{	index = i;
+				return true;
+			} else 
+				if (DynamicArray<T>::ar[i] < val)
+					low = i+1;
+				else
+					high = i-1;
+		}
+
+		index = low;
+		return false;
+	}
+
+	virtual void add(const T &val) {
+		unsigned long index;
+		get_index(val, index);
+		insert(val, index);
+	}
+};
+
+template<class T> class TreeNode: public Node<T> {
+public:
+	TreeNode<T> *parent, *left, *right;
+
+	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;
+			if(parent->right == this)parent->right = 0;
+		}
+	}
+};
+
+template<class T, class N = TreeNode<T> > class BinaryTree: public Collection<T> {
+protected:
+
+	N *root;
+
+	virtual void delete_node(N *n) {
+		if(n->left && n->right) {
+			N *minmax = n->left;
+			while(minmax->right) minmax = minmax->right;
+			n->val = minmax->val;
+			delete_node(minmax);
+			return;
+		} else if(n->right) {
+			if(n->parent) {
+				if(n->parent->left == n) n->parent->left = n->right;
+				else n->parent->right = n->right;
+			} else
+				root = n->right;
+			n->right->parent = n->parent;
+		} else if(n->left) {
+			if(n->parent) {
+				if(n->parent->left == n)	n->parent->left = n->left;
+				else n->parent->right = n->left;
+			} else
+				root = n->left;
+			n->left->parent = n->parent;
+		} else {
+			if(n == root) root = 0;
+		}
+		delete n;
+		Collection<T>::count--;
+	}
+
+	virtual void insert_node(N *n) {
+		N *current = root, *parent = 0;
+		while(current) {
+			parent = current;
+			if(n->val < current->val)
+				current = current->left;
+			else
+				current = current->right;
+		}
+
+		if(parent) {
+			if(n->val < parent->val) {
+				parent->left = n;
+			} else {
+				parent->right = n;
+			}
+		} else
+			root = n;
+
+		n->parent = parent;
+		Collection<T>::count++;
+	}
+
+public:
+	class Iterator {
+		friend class BinaryTree<T, N>;
+	protected:
+
+		class EvalNode {
+		public:
+			bool evaluate;
+			N *node;
+
+			EvalNode(): evaluate(false), node(0) {}
+			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;}
+
+		};
+
+		N *n;
+		LinkedList<EvalNode> stack;
+
+		
+		Iterator(N *start): n(0) {
+			if(start) {
+				stack.push(EvalNode(true, start));
+				next();
+			}
+		}
+
+	public:
+		Iterator(const Iterator &other):n(other.n), stack(other.stack)  {}
+		virtual ~Iterator() {}
+
+		virtual T &val() {return n->val;}
+		virtual void next() {
+			EvalNode en;
+			bool popped = false;
+			while((popped = stack.pop(en)) && en.evaluate) {
+				if(en.node->right) stack.push(EvalNode(true, en.node->right));
+				stack.push(EvalNode(false, en.node));
+				if(en.node->left) stack.push(EvalNode(true, en.node->left));
+			}
+			
+			n = (popped ? en.node : 0);
+		}
+		virtual const bool has_val() {return (n ? true : false);}
+	};
+
+	BinaryTree(): Collection<T>(), root(0) {};
+	BinaryTree(BinaryTree<T> &other): Collection<T>(), root(0) {
+		for(Iterator i = other.start(); i.has_val(); i.next())
+			add(i.val());
+	}
+	virtual ~BinaryTree() {clear();}
+
+	BinaryTree &operator=(BinaryTree<T> &other) {
+		clear();
+		for(Iterator i = other.start(); i.has_val(); i.next())
+			add(i.val());
+		return *this;
+	}
+
+	virtual void clear() {
+		N *current = root, *parent = 0;
+		while(current) {
+			if(current->left) current = current->left;
+			else if(current->right) current = current->right;
+			else {
+				parent = current->parent;
+				delete current;
+				current = parent;
+			}
+		}
+
+		root = 0;
+		Collection<T>::count = 0;
+	}
+
+	void add(const T &val) {
+		N *n = new N(val, 0);
+		insert_node(n);
+	}
+
+	const bool remove(const T &val) {
+		N *current = root;
+		while(current) {
+			if(current->val == val)
+				break;
+			else if(val < current->val)
+				current = current->left;
+			else 
+				current = current->right;
+		}
+
+		if(current) {
+			delete_node(current);
+			return true;
+		}
+
+		return false;
+	}
+
+	const bool contains(const T &val) const {
+		N *current = root;
+		while(current) {
+			if(current->val == val)
+				break;
+			else if(val < current->val)
+				current = current->left;
+			else 
+				current = current->right;
+		}
+
+		return current != 0;
+	}
+
+	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
+			BinaryTree<T, N>::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
+			BinaryTree<T, N>::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
+			BinaryTree<T, N>::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(BinaryTree<T, N>::root == n) BinaryTree<T, 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;
+	B second;
+
+	Pair(const A &f): first(f) {}
+	Pair(const A &f, const B &s): first(f), second(s) {}
+	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;}
+	const bool operator==(const Pair<A,B> &other) const {return first == other.first;}
+	Pair<A,B> &operator=(const Pair<A,B> &other) {first = other.first; second = other.second; return *this;}
+};
+
+//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:
+	
+	N *find(A &key) const {
+		N *n = RedBlackTree< Pair< A, B >, N >::root;
+		while(n) {
+			if(n->val.first == key)
+				return n;
+			else if(key < n->val.first)
+				n = n->left;
+			else
+				n = n->right;
+
+		}
+		return 0;
+	}
+public:
+	//Map(): BinaryTree< Pair<A,B>, N >() {}
+	Map(): RedBlackTree< Pair<A,B>, N >() {}
+	virtual ~Map() {}
+
+	void put(A &key, B &value) {
+		add(Pair<A,B>(key, value));
+	}
+
+	const bool get(A &key, B &val) const {
+		const N *n = find(key);
+		if(n) {
+			val = n->val.second;
+			return true;
+		} else
+			return false;
+	}
+
+	B &operator[](A &key) {
+		N *n = find(key);
+		if(n)
+			return n->val.second;
+		else {
+			Pair< A, B > p(key);
+			N *n = new N(p, 0);
+			insert_node(n);
+			return n->val.second;
+		}
+	}
+
+	virtual const bool exists(A &key) const {
+		const N *n = find(key);
+		if(n) {
+			return true;
+		} else
+			return false;
+	}
+
+	virtual const bool remove(A &key) {
+		N *n = find(key);
+		if(n) {
+			delete_node(n);
+			return true;
+		} else
+			return false;
+	}
+};
-- 
cgit v1.2.3