Печать страницы - Универсальный итератор дерева

Мне частенько приходится работать с разнообразными структурами данных, которые являются деревьями. Частая при этом задача - простой обход всех элементов дерева, обычно решается написанием рекурсивной функции. Но, написав в стодвадцатый раз очередную такую функцию, мне надоело и я сделал универсальный итератор дерева.

Этот итератор может работать с любыми деревьями, узлы которых доступны по указателю или по значению. Список детей должен соответствовать требованиям списков stl (begin(), end(), const_iterator ...).

Пример использования с QObject:

Код

C++ (Qt)
QObject* root_object;
 
// submit tree node type and child list type
tree_iterator<QObject*, QObjectList> it(
    boost::bind(&QObject::children, _1), // submit child list receive method
    root_object // root object
);
 
// iterate all tree nodes
for (; it != it.end(); ++it)
{
    std::cout << it->objectName() << std::endl;
}

Исходник:

Код

C++ (Qt)
#pragma once
 
#include <stack>
#include <boost/function.hpp>
 
/*!
 
 Example:
 
 \code
 
tree_iterator<node_p, tree_node::childs_t> it(
    boost::bind(&tree_node::childs, _1), root);
do
{
    LOG_DEBUG << it.current()->name();
}
while (it.next());
 
tree_iterator<node_p, tree_node::childs_t> it(
    boost::bind(&tree_node::childs, _1), root);
for (; it != it.end(); ++it)
{
    LOG_DEBUG << it->name();
}
 
 \endcode
 
 
*/
template <typename NODE, typename LIST>
class tree_iterator
{
public:
    typedef NODE node_t;
    typedef LIST list_t;
    typedef typename LIST::const_iterator list_iterator_t;
    typedef boost::function<const list_t& (const node_t&)> childs_method_t;
 
    /*! Iterator constructor. */
    tree_iterator(childs_method_t childs, const node_t& root);
 
    /*! Current node */
    const node_t& current() const {return *current_;}
 
    /*! Go next node. Return false if no more nodes in tree. */
    bool next();
 
    /*! Iterator at end? */
    bool at_end() const {return at_end_;}
 
    tree_iterator& operator++();
 
    bool operator==(const tree_iterator& it) const;
    bool operator!=(const tree_iterator& it) const;
    const node_t& operator*() const {return *current_;}
    const node_t& operator->() const {return *current_;}
 
    /*! End of tree iterator. Needed to compare with end. */
    const tree_iterator& end();
 
private:
    struct iterators
    {
        iterators(list_iterator_t current_, list_iterator_t end_)
        : current(current_), end(end_)
        {}
 
        list_iterator_t current;
        list_iterator_t end;
    };
    typedef std::stack<iterators> stack_t;
 
    childs_method_t childs_;
    const node_t* current_;
    stack_t stack_;
    bool at_end_;
};
 
 
////////////////////////////////////////////////////////////////////////////////
// implementation
 
template <typename NODE, typename LIST>
tree_iterator<NODE, LIST>::tree_iterator(childs_method_t childs, const node_t& root)
: childs_(childs)
, current_(&root)
, at_end_(false)
{
    const list_t& list = childs_(*current_);
    iterators it(list.begin(), list.end());
    stack_.push(it);
}
 
template <typename NODE, typename LIST>
bool tree_iterator<NODE, LIST>::next()
{
    iterators& it = stack_.top();
 
    // no more items
    if (it.current == it.end)
    {
        at_end_ = true;
        return false;
    }
 
    current_ = &(*(it.current));
 
    // try moving down
    const list_t& list = childs_(*current_);
    if (list.begin() != list.end())
    {
        iterators it(list.begin(), list.end());
        stack_.push(it);
        return true;
    }
 
    // try moving right
    ++it.current;
    if (it.current != it.end)
        return true;
 
    // try moving up
    while (stack_.size() > 1)
    {
        stack_.pop();
        iterators& it = stack_.top();
        ++it.current;
        if (it.current != it.end)
            return true;
    }
    return true;
}
 
template <typename NODE, typename LIST>
tree_iterator<NODE, LIST>& tree_iterator<NODE, LIST>::operator++()
{
    next();
    return *this;
}
 
template <typename NODE, typename LIST>
const tree_iterator<NODE, LIST>& tree_iterator<NODE, LIST>::end()
{
    return *((tree_iterator<NODE, LIST>*)NULL);
}
 
template <typename NODE, typename LIST>
bool tree_iterator<NODE, LIST>::operator==(const tree_iterator& it) const
{
    if (&it)
    {
        return it.at_end_ == at_end_ || it.current_ == it.current_;
    } else
        return at_end_;
}
 
template <typename NODE, typename LIST>
bool tree_iterator<NODE, LIST>::operator!=(const tree_iterator& it) const
{
    return !(*this == it);
}

Если надо могу еще пару примеров использования доложить :)

Russian Qt Forum

Qt => Кладовая готовых решений => Тема начата: navrocky от Сентябрь 08, 2010, 15:42