From 91031b8f5a4bf86b39e4c4a02412a16e247f8b15 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Sun, 7 Oct 2007 17:34:19 +0000 Subject: Start building a common (client/server) abstract interface for graph objects. git-svn-id: http://svn.drobilla.net/lad/ingen@834 a436a847-0d15-0410-975c-d299462d15a1 --- src/libs/engine/TreeImplementation.hpp | 395 --------------------------------- 1 file changed, 395 deletions(-) delete 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 deleted file mode 100644 index 681079ac..00000000 --- a/src/libs/engine/TreeImplementation.hpp +++ /dev/null @@ -1,395 +0,0 @@ -/* 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