Алгоритм клонированья ветки дерева - списки смежности

ISSET · 21 Авг 2009

Алгоритм клонированья ветки дерева - списки смежности

Извините, если будут ошибки, но я по русски уже давно не писал

Вопрос такой, работаю над алгоритмом клонированья ветки дерева (дерево: списки смежности к сожалению). Бьюсь с этим уже больше месяца и никак. Идея вроде бы простая:

Table:
ID----PID--NAME
---------------------------
1----0----Name-1
2----1----Name-2
3----2----Name-3
4----3----Name-4
5----3----Name-5

Что нам дает дерево:

|-Name-1
|-- Name-2
|--- Name-3
|---- Name-4
|---- Name-5

Все просто, но вот теперь я хочу склонироват данную ветвь и получит Table:
ID----PID--NAME
---------------------------
1----0----Name-1
2----1----Name-2
3----2----Name-3
4----3----Name-4
5----3----Name-5
6----0----Name-1-clon
7----6----Name-2-clon
8----7----Name-3-clon
9----8----Name-4-clon
10---8----Name-5-clon

Что нам дает дерево:
|-Name-1
|-- Name-2
|--- Name-3
|---- Name-4
|---- Name-5
|-Name-1-clon
|-- Name-2-clon
|--- Name-3-clon
|---- Name-4-clon
|---- Name-5-clon

Помогите разобратся, запарился уже и нет свежих мыслей...

zerkms · 21 Авг 2009

1. выбрать узлы
2. добавить выбранные узлы
3. ??????????
4. PROFIT

ISSET · 21 Авг 2009

Это понятно, но заметь, что добавляя надо как то сохранять PID`ы операясь на их новых value`ах

Сдесь то и вся проблема. Не могу понять как сделать, что бы сохранит релации parent-children.

zerkms · 21 Авг 2009

и? добавляй значения. зачем тебе старые PID'ы то таскать?

INSERT INTO `table` (`PID`, `Name`) VALUES (0, $value);

дальше в цикле
INSERT INTO `table` (`PID`, `Name`) VALUES (mysql_insert_id(), $value);

неужели так трудно догадаться? месяц..... мде

ISSET · 21 Авг 2009

zerkms · 21 Авг 2009

я тебе не писал готовый код
я тебе дал намёк. намёк тебя продвинул с 0 на нереальные "уже почти работает".

ISSET · 21 Авг 2009

Какой намёк, то? Чёт я намёка сдесь не вижу?

Если ничего конкретного написать не можешь, то не мусори на форум. Я просил о помощь в логике, а получил "намёк" insert into... умник.

P.S. PHP это не проффесия, я любитель

zerkms · 21 Авг 2009

после вставки узла запоминаешь: (если это па покажется таинственным и недоступным для понимания, то поясняю - это таблица соответствия "старый ид" - "новый ид")
$ref[$old_id] = mysql_insert_id();

теперь при вставке нового узла $ref[$old_pid] это и будет твой искомый новый $pid

ps: никогда на этом форуме не указывай что, когда и кому писать.
pps: никогда не язви в стиле "умник". запомни - ты здесь гость и ты менее компетентен. если ты не понял ответ - переспроси. если ты не понял намёка - переспроси.
ppps: хэв э гуд дэй ;-)

ISSET · 21 Авг 2009

Спасибо, попробую дома. Сейчас надо идти уже домой. Sorry за "умника", но эта проблема меня уже достала.

P.S. А гость не всегда менее компетентен

zerkms · 21 Авг 2009

А гость не всегда менее компетентен

сферический гость не всегда. а ты конкретно в данном вопросе и сейчас - менее.

tf · 21 Авг 2009

не нервничай)

pilot911 · 21 Авг 2009

ребят, уважительнее к гостю, тем более, он из Варшавы

часто к нам из Польши в гости заходят ?

zerkms · 21 Авг 2009

pilot911
я, конечно, погорячился, но гостю нужно тоже совесть иметь.

ps: исправил свои посты на более политкорректные

ISSET · 3 Сен 2009

Короче, никак не получается. Может кто то подскажет все таки, где ошибка?

function autoindex(){ // beru autoindex

$maxID = mysql_fetch_array(mysql_query("SELECT MAX(id) FROM tp"));
return $maxID[0] + 1;
}

// KLONIRUJU RODITELA KOTORYJ EST W $_GET
$rodzic = mysql_fetch_array(mysql_query("SELECT * FROM tp WHERE id = " . $_GET["Page"]));

$newParentName = $rodzic[2] . '-klon';

$newParentID = autoindex();

mysql_query("INSERT INTO tp VALUES (".$newParentID.", ".$rodzic[1].", '".$newParentName."', '".$rodzic[3]."', '".$rodzic[4]."', '".$rodzic[5]."')");

$idNewParent = mysql_fetch_array(mysql_query("SELECT id FROM tp WHERE id = " . $newParentID));

// END

function MapaGalezi($ParentID) { // KLONIRUJU WSEH DETEJ RODITELIA

global $idNewParent;

$result=mysql_query("SELECT * FROM tp WHERE pid = ".$ParentID." ORDER BY name, id"); // BERU WSEH DETEJ RODITELIA

while ( $row = mysql_fetch_array($result) ) {

$newID = autoindex(); // DELAJU ID

$ref[$old_id] = mysql_insert_id(); // <------------ I TUT PROBLEMA

$newPID = $ref[$old_pid]; // <------------ I TUT PROBLEMA

mysql_query("INSERT INTO tp VALUES (".$newID.", ".$newPID.", '".$row["name"]." - ma', '".$row["start"]."', '".$row["stop"]."', '".$row["poziom"]."')");

MapaGalezi($row["id"]);
}
}

MapaGalezi($_GET["Page"]);

Этот код даёт мне склонированную ветвь дерева, но там все дети один под другим:

-Child1
--Child1
---Child1
----Child1
-----Child1

Adelf · 3 Сен 2009

PHP:

//$ParentID - id старой ветки, детей которой надо склонировать
//$newParentId - id клона ветки $ParentID
function MapaGalezi($ParentID, $newParentId) { // KLONIRUJU WSEH DETEJ RODITELIA

$result=mysql_query("SELECT * FROM tp WHERE pid = ".$ParentID." ORDER BY name, id"); // BERU WSEH DETEJ RODITELIA

while ( $row = mysql_fetch_array($result) ) {

$newID = autoindex(); // DELAJU ID

$newPID = $newParentId;

mysql_query("INSERT INTO tp(перечисли тут все поля, по порядку и делай так всегда) VALUES(".$newID.", ".$newPID.", '".$row["name"]." - ma', '".$row["start"]."', '".$row["stop"]."', '".$row["poziom"]."')");

MapaGalezi($row["id"], $newID );
}
}

Код получился неидеальный. Цель была - донести мысль.

zerkms · 3 Сен 2009

рекурсивные функции с глобалами, ну и жесть. аргументы - они для слабаков!

ISSET · 3 Сен 2009

Adelf - спасибо за мысль, немного изменил Твой код и работает

Вот код для поколений:

PHP:

function autoindex(){
	$maxID = mysql_fetch_array(mysql_query("SELECT MAX(id) FROM tp"));
	return $maxID[0] + 1;
}

$rodzic = mysql_fetch_array(mysql_query("SELECT * FROM tp WHERE id = " . $_GET["Page"]));

$newParentName = $rodzic[2] . '-klon';

$newParentID = autoindex();

mysql_query("INSERT INTO tp VALUES (".$newParentID.", ".$rodzic[1].", '".$newParentName."', '".$rodzic[3]."', '".$rodzic[4]."', '".$rodzic[5]."')");

$idNewParentName = mysql_insert_id();

function MapaGalezi($ParentID, $newParentId) {

	$result=mysql_query("SELECT * FROM tp WHERE pid = ".$ParentID." ORDER BY name, id");

	while ( $row = mysql_fetch_array($result) ) {

		$newID = autoindex();

		$newPID = $newParentId;

		mysql_query("INSERT INTO tp VALUES(NULL, ".$newPID.", '".$row["name"]."', '".$row["start"]."', '".$row["stop"]."', '".$row["poziom"]."')");

		echo "INSERT INTO tp VALUES(NULL, ".$newPID.", '".$row["name"]."', '".$row["start"]."', '".$row["stop"]."', '".$row["poziom"]."')<br />";

		MapaGalezi($row["id"], $newID);
	}
}

MapaGalezi($_GET["Page"], $idNewParentName);

Adelf · 3 Сен 2009

Если честно, то у меня бааааальшие сомнения, что это все правильно работает.

Надо отказаться от функции autoindex. Сделать все id-поля autoincrement-ными. Использовать функцию mysql_insert_id(). И сделать все прозрачнее. Задача очень простая, а выглядит слишком "сложно".

ISSET · 3 Сен 2009

Удалил autoindex и везде ID как autoincrement сделал. А код действительно работает. Проверил на ветке, у которой 450 детей и склонировало идеально, каждый чилд под своим парентом

Только клонировало длилось около 20 секунд.

Окончательно код выглядит так:

PHP:

$rodzic = mysql_fetch_array(mysql_query("SELECT * FROM tp WHERE id = " . $_GET["Page"]));

$newParentName = $rodzic[2] . ' -- KLON';

mysql_query("INSERT INTO tp VALUES (NULL, ".$rodzic[1].", '".$newParentName."', '".$rodzic[3]."', '".$rodzic[4]."', '".$rodzic[5]."')");

$idNewParent = mysql_insert_id();

function MapaGalezi($ParentID, $newParentId) {

	$result=mysql_query("SELECT * FROM tp WHERE pid = ".$ParentID." ORDER BY name, id");

	while ( $row = mysql_fetch_array($result) ) {

		$newPID = $newParentId;

		mysql_query("INSERT INTO tp VALUES(NULL, ".$newPID.", '".$row["name"]."', '".$row["start"]."', '".$row["stop"]."', '".$row["poziom"]."')");

		MapaGalezi($row["id"], mysql_insert_id());
	}
}

MapaGalezi($_GET["Page"], $idNewParent);

Adelf · 3 Сен 2009

ну уже поприятней код. Хотя еще работать и работать

Удачи в нашем нелегком деле.

Алгоритм клонированья ветки дерева - списки смежности

Новичок

TDD infected

Новичок

TDD infected

Новичок

TDD infected

Новичок

TDD infected

Новичок

TDD infected

крылья рулят

Новичок

TDD infected

Новичок

Administrator

TDD infected

Новичок

Administrator

Новичок

Administrator