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/GraphObject.cpp | 32 -- src/libs/engine/GraphObject.hpp | 115 ------- src/libs/engine/GraphObjectImpl.cpp | 32 ++ src/libs/engine/GraphObjectImpl.hpp | 116 +++++++ src/libs/engine/Makefile.am | 9 +- src/libs/engine/Node.hpp | 8 +- src/libs/engine/ObjectSender.cpp | 12 +- src/libs/engine/ObjectStore.cpp | 24 +- src/libs/engine/ObjectStore.hpp | 22 +- src/libs/engine/Port.cpp | 2 +- src/libs/engine/Port.hpp | 4 +- src/libs/engine/Tree.hpp | 141 --------- src/libs/engine/TreeImplementation.hpp | 395 ------------------------ src/libs/engine/events/CreateNodeEvent.cpp | 1 - src/libs/engine/events/CreatePatchEvent.cpp | 5 +- src/libs/engine/events/CreatePortEvent.cpp | 1 - src/libs/engine/events/DestroyEvent.cpp | 5 +- src/libs/engine/events/DestroyEvent.hpp | 4 +- src/libs/engine/events/RenameEvent.cpp | 5 +- src/libs/engine/events/RenameEvent.hpp | 4 +- src/libs/engine/events/RequestMetadataEvent.cpp | 2 +- src/libs/engine/events/RequestMetadataEvent.hpp | 4 +- src/libs/engine/events/RequestObjectEvent.hpp | 6 +- src/libs/engine/events/SetMetadataEvent.cpp | 2 +- src/libs/engine/events/SetMetadataEvent.hpp | 6 +- src/libs/engine/events/SetPolyphonicEvent.hpp | 8 +- src/libs/engine/instantiations.cpp | 30 -- src/libs/engine/tests/Makefile.am | 12 - src/libs/engine/tests/node_tree_test.cpp | 94 ------ src/libs/engine/tests/old_node_tree_test.cpp | 72 ----- 30 files changed, 211 insertions(+), 962 deletions(-) delete mode 100644 src/libs/engine/GraphObject.cpp delete mode 100644 src/libs/engine/GraphObject.hpp create mode 100644 src/libs/engine/GraphObjectImpl.cpp create mode 100644 src/libs/engine/GraphObjectImpl.hpp delete mode 100644 src/libs/engine/Tree.hpp delete mode 100644 src/libs/engine/TreeImplementation.hpp delete mode 100644 src/libs/engine/instantiations.cpp delete mode 100644 src/libs/engine/tests/Makefile.am delete mode 100644 src/libs/engine/tests/node_tree_test.cpp delete mode 100644 src/libs/engine/tests/old_node_tree_test.cpp (limited to 'src/libs/engine') diff --git a/src/libs/engine/GraphObject.cpp b/src/libs/engine/GraphObject.cpp deleted file mode 100644 index b18e9687..00000000 --- a/src/libs/engine/GraphObject.cpp +++ /dev/null @@ -1,32 +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 "GraphObject.hpp" -#include "Patch.hpp" -#include "ObjectStore.hpp" - -namespace Ingen { - - -Patch* -GraphObject::parent_patch() const -{ - return dynamic_cast((Node*)_parent); -} - - -} // namespace Ingen diff --git a/src/libs/engine/GraphObject.hpp b/src/libs/engine/GraphObject.hpp deleted file mode 100644 index f2089f42..00000000 --- a/src/libs/engine/GraphObject.hpp +++ /dev/null @@ -1,115 +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 - */ - -#ifndef GRAPHOBJECT_H -#define GRAPHOBJECT_H - -#include -#include -#include -#include -#include -#include -#include -#include "types.hpp" - -using Raul::Atom; -using Raul::Path; - -namespace Raul { class Maid; } - -namespace Ingen { - -class Patch; -class ProcessContext; - - -/** An object on the audio graph - Patch, Node, Port, etc. - * - * Each of these is a Raul::Deletable and so can be deleted in a realtime safe - * way from anywhere, and they all have a map of metadata for clients to store - * arbitrary values in (which the engine puts no significance to whatsoever). - * - * \ingroup engine - */ -class GraphObject : public Raul::Deletable -{ -public: - typedef std::map MetadataMap; - - GraphObject(GraphObject* parent, const string& name, bool polyphonic=false) - : _parent(parent), _name(name), _polyphonic(polyphonic) - { - assert(parent == NULL || _name.length() > 0); - assert(_name.find("/") == string::npos); - assert(path().find("//") == string::npos); - } - - virtual ~GraphObject() {} - - bool polyphonic() const { return _polyphonic; } - virtual void set_polyphonic(Raul::Maid& maid, bool p) { _polyphonic = p; } - - inline GraphObject* parent() const { return _parent; } - inline const string& name() const { return _name; } - - virtual void process(ProcessContext& context) = 0; - - /** Rename */ - virtual void set_path(const Path& new_path) { - assert(new_path.parent() == path().parent()); - _name = new_path.name(); - assert(_name.find("/") == string::npos); - } - - void set_metadata(const string& key, const Atom& value) - { _metadata[key] = value; } - - const Atom& get_metadata(const string& key) { - static Atom null_atom; - MetadataMap::iterator i = _metadata.find(key); - return (i != _metadata.end()) ? (*i).second : null_atom; - } - - const MetadataMap& metadata() const { return _metadata; } - - /** The Patch this object is a child of. */ - virtual Patch* parent_patch() const; - - /** Path is dynamically generated from parent to ease renaming */ - inline const Path path() const { - if (_parent == NULL) - return Path(string("/").append(_name)); - else if (_parent->path() == "/") - return Path(string("/").append(_name)); - else - return Path(_parent->path() +"/"+ _name); - } - -protected: - GraphObject* _parent; - std::string _name; - bool _polyphonic; - -private: - MetadataMap _metadata; -}; - - -} // namespace Ingen - -#endif // GRAPHOBJECT_H diff --git a/src/libs/engine/GraphObjectImpl.cpp b/src/libs/engine/GraphObjectImpl.cpp new file mode 100644 index 00000000..966f8238 --- /dev/null +++ b/src/libs/engine/GraphObjectImpl.cpp @@ -0,0 +1,32 @@ +/* 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 "GraphObjectImpl.hpp" +#include "Patch.hpp" +#include "ObjectStore.hpp" + +namespace Ingen { + + +Patch* +GraphObjectImpl::parent_patch() const +{ + return dynamic_cast((Node*)_parent); +} + + +} // namespace Ingen diff --git a/src/libs/engine/GraphObjectImpl.hpp b/src/libs/engine/GraphObjectImpl.hpp new file mode 100644 index 00000000..1fa6ad06 --- /dev/null +++ b/src/libs/engine/GraphObjectImpl.hpp @@ -0,0 +1,116 @@ +/* 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 + */ + +#ifndef GRAPHOBJECTIMPL_H +#define GRAPHOBJECTIMPL_H + +#include +#include +#include +#include +#include +#include +#include +#include "interface/GraphObject.hpp" +#include "types.hpp" + +using Raul::Atom; +using Raul::Path; + +namespace Raul { class Maid; } + +namespace Ingen { + +class Patch; +class ProcessContext; + + +/** An object on the audio graph - Patch, Node, Port, etc. + * + * Each of these is a Raul::Deletable and so can be deleted in a realtime safe + * way from anywhere, and they all have a map of metadata for clients to store + * arbitrary values in (which the engine puts no significance to whatsoever). + * + * \ingroup engine + */ +class GraphObjectImpl : public Ingen::Shared::GraphObject +{ +public: + typedef std::map MetadataMap; + + GraphObjectImpl(GraphObjectImpl* parent, const string& name, bool polyphonic=false) + : _parent(parent), _name(name), _polyphonic(polyphonic) + { + assert(parent == NULL || _name.length() > 0); + assert(_name.find("/") == string::npos); + assert(path().find("//") == string::npos); + } + + virtual ~GraphObjectImpl() {} + + bool polyphonic() const { return _polyphonic; } + virtual void set_polyphonic(Raul::Maid& maid, bool p) { _polyphonic = p; } + + inline GraphObjectImpl* parent() const { return _parent; } + inline const string& name() const { return _name; } + + virtual void process(ProcessContext& context) = 0; + + /** Rename */ + virtual void set_path(const Path& new_path) { + assert(new_path.parent() == path().parent()); + _name = new_path.name(); + assert(_name.find("/") == string::npos); + } + + void set_metadata(const string& key, const Atom& value) + { _metadata[key] = value; } + + const Atom& get_metadata(const string& key) { + static Atom null_atom; + MetadataMap::iterator i = _metadata.find(key); + return (i != _metadata.end()) ? (*i).second : null_atom; + } + + const MetadataMap& metadata() const { return _metadata; } + + /** The Patch this object is a child of. */ + virtual Patch* parent_patch() const; + + /** Path is dynamically generated from parent to ease renaming */ + inline const Path path() const { + if (_parent == NULL) + return Path(string("/").append(_name)); + else if (_parent->path() == "/") + return Path(string("/").append(_name)); + else + return Path(_parent->path() +"/"+ _name); + } + +protected: + GraphObjectImpl* _parent; + std::string _name; + bool _polyphonic; + +private: + MetadataMap _metadata; +}; + + +} // namespace Ingen + +#endif // GRAPHOBJECTIMPL_H diff --git a/src/libs/engine/Makefile.am b/src/libs/engine/Makefile.am index b5c910f8..224bba24 100644 --- a/src/libs/engine/Makefile.am +++ b/src/libs/engine/Makefile.am @@ -1,4 +1,4 @@ -SUBDIRS = tests events +SUBDIRS = events MAINTAINERCLEANFILES = Makefile.in @@ -42,8 +42,8 @@ libingen_engine_la_SOURCES = \ EventSink.cpp \ EventSink.hpp \ EventSource.hpp \ - GraphObject.cpp \ - GraphObject.hpp \ + GraphObjectImpl.cpp \ + GraphObjectImpl.hpp \ InputPort.cpp \ InputPort.hpp \ JackAudioDriver.cpp \ @@ -99,8 +99,6 @@ libingen_engine_la_SOURCES = \ ThreadManager.hpp \ TransportNode.cpp \ TransportNode.hpp \ - Tree.hpp \ - TreeImplementation.hpp \ engine.cpp \ engine.hpp \ events.hpp \ @@ -169,7 +167,6 @@ libingen_engine_la_SOURCES = \ events/SetPortValueQueuedEvent.hpp \ events/UnregisterClientEvent.cpp \ events/UnregisterClientEvent.hpp \ - instantiations.cpp \ jack_compat.h \ tuning.hpp \ types.hpp \ diff --git a/src/libs/engine/Node.hpp b/src/libs/engine/Node.hpp index b1cefe65..083ceea2 100644 --- a/src/libs/engine/Node.hpp +++ b/src/libs/engine/Node.hpp @@ -21,7 +21,7 @@ #include #include #include "types.hpp" -#include "GraphObject.hpp" +#include "GraphObjectImpl.hpp" namespace Raul { template class List; class Maid; } @@ -46,11 +46,11 @@ namespace Shared { class ClientInterface; } * * \ingroup engine */ -class Node : public GraphObject +class Node : public GraphObjectImpl { public: - Node(GraphObject* parent, const std::string& name, bool poly) - : GraphObject(parent, name, poly) + Node(GraphObjectImpl* parent, const std::string& name, bool poly) + : GraphObjectImpl(parent, name, poly) {} virtual ~Node() {} diff --git a/src/libs/engine/ObjectSender.cpp b/src/libs/engine/ObjectSender.cpp index 97a03bce..07cb0f01 100644 --- a/src/libs/engine/ObjectSender.cpp +++ b/src/libs/engine/ObjectSender.cpp @@ -64,8 +64,8 @@ ObjectSender::send_patch(ClientInterface* client, const Patch* patch, bool recur } // Send metadata - const GraphObject::MetadataMap& data = patch->metadata(); - for (GraphObject::MetadataMap::const_iterator j = data.begin(); j != data.end(); ++j) + const GraphObjectImpl::MetadataMap& data = patch->metadata(); + for (GraphObjectImpl::MetadataMap::const_iterator j = data.begin(); j != data.end(); ++j) client->metadata_update(patch->path(), (*j).first, (*j).second); if (patch->enabled()) @@ -96,8 +96,8 @@ ObjectSender::send_node(ClientInterface* client, const Node* node, bool recursiv client->new_node(node->plugin()->uri(), node->path(), node->polyphonic(), node->ports().size()); // Send metadata - const GraphObject::MetadataMap& data = node->metadata(); - for (GraphObject::MetadataMap::const_iterator j = data.begin(); j != data.end(); ++j) + const GraphObjectImpl::MetadataMap& data = node->metadata(); + for (GraphObjectImpl::MetadataMap::const_iterator j = data.begin(); j != data.end(); ++j) client->metadata_update(node->path(), (*j).first, (*j).second); client->bundle_end(); @@ -137,8 +137,8 @@ ObjectSender::send_port(ClientInterface* client, const Port* port) client->new_port(port->path(), type, port->is_output()); // Send metadata - const GraphObject::MetadataMap& data = port->metadata(); - for (GraphObject::MetadataMap::const_iterator j = data.begin(); j != data.end(); ++j) + const GraphObjectImpl::MetadataMap& data = port->metadata(); + for (GraphObjectImpl::MetadataMap::const_iterator j = data.begin(); j != data.end(); ++j) client->metadata_update(port->path(), (*j).first, (*j).second); // Send control value diff --git a/src/libs/engine/ObjectStore.cpp b/src/libs/engine/ObjectStore.cpp index 4dbe9f0e..27e7565b 100644 --- a/src/libs/engine/ObjectStore.cpp +++ b/src/libs/engine/ObjectStore.cpp @@ -37,7 +37,7 @@ namespace Ingen { Patch* ObjectStore::find_patch(const Path& path) { - GraphObject* const object = find_object(path); + GraphObjectImpl* const object = find_object(path); return dynamic_cast(object); } @@ -47,7 +47,7 @@ ObjectStore::find_patch(const Path& path) Node* ObjectStore::find_node(const Path& path) { - GraphObject* const object = find_object(path); + GraphObjectImpl* const object = find_object(path); return dynamic_cast(object); } @@ -57,14 +57,14 @@ ObjectStore::find_node(const Path& path) Port* ObjectStore::find_port(const Path& path) { - GraphObject* const object = find_object(path); + GraphObjectImpl* const object = find_object(path); return dynamic_cast(object); } /** Find the Object at the given path. */ -GraphObject* +GraphObjectImpl* ObjectStore::find_object(const Path& path) { Objects::iterator i = _objects.find(path); @@ -75,7 +75,7 @@ ObjectStore::find_object(const Path& path) /** Add an object to the store. Not realtime safe. */ void -ObjectStore::add(GraphObject* o) +ObjectStore::add(GraphObjectImpl* o) { assert(ThreadManager::current_thread_id() == THREAD_PRE_PROCESS); @@ -94,7 +94,7 @@ ObjectStore::add(GraphObject* o) /** Add a family of objects to the store. Not realtime safe. */ void -ObjectStore::add(const Table& table) +ObjectStore::add(const Table& table) { assert(ThreadManager::current_thread_id() == THREAD_PRE_PROCESS); @@ -102,7 +102,7 @@ ObjectStore::add(const Table& table) _objects.cram(table); cerr << "[ObjectStore] Adding Table:" << endl; - for (Table::const_iterator i = table.begin(); i != table.end(); ++i) { + for (Table::const_iterator i = table.begin(); i != table.end(); ++i) { cerr << i->first << " = " << i->second->path() << endl; } } @@ -113,7 +113,7 @@ ObjectStore::add(const Table& table) * Returned is a vector containing all descendants of the object removed * including the object itself, in lexicographically sorted order by Path. */ -Table +Table ObjectStore::remove(const Path& path) { return remove(_objects.find(path)); @@ -125,7 +125,7 @@ ObjectStore::remove(const Path& path) * Returned is a vector containing all descendants of the object removed * including the object itself, in lexicographically sorted order by Path. */ -Table +Table ObjectStore::remove(Objects::iterator object) { assert(ThreadManager::current_thread_id() == THREAD_PRE_PROCESS); @@ -133,8 +133,8 @@ ObjectStore::remove(Objects::iterator object) if (object != _objects.end()) { Objects::iterator descendants_end = _objects.find_descendants_end(object); cout << "[ObjectStore] Removing " << object->first << " {" << endl; - Table removed = _objects.yank(object, descendants_end); - for (Table::iterator i = removed.begin(); i != removed.end(); ++i) { + Table removed = _objects.yank(object, descendants_end); + for (Table::iterator i = removed.begin(); i != removed.end(); ++i) { cout << "\t" << i->first << endl; } cout << "}" << endl; @@ -143,7 +143,7 @@ ObjectStore::remove(Objects::iterator object) } else { cerr << "[ObjectStore] WARNING: Removing " << object->first << " failed." << endl; - return Table(); + return Table(); } } diff --git a/src/libs/engine/ObjectStore.hpp b/src/libs/engine/ObjectStore.hpp index c61d4130..d0504d70 100644 --- a/src/libs/engine/ObjectStore.hpp +++ b/src/libs/engine/ObjectStore.hpp @@ -29,7 +29,7 @@ namespace Ingen { class Patch; class Node; class Port; -class GraphObject; +class GraphObjectImpl; /** Storage for all GraphObjects (tree of GraphObject's sorted by path). @@ -44,21 +44,21 @@ class GraphObject; class ObjectStore { public: - typedef Raul::PathTable Objects; + typedef Raul::PathTable Objects; - Patch* find_patch(const Path& path); - Node* find_node(const Path& path); - Port* find_port(const Path& path); - GraphObject* find_object(const Path& path); + Patch* find_patch(const Path& path); + Node* find_node(const Path& path); + Port* find_port(const Path& path); + GraphObjectImpl* find_object(const Path& path); Objects::iterator find(const Path& path) { return _objects.find(path); } - void add(GraphObject* o); - void add(const Table& family); - //void add(TreeNode* o); + void add(GraphObjectImpl* o); + void add(const Table& family); + //void add(TreeNode* o); - Table remove(const Path& path); - Table remove(Objects::iterator i); + Table remove(const Path& path); + Table remove(Objects::iterator i); const Objects& objects() const { return _objects; } Objects& objects() { return _objects; } diff --git a/src/libs/engine/Port.cpp b/src/libs/engine/Port.cpp index d85c1790..880b2c46 100644 --- a/src/libs/engine/Port.cpp +++ b/src/libs/engine/Port.cpp @@ -37,7 +37,7 @@ const char* const DataType::type_uris[4] = { "UNKNOWN", "FLOAT", "MIDI", "OSC" } Port::Port(Node* const node, const string& name, uint32_t index, uint32_t poly, DataType type, size_t buffer_size) - : GraphObject(node, name, true) + : GraphObjectImpl(node, name, true) , _index(index) , _poly(poly) , _buffer_size(buffer_size) diff --git a/src/libs/engine/Port.hpp b/src/libs/engine/Port.hpp index e504507c..fa9c454f 100644 --- a/src/libs/engine/Port.hpp +++ b/src/libs/engine/Port.hpp @@ -22,7 +22,7 @@ #include #include #include "types.hpp" -#include "GraphObject.hpp" +#include "GraphObjectImpl.hpp" #include "DataType.hpp" namespace Raul { class Maid; } @@ -42,7 +42,7 @@ class ProcessContext; * * \ingroup engine */ -class Port : public GraphObject +class Port : public GraphObjectImpl { public: virtual ~Port(); diff --git a/src/libs/engine/Tree.hpp b/src/libs/engine/Tree.hpp deleted file mode 100644 index c6e36926..00000000 --- a/src/libs/engine/Tree.hpp +++ /dev/null @@ -1,141 +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 - */ - -#ifndef TREE_H -#define TREE_H - -#include -#include -#include -#include -using std::string; - -template class Tree; - - -/** A node in a Tree. - */ -template -class TreeNode : public Raul::Deletable -{ -public: - TreeNode(const string& key) - : _parent(NULL), _left_child(NULL), _right_child(NULL), - _key(key), _node(NULL) {} - - TreeNode(const string& key, T n) - : _parent(NULL), _left_child(NULL), _right_child(NULL), - _key(key), _node(n) {} - - ~TreeNode() { - assert(_parent == NULL || _parent->left_child() != this); - assert(_parent == NULL || _parent->right_child() != this); - assert(_left_child == NULL || _left_child->parent() != this); - assert(_right_child == NULL || _right_child->parent() != this); - _parent = _left_child = _right_child = NULL; - } - - string key() const { return _key; } - void key(const string& key) { _key = key; } - TreeNode* parent() const { return _parent; } - void parent(TreeNode* n) { _parent = n; } - TreeNode* left_child() const { return _left_child; } - void left_child(TreeNode* n) { _left_child = n; } - TreeNode* right_child() const { return _right_child; } - void right_child(TreeNode* n) { _right_child = n; } - - bool is_leaf() { return (_left_child == NULL && _right_child == NULL); } - bool is_left_child() { return (_parent != NULL && _parent->left_child() == this); } - bool is_right_child() { return (_parent != NULL && _parent->right_child() == this); } - - T node() { return _node; } - - friend class Tree; - -protected: - TreeNode* _parent; - TreeNode* _left_child; - TreeNode* _right_child; - string _key; - T _node; -}; - - -/** The tree all objects are stored in. - * - * Textbook naive (unbalanced) Binary Search Tree. Slightly different - * from a usual BST implementation in that the "Node" classes (TreeNode) are - * exposed to the user. This is so QueuedEvent's can create the TreeNode in - * another thread, and the realtime jack thread can insert them (without having - * to allocating a TreeNode which is a no-no). - * - * It's also a more annoying implementation because there's no leaf type (since - * a leaf object would have to be deleted on insert). - * - * Tree::iterator is not realtime safe, but the insert/remove/find methods - * of Tree do not use them. - */ -template -class Tree : boost::noncopyable -{ -public: - Tree() : _root(0), _size(0) {} - ~Tree(); - - void insert(TreeNode* const n); - TreeNode* remove(const string& key); - T find(const string& key) const; - TreeNode* find_treenode(const string& key) const; - - size_t size() const { return _size; } - - /** NON realtime safe iterator for a Tree. */ - class iterator - { - public: - iterator(const Tree* tree, size_t size); - ~iterator(); - - T operator*() const; - iterator& operator++(); - bool operator!=(const iterator& iter) const; - - friend class Tree; - - iterator(const iterator& copy); - iterator& operator=(const iterator& copy); - - private: - int _depth; - size_t _size; - TreeNode** _stack; - const Tree* _tree; - }; - - iterator begin() const; - iterator end() const; - -private: - TreeNode* _find_smallest(TreeNode* root); - TreeNode* _find_largest(TreeNode* root); - - TreeNode* _root; - size_t _size; -}; - - -#endif // TREE_H 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; -} - - diff --git a/src/libs/engine/events/CreateNodeEvent.cpp b/src/libs/engine/events/CreateNodeEvent.cpp index 65296de6..6ed860dd 100644 --- a/src/libs/engine/events/CreateNodeEvent.cpp +++ b/src/libs/engine/events/CreateNodeEvent.cpp @@ -22,7 +22,6 @@ #include "Responder.hpp" #include "Patch.hpp" #include "Node.hpp" -#include "Tree.hpp" #include "Plugin.hpp" #include "Engine.hpp" #include "Patch.hpp" diff --git a/src/libs/engine/events/CreatePatchEvent.cpp b/src/libs/engine/events/CreatePatchEvent.cpp index 288eaee3..748d44dc 100644 --- a/src/libs/engine/events/CreatePatchEvent.cpp +++ b/src/libs/engine/events/CreatePatchEvent.cpp @@ -15,17 +15,16 @@ * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ +#include +#include #include "CreatePatchEvent.hpp" #include "Responder.hpp" #include "Patch.hpp" #include "Node.hpp" -#include "Tree.hpp" #include "Plugin.hpp" #include "Engine.hpp" -#include #include "ClientBroadcaster.hpp" #include "AudioDriver.hpp" -#include #include "ObjectStore.hpp" namespace Ingen { diff --git a/src/libs/engine/events/CreatePortEvent.cpp b/src/libs/engine/events/CreatePortEvent.cpp index b8bc75e6..6163d4ab 100644 --- a/src/libs/engine/events/CreatePortEvent.cpp +++ b/src/libs/engine/events/CreatePortEvent.cpp @@ -22,7 +22,6 @@ #include "Responder.hpp" #include "CreatePortEvent.hpp" #include "Patch.hpp" -#include "Tree.hpp" #include "Plugin.hpp" #include "Engine.hpp" #include "Patch.hpp" diff --git a/src/libs/engine/events/DestroyEvent.cpp b/src/libs/engine/events/DestroyEvent.cpp index a3d96ede..2ccad693 100644 --- a/src/libs/engine/events/DestroyEvent.cpp +++ b/src/libs/engine/events/DestroyEvent.cpp @@ -15,11 +15,12 @@ * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ +#include +#include #include "DestroyEvent.hpp" #include "Responder.hpp" #include "Engine.hpp" #include "Patch.hpp" -#include "Tree.hpp" #include "NodeBase.hpp" #include "Plugin.hpp" #include "AudioDriver.hpp" @@ -27,9 +28,7 @@ #include "DisconnectNodeEvent.hpp" #include "DisconnectPortEvent.hpp" #include "ClientBroadcaster.hpp" -#include #include "ObjectStore.hpp" -#include #include "QueuedEventSource.hpp" #include "Port.hpp" diff --git a/src/libs/engine/events/DestroyEvent.hpp b/src/libs/engine/events/DestroyEvent.hpp index 5ab3b01f..77167598 100644 --- a/src/libs/engine/events/DestroyEvent.hpp +++ b/src/libs/engine/events/DestroyEvent.hpp @@ -33,7 +33,7 @@ template class TreeNode; namespace Ingen { -class GraphObject; +class GraphObjectImpl; class Patch; class Node; class Port; @@ -61,7 +61,7 @@ public: private: Path _path; ObjectStore::Objects::iterator _store_iterator; - Table _removed_table; + Table _removed_table; Node* _node; ///< Same as _object if it is a Node, otherwise NULL Port* _port; ///< Same as _object if it is a Port, otherwise NULL DriverPort* _driver_port; diff --git a/src/libs/engine/events/RenameEvent.cpp b/src/libs/engine/events/RenameEvent.cpp index 9e5ef543..c643e456 100644 --- a/src/libs/engine/events/RenameEvent.cpp +++ b/src/libs/engine/events/RenameEvent.cpp @@ -23,7 +23,6 @@ #include "Patch.hpp" #include "RenameEvent.hpp" #include "Responder.hpp" -#include "Tree.hpp" #include "AudioDriver.hpp" #include "MidiDriver.hpp" @@ -78,10 +77,10 @@ RenameEvent::pre_process() return; } - Table removed = _engine.object_store()->remove(_store_iterator); + Table removed = _engine.object_store()->remove(_store_iterator); assert(removed.size() > 0); - for (Table::iterator i = removed.begin(); i != removed.end(); ++i) { + for (Table::iterator i = removed.begin(); i != removed.end(); ++i) { const Path& child_old_path = i->first; assert(Path::descendant_comparator(_old_path, child_old_path)); diff --git a/src/libs/engine/events/RenameEvent.hpp b/src/libs/engine/events/RenameEvent.hpp index ec3a0cec..e01f4409 100644 --- a/src/libs/engine/events/RenameEvent.hpp +++ b/src/libs/engine/events/RenameEvent.hpp @@ -30,7 +30,7 @@ template class ListNode; namespace Ingen { -class GraphObject; +class GraphObjectImpl; class Patch; class Node; class Plugin; @@ -38,7 +38,7 @@ class DisconnectNodeEvent; class DisconnectPortEvent; -/** An event to change the name of an GraphObject. +/** An event to change the name of an GraphObjectImpl. * * \ingroup engine */ diff --git a/src/libs/engine/events/RequestMetadataEvent.cpp b/src/libs/engine/events/RequestMetadataEvent.cpp index fdd0ded3..0567d94d 100644 --- a/src/libs/engine/events/RequestMetadataEvent.cpp +++ b/src/libs/engine/events/RequestMetadataEvent.cpp @@ -19,7 +19,7 @@ #include #include "Responder.hpp" #include "Engine.hpp" -#include "GraphObject.hpp" +#include "GraphObjectImpl.hpp" #include "ObjectStore.hpp" #include "interface/ClientInterface.hpp" #include "ClientBroadcaster.hpp" diff --git a/src/libs/engine/events/RequestMetadataEvent.hpp b/src/libs/engine/events/RequestMetadataEvent.hpp index 714b1ec3..bbc2c871 100644 --- a/src/libs/engine/events/RequestMetadataEvent.hpp +++ b/src/libs/engine/events/RequestMetadataEvent.hpp @@ -25,7 +25,7 @@ using std::string; namespace Ingen { -class GraphObject; +class GraphObjectImpl; namespace Shared { class ClientInterface; } using Shared::ClientInterface; @@ -47,7 +47,7 @@ private: string _path; string _key; Raul::Atom _value; - GraphObject* _object; + GraphObjectImpl* _object; }; diff --git a/src/libs/engine/events/RequestObjectEvent.hpp b/src/libs/engine/events/RequestObjectEvent.hpp index 263ea627..52459ada 100644 --- a/src/libs/engine/events/RequestObjectEvent.hpp +++ b/src/libs/engine/events/RequestObjectEvent.hpp @@ -26,7 +26,7 @@ using std::string; namespace Ingen { -class GraphObject; +class GraphObjectImpl; namespace Shared { class ClientInterface; } using Shared::ClientInterface; @@ -45,8 +45,8 @@ public: void post_process(); private: - string _path; - GraphObject* _object; + const string _path; + GraphObjectImpl* _object; }; diff --git a/src/libs/engine/events/SetMetadataEvent.cpp b/src/libs/engine/events/SetMetadataEvent.cpp index 8e9163f0..ee0a62dc 100644 --- a/src/libs/engine/events/SetMetadataEvent.cpp +++ b/src/libs/engine/events/SetMetadataEvent.cpp @@ -20,7 +20,7 @@ #include "Responder.hpp" #include "Engine.hpp" #include "ClientBroadcaster.hpp" -#include "GraphObject.hpp" +#include "GraphObjectImpl.hpp" #include "ObjectStore.hpp" using std::string; diff --git a/src/libs/engine/events/SetMetadataEvent.hpp b/src/libs/engine/events/SetMetadataEvent.hpp index 363a63eb..e65763c4 100644 --- a/src/libs/engine/events/SetMetadataEvent.hpp +++ b/src/libs/engine/events/SetMetadataEvent.hpp @@ -26,10 +26,10 @@ using std::string; namespace Ingen { -class GraphObject; +class GraphObjectImpl; -/** An event to set a piece of metadata for an GraphObject. +/** An event to set a piece of metadata for an GraphObjectImpl. * * \ingroup engine */ @@ -46,7 +46,7 @@ private: string _path; string _key; Raul::Atom _value; - GraphObject* _object; + GraphObjectImpl* _object; }; diff --git a/src/libs/engine/events/SetPolyphonicEvent.hpp b/src/libs/engine/events/SetPolyphonicEvent.hpp index 4d0084c9..5922d443 100644 --- a/src/libs/engine/events/SetPolyphonicEvent.hpp +++ b/src/libs/engine/events/SetPolyphonicEvent.hpp @@ -26,7 +26,7 @@ using std::string; namespace Ingen { -class GraphObject; +class GraphObjectImpl; /** Delete all nodes from a patch. @@ -43,9 +43,9 @@ public: void post_process(); private: - string _path; - GraphObject* _object; - bool _poly; + const string _path; + GraphObjectImpl* _object; + bool _poly; }; diff --git a/src/libs/engine/instantiations.cpp b/src/libs/engine/instantiations.cpp deleted file mode 100644 index 6dd80445..00000000 --- a/src/libs/engine/instantiations.cpp +++ /dev/null @@ -1,30 +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 - */ - -/** @file - * Explicit template instantiations. - * - * Needed to avoid undefined references, because GCC doesn't automatically - * instantiate templates (at least not well/completely). - */ - -#include "Tree.hpp" -#include "TreeImplementation.hpp" -#include "GraphObject.hpp" - -template class Tree; - diff --git a/src/libs/engine/tests/Makefile.am b/src/libs/engine/tests/Makefile.am deleted file mode 100644 index bb5e8a56..00000000 --- a/src/libs/engine/tests/Makefile.am +++ /dev/null @@ -1,12 +0,0 @@ -if BUILD_UNIT_TESTS - -AM_CXXFLAGS = @JACK_CFLAGS@ @LIBLO_CFLAGS@ @ALSA_CFLAGS@ @RAUL_CFLAGS@ -I../../common -common_ldadd = @JACK_LIBS@ @RAUL_LIBS@ @LIBLO_LIBS@ @ALSA_LIBS@ -lrt -node_tree_test_LDADD = $(common_ldadd) - -noinst_PROGRAMS = node_tree_test - -node_tree_test_SOURCES = \ - node_tree_test.cpp - -endif # BUILD_UNIT_TESTS diff --git a/src/libs/engine/tests/node_tree_test.cpp b/src/libs/engine/tests/node_tree_test.cpp deleted file mode 100644 index 923cb0ba..00000000 --- a/src/libs/engine/tests/node_tree_test.cpp +++ /dev/null @@ -1,94 +0,0 @@ -#include -#include -#include -#include "../Tree.hpp" -#include "../TreeImplementation.hpp" - -using std::vector; -using std::cout; using std::cerr; using std::endl; - -static const uint NUM_NODES = 20; - -int -main() -{ - cout << "\n\n\n\n"; - - Tree tree; - vector names; - vector in_tree; // arrays - uint num_in_tree = 0; - - - string name; - - for (uint i=0; i < NUM_NODES; ++i) { - name = (char)(i+'A'); - TreeNode* n = new TreeNode(name, name); - tree.insert(n); - names.push_back(name); - in_tree.push_back(true); - ++num_in_tree; - } - - cout << "Added " << NUM_NODES << " nodes." << endl; - cout << "Tree size: " << tree.size() << endl << endl; - - cout << "Tree contents: " << endl; - for (Tree::iterator i = tree.begin(); i != tree.end(); ++i) { - cout << (*i) << ", "; - } - cout << endl; - - - while (true) { - bool insert; - int num = rand() % NUM_NODES; - - if (num_in_tree == 0) - insert = true; - else if (num_in_tree == NUM_NODES) - insert = false; - else { - while (true) { - insert = rand() % 2; - num = rand() % NUM_NODES; - if ((insert && !in_tree[num]) || (!insert && in_tree[num])) - break; - } - } - - string name = names[num]; - - if (insert) { - assert(in_tree[num] == false); - cout << "\nInserting '" << name << "'" << endl; - tree.insert(new TreeNode(name, name)); - in_tree[num] = true; - ++num_in_tree; - cout << "Tree size: " << tree.size() << endl; - assert(num_in_tree == tree.size()); - } else { - assert(in_tree[num] == true); - cout << "\nRemoving '" << name << "'" << endl; - TreeNode* removed = tree.remove(name); - assert(removed != NULL); - assert(removed->node() == name); - assert(removed->key() == name); - delete removed; - in_tree[num] = false; - assert(names[num] == name); - --num_in_tree; - cout << "Tree size: " << tree.size() << endl; - assert(num_in_tree == tree.size()); - } - assert(num_in_tree == tree.size()); - cout << "Tree contents: " << endl; - for (Tree::iterator i = tree.begin(); i != tree.end(); ++i) { - cout << (*i) << ", "; - } - cout << endl; - } - - return 0; -} diff --git a/src/libs/engine/tests/old_node_tree_test.cpp b/src/libs/engine/tests/old_node_tree_test.cpp deleted file mode 100644 index 3b5ed485..00000000 --- a/src/libs/engine/tests/old_node_tree_test.cpp +++ /dev/null @@ -1,72 +0,0 @@ -#include -#include "../NodeTree.h" -#include "../NodeBase.h" - -using std::cout; using std::cerr; using std::endl; - -int main() -{ - cout << "\n\n\n\n"; - - NodeBase* n = NULL; - TreeNode* tn = NULL; - TreeNode* baz = NULL; - TreeNode* quuux = NULL; - TreeNode* bar = NULL; - - NodeTree tree; - n = new NodeBase("foo", 0, 0, 0); - tn = new TreeNode(n); - tree.insert(tn); - n = new NodeBase("bar", 0, 0, 0); - bar = new TreeNode(n); - tree.insert(bar); - n = new NodeBase("baz", 0, 0, 0); - baz = new TreeNode(n); - tree.insert(baz); - n = new NodeBase("quux", 0, 0, 0); - tn = new TreeNode(n); - tree.insert(tn); - n = new NodeBase("quuux", 0, 0, 0); - quuux = new TreeNode(n); - tree.insert(quuux); - n = new NodeBase("quuuux", 0, 0, 0); - tn = new TreeNode(n); - tree.insert(tn); - - - cout << "Added 6 nodes." << endl; - cout << "Tree size: " << tree.size() << endl << endl; - - cout << "Iterating: " << endl; - for (NodeTree::iterator i = tree.begin(); i != tree.end(); ++i) { - cout << (*i)->name() << endl; - } - - cout << endl << "Search 'foo' - " << tree.find("foo")->name() << endl; - cout << endl << "Search 'bar' - " << tree.find("bar")->name() << endl; - cout << endl << "Search 'baz' - " << tree.find("baz")->name() << endl; - cout << endl << "Search 'quux' - " << tree.find("quux")->name() << endl; - cout << endl << "Search 'quuux' - " << tree.find("quuux")->name() << endl; - cout << endl << "Search 'quuuux' - " << tree.find("quuuux")->name() << endl; - cout << endl << "Search 'dave' - " << tree.find("dave") << endl; - cout << endl << "Search 'fo' - " << tree.find("fo") << endl << endl; - - cout << "Removing 'baz'." << endl; - tree.remove(baz); - - cout << "Iterating: " << endl; - for (NodeTree::iterator i = tree.begin(); i != tree.end(); ++i) { - cout << (*i)->name() << endl; - } - - cout << "Removing 'bar' (the root): " << endl; - tree.remove(bar); - - cout << "Iterating: " << endl; - for (NodeTree::iterator i = tree.begin(); i != tree.end(); ++i) { - cout << (*i)->name() << endl; - } - - return 0; -} -- cgit v1.2.1