From 98fe0e7056e6697396249531785d3899f94d79be Mon Sep 17 00:00:00 2001 From: David Robillard Date: Sat, 10 Jun 2006 01:52:02 +0000 Subject: More juggling git-svn-id: http://svn.drobilla.net/lad/grauph@15 a436a847-0d15-0410-975c-d299462d15a1 --- src/libs/engine/TreeImplementation.h | 410 +++++++++++++++++++++++++++++++++++ 1 file changed, 410 insertions(+) create mode 100644 src/libs/engine/TreeImplementation.h (limited to 'src/libs/engine/TreeImplementation.h') diff --git a/src/libs/engine/TreeImplementation.h b/src/libs/engine/TreeImplementation.h new file mode 100644 index 00000000..a61ec407 --- /dev/null +++ b/src/libs/engine/TreeImplementation.h @@ -0,0 +1,410 @@ +/* This file is part of Om. Copyright (C) 2006 Dave Robillard. + * + * Om is free software; you can redistribute it and/or modify it under the + * terms of the GNU General Public License as published by the Free Software + * Foundation; either version 2 of the License, or (at your option) any later + * version. + * + * Om is distributed in the hope that it will be useful, but WITHOUT ANY + * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS + * FOR A PARTICULAR PURPOSE. See the GNU General Public License for details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include "Tree.h" +#include +#include +#include +using std::cerr; using std::endl; + + +/* FIXME: this is all in horrible need of a rewrite. */ + + +/** Destroy the tree. + * + * Note that this does not delete any TreeNodes still inside the tree, + * that is the user's responsibility. + */ +template +Tree::~Tree() +{ +} + + +/** Insert a node into the tree. Realtime safe. + * + * @a n will be inserted using the key() field for searches. + * n->key() must not be the empty string. + */ +template +void +Tree::insert(TreeNode* const n) +{ + assert(n != NULL); + assert(n->left_child() == NULL); + assert(n->right_child() == NULL); + assert(n->parent() == NULL); + assert(n->key().length() > 0); + assert(find_treenode(n->key()) == NULL); + + if (m_root == NULL) { + m_root = n; + } else { + bool left = false; // which child to insert at + bool right = false; + TreeNode* i = m_root; + while (true) { + assert(i != NULL); + if (n->key() <= i->key()) { + if (i->left_child() == NULL) { + left = true; + break; + } else { + i = i->left_child(); + } + } else { + if (i->right_child() == NULL) { + right = true; + break; + } else { + i = i->right_child(); + } + } + } + + assert(i != NULL); + assert(left || right); + assert( ! (left && right) ); + + if (left) { + assert(i->left_child() == NULL); + i->left_child(n); + } else if (right) { + assert(i->right_child() == NULL); + i->right_child(n); + } + n->parent(i); + } + ++m_size; +} + + +/** Remove a node from the tree. + * + * Realtime safe, caller is responsible to delete returned value. + * + * @return NULL if object with @a key is not in tree. + */ +template +TreeNode* +Tree::remove(const string& key) +{ + TreeNode* node = find_treenode(key); + TreeNode* n = node; + TreeNode* swap = NULL; + T temp_node; + string temp_key; + + if (node == NULL) + return NULL; + + // Node is not even in tree + if (node->parent() == NULL && m_root != node) + return NULL; + // FIXME: What if the node is in a different tree? Check for this? + +#ifndef NDEBUG + const T& remove_node = node->node(); // for error checking +#endif // NDEBUG + + // n has two children + if (n->left_child() != NULL && n->right_child() != NULL) { + if (rand()%2) + swap = m_find_largest(n->left_child()); + else + swap = m_find_smallest(n->right_child()); + + // Swap node's elements + temp_node = swap->m_node; + swap->m_node = n->m_node; + n->m_node = temp_node; + + // Swap node's keys + temp_key = swap->m_key; + swap->m_key = n->m_key; + n->m_key = temp_key; + + n = swap; + assert(n != NULL); + } + + // be sure we swapped correctly (ie right node is getting removed) + assert(n->node() == remove_node); + + // n now has at most one child + assert(n->left_child() == NULL || n->right_child() == NULL); + + if (n->is_leaf()) { + if (n->is_left_child()) + n->parent()->left_child(NULL); + else if (n->is_right_child()) + n->parent()->right_child(NULL); + + if (m_root == n) m_root = NULL; + } else { // has a single child + TreeNode* child = NULL; + if (n->left_child() != NULL) + child = n->left_child(); + else if (n->right_child() != NULL) + child = n->right_child(); + else + exit(EXIT_FAILURE); + + assert(child != n); + assert(child != NULL); + assert(n->parent() != n); + + if (n->is_left_child()) { + assert(n->parent() != child); + n->parent()->left_child(child); + child->parent(n->parent()); + } else if (n->is_right_child()) { + assert(n->parent() != child); + n->parent()->right_child(child); + child->parent(n->parent()); + } else { + child->parent(NULL); + } + if (m_root == n) m_root = child; + } + + // Be sure node is cut off completely + assert(n != NULL); + assert(n->parent() == NULL || n->parent()->left_child() != n); + assert(n->parent() == NULL || n->parent()->right_child() != n); + assert(n->left_child() == NULL || n->left_child()->parent() != n); + assert(n->right_child() == NULL || n->right_child()->parent() != n); + assert(m_root != n); + + n->parent(NULL); + n->left_child(NULL); + n->right_child(NULL); + + --m_size; + + if (m_size == 0) m_root = NULL; + + // Be sure right node is being removed + assert(n->node() == remove_node); + + return n; +} + + +template +T +Tree::find(const string& name) const +{ + TreeNode* tn = find_treenode(name); + + return (tn == NULL) ? NULL : tn->node(); +} + + +template +TreeNode* +Tree::find_treenode(const string& name) const +{ + TreeNode* i = m_root; + int cmp = 0; + + while (i != NULL) { + cmp = name.compare(i->key()); + if (cmp < 0) + i = i->left_child(); + else if (cmp > 0) + i = i->right_child(); + else + break; + } + + return i; +} + + +/// Private /// +template +void +Tree::m_set_all_traversed_recursive(TreeNode* root, bool b) +{ + assert(root != NULL); + + // Preorder traversal + root->node()->traversed(b); + if (root->left_child() != NULL) + m_set_all_traversed_recursive(root->left_child(), b); + if (root->right_child() != NULL) + m_set_all_traversed_recursive(root->right_child(), b); +} + + +/** Finds the smallest (key) node in the subtree rooted at "root" + */ +template +TreeNode* +Tree::m_find_smallest(TreeNode* root) +{ + TreeNode* r = root; + + while (r->left_child() != NULL) + r = r->left_child(); + + return r; +} + + +/** Finds the largest (key) node in the subtree rooted at "root". + */ +template +TreeNode* +Tree::m_find_largest(TreeNode* root) +{ + TreeNode* r = root; + + while (r->right_child() != NULL) + r = r->right_child(); + + return r; + +} + + + +//// Iterator Stuff //// + + + +template +Tree::iterator::iterator(const Tree *tree, size_t size) +: m_depth(-1), + m_size(size), + m_stack(NULL), + m_tree(tree) +{ + if (size > 0) + m_stack = new TreeNode*[size]; +} + + +template +Tree::iterator::~iterator() +{ + delete[] m_stack; +} + + +/* FIXME: Make these next two not memcpy (possibly have to force a single + * iterator existing at any given time) for speed. + */ + +// Copy constructor (for the typical for loop usage) +template +Tree::iterator::iterator(const Tree::iterator& copy) +: m_depth(copy.m_depth), + m_size(copy.m_size), + m_tree(copy.m_tree) +{ + if (m_size > 0) { + m_stack = new TreeNode*[m_size]; + memcpy(m_stack, copy.m_stack, m_size * sizeof(TreeNode*)); + } +} + + +// Assignment operator +template +typename Tree::iterator& +Tree::iterator::operator=(const Tree::iterator& copy) { + m_depth = copy.m_depth; + m_size = copy.m_size; + m_tree = copy.m_tree; + + if (m_size > 0) { + m_stack = new TreeNode*[m_size]; + memcpy(m_stack, copy.m_stack, m_size * sizeof(TreeNode*)); + } + return *this; +} + + +template +T +Tree::iterator::operator*() const +{ + assert(m_depth >= 0); + return m_stack[m_depth]->node(); +} + + +template +typename Tree::iterator& +Tree::iterator::operator++() +{ + assert(m_depth >= 0); + + TreeNode* tn = m_stack[m_depth]; + --m_depth; + + tn = tn->right_child(); + while (tn != NULL) { + ++m_depth; + m_stack[m_depth] = tn; + tn = tn->left_child(); + } + + return *this; +} + + +template +bool +Tree::iterator::operator!=(const Tree::iterator& iter) const +{ + // (DeMorgan's Law) + return (m_tree != iter.m_tree || m_depth != iter.m_depth); +} + + +template +typename Tree::iterator +Tree::begin() const +{ + typename Tree::iterator iter(this, m_size); + iter.m_depth = -1; + + TreeNode *ptr = m_root; + while (ptr != NULL) { + iter.m_depth++; + iter.m_stack[iter.m_depth] = ptr; + ptr = ptr->left_child(); + } + + return iter; +} + + +template +typename Tree::iterator +Tree::end() const +{ + typename Tree::iterator iter(this, 0); + iter.m_depth = -1; + + return iter; +} + + -- cgit v1.2.1