summaryrefslogtreecommitdiffstats
path: root/src/libs/engine/TreeImplementation.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/libs/engine/TreeImplementation.h')
-rw-r--r--src/libs/engine/TreeImplementation.h410
1 files changed, 410 insertions, 0 deletions
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 <cstdlib>
+#include <iostream>
+#include <cassert>
+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 <typename T>
+Tree<T>::~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<typename T>
+void
+Tree<T>::insert(TreeNode<T>* 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<T>* 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<typename T>
+TreeNode<T>*
+Tree<T>::remove(const string& key)
+{
+ TreeNode<T>* node = find_treenode(key);
+ TreeNode<T>* n = node;
+ TreeNode<T>* 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<T>* 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<typename T>
+T
+Tree<T>::find(const string& name) const
+{
+ TreeNode<T>* tn = find_treenode(name);
+
+ return (tn == NULL) ? NULL : tn->node();
+}
+
+
+template<typename T>
+TreeNode<T>*
+Tree<T>::find_treenode(const string& name) const
+{
+ TreeNode<T>* 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<typename T>
+void
+Tree<T>::m_set_all_traversed_recursive(TreeNode<T>* 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<typename T>
+TreeNode<T>*
+Tree<T>::m_find_smallest(TreeNode<T>* root)
+{
+ TreeNode<T>* 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<typename T>
+TreeNode<T>*
+Tree<T>::m_find_largest(TreeNode<T>* root)
+{
+ TreeNode<T>* r = root;
+
+ while (r->right_child() != NULL)
+ r = r->right_child();
+
+ return r;
+
+}
+
+
+
+//// Iterator Stuff ////
+
+
+
+template<typename T>
+Tree<T>::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<T>*[size];
+}
+
+
+template<typename T>
+Tree<T>::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<typename T>
+Tree<T>::iterator::iterator(const Tree<T>::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<T>*[m_size];
+ memcpy(m_stack, copy.m_stack, m_size * sizeof(TreeNode<T>*));
+ }
+}
+
+
+// Assignment operator
+template<typename T>
+typename Tree<T>::iterator&
+Tree<T>::iterator::operator=(const Tree<T>::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<T>*[m_size];
+ memcpy(m_stack, copy.m_stack, m_size * sizeof(TreeNode<T>*));
+ }
+ return *this;
+}
+
+
+template<typename T>
+T
+Tree<T>::iterator::operator*() const
+{
+ assert(m_depth >= 0);
+ return m_stack[m_depth]->node();
+}
+
+
+template<typename T>
+typename Tree<T>::iterator&
+Tree<T>::iterator::operator++()
+{
+ assert(m_depth >= 0);
+
+ TreeNode<T>* 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<typename T>
+bool
+Tree<T>::iterator::operator!=(const Tree<T>::iterator& iter) const
+{
+ // (DeMorgan's Law)
+ return (m_tree != iter.m_tree || m_depth != iter.m_depth);
+}
+
+
+template<typename T>
+typename Tree<T>::iterator
+Tree<T>::begin() const
+{
+ typename Tree<T>::iterator iter(this, m_size);
+ iter.m_depth = -1;
+
+ TreeNode<T> *ptr = m_root;
+ while (ptr != NULL) {
+ iter.m_depth++;
+ iter.m_stack[iter.m_depth] = ptr;
+ ptr = ptr->left_child();
+ }
+
+ return iter;
+}
+
+
+template<typename T>
+typename Tree<T>::iterator
+Tree<T>::end() const
+{
+ typename Tree<T>::iterator iter(this, 0);
+ iter.m_depth = -1;
+
+ return iter;
+}
+
+