Отслеживание счетчиков

[Igors]

Добрый день

Есть такая структурка

Код

C++ (Qt)
struct Node {
  ...
  Node * m_owner; 
  QList<Node *> m_child;   // чайлв ноды
 
  QScopedPointer<Container> m_data;  // контейнер данных
};

Нод может быть или "папкой" (тогда mData = null) или "листом" (есть m_data но нет чайлдов), но не тем и другим вместе.

Для UI нужно знать максимальное число эл-тов что сидят в ноде m_data. Для нода-листа это просто m_data->size(). Для узла это макс из всех его чайлдов рекурсивно. Ну и надо знать макс по всем нодам. Дерево довольно развесистое, поэтому пробегаться по всему для каждого запроса UI не годится. Какие есть предложения?

Спасибо  

[Racheengel]

Добавить int m_nodesCount в структуру, изначально и каждый раз при изменении данных рекурсивно устанавливать для "родителей" m_owner->m_nodesCount=-1.

При запросе макс. числа нодов обновлять m_nodesCount свой и рекурсивно чайлдов, пока m_nodesCount<0.
Иначе вернуть m_nodesCount.

[Igors]

Добавить int m_nodesCount в структуру, изначально и каждый раз при изменении данных рекурсивно устанавливать для "родителей" m_owner->m_nodesCount=-1.

При запросе макс. числа нодов обновлять m_nodesCount свой и рекурсивно чайлдов, пока m_nodesCount<0.
Иначе вернуть m_nodesCount.

Тогда уж что-то типа m_MaхDataСount. Но вот так запросто добавлять новый (полноценный) член данных только для мелочи в UI - не западло ли?

И тут такая неприятность: отследить "факт изменения" из класса Container можно, но непросто - там масса всяких clear, erase и др. А вот отследить из класса Node практически нереально. А делать у Container член Node * m_owner ну очень не хочется - придется все время заботиться о нем при копировании и.т.п.

[Racheengel]

Ну это ж стандартная вещь - или памятью жертвовать (кэш же), или скоростью.
Добавить переменную, если это ускорит - имхо стоит того.
Ну а без отслеживания тогда тяжко будет. Разве что кэшировать для контейнера все его ноды (или хотя бы их crc считать и сравнивать).

[Igors]

Нашел точку отлова! Это момент когда Container сохраняется для undo - там всегда есть Node, владелец контейнера. Правда будет много холостых вызовов, не все операции меняют число эл-тов. Ну ладно, тут надо просто запомнить "такой-то нод (лист)" возможно изменил число эл-тов.

Ну это ж стандартная вещь - или памятью жертвовать (кэш же), или скоростью.

Ну а почему не кеш? Правда придется редактировать его в деструкторе Node - переживу. Только вот что (или как) хранить в кеше?

[Racheengel]

Поскольку важен не контент нодов, а только их количество, то m_nodesCount для каждого нода и будет кэшем.

[Igors]

Поскольку важен не контент нодов, а только их количество, то m_nodesCount для каждого нода и будет кэшем.

Хмм,,, А может так

Код

C++ (Qt)
typedef QPair<Node *, int> TCount;
typedef QHash<Node *, TCount> THash;
 

Счетчик изменился для нода - если этот нод был с макс счетчиком у родителя, то second = -1 (нужен пробег для новой установки макс). В хеш храним только узлы + 1 общий. Покритикуйте

[Racheengel]

Наверное, можно еще проще - каждый нод знает своего нода-родителя, и если нод изменился, то инвалидирует счетчики всех предков по цепочке до верхнего нода. А верхний уже делает пересчет, если надо.

[Igors]

Наверное, можно еще проще - каждый нод знает своего нода-родителя, и если нод изменился, то инвалидирует счетчики всех предков по цепочке до верхнего нода. А верхний уже делает пересчет, если надо.

Чтобы инвалидировать родителю нужно хранить указатель на макс чайлд, Поэтому и заводится пара TCount.
На удаление - вроде тоже все норм, отрабатывается так же как и изменение счетчика. Еще проблемы? 

[Racheengel]

ну, "в теории" должно работать, вроде как...
теперь надо писать Кодъ, может что и вылезет

[Igors]

теперь надо писать Кодъ, может что и вылезет

Кот написан (и даже работает  ). Но, боже, почему получилось так сложно (и много)? Вкратце повторю задачу

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

Может есть способ попроще чем обсуждался выше?