Перемещение узлов дерева вместе со всеми дочерними узлами в новые места
mysql_tree_move
mysql_tree_move -- Перемещение узлов дерева вместе со всеми дочерними узлами в новые места
Содержание
Описание
mixed mysql_tree_move(string $table, array $data[, bool $is_ignore=false]);
Требуемая библиотека: mysql.tree
Перемещает узлы дерева вместе со всеми дочерними узлами в новые места дерева.
$table
-
Имя таблицы, в которой хранится дерево.
Эта таблица должны быть создана при помощи функции mysql_tree_create.
$data
-
$data - это массив элементов.
Каждый элемент содержит в себе информацию о том, какой узел куда требуется
переместить. Каждый элемент - это массив, в котором содержатся следующие
поля:
from
-
i_id узла, который требуется переместить.
Это поле является обязательным для всех элементов.
to
-
i_id элемента, к которому требуется переместить
узел from.
Значение этого поля трактуется по-разному, в зависимости от значения
поля sibling.
Узел to не может являться
ребенком узла from.
sibling
-
Задает размещение перемещаемого узла относительно
узла to. Значение по умолчанию - false.
Если значение этого поля истино, то:
-
Если задано значение узла to,
то узел from вставляется братом узла
to
слева или справа от узла
to,
в зависимости от значения поля left.
-
Если значение поля
to
не задано, то узел from, не изменяя своего родителя,
перемещается на один узел правее или на один
узел левее относительно текущего расположения, в зависимости от
значения поля left.
Если значение поля
to
не задано, то поле
left
является обязательным.
Если значение этого поля ложно или не указано, то:
-
Если задано значение узла to,
то узел from вставляется
левым или правым ребенком узла
to,
в зависимости от значения поля left.
-
Если значение поля
to
не задано, то узел from, не
изменяя своего родителя,
становится левым или правым ребенком своего родителя
(перемещается в крайнюю левую или в крайнюю правую позицию),
в зависимости от
значения поля left.
Если значение поля
to
не задано, то узел
from
становится левым или правым ребенком, смотря куда ближе
("приклеивается" к самому ближнему концу списка своих братьев).
При этом близость определяется не количеством братьев,
а количеством братьев с учетом всех дочерних узлов этих братьев.
Если слева от узла - 1 брат (у которого 20 дочерних вершин),
а справа - 10 (у которых нет дочерних вершин), то считается, что
этот узел ближе к правому краю.
left
-
Задает размещение узла from относительно
узла to. Это поле может принимать следующие значения:
-
если значение этого поля не указано, то оно принимается равным
true или false, в зависимости от того, для какого значения
потребуется пересчитать меньшее число узлов дерева.
Значение поля left не может быть не
указано, если в поле sibling
передана истина и
значение поля to
не указано.
-
если значение этого поля - true, то узел
from вставляется либо левым ребенком,
либо левым братом узла to, в зависимости
от значения поля sibling.
Если значение поля
sibling - истинно, и
значение поля to не указано,
то узел
from
перемещается на одну позицию левее.
-
если значение этого поля - false, то узел
from вставляется либо правым ребенком,
либо правым братом узла to, в зависимости
от значения поля sibling.
Если значение поля
sibling - истинно, и
значение поля to не указано,
то узел
from
перемещается на одну позицию правее.
right
-
Если задано значение этого поля, то значение
поля
left
считается по формуле:
left=!right;
Исходное значение поля
left
в таком случае игнорируется.
$is_ignore
-
Определяет реакцию функции в случае ошибок.
Если $is_ignore=true, то некоторые ошибки
могут быть проигнорированы.
Все "хорошие" элементы массива
$data
в таком случае будут перемещены.
Если $is_ignore=false, то
в случае ошибки не будет перемещен ни один узел.
Возвращаемые значения:
-1
-
Внутренняя ошибка, которая не отлавливается этой функцией.
Например, ошибка при выполнении sql-запроса.
0
-
Все узлы успешно перемещены.
false
-
Может быть возвращено только если в
$is_ignore
передано значение истина. Такой результат означает, что
некоторые узлы - успешно перемещены, а некоторые элементы
массива
$data
были проигнорированы.
1
-
В качестве аргумента
$data
был передан не массив, либо один из элементов этого массива не является
массивом.
В случае такой ошибки генерируется так же сообщение об ошибке
при помощи trigger_error.
2
-
Значение поля
from
не указано, либо не является числовым.
В случае такой ошибки генерируется так же сообщение об ошибке
при помощи trigger_error.
3
-
Значение поля
to
не указано, либо не является числовым.
В случае такой ошибки генерируется так же сообщение об ошибке
при помощи trigger_error.
4
-
Значение поля
to
совпадает со значением поля
from,
либо узел
to
является дочерним по отношению к узлу
from.
Эта ошибка может быть проигнорирована, если
в качестве аргумента
$is_ignore
передана истина.
5
-
Узел
from
не существует.
Эта ошибка может быть проигнорирована, если
в качестве аргумента
$is_ignore
передана истина.
6
-
Узел
to
не существует.
Эта ошибка может быть проигнорирована, если
в качестве аргумента
$is_ignore
передана истина.
7
-
Узел
to
является корневым и в качестве значения поля
sibling
передана истина.
Эта ошибка может быть проигнорирована, если
в качестве аргумента
$is_ignore
передана истина.
8
-
Значение поля
sibling
истинно, значение поля
to
не указано и узел
from
является самым левым (или самым правым)
узлом.
Эта ошибка может быть проигнорирована, если
в качестве аргумента
$is_ignore
передана истина.
9
-
Значение поля
sibling
истинно, и не указано ни значение поля
to,
ни значение поля
left.
В случае такой ошибки генерируется так же сообщение об ошибке
при помощи trigger_error.
10
-
Узел
from
является корневым. Корневой узел нельзя перемещать.
Эта ошибка может быть проигнорирована, если
в качестве аргумента
$is_ignore
передана истина.
Следует помнить, что элементы массива
$data
обрабатываются по очереди, один за одним.
Поскольку в этом массиве Вы можете задать любую последовательность
перемещений в дереве, то это означает, что в некоторый
момент узел
to
может оказаться дочерним узлом для узла
from,
даже если в исходном дереве такого родства не было.
Это несколько затрудняет проверку исходных данных, если они приходят
из формы. Либо передавайте истину в качестве
$is_ignore,
если Вы допускаете перемещения откуда угодно куда угодно,
либо ограничьте пользователя в том, откуда куда он может перемещать
узлы.
Пример. Использование mysql_tree_move().
<?php
$a=array(
//узел 2 сделать потомком узла 3, поместить его справа или слева,
// куда будет ближе
array('from' => 2,'to' => 3),
//узел 4 переместить на один узел левее
array('from' => 4,'sibling' => true,'left' => true),
//узел 5 расположить слева от узла 6
array('from' => 5,'to' => 6,'sibling' => true,'left' => true),
//узел 7 сделать правым ребенком узла 2
array('from' => 7,'to' => 2,'left' => false),
//узел 8 расположить справа или слева от узла 7, куда будет ближе
array('from' => 8,'to' => 7,'sibling' => true),
//следующий элемент вызовет ошибку, поскольку в результате
// предыдущих перемещений
// узел 8 стал дочерним по отношению к узлу 3
// (узел 2 стал ребенком 3, узел 7 стал ребенком 2,
// а узел 8 стал братом узла 7, и, следовательно,
// ребенком узла 2)
array('from' => 3,'to' => 8,'sibling' => true),
);
$r=mysql_tree_move('light_text_tree',$a,true);
if($r===false) $r=-2;
switch($r)
{
case 0:
echo "Все успешно перемещено";
break;
case -2:
echo "Некоторые элементы не были перемещены в результате ошибок";
break;
case 2:
case 3:
echo "Вы указали несуещствующие узлы дерева";
break;
default:
trigger_error("Invalid function result (".$r.")");
echo "На сервере произошла внутренняя ошибка.";
}
?>
|
Детали реализации
Для того, что бы понять написанное ниже, Вы должны ознакомиться с
методом хранения деревьев в базах данных,
предложенным Joe Celko, а так же
хорошо представлять себе, какие операции следует производить,
что бы перемещать узлы в дереве, хранящимся таким способом.
Функция устроена таким образом, что она пытается выполнить несколько
перемещений одним sql-запросом. Это может значительным образом
сократить общее время перемещения всех необходимых вершин в дереве,
поскольку для перемещения каждой отдельной вершины
может потребоваться пересчитать значительную часть дерева,
которую так же придется пересчитывать при перемещении остальных вершин.
Тем не менее, само построение такого sql-запроса -
довольно трудоемкая задача. При некоторых обстоятельствах
(при маленьком дереве и большом количестве перемещений)
может даже оказаться, что быстрее выполнить перемещения
несколькими sql-запросами.
Скорость построения sql-запроса в значительной степени зависит от того,
на скольких разных интервалах следует произвести пересчет узлов
дерева.
Разными считаются интервалы, если они не смежные,
либо если на этих интервалах правые и левые значения узлов
следует пересчитывать на разные значения.
Если два интервала являются смежными и на этих интервалах
следует производить пересчет на одинаковые значения,
то фактически эти два интервала являются одним интервалом.
При перемещении одного узла, седует пересчитать все узлы на двух разных
интервалах. При перемещении нескольких узлов, количество разных
интервалов зависит от характера перемещения узлов.
Например, если некоторые узлы, являющиеся смежными братьми,
перемещаются в новую родительскую вершину в таком же порядке
(слева на право), как они располагались в исходной родительской вершине,
то число разных интервалов будет равно двум, как и при перемещении одной
вершины. В таком случае функция
даст значительное (максимальное) ускорение перемещения узлов дерева.
Если перемещается некоторый узел дерева А, а потом перемещается узел В,
который в исходном дереве был родительским для узла А,
то при перемещении узла В потребуется произвести пересчет не по двум
дополнительным разным интервалам, а уже по трем
дополнительным разным интервалам (интервал
для узла В раньше был одним интервалом, который включал в себя интервал для узла А, а
теперь это два разных интервала + отдельный интервал для узла А).
Не сложно посчитать, на скольких разных интервалах
нужно будет пересчитать дерево, если потребуется так же переместить узел С,
который в исходном дереве являлся родительским для узла В.
Экспериментальным путем установлено, что в наихудшем случае
(когда по всему дереву
случайные вершины перемещаются в случайных направлениях;
дерево маленькое, в нем содержится всего 1000 вершин)
функция не будет вызывать замедления процесса перемещения, если
количество разных интервалов, на которых следует произвести пересчет узлов,
не превышает 70.
Функция устроена таким образом, что при превышении этого лимита
она генерирует новый sql-запрос.
В большинстве реальных случаев, однако, перемещения будут выполняться
одним sql-запросом. Ограничение "70 разных интервалов" означает,
что за один проход перемещается порядка 30-40 узлов в разных направлениях.
Если же узлы перемещаются в одном направлении, есть варианты, когда
узлы были и остаются смежными, то количество узлов, которые можно
переместить, не превысив это ограничение, возрастает.
Кроме того, если общее число узлов в дереве не превышает 36, то любое
количество перемещений в любых направлениях будет выполнено за один проход,
поскольку для такого дерева максимальное количество принципиально возможных
разных
интервалов равно 70 (для каждого узла - левое и правое значение; корневой узел
не может быть перемещен, и поэтому не учитывается).
Скачать
Библиотека функций для работы с деревьями:
zip-архив, 19 734 байт: скачать
|
|| разделы::
