From 573e3c67a9f113b2bd101c669b1b86615356fc13 Mon Sep 17 00:00:00 2001 From: sje Date: Thu, 4 Oct 2007 05:12:22 +0000 Subject: fix to binary tree delete...again! git-svn-id: https://server.scottellis.com.au/svn/mim_plugs@352 4f64403b-2f21-0410-a795-97e2b3489a10 --- MySpace/collection.h | 83 +++++++++++++++++++++++++++---------- font_service/collection.h | 87 +++++++++++++++++++++++++++------------ meta2/collection.h | 8 ++-- meta2/version.h | 2 +- ping/collection.h | 102 +++++++++++++++++++++++++++++++--------------- 5 files changed, 195 insertions(+), 87 deletions(-) diff --git a/MySpace/collection.h b/MySpace/collection.h index 6daccfb..2c69216 100644 --- a/MySpace/collection.h +++ b/MySpace/collection.h @@ -1,3 +1,5 @@ +#include + template class Collection { protected: unsigned long count; @@ -111,6 +113,18 @@ public: return false; } + virtual const bool contains(T &val) const { + ListNode *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 @@ -170,10 +184,13 @@ public: Collection::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::count, 0);} + virtual Iterator start() const {return Iterator(ar, Collection::count, 0);} virtual void add(T &val) { if(Collection::count == limit) { @@ -184,6 +201,12 @@ public: ar[Collection::count++] = val; } + virtual void add_all(DynamicArray &other) { + for(DynamicArray::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::count; i++) { if(ar[i] == val) { @@ -223,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::count; i++) { if(ar[index] == val) { index = i; @@ -233,6 +256,15 @@ public: return false; } + const int index_of(const T &val) const { + for(int i = 0; i < Collection::count; i++) { + if(ar[i] == val) { + return i; + } + } + return -1; + } + // stack functions virtual const bool pop(T &val) { if(Collection::count) { @@ -289,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; } } }; @@ -301,27 +333,21 @@ protected: TreeNode *delete_node(TreeNode *n) { if(n->left && n->right) { - //if(rand() & 1) { // ? - TreeNode *minmax = n->left; - while(minmax->right) minmax = minmax->right; - //} else { - // Node *minmax = current->right; - // while(minmax->left) minmax = minmax->left; - //} + TreeNode *minmax = n->left; + while(minmax->right) minmax = minmax->right; n->val = minmax->val; delete_node(minmax); - Collection::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; @@ -355,6 +381,7 @@ protected: } else root = n; + Collection::count++; } public: @@ -437,7 +464,6 @@ public: void add(T &val) { TreeNode *n = new TreeNode(val, 0); insert_node(n); - Collection::count++; } const bool remove(T &val) { @@ -459,7 +485,21 @@ public: return false; } - Iterator start() {return Iterator(root);} + const bool contains(T &val) const { + TreeNode *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 Pair { @@ -480,12 +520,12 @@ public: template class Map: public BinaryTree< Pair< A, B > > { protected: - const TreeNode > *find(A &val) const { + TreeNode > *find(A &key) const { TreeNode > *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; @@ -518,12 +558,11 @@ public: Pair< A, B > p(key); TreeNode > *n = new TreeNode >(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 > *n = find(key); if(n) { return true; @@ -531,7 +570,7 @@ public: return false; } - const bool remove(A &key) { + virtual const bool remove(A &key) { TreeNode > *n = find(key); if(n) { delete_node(n); 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 + template class Collection { protected: unsigned long count; @@ -111,13 +113,21 @@ public: return false; } + virtual const bool contains(T &val) const { + ListNode *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::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::count, 0);} + virtual Iterator start() const {return Iterator(ar, Collection::count, 0);} virtual void add(T &val) { if(Collection::count == limit) { @@ -188,6 +201,12 @@ public: ar[Collection::count++] = val; } + virtual void add_all(DynamicArray &other) { + for(DynamicArray::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::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::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::count; i++) { + if(ar[i] == val) { + return i; + } + } + return -1; + } + // stack functions virtual const bool pop(T &val) { if(Collection::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 *delete_node(TreeNode *n) { if(n->left && n->right) { - //if(rand() & 1) { // ? - TreeNode *minmax = n->left; - while(minmax->right) minmax = minmax->right; - //} else { - // Node *minmax = current->right; - // while(minmax->left) minmax = minmax->left; - //} + TreeNode *minmax = n->left; + while(minmax->right) minmax = minmax->right; n->val = minmax->val; delete_node(minmax); - Collection::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::count++; } public: @@ -441,7 +464,6 @@ public: void add(T &val) { TreeNode *n = new TreeNode(val, 0); insert_node(n); - Collection::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 *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 Pair { @@ -484,12 +520,12 @@ public: template class Map: public BinaryTree< Pair< A, B > > { protected: - TreeNode > *find(A &val) { + TreeNode > *find(A &key) const { TreeNode > *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 > *n = new TreeNode >(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 > *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 > *n = find(key); if(n) { delete_node(n); diff --git a/meta2/collection.h b/meta2/collection.h index 9067158..2c69216 100644 --- a/meta2/collection.h +++ b/meta2/collection.h @@ -321,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; } } }; @@ -340,20 +340,18 @@ protected: 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; - n->parent = 0; // don't mess with pointers } 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; n->left->parent = n->parent; - n->parent = 0; // don't mess with pointers } else { if(n == root) root = 0; } diff --git a/meta2/version.h b/meta2/version.h index f8e3ee7..3c62707 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 6 +#define __BUILD_NUM 7 #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 8073c21..2c69216 100644 --- a/ping/collection.h +++ b/ping/collection.h @@ -1,3 +1,5 @@ +#include + template class Collection { protected: unsigned long count; @@ -111,13 +113,21 @@ public: return false; } + virtual const bool contains(T &val) const { + ListNode *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); } @@ -146,15 +156,15 @@ template class DynamicArray: public Collection { protected: T *ar; - unsigned long initial, increment, limit; + unsigned long initial, limit, increment; public: class Iterator { friend class DynamicArray; protected: T *ar; - unsigned long pos; 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) {} @@ -168,16 +178,19 @@ public: DynamicArray(unsigned long init = 0, unsigned long inc = 1): Collection(), ar(0), initial(init), limit(init), increment(inc) { if(limit) ar = (T *)malloc(limit * sizeof(T)); } - virtual ~DynamicArray() {free(ar);} + virtual ~DynamicArray() {if(ar) free(ar);} virtual void clear() { Collection::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::count, 0);} + virtual Iterator start() const {return Iterator(ar, Collection::count, 0);} virtual void add(T &val) { if(Collection::count == limit) { @@ -188,6 +201,12 @@ public: ar[Collection::count++] = val; } + virtual void add_all(DynamicArray &other) { + for(DynamicArray::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::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::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::count; i++) { + if(ar[i] == val) { + return i; + } + } + return -1; + } + // stack functions virtual const bool pop(T &val) { if(Collection::count) { @@ -267,10 +295,11 @@ public: if ( DynamicArray::ar[i] == val ) { index = i; return true; - } else if (DynamicArray::ar[i] < val) - low = i+1; - else - high = i-1; + } else + if (DynamicArray::ar[i] < val) + low = i+1; + else + high = i-1; } index = low; @@ -292,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; } } }; @@ -304,27 +333,21 @@ protected: TreeNode *delete_node(TreeNode *n) { if(n->left && n->right) { - //if(rand() & 1) { // ? - TreeNode *minmax = n->left; - while(minmax->right) minmax = minmax->right; - //} else { - // Node *minmax = current->right; - // while(minmax->left) minmax = minmax->left; - //} + TreeNode *minmax = n->left; + while(minmax->right) minmax = minmax->right; n->val = minmax->val; delete_node(minmax); - Collection::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; @@ -358,6 +381,7 @@ protected: } else root = n; + Collection::count++; } public: @@ -440,7 +464,6 @@ public: void add(T &val) { TreeNode *n = new TreeNode(val, 0); insert_node(n); - Collection::count++; } const bool remove(T &val) { @@ -462,7 +485,21 @@ public: return false; } - Iterator start() {return Iterator(root);} + const bool contains(T &val) const { + TreeNode *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 Pair { @@ -483,12 +520,12 @@ public: template class Map: public BinaryTree< Pair< A, B > > { protected: - TreeNode > *find(A &val) { + TreeNode > *find(A &key) const { TreeNode > *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; @@ -521,12 +558,11 @@ public: Pair< A, B > p(key); TreeNode > *n = new TreeNode >(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 > *n = find(key); if(n) { return true; @@ -534,7 +570,7 @@ public: return false; } - const bool remove(A &key) { + virtual const bool remove(A &key) { TreeNode > *n = find(key); if(n) { delete_node(n); -- cgit v1.2.3