Russian Qt Forum

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



Название: Универсальный итератор дерева
Отправлено: navrocky от Сентябрь 08, 2010, 15:42
Мне частенько приходится работать с разнообразными структурами данных, которые являются деревьями. Частая при этом задача - простой обход всех элементов дерева, обычно решается написанием рекурсивной функции. Но, написав в стодвадцатый раз очередную такую функцию, мне надоело и я сделал универсальный итератор дерева.

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

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


Название: Re: Универсальный итератор дерева
Отправлено: Авварон от Сентябрь 08, 2010, 20:06
а нахрена ради обычной темплейт функции таскать буст? листа в std прямо нету


Название: Re: Универсальный итератор дерева
Отправлено: zenden от Сентябрь 08, 2010, 21:42
Авварон
Зачем так грубо отвечать? Так вы всех альтруистов распугаете...


Название: Re: Универсальный итератор дерева
Отправлено: Авварон от Сентябрь 08, 2010, 22:45
да идея с разделом конечно хорошая, но код реально стремный. Если уж кладете код, то причешите, уберите лишние зависимости, избавьтесь от утечек. Чтоб совсем хорошо было, соблюдите кодинг-стайл троллей


Название: Re: Универсальный итератор дерева
Отправлено: navrocky от Сентябрь 08, 2010, 23:02
а нахрена ради обычной темплейт функции таскать буст?

што? в boost.function можно биндить методы..

Цитировать
листа в std прямо нету

это о чем?

зыж и вообще я считаю что кодить на плюсах и не использовать буст - это мягко говоря.. недальновидно

Цитировать
Чтоб совсем хорошо было, соблюдите кодинг-стайл троллей

не весь код касается Qt, причем тут ихний кодинг-стайл..


Название: Re: Универсальный итератор дерева
Отправлено: Авварон от Сентябрь 08, 2010, 23:16
ну то есть ради ОДНОГО тайпдефа мне надо тащить весь буст?
спасибо, я заюзаю обычный коллбэк


Название: Re: Универсальный итератор дерева
Отправлено: navrocky от Сентябрь 08, 2010, 23:33
ну то есть ради ОДНОГО тайпдефа мне надо тащить весь буст?
спасибо, я заюзаю обычный коллбэк
каким образом обычным коллбэком можно биндить методы? тогда придется объявлять дополнительную функцию, а это уже геморрой..


Название: Re: Универсальный итератор дерева
Отправлено: Авварон от Сентябрь 09, 2010, 13:51
меньший, чем разбираться в бусте


Название: Re: Универсальный итератор дерева
Отправлено: navrocky от Сентябрь 09, 2010, 15:30
Да я не спорю, хочется работать больше руками, пожалуйста.. Это конечно проще, чем "разобраться" в бусте.


Название: Re: Универсальный итератор дерева
Отправлено: Авварон от Сентябрь 09, 2010, 16:05
1 строчка тайпдефа очень сложно разобраться "руками"