Как организовать оптимальное хранение ошибок в иерархической структуре?

Question

[nomit]

Всем привет, столкнулся со следующей задачей, может, кто уже решал.
Есть иерархическая структура, каждый уровень имеет список "Маркеров". Маркер может иметь 3 состояния(Error=0, Warning=1, Normal=2 - приоритет по убыванию).
Если на нижнем уровне существует маркер с ошибкой, то автоматически вышестоящие уровне становятся с ошибкой. Маркеры могут "добавляться" "удаляться" на любом уровне.

Необходимо, взяв любой уровень иерархии, определить состояние уровня.

PS
Можно решить в лоб, каждый раз вычисляя состояние, но это не подойдет.
Еще придумал решение с хранением данных в HashMap. Ключ это объект иерархии, а значение это список упорядоченных пар всех детей уровня ниже с их состоянием, возможно, есть что-то оптимальнее.

Answer 1

[Ubloobok]

Насколько часто приходится вычислять состояния и сколько объектов?

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

Подписываем узел на событие "ИзменениеСостояния" у дочерних узлов. Каждый узел распространяет событие своему родителю, вплоть до корневого. В каждом узле храним признак "isActualState", = "true" если дочерние узлы НЕ оповещали об изменении состояния, = "false" если хотя бы один из дочерних узлов оповестил. После генерации события, происходит перерасчет состояния с повторным вычислением состояния только в той ветке, где реально были изменения (isActualState=false), а от всех остальных будет использоваться текущее хранимое состояние.

Answer 2

[mrstrictly]

Как-то так: pastebin.com/K6Z8JqVT
То есть, идея в том, чтобы подписать узел на событие изменения состояния "маркера" при его добавлении в узел. При этом, узел распространяет события своему родителю (если он есть) вплоть до корневого. Каждый узел хранит компактный набор счетчиков состояний, связанных с его "маркерами" и "маркерами" дочерних узлов. Что-то еще более оптимизировать, на мой взгляд, смысла нет, т.к. TreeMap (O(nlog(n)) с ключом по состоянию -- это и так очень быстро.
Код, разумеется, не thread-safe.

Comments

[nomit]

Спасибо довольно интересное решение.