• Advertisement

Archived

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

Tree Iterators

This topic is 5848 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

I am writing a tree structure - actually a skeleton structure since I''m eventually planning to use it for animation. Each node (or bone) looks something like this
template<class T> class Bone {

    Bone* parent;
    vector<Bone *> children;

    T *object;
    ...

    inline vector<Bone *>::iterator first_child(void) {
        return children.begin();
    }

    inline vector<Bone *>::iterator last_child(void) {
        return children.end();
    }

    ...
};
 
with pointers to the parent Bone, the actual object, and a vector containing any children of the bone. A skeleton is just made up of a bunch of bones in the usual way. The skeleton_iterator class is defined as follows (thanks to this article")
template<class T> class skeleton_iterator {

    stack<vector<Bone<T> *>::iterator> bStack;

    typedef std::forward_iterator_tag iterator_category;
    typedef T value_type;
    typedef std::ptrdiff_t difference_type;
    typedef T*& reference;
    typedef T** pointer;
    typedef Bone<T>* boneptr;

    reference operator*() const { return p->object; }
    pointer operator->() const { return &(p->object); }

    boneptr p;

    skeleton_iterator(boneptr x) : p(x) {
       bStack.push(&p);
    }
    
    ...

};
 
And after that I struggled with a ++ operator for the weekend Basically the idea was to start off at the root node which is returned by a skeleton::begin(). After that current thingy the iterator is pointing to is the object in the boneptr p. To increment it checks to see if p has any children. If it does it moves down to the first child and sticks a vector<Bone *>::iterator to p''s children into the bStack. If p has no children it increments the last vector<Bone *>iterator in the bStack. If this is then the last of the children it moves up the stack, otherwise it moves on to the next child. Something like this:
skeleton_iterator& operator++() {
    if(p->first_child()) {
        bStack.push(p->first_child());
        p = *bStack.top();
    }

    else {
        while (++bStack.top() == p->parent->last_child()) {
            bStack.pop();
            p = *bStack.top();
        }
        p = *bStack.top();
    }

    return *this;
}
 
To terminate I have this global dummy Bone whose object member points to nothing. This is stuck in as the last child of the root Bone and is also returned by skeleton::end() so
skeleton<blah>::iterator i = S.begin();
while (i != S.end()) {
    ...
    ++i;
}
 
behaves as expected. (it was all I could think of) If anyone is interested the entire code is here It seems to work OK but if anyone has any comments I''d appreciate them.

Share this post


Link to post
Share on other sites
Advertisement

  • Advertisement