Конвертирование Adjacency List в Nested Sets

дедушка АУ

Новичок
Конвертирование Adjacency List в Nested Sets

Всем привет )
Сабж.
щас у мя

CREATE TABLE `chapters` (
`ChapterID` int(6) unsigned NOT NULL auto_increment,
`ChapterPID` int(6) unsigned default NULL,
`Name` varchar(255) NOT NULL default '',
`Description` varchar(255) default NULL,
`SortOrder` tinyint(3) unsigned default NULL,
PRIMARY KEY (`ChapterID`),
UNIQUE KEY `ChapterID` (`ChapterID`)
) ENGINE=MyISAM DEFAULT CHARSET=cp1251;

помню что как-то можно было автоматом пройтись по данному списку и повставлять left и right автоматом

плиз напомните:)
 

Popoff

popoff.donetsk.ua
помню что как-то можно было автоматом пройтись по данному списку и повставлять left и right автоматом
нет, одного прохода не достаточно: чтобы узнать правое значение, нужно знать количество детей. чтобы дойти до детей, нужно пройти родительскую вершину. поэтому родительская вершина будет посещена дважды: 1) при переходе к детям - проставляется левое значение и 2) при возврате от детей - проставляется правое значение.

помню что как-то можно было
а подумать?

или тот, кто говорит слово "автоматом", подразумевает слово "есть готовый скрипт"?
 

дедушка АУ

Новичок
нет, одного прохода не достаточно: чтобы узнать правое значение, нужно знать количество детей. чтобы дойти до детей, нужно пройти родительскую вершину. поэтому родительская вершина будет посещена дважды: 1) при переходе к детям - проставляется левое значение и 2) при возврате от детей - проставляется правое значение.
а если рекрурсивом от родителей к детям + isert этих детей к родителю?

а подумать?
или тот, кто говорит слово "автоматом", подразумевает слово "есть готовый скрипт"?
не хотелось изобретать велосипед дважды. просто почему то думал что такой скрипт уже где-то видел)
 

дедушка АУ

Новичок
Popoff
написал)

в ФАКе? а как же всемирно известное утверждение коренных жителей форума о том что надо самому думать головой? типа "здесь тебе никто ничего не сделает", получится бери готовое вставляй и работай.
мне скрипта не жалко :) выложу без проблем =)))
НО не противоречит ли это вашим же словам
"а подумать?" ? :)

-~{}~ 05.10.05 13:15:

идея ясна "рекрурсив от родителей к детям + insert этих детей к родителю" ;)
 

Popoff

popoff.donetsk.ua
дедушка АУ
Призыв "подумай!" предназначен не для того, кто его делает. Тому, кто призывает "подумай!", скорее всего наплевать на судьбу того, кого он призывает. А вот тому, кого призывают, не должно быть наплевать на себя. Если человек не откликается на призыв "подумай!", то он будет обречен постоянно ждать подачки от других - когда же за него решат его проблему. Если человек откликнется на этот призыв, то тем самым приобретет известную независимость от окружающего мира - свои проблемы он теперь сможет решать самостоятельно. И, вероятно, гораздо быстрее.

Да, мне, и большинству тех, кто призывает других подумать, интереснее общаться с людьми, которые сами любят думать. Первые сто раз объяснять, почему "два жы два равно четыре", я мог спокойно. Но людей, которые этого не понимают, оказывается, гораздно больше, чем сто. И, наверное, поэтому даже очень терпеливый человек, к коим я себя, любимого, отношу, на сто первый начнет думать о том, что тот, кто не понимает, почему "два жы два равно четыре", на самом деле не хочет понимать этого.

Да, создание фака противоречит призыву "подумай!". Можно было бы даже сказать, что фак сам по себе является средством развращения. Но он является средством развращения лишь для тех, кто не хочет думать. Это дело каждого отдельного человека решать, хочет ли он думать или нет.

Фак создается для того, чтобы оградить себя от общения с людьми, которые не хотят думать. Хотя, конечно, это - не более чем одна из многих целей.

====

Написал - поделись с общественностью! :)
 

дедушка АУ

Новичок
Popoff
не дави интеллектом :))))

Написал - поделись с общественностью!
забирай :)) тока если что не так скажи - подправлю (мож че неграмотно или тп)

значит таблицы две: chapters(из которого берутся данные) и tree (новое дерево)

дело в том что id в tree буду различаться от id которое в chapters, т.к. в tree добавится корень дерева Главная, поэтому приходится брать уже новый id из tree и использовать его при вставке потомков.

Функция рекурсивно проходит от родителей к потомкам добавляя новых потомков используя функцию insert из класса CDBTree + CDatabase


значит таблицы две: chapters(из которого берутся данные) и tree (новое дерево)

дело в том что id в tree буду различаться от id которое в chapters, т.к. в tree добавится корень дерева Главная, поэтому приходится брать уже новый id из tree и использовать его при вставке потомков.

Функция рекурсивно проходит от родителей к потомкам добавляя новых потомков используя функцию insert из класса CDBTree + CDatabase

PHP:
//$gEng->ptrDBTree->clear(array("Name"=>"Главная"));  //вставляем корень дерева (у меня он уже был вставлен id=1)


function recursiveTree(&$e,$id){
        	
   if ($id=='0'){
      $result = $e->ptrDB->query("SELECT * FROM chapters WHERE ChapterPID is NULL ORDER BY SortOrder"); //в таблице chapters все родители были с ChapterID=NULL
   } else {
      $result = $e->ptrDB->query("SELECT * FROM chapters WHERE ChapterPID='$id' ORDER BY SortOrder");        		
   }
        	
   if (mysql_num_rows($result)!==0) {
      while ($row=$e->ptrDB->fetch_array($result)) {

         if ($id=='0'){ 
            $pid = '1';
         } else {
        				      				
            $get_parentNodeInfo_result = $e->ptrDB->query("SELECT Name FROM chapters WHERE ChapterID='$id'"); //узнаем имя нового родителя из таблицы 
            $get_parentNodeInfo_array = mysql_fetch_array($get_parentNodeInfo_result);	
        				
            $get_pid_result = $e->ptrDB->query("SELECT ChapterID FROM tree WHERE Name='".$get_parentNodeInfo_array['Name']."'");//узнаем id нового родителя в tree используя имя полученное из таблицы chapters
            $get_pid_array = mysql_fetch_array($get_pid_result);
            $pid = $get_pid_array['ChapterID'];
         }

         if ($e->ptrDBTree->insert($pid,array("ChapterPID"=>$pid,"Name"=>$row['Name']))) {
            echo "Запись добавлена<br>";
         } else {
            echo "Ошибка: запись не добавлена<br>";	
            return false;
         }

         recursiveTree($e,$row['ChapterID']);
	 return true;
      }
        			
   } else {
      echo "Потомков нет.<br><br><br>";
   }
}
        
recursiveTree($gEng,"0");
таблица chapter (из которой берутся данные)
CREATE TABLE `chapters` (
`ChapterID` int(6) unsigned NOT NULL auto_increment,
`ChapterPID` int(6) unsigned default NULL,
`Name` varchar(255) NOT NULL default '',
`Description` varchar(255) default NULL,
`SortOrder` tinyint(3) unsigned default NULL,
PRIMARY KEY (`ChapterID`),
UNIQUE KEY `ChapterID` (`ChapterID`)
) ENGINE=MyISAM DEFAULT CHARSET=cp1251;

таблица tree (где формируется новое дерево)
CREATE TABLE `tree` (
`ChapterID` int(6) unsigned NOT NULL auto_increment,
`ChapterPID` int(6) unsigned default NULL,
`Name` varchar(255) NOT NULL default '',
`Description` varchar(255) default NULL,
`SortOrder` tinyint(3) unsigned default NULL,
`cLeft` INT UNSIGNED NOT NULL,
`cRight` INT UNSIGNED NOT NULL,
`cLevel` INT UNSIGNED NOT NULL,
PRIMARY KEY (`ChapterID`),
UNIQUE KEY `ChapterID` (`ChapterID`),
KEY(cLeft, cRight, cLevel)
);

-~{}~ 06.10.05 08:57:

ChapterPID был сохранен для удобства :) но совершенно необязателен
 

Popoff

popoff.donetsk.ua
Вот тебе мой вариант:
PHP:
<?php

function tree_al_ns($s_table,$k_parent=0,$i_value=0)
//обновляет вложенные множества в соответствие со списками смежности
//$s_table содержит в себе имя таблицы с деревом.
//  В этой таблице дерево хранится комбинированным способом:
//  списки смежности и вложенные множества
//$k_parent - идентификатор текущей родительской вершины.
//  0 - для корневой вершины
//$i_value - идентификатор первого свободного значения (левого или правого)
//возвращает следующее свободное значение или
//  false в случае ошибки
//пример вызова:
//  if(tree_al_ns('t_catalog_tree')===false)
//    echo 'Конвертирование прошло с ошибками.';
{
  if(!is_numeric($k_parent)||!is_numeric($i_value)) return false;
  $r=mysql_query("select k_item from ".$s_table." where k_parent=".$k_parent);
  if(!$r) return false;
  for($i=0;$i<mysql_num_rows($r);$i++)
  {
    $f=mysql_fetch_row($r);
    $k_item=$f[0];
    $i_right=tree_al_ns($s_table,$k_item,$i_value+1);
    if($i_right===false) return false;
    if(!mysql_query("
      update
        ".$s_table."
      set
        i_left=".$i_value.",
        i_right=".$i_right."
      where
        k_item=".$k_item."
      ")) return false;
    $i_value=$i_right+1;
  }
  return $i_value;
}

?>
отличия от твоего состоят в следующем:
1. это одно дерево, а не два. это дерево представлено комбинацией списков смежности и вложенных множеств. поэтому все хранится в одной таблице.
2. собственно поэтому идентификатор совпадает
3. вставка узла во вложенных множествах - это довольно долгая операция. это, без сомнения, минус твоего способа. в моем способе узлы не вставляются, а только пересчитываются правые и левые значения
4. но в моем способе тоже можно обнаружить недостаток. например, не совсем ясно, как будет быстрее, так как я решил задачу - загружать непосредственных потомков для каждой вершины отдельно или если загрузить сразу все дерево в память.

==========

Не совсем ясно, какой из этих двух способов лучше. Если поместить в факе мой способ, то ищущие будут задаваться вопросом "а как же ш быть, если нам нужно создать другое дерево". если поместить твой способ, то другие ищущие будут задаваться вопросом "а что делать, если дерево уже существует и операция insert нам не подходит?". если помещать оба способа, то логично было бы поместить также и все остальные способы.

Именно поэтому я и сказал: "подумай!". потому что кода-то всего десять несчастных операторов.
 

дедушка АУ

Новичок
ну я не знаю)) смотрите сами помещать или нет) в любом случае твой вариант куда грамотнее моего :)

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