Деревянный айтем

[ssoft]

Почему люди (даже хорошие) повторяют эту песню model-view хотя ее несуразность очевидна и лезет из всех щелей?

Про model-view специально ничего не писал).
На совсем базом уровне вся функциональность может быть представлена в виде цепочки преобразований

[data1]--transform1-->[data2] --transform3-->... -->[dataN]

data1 по отношению к data2 первичны. Так и исходные данные по отношению к способу их отображения первичны, даже если данные агрегированы в структуры GUI.

Но это не по теме).

То же отношение "иерархия" (если хотите "представление"). Линковка одного объекта к другому обычно выполняется с целью наследования трансформов парента (т.е. чайлд двигается (и/или врашается, скалится, деформируется и.т.п.) вместе с парентом, т.е. логика та же - операции над парентом применяются к его чайлдам. Если чайлд имеет свои анимации, то они должны быть пересчитаны так чтобы на момент линковки были дефаултами. Аналогично при отлинковке. Поэтому говорить о том что, мол, "никаких отношений между объектами нет" явно неуместно, да и просто противоречит здравому смыслу. Отношение "иерархия" налицо, подтверждается и визуально, и опциями, и как угодно. А что оно не вписывается в каноны model-view - так в этом я не виноват  Улыбающийся

Тема 3D мне очень хорошо понятна). Пользователь выполняет операции и строит зависимости в своих терминах и определениях, не обязательно имеется прямое соответствие между действиями пользователя и происходящим на программном уровне.
Например, пользователь выполнил операцию удаления объекта, а программа должна поддерживать Undo, тогда фактического удаления объекта в программе может и не быть.

Линковка одного графического объекта к другому может выполняться для разных нужд - применение каких-то свойств (трансформации, анимации, эффектов), порядок отображения, компоновка (layouting) и для многого другого.
Может существовать сразу несколько вариантов упорядочивания одних и тех же графических объектов для решения этих разных задач. Способ упорядочивания list, map, tree, custom определяет наличие отношений определенного вида между элементами контейнера.  Элемент контейнера может быть связан с графическими объектами какими-либо с отношениями. Вопросы о том, кто владеет графическими объектами раскрывают только виды отношений между элементами контейнера и графическими объектами. Виды отношений контейнеров и эх элементов предопределены в самих реализациях контейнеров.

Мы что, не можем наладить связи для организации любого числа структур? Какая разница где храним

Конечно, можем. Другой вопрос - зачем? Так как разница всё же есть - в эффективности.
Если требуется наибыстрейший перебор всех элементов, то нужно использовать vector; если при этом частые удаления/вставки, то list; если ..., то ...; если требуется дерево, то нужно использовать дерево; если другой граф, то нужно использовать другой.
Каждая из структур имеет свои сильные и слабые стороны. Решение в общем виде всегда будет проигрывать в конкретных частных случаях.

Вы часто ставите вопрос в общем виде, подразумевая свой конкретный частный случай).
Проект с template выложу попозже).

[Igors]

Конечно, можем. Другой вопрос - зачем?

Просто потому что объект имеет (или может иметь) 2 и более отношений/связей с другими. Строить свою структуру для каждого типа отношений.. ну иногда может и так, но не блеск. Вот хотя бы простейший случай: объект удаляется - и вычистить его из всех структур не так уж просто. В большинстве случаев выгоднее "агрегировать данные структуры в сам объект" (я верно выражаюсь?  )

Вы часто ставите вопрос в общем виде, подразумевая свой конкретный частный случай).

Углубление в конкретику пагубно для обсуждения  Пример с трансформами выше - вряд ли Вам он чем-то помог, Вы и так это знали. Просто хотел напомнить что каждое отношение создается не так себе, а имеет совершенно конкретный ф-ционал/смысл который обязан поддерживаться. Можно рассказать и про упомянутый "by master matrial" но это не внесет ровным счетом ничего нового, все то же: чайлд (по сути "клиент") юзает парента (сервер). Установка/разрыв связи практически всегда сильно влияет на чайлда, но почти никогда на парента (хотя исключения все же есть). А вот что там и как меняется - чисто подробности конкретной задачи и отношения к обсуждению не имеют.

Проект с template выложу попозже).

Не вопрос. Собсно данную тему можно рассматривать чисто как "дело/вопрос техники". Допустим мы хотим связывать наши структуры в 2 независимых (непротиворечивых !?) дерева. Да просто так, без раздумий

Код:

struct CTreeItem {
  QString m_name;   // какие-то свои/содержательные данные структуры
  ...
 // Данные для связки в первое дерево
  CTreeItem * m_parent;
  QVector< CTreeItem *> m_child;

 // Данные для связки во второе дерево
  CTreeItem * m_parent2;
  QVector< CTreeItem *> m_child2;
...
};

И можно с полным правом заявить что наша модель поддерживает "multiply hierarchy(ies)"  Однако работать с этим будет не очень удобно. Заведя конкретные поля для каждого типа отношения/зависимости мы лишаемся возможности "пробежаться по всем", и вынуждены расписывать/повторять каждое действие напр для m_child, m_child2 и.т.п.

Как здесь воткнуть шаблоны - ума не приложу, интересно посмотреть (но "торопыться нэ надо"  )

[ssoft]

Как и обещал, запилил одну из возможных реализаций Tree (https://gitlab.com/ssoft-sandbox/prog.org.ru/tree-example).

Дерево Tree содержит узлы Tree::Node  в виде композитной иерархии с использованием ::std::list.
Параметрами шаблона дерева являются:
 - тип хранимого в узлах значения
 - тип наблюдателя за деревом (ниже подробнее)
 - тип аллокатора для узлов Node (по умолчанию ::std::allocator)

Тип наблюдателя за деревом Observer необходим для сбора и хранения дополнительной информации об элементах дерева:
 - подсчету статистики (общей и по каждому из узлов);
 - индексации и/или упорядочивания узлов по любым критериям;
 - и др.

Конкретная реализация Observer должна содержать:
 - определение типа NodeInfo, значение которого встраивается в узел Node (доступно по методу info())
 - реализацию методов:
     --  void afterInsert ( NodeIdent ident );
     --  void beforeErase ( NodeIdent ident );
   позволяющую наблюдателю что-то считать и/или индексировать и/или делать что-то ещё.

Узел дерева Node содержит
 - ассоциацию с самим деревом
 - ассоциацию с вышестоящим узлом
 - значение Value
 - информацию наблюдателя Info
 - двусвязный список нижестоящих узлов

В примере представлено:
 - Scene - класс сцены, которая хранит (композитно агрегирует) какие-то ресурсы в ассоциативном контейнере;
 - TransformValue - содержит ассоциативную связь с ресурсом (в виде ссылки) и дополнительный атрибут bool m_use_parent_transform;
 - TransformObserver - реализация наблюдателя, который обеспечивает быстрый поиск узла дерева по ссылке на ресурс сцены;
 - TransformTree - дерево элементов TransformValue с наблюдателем TransformObserver.

В методе main показано:
 - заполнение/удаление дерева;
 - перебор узлов по иерархии;
 - произвольный доступ к узлам с использованием функциональности наблюдателя;
 - полный линейный перебор узлов с использованием функциональности наблюдателя;
 - подсчет количества всех узлов с использованием функциональности наблюдателя;
 - удаление узлов дерева с использованием функциональности наблюдателя.

[Igors]

Как и обещал, запилил одну из возможных реализаций Tree

С удовольствием поизучал, много всяких интересных штучек которые (пока) в мой арсенал не входят. Спасибо. Все-таки... ну а стоит ли так "наворачивать"? Не, ну если маленько посидеть, потыкать браузером IDE и прочесть примечания - конечно ничего сложного нет, но первое впечатление пугающее  Заметил что Вы стремитесь к полному истреблению "голых указателей".  Два момента по ф-ционалу

1) Допустим в дереве (но не в сцене) есть такая иерархия

A
  B
    C

Сцена удаляет "A". Будет ли она затем удалять "B" и/или "С" - сугубо ее (сцены) личное дело, в момент удаления "A" дереву об этом ничего не известно. Поэтому чайлд "B" должен быть отлинкован, и связка B-C сохранена. Не вижу такой возможности с композитной агрегацией. Также более идейно автоматом удалять ноды дерева не имеющие никаких связок. Напр удаляется "B". Тогда если нод дерева "A" не имеет парента то он тоже должен быть удален, аналогично "С" если у него нет чайлдов

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

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

Ключевое слово "много". Конкретно сейчас их уже 29. Ну и что я должен делать?

Код

C++ (Qt)
struct Scene {
  ...
  Tree<params1> TransformTree;
  Tree<params2> MaterialTree;
  ...
  Tree<params29> LastTree;
};

И на каждой операции (напр удаление нода сцены) перебирать 29 деревьев (причем даже не в цикле а "по одному")? Это нестерпимо, поэтому напрашивается так

Код

C++ (Qt)
struct Scene {
  ...
  QList<Tree<params_x>> trees;
  ...
};

Очевидно что это неоптимально (поиск в 29 хешах), а если хотим инстанциировать разные деревья разными аргументами шаблона - придется еще городить немалую городушку. В принципе это реализация мечты Карслона "8 тортов с 1 свечой", а хотелось бы наоборот.

Обсерверы - да, так или иначе что-то делать придется, но отделаться простыми методами вряд ли удастся. Здесь пока "не созрело", сначала надо присмотреться какие проблемы полезут.

[ssoft]

1) Допустим в дереве (но не в сцене) есть такая иерархия

A
  B
    C

Сцена удаляет "A". Будет ли она затем удалять "B" и/или "С" - сугубо ее (сцены) личное дело, в момент удаления "A" дереву об этом ничего не известно. Поэтому чайлд "B" должен быть отлинкован, и связка B-C сохранена. Не вижу такой возможности с композитной агрегацией.

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

Также более идейно автоматом удалять ноды дерева не имеющие никаких связок. Напр удаляется "B". Тогда если нод дерева "A" не имеет парента то он тоже должен быть удален, аналогично "С" если у него нет чайлдов

Здесь можно получить неожиданное поведение (предсказуемое, но не очевидное).

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

Как минимум не нужно специально 29 разных деревьев реализовывать. 

Отношения между объектами  могут быть самыми разнообразными и выражаться самым разным ф-ционалом, как раз проблема в том что этих отношений очень много.
Ключевое слово "много". Конкретно сейчас их уже 29. Ну и что я должен делать?
И на каждой операции (напр удаление нода сцены) перебирать 29 деревьев (причем даже не в цикле а "по одному")? Это нестерпимо ...
...
реализация мечты Карслона "8 тортов с 1 свечой", а хотелось бы наоборот.

Во-первых, для деревьев можно использовать гетерогенный контейнер и и хранить их в виде списка, мапы, хеша или в любом другом виде, аля List< AnyTree >.
Во-вторых, можно в сцене завести вспомогательное отображение, которое по ключу выдаст перечень {дерево, итератор в дереве}, и будет 1 свечка на 29 тортов).

[ssoft]

Заметил что Вы стремитесь к полному истреблению "голых указателей".

Так и есть. "Голый указатель" ничего толкового о себе не скажет, какая это взаимосвязь - ассоциация (ссылка), агрегация (владение общее/совместное), предполагается ли использование наследования?
Чтобы это понять, приходится изучать практически весь код, где используется голый указатель. Со специальными (умными или переопределенными через using/typedef) намного понятнее, что имеется в виду.

[Igors]

Так и есть. "Голый указатель" ничего толкового о себе не скажет, какая это взаимосвязь - ассоциация (ссылка), агрегация (владение общее/совместное), предполагается ли использование наследования?
Чтобы это понять, приходится изучать практически весь код, где используется голый указатель. Со специальными (умными или переопределенными через using/typedef) намного понятнее, что имеется в виду.

Никогда не был борцом за "идейную чистоту", но все-таки "указатель" - это свое, родное, ведь все начиналось как альтернатива ассемблеру. Да, безликость/неопределенность указателя часто доставляет проблемы (особенно с пониманием), но с др стороны попытки любой ценой использовать только ссылки или итераторы, на мой взгляд, часто не очень органичны/естественны. Напр понять к чему итератор никак не дешевле чем роль указателя. Впрочем это дело вкуса

[Авварон]

Igors
Ну итератор и есть логически указатель на элемент. Заметьте не "вумный" указатель, а обычный. Их делали, чтобы все контейнеры были похожи на сишные массивы со всеми вытекающими. Вообще, это изначально была плохая абстракция. Ждем Ranges=)

[Igors]

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

Ну не со всеми, напр ассоциативный контейнер не будет иметь доступа по индексу.

Вообще, это изначально была плохая абстракция.

Ну может и не такая уж плохая (напр для того же ассоциативного выбора нет), но что ею (массово) злоупотребляют - это точно.

Ждем Ranges=)

А шо это Киньте ссылочку если не затруднит. Спасибо

[Igors]

Во-первых, для деревьев можно использовать гетерогенный контейнер и и хранить их в виде списка, мапы, хеша или в любом другом виде, аля List< AnyTree >.
Во-вторых, можно в сцене завести вспомогательное отображение, которое по ключу выдаст перечень {дерево, итератор в дереве}, и будет 1 свечка на 29 тортов).

Попробую сделать некоторые выводы. По существу мы хотим спроектировать manager ссылок/связей (с деревьями или как - это все-таки вторично/реализация). Этот manager ОДИН объект (во всяком случае с точки зрения использования), напр член класса "сцена".

Код

C++ (Qt)
struct Scene {
 ...
 CReferenceManager mRefMan;
 ...
};

Поскольку он один а типов ссылок десятки, то выходит что практически каждое обращение к manager'у должно быть идентифицировано каким-то ключом (какие ссылки мы хотим читать/писать). Пусть этот ключ - просто enum, напр

Код

C++ (Qt)
enum TArcType {
  ARC_TYPE_ANY  = 0,
  ARC_TYPE_HIERARCHY  = 1,
  ARC_TYPE_MATERIAL  = 2,
  ARC_TYPE_SKIN  = 3,
  ...
  ARC_TYPE_SOMETHING  = 29,
}; 

Теперь нужно набросать методы этого manager'а, т.е. что мы от него хотим. Обход дерева и.т.п. - да, есть и такие задачи, но далеко не первые.  В первую очередь для каждого нода/элемента сцены нужно знать "кто ссылается на него" и "на кого ссылается он". Заметим что интересны только ссылки, сами по себе внутренние структуры типа "ноды дерева" бесполезны и светить их снаружи смысла нет. Пусть Node - элемент сцены, тогда напрашиваются такие геттеры

Код

C++ (Qt)
struct CReferenceManager {
...
Node * GetInpNode( TArcType type, const Node * src ) const;
Node * GettOutNode( TArcType type, const Node * src ) const;

Неплохо, во многих случаях ссылка данного типа может быть только одна (или NULL - никакой). Но не во всех. Как тогда извлекать инфу о ссылке? Думаю нужно вводить класс/сущность "ссылка/связка", предлагаю такую, незатейливую

Код

C++ (Qt)
struct CRefArc {
  TArcType mType;
  Node * mNode;
  CArcData * mData;   // данные ссылки (проблематично) 
};

И, не мудрствуя лукаво, возвращать константные указатели на нее, напр

Код

C++ (Qt)
struct CReferenceManager {
...
const CRefArc * GetInpArc( TArcType type, const Node * src, int * arcCount ) const;
const CRefArc * GetOutArc( TArcType type, const Node * src, int * arcCount ) const;
};

Ну пока хватит, критикуем, предлагаем...

[Igors]

..критикуем, предлагаем...

Мда..  Ну ладно, расскажу пока что такое "данные ссылки", может появятся идеи.

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

Код:

struct CBoneWeight  {
  int vertexIndex;
  double weight;
};

typedef std::vector<CBoneWeight> CBoneInfo;  // каждая прилинкованная бона имеет этот вектор

Вот тут все четко - данные принадлежат именно ссылке, сами по себе они не имеют смысла ни для кости ни для модели.

Однако меня смущает что этот случай - единственный, никаких других не находится. В подавляющем большинстве случаев достаточно "голого факта" ссылки, ссылающийся обычно прекрасно сам знает что делать. В немногих других да, есть данные что используются совместно со ссылкой, но они просто принадлежат ссылающемуся. Напр зависимость "иерархия" имеет набор опций (напр наследовать ли вращение парента и.т.п.), но эти опции должны предъявляться в UI объекта независимо от наличия парента в данный момент. Ладно, вот изначальная плохонькая констукция

Код

C++ (Qt)
struct CRefArc {
  TArcType mType;
  Node * mNode;
  CArcData * mData;   // данные ссылки (проблематично) 
};
 

Что здесь мне не нравится

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

- данные (mData) шарятся - если их имеет парент то и чайлд тоже. Тупо QSharedPointer<CArcData> вроде в тему, но хз

- стандартная проблема копирования указателя на полиморфный класс (вместе с содержимым). Придется видимо заряжать

Код

C++ (Qt)
virtual CArcData * CArcData::Clone( void ) const = 0;

Что при желании можно причислить к "костылям"

Связываться с богомерзкими темплейтами - обычная история, себе дороже. Это моментально сделает вмещающий класс (CRefArc) шаблонным, дальше развалится его владелец и.т.п. И придется работать на аптеку с "гетерогенными контейнерами"

Или все-таки можно сделать как-то "модерново" вместо этого "С с классами"? (та знаю что нет ну а вдруг?  )

[Авварон]

Ну вот и "пошли детали" без которых не догадаться что там вам надо. Откуда нам было знать, что такое данные связи и как часто они нужны?

Ну хорошо, чем вам "матричный" граф не нравится? Есть матрица N*N где N - количество нод. В ячейке i,j лежит битарей, который говорит, какие связи между нодами i,j есть.
Матрицу можно реализовать на основе хэша (ключ - std::pair<int /*i/*, int /*j*/>), тогда возможно меньше будет пропадать места, энивей, добавление элемента не будет требовать релокации всей матрицы.
Тогда дату для одной связи можно положить в соседний хэш с аналогичным ключом.
Плюс решения - есть универсальный "граф" который держит любое кол-во связей.
Минус - что данные о связи отдельно. Ну так вроде это и была хотелка.
Еще минус - загадочные undo и redo, которые может быть сложно реализовать (придется побегать циклами по матрице, ну ой, ничего страшного)

[Igors]

Ну хорошо, чем вам "матричный" граф не нравится? Есть матрица N*N где N - количество нод. В ячейке i,j лежит битарей, который говорит, какие связи между нодами i,j есть.

Так а где взять эти индексы i/j ? Они же сразу "уплывут" если удалился объект сцены.

Матрицу можно реализовать на основе хэша (ключ - std::pair<int /*i/*, int /*j*/>), тогда возможно меньше будет пропадать места, энивей, добавление элемента не будет требовать релокации всей матрицы.

Тогда уже ключ хеша QPair<Node *, Node *>, но как тогда напр "пробежаться по всем чайлдам" (причем в порядке их следования)? Хотелка как раз в том что для любого нода сцены иметь под рукой всех его парентов и чайлдов.

Еще минус - загадочные undo и redo, которые может быть сложно реализовать (придется побегать циклами по матрице, ну ой, ничего страшного)

Заметим что при undo порядок следования чайлдов (как они были прилинкованы к паренту) должен быть точно восстановлен.

Ну вот и "пошли детали" без которых не догадаться что там вам надо. Откуда нам было знать, что такое данные связи и как часто они нужны?

Ну "как работают боны" - вполне в рамках популярных знаний, причем с бородой, за последние 25 лет не слышал ничего нового. Впрочем и этого не требуется - "зависимость может иметь собственные данные" - все что Вам нужно знать для разработки структур/архитектуры. Популярно мнение что, мол, надо все-все знать/изучить и вот тогда... Это наивное заблуждение (а чаще просто повод увильнуть от работы), объем инфы быстро превышает (небольшую) емкость мозга. Всех подробностей не помнят даже авторы. Напр я помню "29" потому что на загрузке есть точка где все они настраиваются, я туда progress bar добавлял. Из этих 29 зависимостей я помню может один десяток (в основном те что сам писал).

Тогда дату для одной связи можно положить в соседний хэш с аналогичным ключом.
Плюс решения - есть универсальный "граф" который держит любое кол-во связей.
Минус - что данные о связи отдельно. Ну так вроде это и была хотелка.

Да, есть такой вариант

Код

C++ (Qt)
struct CRefArc {
  TArcType mType;
  Node * mNode;
};
typedef QPair<Node *, CRefArc> TArcDataKey;   // ключ для поиска данных ссылки
typedef QHash<TArcDataKey, CArcData *> TArcDataHash;   // класс для хранения данных ссылок 

Ну пока не знаю чем он хорош/плох. Пока вижу только что в использовании несколько неудобен - нужно смотреть чтобы key.first был именно чайлдом. Все-таки придется тащить базовый CArcData? Можно пережить но лучше бы без него.

[ssoft]

Доделал реализацию Tree, код все там же (https://gitlab.com/ssoft-sandbox/prog.org.ru/tree-example).

Как и обещал, всё усложнилось в реализации , но в использовании осталось всё по простому (на мой взгляд, конечно).

Узлы Node теперь реализуют классический parent-child, пример их отдельного использования в exampleParentChild.cpp.
Работает копирование/перемещение узлов и передача чайлдов.

Дерево осталось с наблюдателем. Из дерева можно извлечь узел со всей иерархией, далее можно перенести узел в другое дерево.
Также доступно копирование/перемещение узлов и передача чайлдов.

Кроме дерева, как я понял, требуется еще и направленный граф (Node|Edge).
Задачка тоже интересная сама по себе. Если найду в себе силы, сделаю и его. 

[Igors]

Доделал реализацию Tree, код все там же (https://gitlab.com/ssoft-sandbox/prog.org.ru/tree-example).

Как и обещал, всё усложнилось в реализации ,

Да, в этот раз я "ни асилил" 

..но в использовании осталось всё по простому (на мой взгляд, конечно).

Ну как... было бы прекрасно "просто пользоваться" не вникая в "детали реализации", но так не всегда выходит. Напр нод сцены удаляется, надо записать данные для undo, и вот уже, вероятно, (глубокого) изучения внутренностей не избежать. И это будет непросто. Хотя, справедливости ради, это довольно противная задачка для любой "деревянной" структуры, даже самой примитивной.

Кроме дерева, как я понял, требуется еще и направленный граф (Node|Edge).

Ну вообще-то не "кроме/еще" а он-то и требовался  Собсно чего я туда полез. Цель (которую я уже не раз озвучивал)

- для любого нода уметь находить "кто ссылается на него" и "на кого ссылается он".

Сейчас это решается просто членами класса, "голыми" указателями. Напр

Код

C++ (Qt)
struct  GeomGroup : public Node {
...
  Material * masterMaterial;
...
};

И .. это все! Если нужен список ссылающихся на какой-то Material (напр для того же undo), то пробегаемся по всем GeomGroup и находим всех с masterMaterial == this. Как ни странно, пока сцена невелика - такое свинство работает, но вот дальше тормоза, да и "поискового кода" не так уж мало. Ну и как решать? Прямолинейно

Код

C++ (Qt)
struct  Material : public Node {
...
  std::vector<GeomGroup *> materialUsers;  // список "ссылающихся"
...
};

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

Эта задача близка к "дереву", но не равна ей. Может быть N парентов и/или данные конкретной зависимости (хотя оба случаи очень редки). А главное - "фокус" на том что зависимостей "много" и всяких-разных. Поэтому думаю лучше сразу создавать деревянный контейнер что хранит все зависимости (а не распылять их "по деревьям"). Какие-то "внутренние ноды" неизбежны, но давать их наружу не следует, пользователь класса должен оперировать только с "зависимостями" (между парой нодов сцены).

Спасибо