Есть такой класс — элемент в некоем дереве.

class element {

  collection<element*> children;
  collection<element*> visible_children;

  void visit_tree( std::function<void(element*)> visitor);
};

Нужно написать функцию visit_tree которая посещает детей ровно один раз для данного visitor.

Специфика: коллекция visible_children может содержать как элементы из children так и какие-то другие, в том числе и из глубины иерархии.

Как бы классическая имплементация использует hash_set для обнаружения факта посещения:

  void element::visit_tree( std::function<void(element*)> visitor) {
   
     std::hash_set<uint_ptr> visited; 

     std::function<void(element*)> worker = [&]( element* el) {
        if( visited.has( uint_ptr(el) ) )
           return; 
        visited.put(el);
        visitor(el);
        children.for_each(worker);  
        visible_children.for_each(worker);
     };
  }

Вопрос можно ли как-нибудь обойтись без этого hash_set ?
Я в принципе могу добавить скажем так uint поле в element для маркерных целей.

Проблема осложняется еще тем что visitor функтор в принипе тоже может запускать visit_tree для каких-то других своих целей.

Задача а приниципе сходная с GC mark-n-sweep ситуациями поэтому может кто-то видел более элегантное решение?

Здравствуйте, c-smile, Вы писали:


CS>Вопрос можно ли как-нибудь обойтись без этого hash_set ?
CS>Я в принципе могу добавить скажем так uint поле в element для маркерных целей.

Ну точно не hash_set — это тормоза на ровном месте.

CS>Проблема осложняется еще тем что visitor функтор в принипе тоже может запускать visit_tree для каких-то других своих целей.

Ну 640К uint должно хватить для чего угодно.
Только их потом придется бегать очищать же. Или у тебя обработка однократная?

А деревья меняются по ходу дела? Или создаются вначале и так и живут?
А то можно ведь параллельную структуру данных завести.

Можно ли каждому элементу присвоить номер (в процессе заполнения дерева)? Если да, то вместо hash_set можно использовать просто битовый vector и обращаться к нему по номеру элемента — чистить его очень быстро и легко.
Если у тебя flat tree (т.е. поверх массива) — то это вообще тривиально будет.

You will always get what you always got
  If you always do  what you always did

Здравствуйте, jazzer, Вы писали:

J>Здравствуйте, c-smile, Вы писали:


CS>>Вопрос можно ли как-нибудь обойтись без этого hash_set ?
CS>>Я в принципе могу добавить скажем так uint поле в element для маркерных целей.

J>Ну точно не hash_set — это тормоза на ровном месте.

CS>>Проблема осложняется еще тем что visitor функтор в принипе тоже может запускать visit_tree для каких-то других своих целей.

J>Ну 640К uint должно хватить для чего угодно.
J>Только их потом придется бегать очищать же. Или у тебя обработка однократная?

Обработка неоднократная. Я в принципе могу прикопать где-то некий mask, типа

static uint generation_mask = 1;

class element {

  uint visitor_mask;

  element() : visitor_mask(0) {}

  void element::visit_tree( std::function<void(element*)> visitor) {

     generation_mask <<= 1;

     // проверка на bit 0/1 ...

     std::function<void(element*)> worker = [&]( element* el) {
        if( (visitor_mask & generation_mask) != 0)        
           return; 
        visitor_mask ^= generation_mask; 
        visitor(el);
        children.for_each(worker);  
        visible_children.for_each(worker);
     };

     worker(this);
     
     generation_mask >>= 1;

  }
}

В этом случае глубина вложения visit_tree ограничена 32 что в принципе устраивает.


J>А деревья меняются по ходу дела? Или создаются вначале и так и живут?
J>А то можно ведь параллельную структуру данных завести.

Меняются.

J>Можно ли каждому элементу присвоить номер (в процессе заполнения дерева)? Если да, то вместо hash_set можно использовать просто битовый vector и обращаться к нему по номеру элемента — чистить его очень быстро и легко.
J>Если у тебя flat tree (т.е. поверх массива) — то это вообще тривиально будет.

Не понял что имеется ввиду. Поясни. Элементов много.

Здравствуйте, c-smile, Вы писали:

[]

J>>А деревья меняются по ходу дела? Или создаются вначале и так и живут?
J>>А то можно ведь параллельную структуру данных завести.

CS>Меняются.

J>>Можно ли каждому элементу присвоить номер (в процессе заполнения дерева)? Если да, то вместо hash_set можно использовать просто битовый vector и обращаться к нему по номеру элемента — чистить его очень быстро и легко.
J>>Если у тебя flat tree (т.е. поверх массива) — то это вообще тривиально будет.

CS>Не понял что имеется ввиду. Поясни. Элементов много.

Рискну влезть и предположить, что jazzer имел ввиду, что если все элементы дерева хранятся в одном массиве, а в children и visible_chidlren используются лишь указатели на элементы в этом массиве, то каждому элементу можно сопоставить индекс в массиве. В этом случае visited будет битовым вектором, и признак посещения элемента — это лишь бит по индексу элемента.

Мне кажется, если есть возможность элементам при создании в дереве присваивать возрастающие id = last_used_id++, то при незначительных изменениях в дереве (ну и при условии что элементы не перемещаются между деревьями) все элементы в нем будут иметь индексы от 0 до last_used_id и битовый вектор подойдет в качестве visited.

Здравствуйте, c-smile, Вы писали:

J>>Ну 640К uint должно хватить для чего угодно.
J>>Только их потом придется бегать очищать же. Или у тебя обработка однократная?

CS>Обработка неоднократная. Я в принципе могу прикопать где-то некий mask, типа
CS>В этом случае глубина вложения visit_tree ограничена 32 что в принципе устраивает.

Да, я именно это и имел в виду.

J>>А деревья меняются по ходу дела? Или создаются вначале и так и живут?
J>>А то можно ведь параллельную структуру данных завести.

CS>Меняются.

J>>Можно ли каждому элементу присвоить номер (в процессе заполнения дерева)? Если да, то вместо hash_set можно использовать просто битовый vector и обращаться к нему по номеру элемента — чистить его очень быстро и легко.

Если можно пронумеровать (при создании или отдельным проходом, если дерево редко перетряхивается) — то ты просто заводишь вектор флагов (или интов, если нужно считать количество заходов, или чего угодно еще) размера дерева, и потом в обработчике берешь id элемента и используешь его как индекс в массиве флагов. Рулез в том, что будет ровно одна аллокация и чистить (обнулять) можно банальным memset.
Плюс вектор можно заводить свой на каждый обработчик — код будет примерно такой же, как с hash_set, но гораздо дешевле, во всех смыслах (и скорость доступа, и использование памяти), плюс по нему потом можно быстро сделать агрегацию, если у тебя визитор агрегирующий.
Причем не беда, если в векторе будут дырки из-за того, что какие-то номера изчезли из дерева — тебе ведь для визитации нужно только на текущей номер смотреть: т.е. чистишь один раз, а дальше взводишь/проверяешь флаг.

J>>Если у тебя flat tree (т.е. поверх массива) — то это вообще тривиально будет.

CS>Не понял что имеется ввиду. Поясни. Элементов много.

flat_xxx — это ххх на массиве.
Например, http://www.boost.org/doc/libs/1_55_0/boost/container/detail/flat_tree.hpp (на нем реализованы бустовские flat_(multi)map/set: http://www.boost.org/doc/libs/1_55_0/doc/html/container/non_standard_containers.html#container.non_standard_containers.flat_xxx)

Соответственно если ты можешь реализовать свое дерево на массиве (например, через Boost.Intrusive), то номером элемента естественным образом становится номер ноды в массиве (просто разница указателей) — а дальше как выше, с вектором. Причем в этом случае ты сможешь прыгать из массива флагов в элемент дерева за один шаг — так как есть взаимно-однозначное соответствие между ними.

You will always get what you always got
  If you always do  what you always did

Здравствуйте, c-smile, Вы писали:

CS>Специфика: коллекция visible_children может содержать как элементы из children так и какие-то другие, в том числе и из глубины иерархии.

Казалось бы! Если множество children со всеми вложенными покрывает множество visible_children со всеми их вложенными, то достаточно пробежаться только по children.

Расскажи подробнее про порядок обхода.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, c-smile, Вы писали:

CS>>Специфика: коллекция visible_children может содержать как элементы из children так и какие-то другие, в том числе и из глубины иерархии.

К>Казалось бы! Если множество children со всеми вложенными покрывает множество visible_children со всеми их вложенными, то достаточно пробежаться только по children.

К>Расскажи подробнее про порядок обхода.

Врядли. Я так понял ситуацию:
children — это непосредственно дети элемента
visible_children — то что отображается — здесь отработают какие нибудь фильтры над children + дети могут приходить с нижних иерархий, например в каком нибудь случае уплощения дерева, когда детей с нижних иерархий надо передвинуть в рутовую ноду.

Если это так, то у меня в голове возникает пока такая простая мысль: пройтись по всем нодам и сохранить указатели на них, потом в полученном массиве удалить дупликаты и потом пустить по этому массиву визитор.

Здравствуйте, korzhik, Вы писали:

К>>Казалось бы! Если множество children со всеми вложенными покрывает множество visible_children со всеми их вложенными, то достаточно пробежаться только по children.

K>Врядли. Я так понял ситуацию:
K>children — это непосредственно дети элемента

Так я же сказал: "множество со всеми вложенными", т.е. дети детей и т.д.

K>visible_children — то что отображается — здесь отработают какие нибудь фильтры над children + дети могут приходить с нижних иерархий, например в каком нибудь случае уплощения дерева, когда детей с нижних иерархий надо передвинуть в рутовую ноду.

K>Если это так, то у меня в голове возникает пока такая простая мысль: пройтись по всем нодам и сохранить указатели на них, потом в полученном массиве удалить дупликаты и потом пустить по этому массиву визитор.


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

Либо это не дерево, а чёрт знает что.
Либо порядок обхода какой-нибудь хитрый вширь с опережениями, а не вглубь: например, оббежали непосредственных детей и видимых; затем спустились на уровень ниже и повторили процедуру (за вычетом ранее посещённых видимых).

Здравствуйте, jazzer, Вы писали:

J>Соответственно если ты можешь реализовать свое дерево на массиве (например, через Boost.Intrusive), то номером элемента естественным образом становится номер ноды в массиве (просто разница указателей) — а дальше как выше, с вектором. Причем в этом случае ты сможешь прыгать из массива флагов в элемент дерева за один шаг — так как есть взаимно-однозначное соответствие между ними.

Если нет необходимости заводить много разных флагов, причём заранее не известно сколько, то можно хранить эти флаги в самих узлах (которые лежат в массиве) — это может быть быстрее чем отдельный массив, так как меньше индерекций/random access.

С отдельным массивов флагов будет сначала random access в этот массив, а потом к самому элементу. Зато очистка флагов супер-быстрая, да и размер массива флагов намного меньше массива узлов.
С интрузивными флагами будет один random access (точнее для больших объектов могут быть загружены несколько последовательных cache line). Очистка будет медленней чем memset, но это всё же последовательный обход, пусть и с константными прыжками.

Вообще, если гарантированно обходятся все элементы, то очистка флагов необязательна — достаточно помнить какое значение флага в этот раз обозначает visited. При такой схеме можно с уверенностью сказать, что отдельный массив флагов будет медленней (за счёт лишних индерекций).

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Здравствуйте, jazzer, Вы писали:

J>>Соответственно если ты можешь реализовать свое дерево на массиве (например, через Boost.Intrusive), то номером элемента естественным образом становится номер ноды в массиве (просто разница указателей) — а дальше как выше, с вектором. Причем в этом случае ты сможешь прыгать из массива флагов в элемент дерева за один шаг — так как есть взаимно-однозначное соответствие между ними.

EP>Если нет необходимости заводить много разных флагов, причём заранее не известно сколько, то можно хранить эти флаги в самих узлах (которые лежат в массиве) — это может быть быстрее чем отдельный массив, так как меньше индерекций/random access.

так это и обсуждалось же сначала

EP>С отдельным массивов флагов будет сначала random access в этот массив, а потом к самому элементу. Зато очистка флагов супер-быстрая, да и размер массива флагов намного меньше массива узлов.
EP>С интрузивными флагами будет один random access (точнее для больших объектов могут быть загружены несколько последовательных cache line). Очистка будет медленней чем memset, но это всё же последовательный обход, пусть и с константными прыжками.

Дык никто не спорит, что встроенные флаги быстрее. Просто они для общего случая не подходят, если визиторы разные и им хранить нужно разное.

EP>Вообще, если гарантированно обходятся все элементы, то очистка флагов необязательна — достаточно помнить какое значение флага в этот раз обозначает visited. При такой схеме можно с уверенностью сказать, что отдельный массив флагов будет медленней (за счёт лишних индерекций).

А если иметь flat tree и порядок обхода не важен — то можно вообще просто напрямую по массиву пройтись и забить на то, что это дерево

You will always get what you always got
  If you always do  what you always did

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, c-smile, Вы писали:

CS>>Специфика: коллекция visible_children может содержать как элементы из children так и какие-то другие, в том числе и из глубины иерархии.

К>Казалось бы! Если множество children со всеми вложенными покрывает множество visible_children со всеми их вложенными, то достаточно пробежаться только по children.

Это HTML DOM tree. children это то что описано в исходном HTML, visible_children это то что рендерится.

Пример, исходный markup:

<table>
  <tr><td>1</td></tr>
</table>

А вот rendering tree:

<table>
  <tbody>
    <tr><td>1</td></tr>
  </tbody>
</table>

В этом случае tbody создано искусственно. Т.е. rendering tree содержит элементы которых нет в children.

В другом случае какие-то элементы могут быть display:none — есть в children (C set) но их не будет в visible_children (V set)

К>Расскажи подробнее про порядок обхода.

Т.е. нужно обходить всегда и С и V — множество C ∪ V математически говоря.

Ибо в общем случае:

(C ⋂ V) ∉ C
(C ⋂ V) ∉ V

Здравствуйте, korzhik, Вы писали:


K>Врядли. Я так понял ситуацию:
K>children — это непосредственно дети элемента
K>visible_children — то что отображается — здесь отработают какие нибудь фильтры над children + дети могут приходить с нижних иерархий, например в каком нибудь случае уплощения дерева, когда детей с нижних иерархий надо передвинуть в рутовую ноду.

Да так и есть.

K>Если это так, то у меня в голове возникает пока такая простая мысль: пройтись по всем нодам и сохранить указатели на них, потом в полученном массиве удалить дупликаты и потом пустить по этому массиву визитор.

1. Построить массив.
2. Создать hash_set за для обнаружения дупликатов.

Это еще хуже чем мой начальный вариант. Там только hash_set.

Здравствуйте, jazzer, Вы писали:

J>А если иметь flat tree и порядок обхода не важен — то можно вообще просто напрямую по массиву пройтись и забить на то, что это дерево

Мой парсер завис на сочетании flat tree ...

Как я понимаю это вектор содержащий все элементы дерева от root.

А как это все планируется обходить если нужно обойти только под-дерево?
И как maintain этот массив? Дерево живое — постоянно меняется. Делать из него двусвязный список разве-что. Но это накладно во многих смыслах.

Здравствуйте, c-smile, Вы писали:

<>
А почему нужно обязательно тащить рядом две иерархии?
Нельзя ли сделать одну объединяющую — при этом каждый узел имеет пометку "оригинальный/домысленный" (tbody) и "видимый/невидимый".

Забег по оригинальным сводится к обходу вглубь всех узлов, но визитёр дёргается только на оригинальных.
Забег по видимым — к обходу вглубь с полным игнорированием невидимых.
Забег по всем — к обходу вглубь.

И не надо при этом париться синхронизацией двух деревьев.

Я не спрашиваю, зачем вообще хранить оригинальную структуру. Ну прочитали html, распарсили, домыслили до канонического вида... И всё, дальше работай себе с каноническим, со всей этой кучей tbody.

Здравствуйте, c-smile, Вы писали:

CS>Здравствуйте, jazzer, Вы писали:

J>>А если иметь flat tree и порядок обхода не важен — то можно вообще просто напрямую по массиву пройтись и забить на то, что это дерево

CS>Мой парсер завис на сочетании flat tree ...

Ну это относительно стандартный термин, я так понимаю... Когда в памяти все кусочком лежит, а не разбросано по всей куче

CS>Как я понимаю это вектор содержащий все элементы дерева от root.

да. Вернее, не элементы, а узлы.

CS>А как это все планируется обходить если нужно обойти только под-дерево?
Ну у узла же есть ссылки на детей/родителей. Так что все чтоно так же.

CS>И как maintain этот массив? Дерево живое — постоянно меняется. Делать из него двусвязный список разве-что.
Зачем список? Дерево. Ты же можешь несколько ссылок (указателей, или вообще индексов в массиве, чтоб проще было растить вектор) в узле хранить — на родителя, на своего первого ребенка, на следующего своего брата (с тем же родителем)...

CS>Но это накладно во многих смыслах.

Ну тут, как и во многих таких случаях, однозначного ответа нет, все зависит от сценария использования.
Оно вот действительно постоянно меняется? Вот прям на каждый третий чих? Или максимум пара нодов там/сям вставится (типа твоего tbody)?
Надо смотреть на твои реальные сценарии и считать, какой вариант дороже выйдет.
Ты это все лучше нас знаешь, а нам маловато условий.

You will always get what you always got
  If you always do  what you always did

Здравствуйте, c-smile, Вы писали:

CS>Задача а приниципе сходная с GC mark-n-sweep ситуациями поэтому может кто-то видел более элегантное решение?

В итоге постулирую следуюшую лемму: задача в данной постановке (однократное сканирование) не
может быть решена с использованием переменных состояния сохраняемых в самих элементах/узлах.

Только с использованием внешнего storage т.е. это код ниже и его вариации есть единственный разумный способ.

 void element::visit_tree( std::function<void(element*)> visitor) {
   
     std::hash_set<uint_ptr> visited; 

     std::function<void(element*)> worker = [&]( element* el) {
        if( visited.has( uint_ptr(el) ) )
           return; 
        visited.put(el);
        visitor(el);
        children.for_each(worker);  
        visible_children.for_each(worker);
     };
  }

То же относится и графам содержащих циклы например.

Здравствуйте, c-smile, Вы писали:

CS>Здравствуйте, c-smile, Вы писали:

CS>>Задача а приниципе сходная с GC mark-n-sweep ситуациями поэтому может кто-то видел более элегантное решение?

CS>В итоге постулирую следуюшую лемму: задача в данной постановке (однократное сканирование) не
CS>может быть решена с использованием переменных состояния сохраняемых в самих элементах/узлах.

В смысле, это изменение требований?
В чем проблема добавить флажок/флажки в элементы?
Вон в Boost.Graph навешивают дополнительные данные на узлы только в путь.

CS>Только с использованием внешнего storage т.е. это код ниже и его вариации есть единственный разумный способ.

Тогда зависит от того, насколько часто и катастрофически перетряхивается дерево.
Потому что если нечасто или несильно — может, подойдет вариант с нумерацией и, соответственно, массивом вместо hash_set?

You will always get what you always got
  If you always do  what you always did

Здравствуйте, c-smile, Вы писали:

CS>В итоге постулирую следуюшую лемму: задача в данной постановке (однократное сканирование) не
CS>может быть решена с использованием переменных состояния сохраняемых в самих элементах/узлах.

Если есть ожидаемые сценарии использования, то имхо можно подобрать какой-нибудь комбинрованный вариант — например завести байт под флажки в элементе: при каждом новом рекурсивном обходе использовать следующий свободный бит, если глубина рекурсии превышает количество бит в типе под флажки переходить на "медленное" решение с внешним хранилищем.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, c-smile, Вы писали:

CS>>В итоге постулирую следуюшую лемму: задача в данной постановке (однократное сканирование) не
CS>>может быть решена с использованием переменных состояния сохраняемых в самих элементах/узлах.

А>Если есть ожидаемые сценарии использования, то имхо можно подобрать какой-нибудь комбинрованный вариант — например завести байт под флажки в элементе: при каждом новом рекурсивном обходе использовать следующий свободный бит, если глубина рекурсии превышает количество бит в типе под флажки переходить на "медленное" решение с внешним хранилищем.

Этот алгоритм я и описал здесь:
http://rsdn.ru/forum/cpp.applied/5669052.1

Автор: c-smile
Дата: 01.07.14

Он работает в принципе, но только в случае если допускается двойной проход по дереву — второй раз нужно сбросить флаги элементов в исходное состояние.

Здравствуйте, jazzer, Вы писали:

J>Здравствуйте, c-smile, Вы писали:

CS>>Здравствуйте, c-smile, Вы писали:

CS>>>Задача а приниципе сходная с GC mark-n-sweep ситуациями поэтому может кто-то видел более элегантное решение?

CS>>В итоге постулирую следуюшую лемму: задача в данной постановке (однократное сканирование) не
CS>>может быть решена с использованием переменных состояния сохраняемых в самих элементах/узлах.

J>В смысле, это изменение требований?

Нет, требования не изменились.

J>В чем проблема добавить флажок/флажки в элементы?

Проблемы нет.

J>Вон в Boost.Graph навешивают дополнительные данные на узлы только в путь.

"навешивают дополнительные данные" именно для целей однократного обхода?

CS>>Только с использованием внешнего storage т.е. это код ниже и его вариации есть единственный разумный способ.

J>Тогда зависит от того, насколько часто и катастрофически перетряхивается дерево.

Практически любое изменение DOM на странице. В случае RSDN сайта это например открытие/закрытие узлов в дереве форумов.

J>Потому что если нечасто или несильно — может, подойдет вариант с нумерацией и, соответственно, массивом вместо hash_set?

Часто. И потом нумерация (сквозная) это тоже проход по дереву в общем случае.

Здравствуйте, c-smile, Вы писали:

CS>В итоге постулирую следуюшую лемму: задача в данной постановке (однократное сканирование) не
CS>может быть решена с использованием переменных состояния сохраняемых в самих элементах/узлах.

Почему это не может?

Заводим для каждого узла переменную — токен.
Перед сканированием создаём уникальное значение токена.
В ходе сканирования проверяем и, если он отличается, присваиваем.
При модификации дерева новым узлам присваиваем последнее использованное значение токена, тем самым мы гарантируем, что перекрутка нам не грозит.
Либо выделяем под токен заведомо многоразрядный числовой тип, чтобы перекрутка нам в принципе не грозила. Это зависит от твоих ожиданий, как часто сканировать и как долго жить. 64 бит, скорее всего, хватит.

Здравствуйте, Кодт, Вы писали:

К>Почему это не может?

К>Заводим для каждого узла переменную — токен.
К>Перед сканированием создаём уникальное значение токена.
К>В ходе сканирования проверяем и, если он отличается, присваиваем.

Скажем есть дерево у которого nodes имеют имена A,B,C и т.д.
И есть узел

Z = {
  kids : [ A, B, C ];
  vkids : [ A, F, G ];
}

после тривиального сканирования только kids имеем такое состояние:

Начальный токен = 1

Z(1) = {
  kids : [ A(1), B(1), C(1) ];
  vkids : [ A(1), D, E ];
}

после сканирования оставшихся vkids имеем:

Z(1) = {
  kids : [ A(1), B(1), C(1) ];
  vkids : [ A(1), D(1), E(1) ];
}

so far so good как говорится.

Теперь то же самое но с учетом "Проблема осложняется еще тем что visitor функтор в принипе тоже может запускать visit_tree для каких-то других своих целей."

Запускаем scan tree еще раз для kids, каждый visit запускает свой scan (наращивая token)

Начальный токен теперь = 2

Z(2) = {
  kids : [ A(3), B(4), C(5) ];
  vkids : [ A(3), D(1), E(1) ];
}

и если теперь мы запустим сканирование vkids то т.к. 2 != 3 мы опять зайдем в A.
Что по условию задачи недопутимо.

Здравствуйте, c-smile, Вы писали:

CS>Теперь то же самое но с учетом "Проблема осложняется еще тем что visitor функтор в принипе тоже может запускать visit_tree для каких-то других своих целей."

А, ну если обход реентерабельный, то конечно, всё плохо. Нужно каждому узлу приписать столько булевых признаков "посещено", сколько одновременных обходов допускается.

Эти булевы признаки, ясное дело, можно представить или как индивидуальные метки узлов, или как вхождение в централизованные множества, присущие каждой процедуре обхода.

Надо заметить, что неограниченный реентер — это смерть приложению. Если он возникает, надо паниковать и заменять синхронную рекурсию на асинхронную, — т.е. визитёр не лезет немедленно, а создаёт отложенную задачу, которая выполнится после обхода.
Можно пойти по пути фортран-3 и запретить рекурсию в принципе. Первый зашёл, второй зашёл и тут же получил по пальцам: давай-ка, откладывай!

А можно и не зверствовать, а работать с централизованными множествами.


Следующий неприятный момент для осознания.
Если визитёр меняет структуру дерева, то он и сам себе может в ногу выстрелить, а уж в условиях реентера — выстрелить и родительской процедуре обхода.
Как это разруливать? Загадка. Одно из направлений — чисто функциональные иммутабельные структуры данных и версионирование.
Самая примитивная реализация — это делать слепок коллекции перед обходом.

(А может, ну его нафиг и махнуть в Саранск? )

Здравствуйте, Кодт, Вы писали:

К>(А может, ну его нафиг и махнуть в Саранск? )

Где-то таким образом я и поступил На Хаш, на Мапск состав отправится, вагончик тронется, перон останентся ...

Здравствуйте, c-smile, Вы писали:

CS>Здравствуйте, Аноним, Вы писали:

CS>Он работает в принципе, но только в случае если допускается двойной проход по дереву — второй раз нужно сбросить флаги элементов в исходное состояние.

Опять же, можно добавить ещё один счётчик — идентификатор нового (невложенного) поиска, и если у узла он отличается от текущего значения, считать при сравнении что флаг посещений нулевой. Придётся правда сбрасывать все флаги у всех элементов когда этот счётчик переполнится.

Ещё можно хранить эти флаги в отдельном массиве, а в элементах — индекс в массиве и при сбросе просто обнулять весь массив. Но тут всё сильно зависит от деталей задачи, как часто что и где меняется и обходится.