IMHO.WS - Проблемы с построением "дерева"(+)

IMHO.WS (http://www.imho.ws/index.php)

- Веб-программирование (http://www.imho.ws/forumdisplay.php?f=29)

- - Проблемы с построением "дерева"(+) (http://www.imho.ws/showthread.php?t=78590)

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

метод для обмена двух узлов:

Код:

function SwapNodes($categoryID1, $categoryID2)

                {

                        if ($this->getNodeInfo($categoryID1) == 0)

                        {

                                $nodeInfo1 = $this->nodeInfo;

                        }

                        if ($this->getNodeInfo($categoryID2) == 0)

                        {

                                $nodeInfo2 = $this->nodeInfo;

                        }

                        // todo:

                        // check for rule: both nodes must have same parentID

                        $db = new MySql(null, "mport4", null, null);

                        $db->MySql_Connect();

                        $db->MySql_SelectDb();

                        

                        $updateQuery = "update categories set

                        cat_LEFT = case 

                        when cat_LEFT between " . $nodeInfo1["left"] . " and " . $nodeInfo1["right"] . " then " . 

                        $nodeInfo2["right"] . "+cat_LEFT-" . $nodeInfo1["right"] .

                        " when cat_LEFT between " . $nodeInfo2["left"] . " and " . $nodeInfo2["right"] . " then "  .

                        $nodeInfo1["left"] . "+cat_LEFT-" . $nodeInfo2["left"] . " else " .

                        $nodeInfo1["left"] . "+" .  $nodeInfo2["right"] . "+cat_LEFT-" . $nodeInfo1["right"] . "-" . $nodeInfo2["left"] . " end," .

                        " cat_RIGHT = case

                        when cat_RIGHT between " . $nodeInfo1["left"] . " and " .  $nodeInfo1["right"] . " then " .

                        $nodeInfo2["right"]  . "+cat_RIGHT-" . $nodeInfo1["right"] .

                        " when cat_RIGHT between " . $nodeInfo2["left"] . " and " . $nodeInfo2["right"] . " then " .

                        $nodeInfo1["left"] . "+cat_RIGHT-" . $nodeInfo2["left"] . " else " .

                        $nodeInfo1["left"] . "+" . $nodeInfo2["right"] . "+cat_RIGHT-" . $nodeInfo1["right"] . "-" . $nodeInfo2["left"] . " end " .

                        " where cat_LEFT between " . $nodeInfo1["left"] . " and " . $nodeInfo2["right"] . 

                        " and " . $nodeInfo1["left"] . "<" . $nodeInfo1["right"] . 

                        " and " . $nodeInfo1["right"] . "<" . $nodeInfo2["left"] .

                        " and " . $nodeInfo2["left"] . "<" . $nodeInfo2["right"];

                        

                        $db->MySql_QueryDb($updateQuery);

                        

                        if (mysql_affected_rows($db->dbConn) > 0)

                        {

                                return 0;                                

                        }

                        return -1;                        

                }

p.s. нужно добавить проверки.

Когда будешь вводить внешний индекс сортировки, его нужно строить так, чтобы сохранялась структура дерева. То есть помимо простой сортировки нужно будет учитывать и сортировку по left. Это влечет как минимум дополнительные вычисления. А в общем идея здравая.

Цитата:

Sheryld:
if ($this->getNodeInfo($categoryID1) == 0)
{
$nodeInfo1 = $this->nodeInfo;
}

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

Код:

if (false === ($nodeInfo1 = $this->getNodeInfo($categoryID1)) return false;

но обеспечивающую достаточную защиту от некорретных данных

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

Цитата:

Sheryld:
тут бы вообще надо создавать новый экземпляр класса, с копирующим конструктором, но я не знаю, как это сделать в php.

В четверке почти никак, только ручками создавать копию, либо определять собственный метод clone(). В пятом есть магический метод __clone()...

подводя итоги. не хватает методов:

InsertTo
MoveTo

т.е. вставлять/двигать узел(целиком) в конкретную позицию.

Clone

клонировать узел.

Одиночное удаление узла. Но это вобщем не сложно и не к спеху:)

если кто знает где найти алгоритмы, прошу ссылку:)

InsetTo и Clone по сути одно и то же если речь идет о копировании существующего узла.
Решать можно так:
1. Выбираем поддерево с корнем в нужном нам узле.
2. Вызываем рекурсивный метод добавления дерева в дерево:) (пишется за 10 минут)

С переносом сложнее.. там нужно сохранить и идентификаторы, но как вариант, можно сначала скопировать куда-нибудь в переменную поддерево, которое переносим, удалить его и вставить в нужное место с указанием всех данных (кроме left, right и level)

Sheryld

Цитата:

Sheryld:
Одиночное удаление узла

а вот это не так легко.. тебе надо что-то сделать с детями узла :)

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

и кстати, насчет рекурсивного метода не понял. к чему он тут?

рекурсивный метод -- самый простой способ решить эту задачу. не всегда правда оптимальный.

Теперь давай смотреть на структуру дерева.
При добавлении N узлов нужно увеличить left и right всех узлов "правее" нового на 2*N. При удалении этих же N узлов -- на 2*N.

Теперь дальше. При изменении родителя узла нужно изменить left, right и level. С последним все ясно. с left и right дело обстоит так:
новый left (и right) узлов, который перенесли и всех узлов "правее" нужно увеличить на разность right родителя и left исходного.

Я не слишком сильно оптимизировал это место, поскольку обновление происходит по индексу да и операция переноса выполняется крайне редко (в моем случае).

Выглядит это так
1. Сдвигаю дерево для новых узлов
2. Меняю left и right указанного узла и его детей так, чтобы они заполнили пустое место.
3. Ещё раз сдвигаю дерево.

Если оптимизировать до одного запроса, то нужно ставить в запрос условия на left и right.
выделять нужно три варианта:
1. узел между тем, в который вставляют и тем который вставляют.
2. узел внутри того, который вставляют.
3. узел после того, который вставляют.

Первую группу сдвигаем "вправо" на количество вставляемых узлов.
Для второй группы изменяем родителя.
Третью сдвигаем "влево" на количество вставляемых узлов + изменяем level этих узлов.

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

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