More juggling

git-svn-id: http://svn.drobilla.net/lad/grauph@15 a436a847-0d15-0410-975c-d299462d15a1

1 files changed, 0 insertions, 410 deletions

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 <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;
-}
-
-