Instead of using a pre-written tree library I decided to write my own, which I could use for the base of my scenegraph oriented game engine.
I wrote the tree node class with no problems whatsoever, the problems come when It gets to writing the iterators. I''m writing my iterators with a similar style to the STL iterators (even though I don''t know too much about them!).
For example:
// Where e is a Node in the Tree
PreorderIterator<std::string> iter;
for (iter=e.Root(); iter!=iter.End(); ++iter)
{
std::cout << *iter.GetNode() << std::endl;
}
When I first tested it, I realised it will never get to the last node of the tree, because the != statement will be false..
So I decided I needed a temporary node to add to the end node, so this node would be used as the real end node. I then delete this temporary node on the iterators destruction.
This method was fine, until I thought about nesting iterators and nesting using different types of iterators, consider:
PreorderIterator<std::string> iter;
for (iter=e.Root(); iter!=iter.End(); ++iter)
{
PreorderIterator<std::string> iter2;
for (iter2=e.Root(); iter2!=iter.End(); ++iter2)
{
// Do something interesting.
}
}
Two temporary nodes will be created, and the nested loop will execute on the ''dummy'' node the first iterator created! (this could be very bad!). I can''t think of a good solution to this problem, and I haven''t found any Tree Iterators in a similar style to mine (at my current level I can''t read the stl/boost code! (if anyone can?)).
So can anyone please suggest a solution to this, it would help a lot.
I hope I explained clearly enough, here is my source code so far:
My node class:
#ifndef Second_Reality_Engine_Node
#define Second_Reality_Engine_Node
//-----------------------------------------------------------------------------
// Node
// Desc: A template class representing a node of a tree
// Q: What operation should the equality operator represent?
//-----------------------------------------------------------------------------
template <class T>
class Node : public T
{
public:
Node();
Node(const Node<T>&);
~Node();
void AttachChild(Node<T>*);
void AttachToParent(Node<T>*);
void Detach();
Node<T>* Root();
Node<T>* End();
Node<T>* RightMost();
Node<T>* LeftMost();
bool IsFirst() const;
bool IsLast() const;
Node<T> *Parent() const;
Node<T> *Child() const;
Node<T> *Previous() const;
Node<T> *Next() const;
//const Node& operator=(const Node&);
private:
Node * parent;
Node * child;
Node * next;
Node * previous;
};
//-----------------------------------------------------------------------------
// Class Node Implementaion
//-----------------------------------------------------------------------------
template <class T>
Node<T>::Node(): parent(0), child(0), previous(0), next(0)
{
}
template <class T>
Node<T>::Node(const Node & node):
parent(node.parent), child(node.child), previous(node.previous), next(node.next)
{
}
template <class T>
Node<T>::~Node()
{
}
template <class T>
void Node<T>::AttachChild(Node<T> * node)
{
if (child)
{
node->parent=this;
child->previous->next=node;
node->previous=child->previous;
child->previous=node;
node->next=child;
}
else
{
child=node;
node->parent=this;
child->next=node;
child->previous=node;
}
}
template <class T>
void Node<T>::AttachToParent(Node<T> * node)
{
if (node->child)
{
parent=node;
previous=node->child->previous;
next=node->child;
node->child->previous->next=this;
node->child->previous=this;
}
else
{
node->child=this;
parent=node;
node->next=node;
node->previous=node;
}
}
template <class T>
void Node<T>::Detach()
{
if (IsFirst())
{
parent->child = (next==this) ? 0 : next;
}
parent=0;
next=this;
previous=this;
}
template <class T>
Node<T>* Node<T>::Root()
{
Node<T> *node=this;
while (node->Parent())
{
node=node->Parent();
}
return node;
}
template <class T>
Node<T>* Node<T>::End()
{
Node<T> *node=Root();
while(node->child)
{
node=node->child->previous;
}
return node;
}
template <class T>
bool Node<T>::IsFirst() const
{
return (parent->child==this);
}
template <class T>
bool Node<T>::IsLast() const
{
return (parent->child->previous==this);
}
template <class T>
Node<T>* Node<T>::Parent() const
{
return parent;
}
template <class T>
Node<T>* Node<T>::Child() const
{
return child;
}
template <class T>
Node<T>* Node<T>::Previous() const
{
return previous;
}
template <class T>
Node<T>* Node<T>::Next() const
{
return next;
}
#endif // Second_Reality_Engine_Node
My node iterators:
#ifndef Second_Reality_Engine_Iterator
#define Second_Reality_Engine_Iterator
#include <srnode.h>
//-----------------------------------------------------------------------------
// NodeIterator
// Desc: A base class for the Node tree iterators
//-----------------------------------------------------------------------------
template <class T>
class NodeIterator
{
public:
Node<T>* GetNode(){return node;};
Node<T>* operator ++();
Node<T>* operator --();
virtual Node<T>* operator =(Node<T>* node)=0;
virtual bool operator !=(Node<T>* node)=0;
//Node<T>* Begin(Node<T>*);
Node<T>* End();
protected:
Node<T> * eNode;
Node<T> * node;
};
//-----------------------------------------------------------------------------
// PreorderIterator
// Desc: Iterates a tree using PreorderTraversal
//-----------------------------------------------------------------------------
template <class T>
class PreorderIterator : public NodeIterator<T>
{
public:
PreorderIterator(){eNode=0;};
~PreorderIterator(){if (eNode) delete eNode;}; // delete the temporary node
Node<T>* operator ++();
Node<T>* operator =(Node<T>* nn);
bool operator !=(Node<T> * nn){return node!=nn;};
Node<T>* Begin(Node<T>*);
Node<T>* End();
};
/*template <class T>
Node<T>* PreorderIterator<T>::Begin(Node<T>* nn)
{
return nn->Root();
}*/
template <class T>
Node<T>* PreorderIterator<T>::End()
{
if (eNode)
{
return eNode;
}
else
{
eNode=new Node<T>;
node->End()->Parent()->AttachChild(eNode);
return eNode;
}
}
template <class T>
Node<T>* PreorderIterator<T>::operator =(Node<T>* nn)
{
return node=nn;
}
template <class T>
Node<T>* PreorderIterator<T>::operator ++()
{
if (!node->Child())
{
if (node->IsLast())
{
node=node->Parent();
while (node->Previous()->IsFirst())
{
node=node->Parent();
}
node=node->Next();
return node;
}
else
{
node=node->Next();
return node;
}
}
else
{
node=node->Child();
return node;
}
}
//-----------------------------------------------------------------------------
// PostorderIterator
// Desc: Iterates a tree using PreorderTraversal
//-----------------------------------------------------------------------------
template <class T>
class PostorderIterator : public NodeIterator<T>
{
public:
PostorderIterator(){eNode=0;};
~PostorderIterator(){if (eNode) delete eNode;};
Node<T>* operator ++();
Node<T>* operator ++(int a);
Node<T>* operator =(Node<T>* nn);
bool operator !=(Node<T> * nn){return node!=nn;};
Node<T>* Begin();
Node<T>* End();
};
#endif // Second_Reality_Engine_Iterator
Thanks.
