Придумал простой итератор для обхода произвольного дерева:
(для облегчения кода прежде всего)
Эта фича позволяет сильно облегчить код и делать так:
Обходит дерево в таком же порядке как и такая рекурсия:
1. проваливаемся в самый низ по цепочке first_child->first->child->… (это самая левая ветка если картинку нарисовать)
2. запоминаю, что надо вернуть найденный элемент
3. переключаю итератор на следующий элемент, который верну при след. Next()
при этом, если поднимаюсь наверх — ставлю защиту от проваливания вниз в то же место — ставлю iter.bottom
(при этом если у него есть дети — то он опять провалится вниз, как и надо, при вызове Next())
Это офигенно удобно, когда нужно сделать много разных действий с деревом в разных местах кода. Особенно, когда доступ к дереву нужен из других классов.
Если использовать способ с рекурсией — то придется писать кучу неудобных, некрасивых вспомогательных функций. А так — работа с деревом через простой итератор:
UPD:
[14:26:11] Petrov: вот мне встречались такого типа алгоритмы про это:
www.perlmonks.org/?node_id=600456
(для облегчения кода прежде всего)
struct Document<br/>{<br/> Concept *root;<br/> struct Iter<br/> {<br/> Concept *start;<br/> Concept *cur;<br/> Concept *bottom;<br/> }iter;<br/> <br/> Concept* Begin(Concept *c)<br/> {<br/> iter.start = c;<br/> iter.cur = c;<br/> iter.bottom = 0;<br/> return Next();<br/> }<br/> Concept * Next()<br/> {<br/> if (!iter.cur) return 0;<br/> <br/> while (iter.cur != iter.bottom && iter.cur->first_child)<br/> iter.cur = iter.cur->first_child;<br/> <br/> Concept *ret = iter.cur;<br/> <br/> if (iter.cur == iter.start)<br/> iter.cur = 0;<br/> else if (iter.cur->next)<br/> iter.cur = iter.cur->next;<br/> else <br/> {<br/> iter.cur = iter.cur->parent;<br/> iter.bottom = iter.cur;<br/> }<br/> return ret;<br/> }<br/>};<br/> <br/>
Эта фича позволяет сильно облегчить код и делать так:
Concept *clicked = ConceptFromMouse();<br/>for (Concept *c = document->Begin(clicked); c; c=document->Next())<br/>{<br/> DoSomething( c );<br/>} <br/>
Обходит дерево в таком же порядке как и такая рекурсия:
void DoSomethingHelper(root)<br/>{<br/> for (Concept *c = root; c; c=c->next)<br/> {<br/> DoSomethingHelper(c->first_child);<br/> }<br/> DoSomething(root);<br/>}<br/> <br/>
Описание работы:
1. проваливаемся в самый низ по цепочке first_child->first->child->… (это самая левая ветка если картинку нарисовать)
2. запоминаю, что надо вернуть найденный элемент
3. переключаю итератор на следующий элемент, который верну при след. Next()
при этом, если поднимаюсь наверх — ставлю защиту от проваливания вниз в то же место — ставлю iter.bottom
(при этом если у него есть дети — то он опять провалится вниз, как и надо, при вызове Next())
Применение:
Это офигенно удобно, когда нужно сделать много разных действий с деревом в разных местах кода. Особенно, когда доступ к дереву нужен из других классов.
Если использовать способ с рекурсией — то придется писать кучу неудобных, некрасивых вспомогательных функций. А так — работа с деревом через простой итератор:
void DocumentEditor::OnDrag( Concept *con, float dx, float dy )<br/>{<br/> // drag with childs<br/> for (Concept *c = document->Begin(con); c; c=document->Next())<br/> {<br/> c->x += dx;<br/> c->y += dy;<br/> }<br/>} <br/>
UPD:
[14:26:11] Petrov: вот мне встречались такого типа алгоритмы про это:
www.perlmonks.org/?node_id=600456