From bb1c49dfa484db080938cff6f8f70167c9026a1c Mon Sep 17 00:00:00 2001 From: David Robillard Date: Tue, 24 Jul 2007 19:26:47 +0000 Subject: Consistently rename all C++ files .cpp/.hpp. Fix (some) inclusion guard names to not clash with other libs. git-svn-id: http://svn.drobilla.net/lad/ingen@613 a436a847-0d15-0410-975c-d299462d15a1 --- src/libs/engine/TreeImplementation.hpp | 395 +++++++++++++++++++++++++++++++++ 1 file changed, 395 insertions(+) create mode 100644 src/libs/engine/TreeImplementation.hpp (limited to 'src/libs/engine/TreeImplementation.hpp') diff --git a/src/libs/engine/TreeImplementation.hpp b/src/libs/engine/TreeImplementation.hpp new file mode 100644 index 00000000..681079ac --- /dev/null +++ b/src/libs/engine/TreeImplementation.hpp @@ -0,0 +1,395 @@ +/* This file is part of Ingen. + * Copyright (C) 2007 Dave Robillard + * + * Ingen 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. + * + * Ingen 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., + * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include "Tree.hpp" +#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 (_root == NULL) { + _root = n; + } else { + bool left = false; // which child to insert at + bool right = false; + TreeNode* i = _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); + } + ++_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 && _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 = _find_largest(n->left_child()); + else + swap = _find_smallest(n->right_child()); + + // Swap node's elements + temp_node = swap->_node; + swap->_node = n->_node; + n->_node = temp_node; + + // Swap node's keys + temp_key = swap->_key; + swap->_key = n->_key; + n->_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 (_root == n) _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 (_root == n) _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(_root != n); + + n->parent(NULL); + n->left_child(NULL); + n->right_child(NULL); + + --_size; + + if (_size == 0) _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 = _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; +} + + +/** Finds the smallest (key) node in the subtree rooted at "root" + */ +template +TreeNode* +Tree::_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::_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) +: _depth(-1), + _size(size), + _stack(NULL), + _tree(tree) +{ + if (size > 0) + _stack = new TreeNode*[size]; +} + + +template +Tree::iterator::~iterator() +{ + delete[] _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) +: _depth(copy._depth), + _size(copy._size), + _tree(copy._tree) +{ + if (_size > 0) { + _stack = new TreeNode*[_size]; + memcpy(_stack, copy._stack, _size * sizeof(TreeNode*)); + } +} + + +// Assignment operator +template +typename Tree::iterator& +Tree::iterator::operator=(const Tree::iterator& copy) { + _depth = copy._depth; + _size = copy._size; + _tree = copy._tree; + + if (_size > 0) { + _stack = new TreeNode*[_size]; + memcpy(_stack, copy._stack, _size * sizeof(TreeNode*)); + } + return *this; +} + + +template +T +Tree::iterator::operator*() const +{ + assert(_depth >= 0); + return _stack[_depth]->node(); +} + + +template +typename Tree::iterator& +Tree::iterator::operator++() +{ + assert(_depth >= 0); + + TreeNode* tn = _stack[_depth]; + --_depth; + + tn = tn->right_child(); + while (tn != NULL) { + ++_depth; + _stack[_depth] = tn; + tn = tn->left_child(); + } + + return *this; +} + + +template +bool +Tree::iterator::operator!=(const Tree::iterator& iter) const +{ + // (DeMorgan's Law) + return (_tree != iter._tree || _depth != iter._depth); +} + + +template +typename Tree::iterator +Tree::begin() const +{ + typename Tree::iterator iter(this, _size); + iter._depth = -1; + + TreeNode *ptr = _root; + while (ptr != NULL) { + iter._depth++; + iter._stack[iter._depth] = ptr; + ptr = ptr->left_child(); + } + + return iter; +} + + +template +typename Tree::iterator +Tree::end() const +{ + typename Tree::iterator iter(this, 0); + iter._depth = -1; + + return iter; +} + + -- cgit v1.2.1