Как мне управлять деревом неизменяемых объектов?

Question

Я строю целое приложение из неизменяемых объектов, чтобы упростить реализацию многопоточности и отмены. Я использую Google Collections Library, который предоставляет неизменные версии Map, List и Set.

Моя модель приложения выглядит как дерево:

• Сцена является объектом верхнего уровня, который содержит ссылку на корневой узел.
• Каждый узел может содержать дочерние узлы и порты.

Объект график может выглядеть следующим образом:

Scene 
| 
+-- Node 
     | 
     +-- Node 
      | 
      +- Port 
     +-- Node 
      | 
      +- Port 
      +- Port 

Если все эти объекты являются неизменяемыми, управляются верхнего уровня SceneController объекта:

• Что является лучшим способом построить эту иерархию?
• Как заменить объект, который является сколь угодно глубоким в дереве объектов?
• Есть ли способ поддерживать обратные ссылки, например. Узел, имеющий атрибут «parent»?

И в более общем плане:

• ли какие-либо модели появились для работы с этим типом данных?
• Имеется ли (академическая) литература по этой теме?
• Это хорошая идея?

Answer 1

Здесь представлены два представляющих интерес понятия. Во-первых, постоянные структуры данных. Если все элементы дерева неизменяемы, то можно получить новое дерево из исходного дерева, заменив некоторые части, но ссылаясь на более старые части, тем самым экономя время и память.

Например, если бы вы добавили третий порт к узлу, у которого уже есть два порта, вам нужно будет создать новую сцену, новый потомок Сцена и узел, который вы меняете. Другой узел и все порты не нужно создавать заново - вы просто ссылаетесь на них в новых сценах/узлах.

Другая концепция: Молния. Застежка-молния - это способ «перемещаться» через постоянную структуру данных для оптимизации локальных изменений.Например, если вы добавили четыре новых порта вместо одного, но вы добавили каждый порт по одному, вам нужно будет создать четыре новых сценария и восемь новых узлов. С застежкой-молнией вы откладываете такие творения, пока не закончите, сохраняя эти промежуточные объекты.

Лучшее объяснение, которое я когда-либо читал о молнии, это here.

Теперь использование застежки-молнии для навигации по структуре данных устраняет необходимость иметь обратные ссылки. У вас может иметь обратные ссылки в неизменяемой структуре, умным использованием рекурсивных конструкторов. Однако такая структура данных не будет постоянным. Непрерывные неизменные структуры данных обладают плохими изменениями, поскольку вам нужно копировать все данные каждый раз.

Что касается академической литературы, я рекомендую Структуры данных с чисто функцией, Окасаки (dissertation PDF, fully fledged book).

Answer 2

Если ваше дерево неизменно, то если вы хотите его изменить, вы должны будете произвести новое дерево.

Это звучит плохо, но его нет, если все ваши узлы также неизменяемы! Поскольку вам не нужно делать копии неизменяемых объектов, ваше новое дерево будет в основном ссылаться на старое дерево, за исключением сделанных вами изменений.

Вам нужно будет спроектировать свое дерево таким образом, чтобы каждое неизменяемое дерево ссылалось на другие неизменные деревья. Таким образом, вам не нужно будет воспроизводить все неизменяемое дерево.

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