diff options
Diffstat (limited to 'plugins/ping/collection.h')
| -rw-r--r-- | plugins/ping/collection.h | 834 |
1 files changed, 0 insertions, 834 deletions
diff --git a/plugins/ping/collection.h b/plugins/ping/collection.h deleted file mode 100644 index f8709e3ef8..0000000000 --- a/plugins/ping/collection.h +++ /dev/null @@ -1,834 +0,0 @@ -#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;
- }
-};
|