diff options
Diffstat (limited to 'font_service/collection.h')
| -rw-r--r-- | font_service/collection.h | 87 |
1 files changed, 61 insertions, 26 deletions
diff --git a/font_service/collection.h b/font_service/collection.h index 66dd850..2c69216 100644 --- a/font_service/collection.h +++ b/font_service/collection.h @@ -1,3 +1,5 @@ +#include <malloc.h>
+
template<class T> class Collection {
protected:
unsigned long count;
@@ -111,13 +113,21 @@ public: 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(T val) {
add_front(val);
}
@@ -174,10 +184,13 @@ public: Collection<T>::count = 0;
limit = initial;
if(limit) ar = (T *)realloc(ar, limit * sizeof(T));
- else free(ar);
+ else {
+ free(ar);
+ ar = 0;
+ }
}
- virtual Iterator start() {return Iterator(ar, Collection<T>::count, 0);}
+ virtual Iterator start() const {return Iterator(ar, Collection<T>::count, 0);}
virtual void add(T &val) {
if(Collection<T>::count == limit) {
@@ -188,6 +201,12 @@ public: ar[Collection<T>::count++] = val;
}
+ virtual void add_all(DynamicArray<T> &other) {
+ for(DynamicArray<T>::Iterator i = other.start(); i.has_val(); i.next()) {
+ add(i.val());
+ }
+ }
+
virtual const bool remove(T &val) {
for(unsigned long i = 0; i < Collection<T>::count; i++) {
if(ar[i] == val) {
@@ -227,7 +246,7 @@ public: return ar[index];
}
- const bool index_of(const T &val, unsigned long &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;
@@ -237,6 +256,15 @@ public: 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) {
@@ -293,7 +321,7 @@ public: virtual ~TreeNode() {
if(parent) {
if(parent->left == this) parent->left = 0;
- else parent->right = 0;
+ if(parent->right == this)parent->right = 0;
}
}
};
@@ -305,27 +333,21 @@ protected: 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;
- //}
+ TreeNode<T> *minmax = n->left;
+ while(minmax->right) minmax = minmax->right;
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;
+ 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;
+ if(n->parent->left == n) n->parent->left = n->left;
else n->parent->right = n->left;
} else
root = n->left;
@@ -359,6 +381,7 @@ protected: } else
root = n;
+ Collection<T>::count++;
}
public:
@@ -441,7 +464,6 @@ public: void add(T &val) {
TreeNode<T> *n = new TreeNode<T>(val, 0);
insert_node(n);
- Collection<T>::count++;
}
const bool remove(T &val) {
@@ -463,7 +485,21 @@ public: return false;
}
- Iterator start() {return Iterator(root);}
+ const bool contains(T &val) const {
+ TreeNode<T> *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);}
};
template<class A, class B> class Pair {
@@ -484,12 +520,12 @@ public: template<class A, class B> class Map: public BinaryTree< Pair< A, B > > {
protected:
- TreeNode<Pair< A, B > > *find(A &val) {
+ TreeNode<Pair< A, B > > *find(A &key) const {
TreeNode<Pair< A, B > > *n = BinaryTree< Pair< A, B > >::root;
while(n) {
- if(n->val.first == val)
+ if(n->val.first == key)
return n;
- else if(val < n->val.first)
+ else if(key < n->val.first)
n = n->left;
else
n = n->right;
@@ -522,12 +558,11 @@ public: 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 {
+ virtual const bool exists(A &key) const {
const TreeNode<Pair< A, B > > *n = find(key);
if(n) {
return true;
@@ -535,7 +570,7 @@ public: return false;
}
- const bool remove(A &key) {
+ virtual const bool remove(A &key) {
TreeNode<Pair< A, B > > *n = find(key);
if(n) {
delete_node(n);
|