diff options
Diffstat (limited to 'MySpace/collection.h')
| -rw-r--r-- | MySpace/collection.h | 546 |
1 files changed, 546 insertions, 0 deletions
diff --git a/MySpace/collection.h b/MySpace/collection.h new file mode 100644 index 0000000..e02cedf --- /dev/null +++ b/MySpace/collection.h @@ -0,0 +1,546 @@ +template<class T> class Collection {
+protected:
+ unsigned long count;
+public:
+ Collection(): count(0) {}
+
+ virtual void clear() = 0;
+ virtual void add(T &val) = 0;
+ virtual const bool remove(T &val) = 0;
+
+ const unsigned long size() const {return count;}
+};
+
+template<class T> class Node {
+public:
+ T val;
+
+ Node(T &v): val(v) {}
+ virtual ~Node() {}
+};
+
+template<class T> class ListNode: public Node<T> {
+public:
+ ListNode<T> *next, *prev;
+
+ ListNode(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(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(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;
+ }
+
+ // queue/stack functions
+ // stack - use push/pop
+ // queue - use push_back/pop
+ virtual void push(T &val) {
+ add_front(val);
+ }
+
+ 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);
+ }
+
+ virtual Iterator start() {return Iterator(ar, Collection<T>::count, 0);}
+
+ virtual void add(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 const bool remove(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(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) {
+ for(int i = 0; i < Collection<T>::count; i++) {
+ if(ar[index] == val) {
+ index = i;
+ return true;
+ }
+ }
+ return false;
+ }
+
+ // 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(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(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(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(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;
+ else parent->right = 0;
+ }
+ }
+};
+
+template<class T> class BinaryTree: public Collection<T> {
+protected:
+
+ TreeNode<T> *root;
+
+ TreeNode<T> *delete_node(TreeNode<T> *n) {
+ if(n->left && n->right) {
+ //if(rand() & 1) { // ?
+ TreeNode<T> *minmax = n->left;
+ while(minmax->right) minmax = minmax->right;
+ //} else {
+ // Node *minmax = current->right;
+ // while(minmax->left) minmax = minmax->left;
+ //}
+ n->val = minmax->val;
+ delete_node(minmax);
+ Collection<T>::count--;
+ return n;
+ } 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--;
+ return 0;
+ }
+
+ void insert_node(TreeNode<T> *n) {
+ TreeNode<T> *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;
+ n->parent = parent;
+ } else {
+ parent->right = n;
+ n->parent = parent;
+ }
+ } else
+ root = n;
+
+ }
+
+public:
+ class Iterator {
+ friend class BinaryTree<T>;
+ protected:
+
+ class EvalNode {
+ public:
+ bool evaluate;
+ TreeNode<T> *node;
+
+ EvalNode(): evaluate(false), node(0) {}
+ EvalNode(const bool eval, TreeNode<T> *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;
+ LinkedList<EvalNode> stack;
+
+
+ Iterator(TreeNode<T> *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() {
+ TreeNode<T> *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(T &val) {
+ TreeNode<T> *n = new TreeNode<T>(val, 0);
+ insert_node(n);
+ Collection<T>::count++;
+ }
+
+ const bool remove(T &val) {
+ TreeNode<T> *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;
+ }
+
+ Iterator start() {return Iterator(root);}
+};
+
+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(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 Map: public BinaryTree< Pair< A, B > > {
+protected:
+
+ const TreeNode<Pair< A, B > > *find(A &val) const {
+ TreeNode<Pair< A, B > > *n = BinaryTree< Pair< A, B > >::root;
+ while(n) {
+ if(n->val.first == val)
+ return n;
+ else if(val < n->val.first)
+ n = n->left;
+ else
+ n = n->right;
+
+ }
+ return 0;
+ }
+public:
+ Map(): BinaryTree< Pair<A,B> >() {}
+ virtual ~Map() {}
+
+ void put(A &key, B &value) {
+ add(Pair<A,B>(key, value));
+ }
+
+ const bool get(A &key, B &val) const {
+ const TreeNode<Pair< A, B > > *n = find(key);
+ if(n) {
+ val = n->val.second;
+ return true;
+ } else
+ return false;
+ }
+
+ B &operator[](A &key) {
+ TreeNode<Pair< A, B > > *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);
+ insert_node(n);
+ Collection< Pair< A, B > >::count++;
+ return n->val.second;
+ }
+ }
+
+ const bool exists(A &key) const {
+ const TreeNode<Pair< A, B > > *n = find(key);
+ if(n) {
+ return true;
+ } else
+ return false;
+ }
+
+ const bool remove(A &key) {
+ TreeNode<Pair< A, B > > *n = find(key);
+ if(n) {
+ delete_node(n);
+ return true;
+ } else
+ return false;
+ }
+};
|