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/engine/TreeImplementation.h | 410 ---------------------------------------- 1 file changed, 410 deletions(-) delete mode 100644 src/engine/TreeImplementation.h (limited to 'src/engine/TreeImplementation.h') diff --git a/src/engine/TreeImplementation.h b/src/engine/TreeImplementation.h deleted file mode 100644 index a61ec407..00000000 --- a/src/engine/TreeImplementation.h +++ /dev/null @@ -1,410 +0,0 @@ -/* 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