Меню
Что нового?

Nested Sets, формирование дерева в массиве

31337Ghost

Новичок
Nested Sets, формирование дерева в массиве

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

Это была преамбула - теперь к делу:
Есть массив, в котором сформировано дерево, такого вида -
14(0)
[]17(1)
[][]20(2)
[][][]21(3)
[][][][]16(4)
[][]18(2)
[][][]9(3)
[][][][]13(4)
[][][][]10(4)
[][][][][]12(5)
[][][][][][]11(6)
[][][][][][][]15(7)
[][]22(2)

в массиве хранится id объекта и его уровень, основываясь на этих данных хочется завернуть данный массив в бд по Nested Sets.
Немного запутано объяснил, но все же - надо банально каждому элементу массива приписать left и right положение, т.е. пройтись по всему массиву и каждому элементу приписать недостающие (для таблицы Nested Sets) поля.

В голове крутится такое решение:
Идем по массиву с верху в низ и на каждом элементе увеличиваем счетчик, приписывая каждому пройденному элементу left. Проверяем попутно, если следующий элемент массива имеет level меньше levela текущего элемента, то начинаем шагать обратно (и запоминаем номер элемента на котором остановились - пусть будет X) опять же плюсуя счетчик и прописывая right элементу, мимо которого сейчас идем. Если дошли до элемента, level которого равен levelу элемента X+1 (X - запомненный ранее номер элемента с которого мы пошли "на верх", по структуре, прописывать right) - то вписываем текущему right и перескакиваем на X+1. И так далее пока не дойдем до самого низа.
При таком алгоритме, единственное, первые два элемента массива останутся без right'ов. На этот счет можно изначально считать скольким элементам прописали right, затем взять общее количество элементов массива, получить разницу - это у будет 2, т.е. первые два элемента и пройтись от этой разницы (2) до начала массива и так же вбить им right.

В общем вопрос - есть ли более рациональный способ, нежели тот, который я описал? И нет ли бага в данном алгоритме?

З.Ы. Перечитал эту ахинею, что написал, простите за полную кашу, но мозг уже не хочет придумывать другое описание моей проблемы.
 
zerkms

zerkms

TDD infected
Команда форума
взять любую библиотеку для работы с NS (или написать самому) и просто рекурсивно добавить узлы.
 

31337Ghost

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

-~{}~ 09.07.09 14:19:

В общем получилось вот так, если кому интересно, пригодится:

$result - массив - дерево
$result[][0] - id элемента
$result[][1] - level элемента
$result[][2] - left элемента
$result[][3] - right элемента


PHP: 
$count=1;
$i=0;
$x=-1;
while (true) {
	 if ($x==-1) {
		if ($i==count($result)-1) {
			$result[$i][2]=$count;
		 	$count++;
		 	$result[$i][3]=$count;
		 	$count++;
		 	break;
		}
	 	if ($result[$i+1][1]>=$result[$i][1]) {
		 	$result[$i][2]=$count;
		 	$count++;
		 	$i++;
		 } else {
		 	$x=$i;
		 	$result[$i][2]=$count;
		 	$count++;
		 	$result[$i][3]=$count;
		 	$count++;
		 	$i--;	
		 }
	 } else {
	 	if ($result[$i][1]==$result[$x+1][1]) {
	 		$result[$i][3]=$count;
		 	$count++;
		 	$i=$x+1;
		 	$x=-1;
	 	} else {
	 		$result[$i][3]=$count;
		 	$count++;
		 	$i--;
	 	}
	 }
}

if ((count($result)*2)>$count) {
	for ($i=((count($result)*2)-$count);$i>=0;$i--) {
		$result[$i][3]=$count;
		$count++;
	}
}
 
grigori

grigori

( ͡° ͜ʖ ͡°)
Команда форума
O_O Первый раз вижу псевдографику на этом форуме!
 
zerkms

zerkms

TDD infected
Команда форума
судя по характеру кода та же самая логика очень хорошо может лечь на FSA, и будет смотреться элегантнее и читаемее :)

ps: за решение респект.
 

31337Ghost

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

zerkms

TDD infected
Команда форума
31337Ghost
кстати сейчас вот подумал, смотри как можно реализовать:
(просто идея из головы, реализовывать не пробовал - так что могу где-то ошибаться)

берём плоский массив. и начинаем "зарываться" вглубь. по мере прохождения действуем так:
левый ключ мы и так знаем, постоянно считаем его.
правый пересчитываем динамически примерно так:
- первый элемент рут. левый ключ 1. правый 2 (инициализация)
- переходим на уровень ниже. сохраняем рут (в момент перехода) как breadcrumb (ниже поясню зачем). прописываем элементу левый ключ 2, правый 3.
- пересчёт: по breadcrumb ищем все родительские узлы и делаем +2 на правый ключ.

- если уходим глубже - тогда снова: новому элементу присваиваем левый ключ 3. правый 4. верхним пересчитываем: 3+2 = 5 (для 2 уровня). 4 + 2 = 6 (для первого).
- если уходим выше - то тоже всё очевидно: удаляем из пути ненужные хлебные крошки, а правый ключ-то уже расчитан.

повторяем до готовности. м? :)

ps: про уровень не сказал - но уровень считается тривиально, сам понимаешь.
 

31337Ghost

Новичок
zerkms, спасибо, кстати только сейчас допер, что примерно так, как вы описали, и ведется расчет в примерах по использованию NS :)

Но сам все же добил:

PHP: 
function DigTree($mylevel,$startid,$startcount) {
	global $result;
	$workid=$startid;
	$workcount=$startcount;
	$childres=array();
	$answer=array();
	while (true) {
		if ($workid==count($result)-1) {
			$result[$workid][2]=$workcount;
			$workcount++;
			$result[$workid][3]=$workcount;
			$workcount++;
			$answer[0]=$workcount;
			$answer[1]=$workid;
			return $answer;
			break;
		} else {
			if (($result[$workid][1]==$mylevel) AND ($result[$workid+1][1]==$mylevel+1)) {
				$result[$workid][2]=$workcount;
				$workcount++;
				$childres=DigTree($mylevel+1,$workid+1,$workcount);
				$workcount=$childres[0];
				$result[$workid][3]=$workcount;
				$workcount++;
				$workid=$childres[1];
				if ($workid==count($result)-1) {
					if (($result[$workid][1]==$mylevel) AND ($result[$workid][2]=="") AND ($result[$workid][3]=="")) {
						$result[$workid][2]=$workcount;
						$workcount++;
						$result[$workid][3]=$workcount;
						$workcount++;
					}
					$answer[0]=$workcount;
					$answer[1]=$workid;
					return $answer;
					break;
				}
			} 
			if (($result[$workid][1]==$mylevel) AND ($result[$workid+1][1]==$mylevel)) {
				$result[$workid][2]=$workcount;
				$workcount++;
				$result[$workid][3]=$workcount;
				$workcount++;
				$workid++;
			}
			if (($result[$workid][1]==$mylevel) AND ($result[$workid+1][1]<$mylevel)) {
				$result[$workid][2]=$workcount;
				$workcount++;
				$result[$workid][3]=$workcount;
				$workcount++;
				$workid++;
				$answer[0]=$workcount;
				$answer[1]=$workid;
				return $answer;
				break;
			}
			if ($result[$workid][1]!=$mylevel) {
				$answer[0]=$workcount;
				$answer[1]=$workid;
				return $answer;
				break;
			}
		}		
	}
}

DigTree(0,0,1);
Структура массива $result остается та же.
В прочем предыдущий код тоже расставлял leftы и rightы, только совершенно не для структуры NS :) Текущий же код адекватно разбирается с деревом, находящемся, в массиве) Ура!)

Спасибо за советы)
Кстати - может как-то данный код облегчить, сделать его более симпотичным? А то как-то увесисто получается.
Плюс можно данную функцию запихать в какой нибудь cookbook, ибо мои изыскания функции подобного функционала результата не дали.
 
zerkms

zerkms

TDD infected
Команда форума
Кстати - может как-то данный код облегчить, сделать его более симпотичным?
Нажмите для раскрытия...
ну, если описанный мной алгоритм будет работать, то он будет проще.
 
Войдите или зарегистрируйтесь для ответа.
Сверху