Menu w postaci drzewa

Tak więc ostatnio gdy starałem się o pracę w pewnej firmie, dostałem jako zlecenie stworzenie menu o strukturze drzewa z nieograniczonymi gałęziami, liśćmi. Każdy kto programuje chwilkę w końcu natknie się na ten problem i będzie szukał rozwiązania w internecie. Tak samo było zemną, no więc założenia do projektu:

struktura drzewa
nieograniczona ilość gałęzi i liści
przenoszenie gałęzi wraz z zawartością
usuwanie gałęzi wraz z zawartością

Są to podstawowe założenia do projektu jakie są nam potrzebne, tak więc wyruszając w przygodę z google i znalezieniem jakiejś ciekawej struktury dla sql, na ircu od adi^R dostałem ciekawego linka depesz.com. Gościu opisuje jak rozwiązać ten problem z poziomu sql’a. No tak więc mamy już jeden problem z głowy (poniżej opiszę wszystko po kolei), został nam drugi, algorytm który będzie tą strukturę drzewa tworzył w php i zrobi z nam tego tablicę taką żeby móc ja ładnie użyć z smartami (tak przeszedłem na smarty z ITX, dlaczego? a tak jakoś). No i tu były schody, ponieważ twórcy smartów nie przewidzieli, lub nie chcieli przewidzieć rekurencji w ich skrypcie. Co nam pozostaje? W rekurencji includowanie tego samego pliku przy każdym kolejnym wykonaniu operacji, lub znaleźć plugin który to zrobi za nas.

Dobra po kolei, zacznijmy od kodu sql który jest na potrzebny i niezbędny do życia, więc na pewno potrzebne nam są dwie tabele oto one:

CREATE TABLE "kategorie" (
   "id" serial PRIMARY KEY,
   "name" text, -- ważne name nie jest unique
   "parent_id" integer,
   FOREIGN KEY ("parent_id") REFERENCES "kategorie" ("id") ON DELETE cascade
);
 
CREATE TABLE "powiazania" (
    "id" serial PRIMARY KEY,
    "parent_id" integer NOT NULL,
    "child_id" integer NOT NULL,
    "depth" integer NOT NULL,
    FOREIGN KEY ("parent_id") REFERENCES "kategorie" ("id") ON DELETE cascade,
    FOREIGN KEY ("child_id") REFERENCES "kategorie" ("id") ON DELETE cascade
);

Poprawiłem tutaj trochę po fabryce, czyli po Hubercie Lubaczewskim, autorem tego skryptu. Bo tak mi pasowało zresztą gdy porównacie mój kod sql (mowa o tych 2 tabelach) zobaczycie różnice.

Następne co nam będzie potrzebne to funkcja oraz triger która dodaje za nas powiązania:

CREATE LANGUAGE plpgsql; 
 
CREATE OR REPLACE FUNCTION tree_objects_ai() RETURNS TRIGGER AS
 $BODY$
 DECLARE
 BEGIN
  INSERT INTO powiazania (parent_id, child_id, depth) VALUES (NEW.id, NEW.id, 0);
  INSERT INTO powiazania (parent_id, child_id, depth) SELECT x.parent_id, NEW.id, x.depth + 1 FROM powiazania x WHERE x.child_id = NEW.parent_id;
  RETURN NEW;
 END;
 $BODY$
LANGUAGE 'plpgsql';
 
-- Dzięki tej procedurze, nie ważne czy mamy zagnieżdżenie 2, 3, 9, 231 stopniowe,
-- i tak za każdym razem wykonujemy tylko 1 insert
 
CREATE TRIGGER tree_objects_ai AFTER INSERT ON kategorie FOR EACH ROW EXECUTE PROCEDURE tree_objects_ai();
 
-- Tworzymy trigera który po każdym INSERT'cie wykona procedure trg_powiazania_i, dlaczego trigger i procedura
-- mają taką samą nazwę? Ponoć ułatwia analizę bazy danych... Ja tak tak to czemu nie ;]

Nie będę tutaj się rozpisywał ocb z tymi procedurami, trigerami i powiązaniami pomiędzy tabelami, wszystko możecie sobie doczytać na stronie Huberta.

To był funkcja która tworzy nam powiązania a teraz funkcja która przerzuca gałęzie drzewa pomiędzy sobą.

CREATE OR REPLACE FUNCTION tree_objects_au() RETURNS TRIGGER AS
  $BODY$
  DECLARE
  BEGIN
    IF NOT OLD.parent_id IS DISTINCT FROM NEW.parent_id THEN
      RETURN NEW;
    END IF;
    IF OLD.parent_id IS NOT NULL THEN
      DELETE FROM powiazania WHERE id IN (
        SELECT r2.id FROM powiazania r1 JOIN powiazania r2 ON r1.child_id = r2.child_id
        WHERE r1.parent_id = NEW.id AND r2.depth > r1.depth
      );
    END IF;
    IF NEW.parent_id IS NOT NULL THEN
      INSERT INTO powiazania (parent_id, child_id, depth)
      SELECT r1.parent_id, r2.child_id, r1.depth + r2.depth + 1
      FROM
      powiazania r1,
      powiazania r2
      WHERE
      r1.child_id = NEW.parent_id AND
      r2.parent_id = NEW.id;
      END IF;
      RETURN NEW;
  END;
  $BODY$
  LANGUAGE 'plpgsql';
 
CREATE TRIGGER tree_objects_au AFTER UPDATE ON kategorie FOR EACH ROW EXECUTE PROCEDURE tree_objects_au();
 
-- triger i procedura dzięki której przerzucamy bez problemu gałęzie

Dobra mamy już cały SQL potrzebny i niezbędny do zbudowania takiego menu opartego na wielu poziomach.
A teraz trochę php:

<?php
/**
 * @li gnu/agpl v3 or leter
 * @code utf8
 * @version 0.1
 * @author Przemysław Czekaj
 * @date 09.07.09
 * @file controlers/tpl.php
**/
 
require_once('models/view.php');
 
class ShowData
{
  private $tpl;
  private $obj;
 
  public function __construct($tepel)
  {
    $this->tpl = $tepel;
    $this->obj = new GetData;
    $this->parseKat();
    $this->parseTree();
  }
 
 
  private function parseKat()
  {
    $data = $this->obj->_get_kat();
    $this->tpl->assign('kategorie',$data);
  }
 
  private function setSort(&$sort)
  {
    if($sort != 'ASC' && $sort != 'DESC')
     $sort = 'ASC';
  }
 
  private function parseTree()
  {
    $sort_kat = $_POST['sort_kat'];
    $sort_list = $_POST['sort_list'];
    $this->setSort($sort_kat);
    $this->setSort($sort_list);
    $mast = $this->obj->_get_master_kat($sort_kat);
    $n = count($mast);
    for($i = 0; $i < $n; $i++)
    {
      $tablica['element'][$i]['name'] = $mast[$i]['name'];
      $tablica['element'][$i] = $this->obj->_get_tree($mast[$i]['id'], $tablica['element'][$i], $sort_list);
    }
 
    $this->tpl->assign('tree',$tablica);
  }
}
 
?>

Co to jest? Jest to kontroler templatki, nie chciało mi się tworzyć jakiegoś MVC to zrobiłem pseudo MVC.
Pasowało by Wam pokazać jak to tworzy te drzewo co? No to jeszcze jeden plik z modelu, odpowiedzialny za widok.

<?php
/**
 * @li gnu/agpl v3 or leter
 * @code utf8
 * @version 0.1
 * @author Przemysław Czekaj
 * @date 09.07.09
 * @file models/view.php
**/
 
class GetData
{
 
  public function _get_kat()
  {
    $kat = Doctrine::getTable('Kategoria')->findAll();
    return $kat->toArray();
  }
 
  public function _get_master_kat($sort)
  {
    $kat = Doctrine_Query::create()->query("SELECT k.name FROM Kategoria k WHERE NOT EXISTS (SELECT * FROM Powiazanie p WHERE k.id = p.child_id AND p.depth = 1) ORDER BY k.id $sort");
    return $kat->toArray();
  }
 
  public function _get_sub_kat($id_kat, $sort)
  {
    $kat = Doctrine_Query::create()->query("SELECT k.name FROM Kategoria k JOIN k.Powiazania p ON k.id = p.child_id WHERE p.parent_id = $id_kat AND p.depth = 1 ORDER BY k.id $sort");
    return $kat->toArray();
  }
 
  public function _get_tree($id, $tab, $sort)
  {
    $sub = $this->_get_sub_kat($id, $sort);
    $nn = count($sub);
    for($j = 0; $j < $nn; $j++)
    {
      $tab['element'][$j]['name'] = $sub[$j]['name'];
      $tab['element'][$j] = self::_get_tree($sub[$j]['id'],$tab['element'][$j], $sort);
    }
    return $tab;  
  }
 
}
 
?>

No i tak, teraz jeszcze przydałby by się modele dla doctrine, już pokazuję:

<?php
/**
 * @li gnu/agpl v3 or leter
 * @code utf8
 * @version 0.1
 * @author Przemysław Czekaj
 * @date 07.07.09
 * @file models/doctrine/kategorie.php
**/ 
 
class Kategoria extends Doctrine_Record
{
 
  public function setTableDefinition()
  {
    $this->setTableName('kategorie');
    $this->hasColumn('name','string');
    $this->hasColumn('parent_id','integer');
  }
 
  public function setUp()
  {
    $this->hasMany('Powiazanie as Powiazania', array (
        'local' => 'id',
        'foreign' => 'parent_id',
        )
    );
 
    $this->hasMany('Powiazanie as Powiazanias', array (
        'local' => 'id',
        'foreign' => 'child_id',
        )
    );
 
    $this->hasMany('Kategoria as Kategorie', array (
        'local' => 'parent_id',
        'foreign' => 'id'
        )
    );
  }
}
 
?>

Nie ma tu nic ciekawego, trochę małe zamieszanie wprowadziłem z powiązaniami… przez co nie wiadomo z jakiej przyczyny nie chciał mi działać joinLeft w doctrine, dlatego zmuszony byłem użyć query().

Kolejny model:

<?php
/**
 * @li gnu/agpl v3 or leter
 * @code utf8
 * @version 0.1
 * @author Przemysław Czekaj
 * @date 07.07.09
 * @file models/doctrine/powiazania.php
**/ 
 
class Powiazanie extends Doctrine_Record
{
  public function setTableDefinition()
  {
    $this->setTableName('powiazania');
    $this->hasColumn('parent_id','integer');
    $this->hasColumn('child_id','integer');
    $this->hasColumn('depth','integer');
  }
 
 
  public function setUp()
  {
    $this->hasMany('Kategoria as Kategorie', array (
        'local' => 'parent_id',
        'foreign' => 'id',
        )
    );
 
    $this->hasMany('Kategoria as Kategories', array (
        'local' => 'child_id',
        'foreign' => 'id',
        )
    );
  }
}
 
?>

Jak będę dopisywał to do swojego „cms’a” to obiecuję poprawić powiązania

Dobra, no to mamy praktycznie wszystko co nam było potrzebne, jeszcze dorzucę dwie rzeczy:

<?php
/**
 * @li gnu/agpl v3 or leter
 * @code utf8
 * @version 0.1
 * @author Przemysław Czekaj
 * @date 07.07.09
 * @file models/create.php
**/ 
 
class Dodawanie
{
 
  public function MasterKat($kat)
  {
    $query = new Kategoria;
    $query->name = $kat;
    $query->save();
  }
 
  public function SubKat($kat,$parent)
  {
    $query = new Kategoria;
    $query->name = $kat;
    $query->parent_id = $parent;
    $query->save();
  }
 
}
?>

<?php
/**
 * @li gnu/agpl v3 or leter
 * @code utf8
 * @version 0.3
 * @author Przemysław Czekaj
 * @date 09.07.09
 * @file models/delete.php
**/ 
 
class Niszczenie
{
  public function czyIstniejeKat($kat)
  {
    $query = Doctrine_Query::create()
              ->from('Kategoria')
              ->where('name = ?',$kat)
              ->orWhere('id = ?',(int)$kat);
    $result = $query->execute();
    $result = $result->toArray();
    if(is_array($result[0]))
      return true;
    else
      return false;
  }
 
   public function czyDoPotomka($id_kat,$id_pod)
   {
     $query = Doctrine_Query::create()->query("SELECT k.id, k.name, k.parent_id FROM Kategoria k JOIN k.Powiazania p ON k.id = p.child_id WHERE p.parent_id = $id_kat AND p.depth <> 0");
     $result = $query->toArray();
     $n = count($result);
     for($i = 0; $i < $n; $i++)
     {
       if($result[$i]['id'] == (int)$id_pod)
         throw new Exception ('Nie można przenosić głównej kategorii do sub kategorii danej kategorii'); 
     }
   } //nie chce działać...
 
  public function usunKategorie($kat)
  {
    $query = Doctrine_Query::create()
            ->delete('Kategoria')
            ->where('name = ?',$kat)
            ->orWhere('id = ?',(int)$kat);
    $result = $query->execute();
    return $result;
  }
 
}
 
?>

<?php
/**
 * @li gnu/agpl v3 or leter
 * @code utf8
 * @version 0.1
 * @author Przemysław Czekaj
 * @date 09.07.09
 * @file models/move.php
**/ 
 
class Posuwanie // xD
{
 
  public function MoveKat($kat,$parent)
  {
    $query = Doctrine_Query::create()
              ->update('Kategoria')
              ->set('parent_id','?',(int)$parent)
              ->where('id = '.(int)$kat);
    $result = $query->execute();
    return $result;
  }
 
}
?>

Tak więc mamy tutaj 3 modele, do tworzenia kategorii, do usuwania kategorii, oraz do przenoszenia kategorii.

Teraz pora na kontrolery, tak więc zobaczmy:

<?php
/**
 * @li gnu/agpl v3 or leter
 * @code utf8
 * @version 0.1
 * @author Przemysław Czekaj
 * @date 07.07.09
 * @file controlers/dodaj.php
**/ 
 
require_once('controlers/validate.php');
 
final class HandlerDodaj
{
  private $handle;
  private $ref;
 
  public function __construct($handle)
  {
    $this->handle = $handle;
  }
 
  public function handled_event($ref)
  {
    $this->ref = $ref;
    $this->ref = 'valAdd'.ucfirst($this->ref);
    if(method_exists('Validate',$this->ref))
    {
      $val = new Validate;
      if(is_callable(array($val,$this->ref),true))
      {
        $val->{$this->ref}();
        return true;
      }
      throw new Exception ('Nie można wywołać zdarzenia');
 
      return true;
    }
    throw new Exception ('Brak obsługi zdarzenia');
  }
}
?>

<?php
/**
 * @li gnu/agpl v3 or leter
 * @code utf8
 * @version 0.1
 * @author Przemysław Czekaj
 * @date 07.07.09
 * @file controlers/przenies.php
**/ 
 
require_once('controlers/validate.php');
 
final class HandlerPrzenies
{
  private $handle;
  private $ref;
 
  public function __construct($handle)
  {
    $this->handle = $handle;
  }
 
  public function handled_event($ref)
  {
    $this->ref = $ref;
    $this->ref = 'valPrzenies'.ucfirst($this->ref);
    if(method_exists('Validate',$this->ref))
    {
      $val = new Validate;
      if(is_callable(array($val,$this->ref),true))
      {
        $val->{$this->ref}();
        return true;
      }
      throw new Exception ('Nie można wywołać zdarzenia');
 
      return true;
    }
    throw new Exception ('Brak obsługi zdarzenia');
  }
}
?>

<?php
/**
 * @li gnu/agpl v3 or leter
 * @code utf8
 * @version 0.1
 * @author Przemysław Czekaj
 * @date 07.07.09
 * @file controlers/usun.php
**/ 
 
require_once('controlers/validate.php');
 
final class HandlerUsun
{
  private $handle;
  private $ref;
 
  public function __construct($handle)
  {
    $this->handle = $handle;
  }
 
  public function handled_event($ref)
  {
    $this->ref = $ref;
    $this->ref = 'valDelete'.ucfirst($this->ref);
    if(method_exists('Validate',$this->ref))
    {
      $val = new Validate;
      if(is_callable(array($val,$this->ref),true))
      {
        $val->{$this->ref}();
        return true;
      }
      throw new Exception ('Nie można wywołać zdarzenia');
 
      return true;
    }
    throw new Exception ('Brak obsługi zdarzenia');
 
    return true;
  }
} 
?>

<?php
/**
 * @li gnu/agpl v3 or leter
 * @code utf8
 * @version 0.1
 * @author Przemysław Czekaj
 * @date 07.07.09
 * @file controlers/validate.php
**/
 
require_once('models/delete.php');
require_once('models/create.php');
require_once('models/move.php');
 
final class Validate
{
 
  private $check;
  private $add;
 
  public function __construct()
  {
    $this->check = new Niszczenie;
  }
 
  public function valDeleteKat()
  {
    $nazwa_kat = trim($_POST['nazwa_kategorii']);
    $nazwa_pod = trim($_POST['nazwa_podkategorii']);
    if($nazwa_kat != '')
      $this->doIt($nazwa_kat);
    else
      $this->doIt($nazwa_pod);
  }
 
  public function valPrzeniesKat()
  {
    $nazwa_kat = trim($_POST['nazwa_kategorii']);
    $nazwa_pod = trim($_POST['nazwa_podkategorii']);
    if($nazwa_kat == 0 || $nazwa_pod == 0)
      throw new Exception ('Musisz wybrać skąd dokąd ma być przeniesiona kategoria');
    if ($nazwa_kat == $nazwa_pod)
      throw new Exception ('Nie ma sensu przenoszenia kategorii na ją samą');
    $this->check->czyDoPotomka($nazwa_kat,$nazwa_pod);
 
    if($this->check->czyIstniejeKat($nazwa_kat) && $this->check->czyIstniejeKat($nazwa_pod))
    {
      $przenies = new Posuwanie;
      $przenies->MoveKat($nazwa_kat,$nazwa_pod);
      return true;
    }
    throw new Exception ('Nie istnieje podana kategoria');
 
  }
 
  private function doIt($what)
  {
    if($this->check->czyIstniejeKat($what))
    {
      $this->check->usunKategorie($what);
      return true;
    }
    throw new Exception ('Nie ma podanej kategorii');
  }
 
  private function doItAgain($what,$i = 1,$child = '')
  {
    $this->valKat($what);
    switch($i)
    {
      case 1:
          $this->add->MasterKat($what);
        break;
      case 2:
          $this->add->SubKat($what,$child);
        break;
    }
  }
 
  private function valKat($string)
  {
    if($string == '')
      throw new Exception ('Nazwa kategorii nie może być pusta');
    elseif(!mb_check_encoding($string,'UTF-8'))
      throw new Exception ('Należy ustawić kodowanie w przeglądarce na UTF-8');
    elseif(strlen($string) < 3)
      throw new Exception ('Nazwa kategorii nie może być krótsza niż 3 znaki');
    elseif(!preg_match('/[a-zA-Z0-9ĄąĆćĘęŁłŃńÓóŚśŹźŻż]/',$string))
      throw new Exception ('Nazwa kategorii może składać się wyłącznie z liter i cyfr');
    else
      return true;
  }
 
  public function valAddKat()
  {
    $nazwa_kat = trim($_POST['nazwa_kategorii']);
    $nazwa_pod = trim($_POST['nazwa_podkategorii']);
    $this->add = new Dodawanie;
    if($nazwa_pod != 0)
    {
      $this->doItAgain($nazwa_kat,2,$nazwa_pod);      
    }
    else
    {
      $this->doItAgain($nazwa_kat);
    }
  }
 
}
?>

Wszystkie powyższe kontrolery zostały oparte o dyspozytora:

<?php
/**
 * @li gnu/agpl v3 or leter
 * @code utf8
 * @version 0.1
 * @author Przemysław Czekaj
 * @date 07.07.09
 * @file controlers/dispatcher.php
**/
 
require_once('controlers/dodaj.php');
require_once('controlers/usun.php');
require_once('controlers/przenies.php');
require_once('controlers/tpl.php');
 
final class Dispatcher
{
  private $handle;
  private $tpl;
 
  public function __construct($tepel, $link)
  {
    $this->tpl = $tepel;
    $this->handle = $link;
    $this->handle_the_event();
    $this->display();
  }
 
  public function handle_the_event()
  {
    try // posprawdzajamy co nam tam chce uzytkownik powysyłać
    {
      $name = "Handler".ucfirst($this->handle);
      if ($this->handle != '')
      {
        if (class_exists("$name"))
        {
          $handlerObj = new $name($tpl->handle);
          $handlerObj->handled_event($_GET['co']);
          return true;
        }
        throw new Exception ('Nie można obsłużyć');
      }
    }
    catch(Exception $e) // połapiemy błędy
    {
      $this->tpl->assign('typ_msg','error');
      $this->tpl->assign('wiadomosc',$e->getMessage());
    }
  }
 
  private function display() // poparsujmy troche templatke
  {
    $disTpl = new ShowData($this->tpl);
  }
}
 
?>

Najważniejsze pliki zostały Wam przedstawione, a teraz troche opisu, żeby móc utworzyć drzewo, musimy użyć Rekurencji, została ona użyta w pliku: models/view.php, linia 39. Odwołanie się do samego siebie przez self::, dlaczego po co i jak? Już tłumaczę:
Do stworzenia drzewa użyłem dwóch rzeczy:
1) compiler defun – plugin do smartów – link
2) gotowego przykładu z jquery z budową drzewiastą – link

Jak musi wyglądać tablica w php żeby mogła być przerobiona za pomocą tego pluginu do smartów? Otóż tak:

$tree = array('element'=>array(array('name' => 'test1',
                                     'element' => array(array('name' => 'test1.1'),
                                                        array('name' => 'test1.2',
                                                              'element' => array(array('name' => 'test1.2.1'),
                                                                                 array('name' => 'test1.2.2')
                                                                                )
                                                             ),
                                                        array('name' => 'test1.3',
                                                              'element' => array(array('name' => 'test1.3.1')
                                                                                )
                                                             )
                                                       )
                                    )
                              )
             );

Prawda że nie fajna co? Ni i właśnie za pomocą tej rekurencj którą przedstawiłem powyżej stworzyliśmy taką o to tablice, dzięki której piknie nam wszystko działa.

Teraz jak powinna wyglądać w tpl cała struktura? o tak:

 <ul id="black" class="treeview-black">
 {defun name="testrecursion" list=$tree.element}
 {foreach from=$list item=element}
   {if $element.element}
   <li>
    <span> {$element.name}</span>
    <ul>
      {fun name="testrecursion" list=$element.element}
    </ul>
   </li>
   {else}
    <li> {$element.name}</li>
   {/if}
 {/foreach}
 {/defun}
 </ul>

Dlaczego tak a nie inaczej? Ponieważ użyłem 3 przykładu z struktury drzewiastej w jQuery. Nie wiem co tu jeszcze opisywać, dam Wam do pobrania wszystkie pliki, link poniżej.

Do pobrania całość: link

lip 25, 2009
%H:%i

null #1

Ostro zwalone, masz n zapytań dla n poziomów zagnieżdżeń. Nigdzie nie napisałeś o cacheowaniu takiej kobyły – masz wtedy n zapytań na każdym requeście. Niezły killer Tym bardziej, że można to robić cronowo – jedno zapytanie o wszystkie rekordy, potem tworzenie w php z tego drzewa i zapis do pamięci podręcznej. No i wtedy SQL sprowadza się do jednej tabelki, bez dodatkowych procedur czy triggerów.

BTW pisanie tu dłuższych komentarzy jest mordercze – textarea na komentarz się nie przewija i jest za mały.

cojack #2

To może przedstaw lepsze rozwiązanie w postaci kodu, bo na piśmie to ja też potrafię pisać sporo.

null #3

Jakiś czas temu bełdzio (beldzio.com) chyba publikował w ten sposób zrobione drzewo.

lip 29, 2009
%H:%i

null #4

Trackback chyba coś nie bangla

sie 19, 2009
%H:%i

cojack #5

No coś nie chce działać
kto by się tym przejmował … xD

sie 20, 2009
%H:%i

egz #6

No nic dodac, nic ujac. Cojack style CC nadal leży, przekombinowałeś chyba w 200 miejscach. I jeszcze to DOCTRINE. ALE, muszę również NULLowi zwrócić uwagę… Jedna tabelka? Nie sądzę. Nie przy dowolnie zagnieżdzanych gałęziach na N poziomach. Wyszukiwanie po tym i przenoszenie to dopiero morderstwo dla bazy. Anyway, mnie się rozwiązanie nie podoba. Tutaj kombinatoryka bierze górę, zamiast to co jest przedmiotem publikacji blogowych: „sposob na rozwiazanie postawionego problemu”.

sie 21, 2009
%H:%i

cojack #7

Dobra, no tak mi wjechaliście na ambicje, że napisze lepsze! W dodatku Doctrine chyba mam wbudowane coś takiego, to przedstawię jak użyć

wrz 20, 2009
%H:%i

Paweł Kruczyński #8

O boże! Polecam poszukać tematu MPTT (Modified Preorder Tree Traversal). Taką strukturę można trzymać w jednej tabeli, np. z kolumnami ID, Name, PID, L, R. Dodając elementy podajemy tylko wartości dla Name, i PID (parent ID) – ID jest zazwyczaj auto_increment. Po każdym dodaniu, przesunięciu lub usunięciu elementu musimy uruchomić zew. procedurkę w PHP lub SQL wyliczjącą wartości kolumn L i R. A co to są kolumny L iR ? – To właśnie cały power tej metodologii! Dodam, że nie ma szybszej metody obsługi / przeszukiwania dużych / nieogranicznonych struruktur drzewiastych. Procedura przebudowująca drzewo w Perlu może wyglądać jak poniżej (W mojej tabeli kategorii, założyłem nadrzędną kategorię o ID = 0 i PID = 0 – może mało logicznie ale mam założony foregin constraint na kolumnie PID):

sub rebuild_tree(;$$$$)
{
my $table = shift || „t_categories”;
my $PID = shift || 0;
my $L = shift || 0;

if (shift || 1)
{
$dbh->do(”
update $table
set PID = 0,
L = null,
R = null
where ID = PID
and ID 0
„);
}

my $R = $L + 1;

my $sth = $dbh->prepare(”
select ID
from $table
where PID = $PID
and ID PID
order by Name asc
„);

$sth->execute();

while (my $row = $sth->fetchrow_hashref())
{
$R = rebuild_tree($table, $row->{‘ID’}, $R, undef);
}

$sth->finish();

$dbh->do(”
update $table
set L = $L,
R = $R
where ID = $PID
„);

return $R + 1;
}

Po usunięciu elementu (DELETE), przeniesieniu (UPDATE) lub dodaniu (INSERT) – wystarczy wywołać w/w procedurę a select’y wywoływać w oparciu nie o pole PID a o wartości L i R (zgodnnie z metodologią MPTT)

Paweł Kruczyński #9

W w/w kodzie poucinało znaki większości/mniejszości i znak „różne od” (pewnie zidentyfikowane, jako części tagów) .. ale, jakby coś – to podeślę zainteresowanym mailem: kruk AT op DOT pl

wrz 21, 2009
%H:%i

cojack #10

Boziu, to byly moje pierwsze kroki z drzewkiem, teraz kminie drzewko w doctrine, jak tylko najdzie mnie wena to napisze o tym.

Paweł Kruczyński #11

OK! Chcesz powiedzieć że istnieje wydajniejszy sposób podejścia do tego problemu? Hmm, zajrzę tu za jakiś czas

gru 9, 2009
%H:%i

maur #12

„bo na piśmie to ja też potrafię sporo” ehh, cojack, cojack. Odrobinkę pokory.

cojack #13

No mercy

sie 28, 2010
%H:%i

Jx #14

O jaaa. Ale technologia – ja właśnie kilka dni temu napisałem sobie takie drzewko z twoimi założeniami. Prbowałem to podłączyć do jakichś templatów i natknąłem się w necie na hasło MPTT i tą stronę – nawet nie wiedziałem że można znaleźć gotowe przykłady – ale ten to chyba przesada. Zastrzegam że nie znam Doctrine i innych frameworkow bo dopiero zaczynam. Do drzewa wystarczy jedna tabela w mySql i 2 klasy. tabela trzyma elementy menu: id, parentId, priorytet, level, sort (i inne nazwy, opisy, id obrazków dla upiększenia). Klasa MenuElement trzyma dane z bazy i metody usuwania, zmiany zmiennych. Klasa Menu ładuje strukturę do tablicy z MenuElementami. Aby stworzyć drzewo z tablicy trzeba sobie zdefiniowac nowego usort-a (u mnie wg priorytet, parentId, nazwa) a potem poprzenosic kilkoma ifami do nowej tablicy wyszukując elementy podrzędne. W trakcie tego procesu nadajemy elementom level (poziom zagnieżdżenia) i sort (nowa kolejność elementow) i wrzucamy te 2 wartosci do tablicy w SQLu. Jeśli potem metodami zmieniasz drzewo to nie machasz rekordami w SQLu tylko zmieniasz liczby w level i sort. Od kiedy to tabela w SQL musi odzwierciedlać strukture. Od tego macie SELECTa (u mnie ORDER BY sort ASC)

sie 29, 2010
%H:%i

cojack #15

Ja chciałbym dodać tylko że to rozwiązanie moje, której jest w tym wpisie, jest bardzo pamięciożerne i nie optymalne, także zgadzam się z Jx że to jest do dupy. W wpisach o Ltree możecie znaleźć najlepsze rozwiązanie z strukturą drzewiastą w sql.

Powrót do posta. Dzięki za podlinkowanie.

Drzewka | Aplikacje internetowe

Menu w postaci drzewa

Powrót do posta. Dzięki za podlinkowanie.

Zostaw komentarz

Kategorie

Archiwa

Bądź wolny

Popularne posty

Chmura tagów

Ostatnie posty