Перемещение узлов дерева вместе со всеми дочерними узлами в новые места


Прислал: Yuri Popoff [ 10.05.2005 @ 22:31 ]
Раздел:: [ Статьи по PHP ]

mysql_tree_move

mysql_tree_move -- Перемещение узлов дерева вместе со всеми дочерними узлами в новые места

Содержание

  • Описание функции ( http://webscript.ru/#description )
  • Детали реализации ( http://webscript.ru/#details )
  • Скачать ( http://webscript.ru/#download )

ї

Описание

mixed mysql_tree_move(string $table ( http://webscript.ru/#arg.table ), array $data ( http://webscript.ru/#arg.data )[, bool $is_ignore ( http://webscript.ru/#arg.is_ignore )=false]);

Требуемая библиотека: mysql.tree ( http://webscript.ru/./ )

Перемещает узлы дерева вместе со всеми дочерними узлами в новые места дерева.

from ( http://webscript.ru/#arg.data.from ). Значение этого поля трактуется по-разному, в зависимости от значения поля sibling ( http://webscript.ru/#arg.data.sibling ). Узел to ( http://webscript.ru/#arg.data.to ) не может являться ребенком узла from ( http://webscript.ru/#arg.data.from ).
to ( http://webscript.ru/#arg.data.to ). Значение по умолчанию - false. Если значение этого поля истино, то:
  • Если задано значение узла to ( http://webscript.ru/#arg.data.to ), то узел from ( http://webscript.ru/#arg.data.from ) вставляется братом узла to ( http://webscript.ru/#arg.data.to ) слева или справа от узла to ( http://webscript.ru/#arg.data.to ), в зависимости от значения поля left ( http://webscript.ru/#arg.data.left ).
  • Если значение поля to ( http://webscript.ru/#arg.data.to ) не задано, то узел from ( http://webscript.ru/#arg.data.from ), не изменяя своего родителя, перемещается на один узел правее или на один узел левее относительно текущего расположения, в зависимости от значения поля left ( http://webscript.ru/#arg.data.left ). Если значение поля to ( http://webscript.ru/#arg.data.to ) не задано, то поле left ( http://webscript.ru/#arg.data.left ) является обязательным.
Если значение этого поля ложно или не указано, то:
  • Если задано значение узла to ( http://webscript.ru/#arg.data.to ), то узел from ( http://webscript.ru/#arg.data.from ) вставляется левым или правым ребенком узла to ( http://webscript.ru/#arg.data.to ), в зависимости от значения поля left ( http://webscript.ru/#arg.data.left ).
  • Если значение поля to ( http://webscript.ru/#arg.data.to ) не задано, то узел from ( http://webscript.ru/#arg.data.from ), не изменяя своего родителя, становится левым или правым ребенком своего родителя (перемещается в крайнюю левую или в крайнюю правую позицию), в зависимости от значения поля left ( http://webscript.ru/#arg.data.left ).

    Если значение поля to ( http://webscript.ru/#arg.data.to ) не задано, то узел from ( http://webscript.ru/#arg.data.from ) становится левым или правым ребенком, смотря куда ближе ("приклеивается" к самому ближнему концу списка своих братьев). При этом близость определяется не количеством братьев, а количеством братьев с учетом всех дочерних узлов этих братьев. Если слева от узла - 1 брат (у которого 20 дочерних вершин), а справа - 10 (у которых нет дочерних вершин), то считается, что этот узел ближе к правому краю.
from ( http://webscript.ru/#arg.data.from ) относительно узла to ( http://webscript.ru/#arg.data.to ). Это поле может принимать следующие значения:
  • если значение этого поля не указано, то оно принимается равным true или false, в зависимости от того, для какого значения потребуется пересчитать меньшее число узлов дерева. Значение поля left ( http://webscript.ru/#arg.data.left ) не может быть не указано, если в поле sibling ( http://webscript.ru/#arg.data.sibling ) передана истина и значение поля to ( http://webscript.ru/#arg.data.to ) не указано.
  • если значение этого поля - true, то узел from ( http://webscript.ru/#arg.data.from ) вставляется либо левым ребенком, либо левым братом узла to ( http://webscript.ru/#arg.data.to ), в зависимости от значения поля sibling ( http://webscript.ru/#arg.data.sibling ). Если значение поля sibling ( http://webscript.ru/#arg.data.sibling ) - истинно, и значение поля to ( http://webscript.ru/#arg.data.to ) не указано, то узел from ( http://webscript.ru/#arg.data.from ) перемещается на одну позицию левее.
  • если значение этого поля - false, то узел from ( http://webscript.ru/#arg.data.from ) вставляется либо правым ребенком, либо правым братом узла to ( http://webscript.ru/#arg.data.to ), в зависимости от значения поля sibling ( http://webscript.ru/#arg.data.sibling ). Если значение поля sibling ( http://webscript.ru/#arg.data.sibling ) - истинно, и значение поля to ( http://webscript.ru/#arg.data.to ) не указано, то узел from ( http://webscript.ru/#arg.data.from ) перемещается на одну позицию правее.
їright
Если задано значение этого поля, то значение поля left ( http://webscript.ru/#arg.data.left ) считается по формуле:
left ( http://webscript.ru/#arg.data.left )=! right ( http://webscript.ru/#arg.data.right );
Исходное значение поля left ( http://webscript.ru/#arg.data.left ) в таком случае игнорируется.
ошибки ( http://webscript.ru/#error ) могут быть проигнорированы. Все "хорошие" элементы массива $data ( http://webscript.ru/#arg.data ) в таком случае будут перемещены. Если $is_ignore=false, то в случае ошибки не будет перемещен ни один узел.

$is_ignore ( http://webscript.ru/#arg.is_ignore ) передано значение истина. Такой результат означает, что некоторые узлы - успешно перемещены, а некоторые элементы массива $data ( http://webscript.ru/#arg.data ) были проигнорированы.

1
В качестве аргумента $data ( http://webscript.ru/#arg.data ) был передан не массив, либо один из элементов этого массива не является массивом. В случае такой ошибки генерируется так же сообщение об ошибке при помощи trigger_error.
2
Значение поля from ( http://webscript.ru/#arg.data.from ) не указано, либо не является числовым. В случае такой ошибки генерируется так же сообщение об ошибке при помощи trigger_error.
3
Значение поля to ( http://webscript.ru/#arg.data.to ) не указано, либо не является числовым. В случае такой ошибки генерируется так же сообщение об ошибке при помощи trigger_error.
4
Значение поля to ( http://webscript.ru/#arg.data.to ) совпадает со значением поля from ( http://webscript.ru/#arg.data.from ), либо узел to ( http://webscript.ru/#arg.data.to ) является дочерним по отношению к узлу from ( http://webscript.ru/#arg.data.from ). Эта ошибка может быть проигнорирована, если в качестве аргумента $is_ignore ( http://webscript.ru/#arg.is_ignore ) передана истина.
5
Узел from ( http://webscript.ru/#arg.data.from ) не существует. Эта ошибка может быть проигнорирована, если в качестве аргумента $is_ignore ( http://webscript.ru/#arg.is_ignore ) передана истина.
6
Узел to ( http://webscript.ru/#arg.data.to ) не существует. Эта ошибка может быть проигнорирована, если в качестве аргумента $is_ignore ( http://webscript.ru/#arg.is_ignore ) передана истина.
7
Узел to ( http://webscript.ru/#arg.data.to ) является корневым и в качестве значения поля sibling ( http://webscript.ru/#arg.data.sibling ) передана истина. Эта ошибка может быть проигнорирована, если в качестве аргумента $is_ignore ( http://webscript.ru/#arg.is_ignore ) передана истина.
8
Значение поля sibling ( http://webscript.ru/#arg.data.sibling ) истинно, значение поля to ( http://webscript.ru/#arg.data.to ) не указано и узел from ( http://webscript.ru/#arg.data.from ) является самым левым (или самым правым) узлом. Эта ошибка может быть проигнорирована, если в качестве аргумента $is_ignore ( http://webscript.ru/#arg.is_ignore ) передана истина.
9
Значение поля sibling ( http://webscript.ru/#arg.data.sibling ) истинно, и не указано ни значение поля to ( http://webscript.ru/#arg.data.to ), ни значение поля left ( http://webscript.ru/#arg.data.left ). В случае такой ошибки генерируется так же сообщение об ошибке при помощи trigger_error.
10
Узел from ( http://webscript.ru/#arg.data.from ) является корневым. Корневой узел нельзя перемещать. Эта ошибка может быть проигнорирована, если в качестве аргумента $is_ignore ( http://webscript.ru/#arg.is_ignore ) передана истина.

Следует помнить, что элементы массива $data ( http://webscript.ru/#arg.data ) обрабатываются по очереди, один за одним. Поскольку в этом массиве Вы можете задать любую последовательность перемещений в дереве, то это означает, что в некоторый момент узел to ( http://webscript.ru/#arg.data.to ) может оказаться дочерним узлом для узла from ( http://webscript.ru/#arg.data.from ), даже если в исходном дереве такого родства не было. Это несколько затрудняет проверку исходных данных, если они приходят из формы. Либо передавайте истину в качестве $is_ignore ( http://webscript.ru/#arg.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 "На сервере произошла внутренняя ошибка.";
}

?>

ї

Детали реализации

Для того, что бы понять написанное ниже, Вы должны ознакомиться с методом хранения деревьев в базах данных ( http://webscript.ru///www.intelligententerprise.com/001020/celko.shtml ), предложенным Joe Celko ( http://webscript.ru///celko.com/ ), а так же хорошо представлять себе, какие операции следует производить, что бы перемещать узлы в дереве, хранящимся таким способом.

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

Тем не менее, само построение такого sql-запроса - довольно трудоемкая задача. При некоторых обстоятельствах (при маленьком дереве и большом количестве перемещений) может даже оказаться, что быстрее выполнить перемещения несколькими sql-запросами.

Скорость построения sql-запроса в значительной степени зависит от того, на скольких разных интервалах следует произвести пересчет узлов дерева.

разных ( http://webscript.ru/#interval.diff ) интервалах. При перемещении нескольких узлов, количество разных ( http://webscript.ru/#interval.diff ) интервалов зависит от характера перемещения узлов.

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

Если перемещается некоторый узел дерева А, а потом перемещается узел В, который в исходном дереве был родительским для узла А, то при перемещении узла В потребуется произвести пересчет не по двум дополнительным разным ( http://webscript.ru/#interval.diff ) интервалам, а уже по трем дополнительным разным ( http://webscript.ru/#interval.diff ) интервалам (интервал для узла В раньше был одним интервалом, который включал в себя интервал для узла А, а теперь это два разных интервала + отдельный интервал для узла А). Не сложно посчитать, на скольких разных ( http://webscript.ru/#interval.diff ) интервалах нужно будет пересчитать дерево, если потребуется так же переместить узел С, который в исходном дереве являлся родительским для узла В.

Экспериментальным путем установлено, что в наихудшем случае (когда по всему дереву случайные вершины перемещаются в случайных направлениях; дерево маленькое, в нем содержится всего 1000 вершин) функция не будет вызывать замедления процесса перемещения, если количество разных ( http://webscript.ru/#interval.diff ) интервалов, на которых следует произвести пересчет узлов, не превышает 70. Функция устроена таким образом, что при превышении этого лимита она генерирует новый sql-запрос.

В большинстве реальных случаев, однако, перемещения будут выполняться одним sql-запросом. Ограничение "70 разных ( http://webscript.ru/#interval.diff ) интервалов" означает, что за один проход перемещается порядка 30-40 узлов в разных направлениях. Если же узлы перемещаются в одном направлении, есть варианты, когда узлы были и остаются смежными, то количество узлов, которые можно переместить, не превысив это ограничение, возрастает.

Кроме того, если общее число узлов в дереве не превышает 36, то любое количество перемещений в любых направлениях будет выполнено за один проход, поскольку для такого дерева максимальное количество принципиально возможных разных ( http://webscript.ru/#interval.diff ) интервалов равно 70 (для каждого узла - левое и правое значение; корневой узел не может быть перемещен, и поэтому не учитывается).

ї

Скачать

Библиотека функций для работы с деревьями:
zip-архив, 19 734 байт: скачать ( http://webscript.ru///counter.mirohost.net/dlcount.php?id=popoff&url=//popoff.donetsk.ua/download/mysql-tree.zip )