Мне частенько приходится работать с разнообразными структурами данных, которые являются деревьями. Частая при этом задача - простой обход всех элементов дерева, обычно решается написанием рекурсивной функции. Но, написав в стодвадцатый раз очередную такую функцию, мне надоело и я сделал универсальный итератор дерева.
Этот итератор может работать с любыми деревьями, узлы которых доступны по указателю или по значению. Список детей должен соответствовать требованиям списков 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);
}
Если надо могу еще пару примеров использования доложить
