Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Tree Node Iterator Problems!

This topic is 5587 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!