Форум PHP

Пишу класс управления вложенными множествами (nested sets). Пардон. Не пишу, а переписываю чужой. Чужой класс выпуска 2005 года, соответственно под пхп-4. Короче много там через ж... Но не в этом дело.

Есть в этом классе методы управления структурой - создать узел, переместить, удалить и т.п. Смущает меня, что эти действия относятся не к дереву, а к узлу. Т.е. мне так кажется что должен быть класс УЗЕЛ в котором все эти методы и класс ДЕРЕВО для которого остаются только методы вывода (все дерево, одна ветка, подмножество узла и т.п.). Но в такой организации меня смущает, что сам по себе узел не имеет смысла. Т.е. все равно класс УЗЕЛ будет работать только при определенной структуре дерева и при наличии класса ДЕРЕВО с которым придется взаимодействовать. Например перед перемещением УЗЛА нужно у ДЕРЕВА запросить подмножество узлов в которые возможно осуществить такое перемещение и т.п.

Ну так я не могу решить, разделять класс на два или нет? С одной стороны вроде в этом разделении нет практической пользы, с другой не покидает ощущение некой недопродуманности. Кто что может сказать?

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

С другой стороны у вас дерево что из себя представляет? Связанный список, где узел знает о потомке или родителе? Или дерево организовано как-то по-другому?

PS Это очень древние деревья, пришли они из 50-60 годов, методы и алгоритмы их обработки от туда же. ООП, кстати, альтернативная этому подходу модель, поэтому несостыковки тут вполне возможны. Если по среди мегаполиса строите пирамиду, а не небоскреб, не жалуйтесь, что нельзя лишних этажей нарастить - пирамиды, это здания для очень дешевой пустынной земли, которой не жалко, небоскребы наоборот для очень дорогой земли, где на махоньком кусочке нужно построить 70-100 этажей, чтобы дом себя хоть как-то окупал, чтобы цена квадратного метра была не запредельной. Вот и тут тоже самое, вы орудуете очень эффективными концепциями, но из другой исторической и экономической эпохи, для других машин, да и других языков программирования...

> С другой стороны у вас дерево что из себя представляет?
Дерево вот такого вида

> узел не знает, где он расположен, только дерево знает свою структуру и может поменять
> принадлежащие ему узлы местами
Узел знает на каком он уровне вложенности и свои left-key и right-key. Т.е. он знает сколько узлов над ним, под ним и слева от него. Но одновременно с этим он не может переместиться не изменив и другие узлы дерева. Даже при создании и удалении любого узла меняется и остальное дерево. Не так это только если он самый последний и на нулевом уровне вложенности и не имеет потомков.

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

А где хранится информация о том, какой узел с каким связан? В узле?

>Т.е. получается что узел без дерева не может существовать.
>Значит и выделять не надо. Вы это хотите сказать?
Лучше не стоит.

> А где хранится информация о том, какой узел с каким связан? В узле?
Ну да. Только тут в двух словах не опишешь. По ссылке выше очень понятно описана модель. Она весьма интересна! Два ключа (левый и правый) содержат в себе очень много информации - количество подчиненных узлов, количество узлов в дереве выше(левее), позицию данного узла в его ветке среди равных. Вся модель строится на left-key, right-key и level. И по этим данным можно одним запросом сделать любую выборку (родителей, всей ветки, подчиненных узлов и т.д.д.)

> Лучше не стоит.
Понятно. Спасибо

Т.е. информация о соседях хранится в узлах... это связанные списки. Это особый способ организации информации, там свои алгоритмы и приемы, очень плохо стыкуется с ООП. С ООП вообще хорошо стыкуется только то, что с расчетом под ООП делается, а все остальное плохо. Это как экономика СССР, все что связано с обороной и построения объемных сооружений - отлично, дешево и качественно, а все остальное - плохо, дорого и не качественно :)
В этом же и слабость ООП, пока вы разрабатываете замкнутую систему, в которую никто кроме вас не вносит изменения - все отлично. Как только вам нужно вносить постоянный поток незапланированных изменений и стыковать программный комплекс с не ООП-кодом (протоколы, базы данных, векторные решения), есть неплохой шанс огрести кучу неприятностей.