Здравствуйте, 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>Он работает в принципе, но только в случае если допускается двойной проход по дереву — второй раз нужно сбросить флаги элементов в исходное состояние.

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

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