Как создать полностью неизменяемую иерархию деревьев? Строительство курицы и яйца

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

Рассмотрим этот простой древовидный класс:

public class SOTree {
    private final Set<SOTree> children = new HashSet<>();
    private SOTree parent;

    public SOTree(SOTree parent) {
        this.parent = parent;
    }

    public SOTree(Set<SOTree> children) {
        for (SOTree next : children)
            children.add(next);
    }


    public Set<SOTree> getChildren() {
        return Collections.unmodifiableSet(children);
    }

    public SOTree getParent() {
        return parent;
    }
}

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

    SOTree root = new SOTree((SOTree)null);
    Set<SOTree> children = createChildrenSomehow(root);
    //how to add children now?  or children to the children?

или

    Set<SOTree> children = createChildrenSomehow(null);
    SOTree root = new SOTree(children);
    //how to set parent on children?

Не заставляя это быть единственным связанным деревом, есть ли какой-нибудь умный способ построить такое дерево и все же все узлы будут полностью неизменными?

Ответы

Ответ 1

Две мысли:

  • Используйте какое-то дерево factory. Вы можете описать дерево с помощью изменяемых структур, а затем factory, который будет собирать неизменяемое дерево. Внутри factory будет иметь доступ к полям разных узлов и, следовательно, может потребовать переустановки внутренних указателей, но созданное дерево будет неизменным.

  • Создайте неизменяемую обертку дерева вокруг изменяемого дерева. То есть, для построения дерева используются изменяемые узлы, но затем создайте класс-оболочку, который затем предоставит неизменный вид дерева. Это похоже на (1), но не имеет явного factory.

Надеюсь, это поможет!

Ответ 2

Эрик Липперт недавно сообщил об этой проблеме. См. Его сообщение в блоге Настойчивость, фасады и рослинские красно-зеленые деревья. Вот выдержка:

На самом деле мы делаем невозможное, сохраняя два дерева разбора. "Зеленое" дерево неизменно, постоянно, не имеет родительских ссылок, построено "снизу вверх", и каждый node отслеживает его ширину, но не ее абсолютную позицию. Когда происходит редактирование, мы восстанавливаем только части зеленого дерева, на которые повлияло редактирование, которое обычно составляет около O (log n) общих узлов синтаксического разбора в дереве.

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

Ответ 3

Создание эффективных, неизменных структур данных может быть сложным. К счастью, есть люди, которые выяснили, как реализовать многие из них уже. Посмотрите здесь для обсуждения большого разнообразия неизменных структур данных.

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

Ответ 4

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

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

  • Посмотрите, как Clojure создает неизменяемые структуры данных. В случае Clojure каждая операция над деревом (например, добавление node) возвращает новое дерево.

  • Сделать создание дерева атомарным. Вы можете создать специальный формат и затем десериализовать дерево. Поскольку все методы сериализации являются внутренними, вам не нужно раскрывать какие-либо изменчивые методы.

  • Перед тем, как factory вернет построенное дерево, сначала заблокируйте его флагом. Это аналог атомной операции.

  • Используйте методы уровня пакета для построения дерева. Таким образом, методы мутаций на узлах не могли быть доступны внешними пакетами.

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

Ответ 5

Не заставляя это быть единственным связанным деревом, есть ли какой-нибудь умный способ построить такое дерево и все же все узлы будут полностью неизменными?

Держите свои интерфейсы и реализации развязанными и не ограничивайте свои узлы дерева тем же классом, что и дерево.

Одним из решений этой проблемы является сохранение иерархии node в каком-либо другом неизменяемом представлении, и когда вызывающий абонент вызывает getChildren() или getParent(), он лениво конструирует дочерние узлы из этого неизменяемого представления. Если вы хотите, чтобы node.getChildren().get(i).getParent() == node был истинным (а не .equals(node) - то есть личность, а не равенство), вам придется кэшировать объекты node, чтобы вы могли их повторно добавить.

Ответ 6

Правильный подход для построения неизменяемого дерева должен заключаться в том, чтобы конструктор каждого node вызывал конструкторы дочерних узлов с самим собой как параметр, при условии, что конструктор child node не должен вызывать привязку к корневой ссылке для себя, чтобы быть сохраненным в любом месте, и не использовать параметр pass-in для любых целей, кроме как инициализировать поле, которое конструктор будет использовать без каких-либо целей, кроме как принять такую ​​инициализацию. Кроме того, родительский конструктор node должен избегать использования каких-либо элементов дочернего элемента node, который бы разыменовал "родительское" поле.

Хотя такой метод, похоже, нарушает правило о том, что конструкторы неизменяемых объектов не должны представлять собой неоперившиеся объекты в качестве параметров для других подпрограмм, "реальное" правило заключается в том, что конструктор неизменяемого объекта не должен позволять ссылаться на который должен использоваться таким образом, чтобы прямо или косвенно получить доступ к любым полям, которые еще не достигли конечного значения. В общем случае, если объект fledgeling предоставляет ссылку на себя во внешний мир, он не будет контролировать, какой внешний код может с ним поделать. Однако в конкретном случае вызова дочернего конструктора node при условии, что код для дочернего элемента node удовлетворяет вышеуказанным требованиям, не будет корневой ссылки на родительский node, , кроме как через родительский node сам. Следовательно, не будет никакой опасности, что любой код, который сделает что-нибудь неожиданное с помощью fledgeling node, получит ссылку на него.

Ответ 7

Поскольку вы хотите, чтобы они были неизменными, вам нужно просто сделать это при строительстве. Создайте один конструктор, который принимает как родительский, так и дочерний, вместо двух отдельных конструкторов.