Мне приходится решать твои проблемы каждый день, но я делаю это не так, как ты пытаешься.
Сделай шаг назад.Какую фундаментальную проблему вы пытаетесь решить? Последовательность .Вы пытаетесь убедиться, что отношение «x является потомком y», а отношение «y является родителем x» всегда согласованно.Это разумная цель.
Предполагается, что каждый элемент напрямую знает как своих детей, так и своих родителей, потому что коллекция детей и родительская ссылка хранятся локально в полях.Это логически требует, чтобы, когда элемент x становился дочерним по отношению к элементу y, вы должны последовательно менять как x.Parent, так и y.Children.Это представляет проблему, с которой вы столкнулись: кто должен «отвечать» за то, чтобы оба изменения были сделаны последовательно?И как вы гарантируете, что только код "отвечает" может изменить родительское поле?
Tricky.
Предположим, мы опровергли ваше предположение.Не обязательно, чтобы каждый элемент знал своих детей и своих родителей.
Техника № 1:
Например, вы можете сказать, что существует один особый предмет, называемый «вселенная», который является предком каждого предмета, кроме самого себя.«Вселенная» может быть синглтоном, хранящимся в известном месте.Когда вы запрашиваете элемент для его родителя, реализация может найти юниверс, а затем выполнить поиск каждого потомка юниверса, ищущего элемент, отслеживая путь по ходу.Когда вы найдете предмет, отлично, все готово.Вы оглядываетесь на один шаг назад на «путь», который привел вас туда, и у вас есть родитель.Более того, вы можете предоставить всю цепочку родителей, если хотите;в конце концов, вы только что вычислили его.
Техника # 2:
Это может быть дорого, если вселенная велика, и для поиска каждого предмета требуется некоторое время.Другое решение состоит в том, чтобы юниверс содержал хеш-таблицу, которая отображает элементы для их родителей, и вторую хеш-таблицу, которая отображает элементы в список их детей.Когда вы добавляете дочерний элемент x к родительскому элементу y, метод «add» фактически вызывает Вселенную и говорит «эй, элемент x теперь является родителем y», а Universe заботится об обновлении хеш-таблиц.Предметы не содержат никакой собственной информации о «связанности»;ответственность за соблюдение лежит на вселенной.
Недостатком является то, что вселенная может содержать циклы;вы можете сказать вселенной, что x - это y, а y - как x.Если вы хотите избежать этого, вам придется написать детектор циклов.
Техника № 3:
Можно сказать, что есть два дерева;«настоящее» дерево и «фасадное» дерево. Настоящее дерево является неизменным и постоянным .В реальном дереве каждый элемент знает своих потомков, но не своего родителя.После того как вы построили неизменное реальное дерево, вы создаете фасадный узел, который является прокси-сервером для корня реального дерева.Когда вы запрашиваете у этого узла его дочерние элементы, он создает новый фасадный узел, обернутый вокруг каждого дочернего элемента , и устанавливает родительское свойство узла фасада для узла, который был запрошен для его дочерних элементов.
Теперь вы можете обращаться с деревом фасада как с родственным деревом, но родительские отношения вычисляются только при прохождении дерева.
Когда вы хотите отредактировать дерево, вы создаете новое реальное дерево, повторно используя как можно больше старого реального дерева.Затем вы делаете новый корень фасада.
Недостатком этого подхода является то, что он работает только в том случае, если вы обычно проходите дерево сверху вниз после каждого редактирования.
Мы используем этот последний подход в компиляторах C # и VB, потому что этоточно ситуация, в которой мы находимся: когда мы перестраиваем дерево разбора после редактирования кода, мы можем повторно использовать большую часть существующего неизменяемого дерева разбора из предыдущего текста.Мы всегда перемещаемся по дереву сверху вниз и хотим вычислять родительские ссылки только при необходимости.