Iterator to traverse entire scene?

[mjstone]

Is there an iterator hidden somewhere that traverses the whole scene graph? I'd like to use some of the standard C++ algorithms and maybe BOOST_FOREACH on it. For example:

Code: Select all

GraphIterator specialNode = std::find_if(GraphIterator(myScene), GraphIterator(), &isSpecial);

[hybrid]

No STL/boost in the Irrlicht internals, so no, you have to traverse on your own.

[vitek]

You could easily create such an iterator if you really needed it.

Travis

[mjstone]

Well, I'm not sure about "easily" but yes, that's probably what I'll do. I just wanted to save myself the trouble if somebody else has done it already.

[mjstone]

In case others find it useful, here's what I came up with. It uses boost::iterator_facade to take care of the boilerplate and provide a fully standard-compliant iterator.

Firstly it needs the following patch to irrList.h to make the dereference operators const. (This is against the 1.5 release):

Code: Select all

Index: irrList.h
===================================================================
--- irrList.h	(revision 1815)
+++ irrList.h	(working copy)
@@ -114,8 +114,8 @@
 		bool operator ==(const Iterator&      other) const { return Current == other.Current; }
 		bool operator !=(const Iterator&      other) const { return Current != other.Current; }
 
-		const T & operator * () { return Current->Element; }
-		const T * operator ->() { return &Current->Element; }
+		const T & operator * () const { return Current->Element; }
+		const T * operator ->() const { return &Current->Element; }
 
 		ConstIterator & operator =(const Iterator & iterator) { Current = iterator.Current; return *this; }
 

Here's the scene iterator:

Code: Select all

#include "irrlicht.h"
#include "boost/iterator/iterator_facade.hpp"
#include <stack>


class SceneIterator : public boost::iterator_facade
    < SceneIterator
    , irr::scene::ISceneNode*
    , boost::forward_traversal_tag
    , irr::scene::ISceneNode*
    > 
{
public:
    SceneIterator() {}

    explicit SceneIterator(irr::scene::ISceneManager* scene) {
        beginChildren(scene->getRootSceneNode());
    }

    // Non-standard iterator member, handy for pretty printing.
    std::size_t depth() const {
        return iterStack.size();
    }

private: // functions for iterator_facade:

    friend class boost::iterator_core_access;

    void increment() {
        // preorder depth first traversal (i.e. parent first)
        if (!beginChildren(*iterStack.top())) {
            nextSibling();
        }
    }

    bool equal(SceneIterator const& other) const {
        return iterStack == other.iterStack && currentEnd == other.currentEnd;
    }

    irr::scene::ISceneNode* dereference() const { 
        return *iterStack.top();
    }

private: // tree walking implementation:
    typedef irr::core::list<irr::scene::ISceneNode*>::ConstIterator ChildIter;

    bool beginChildren(irr::scene::ISceneNode* parent) {
        if (parent->getChildren().empty()) {
            return false;
        }
        else {
            iterStack.push(parent->getChildren().begin());
            currentEnd = parent->getChildren().end();
            return true;
        }
    }

    void nextSibling() {
        ++iterStack.top();
        while (!iterStack.empty() && iterStack.top() == currentEnd) {
            iterStack.pop();
            if (!iterStack.empty()) {
                currentEnd = (*iterStack.top())->getParent()->getChildren().end();
                ++iterStack.top();
            }
            else {
                currentEnd = ChildIter();
            }
        }
    }

    std::stack<ChildIter> iterStack;
    ChildIter currentEnd;
};

You can use it like this:

Code: Select all

    // default-constructed iterator is the "end".
    SceneIterator end; 

    // pretty print the tree (using i.depth())
    for (SceneIterator i=SceneIterator(sceneManager); i!=end; ++i) {
        std::cout << std::string(i.depth(), '\t') << "'" << (*i)->getName() << "'" << std::endl;
    }

    // find the first debug node (with some boost::bind magic)
    SceneIterator i = std::find_if(SceneIterator(sceneManager), end, boost::bind(&ISceneNode::isDebugObject, _1));
    if (i != end) std::cout << (*i)->getName() << std::endl;