Nested set to unordered list (ul li) kako

[ dalibor_zdravkovic @ 22.08.2010. 08:32 ] @

Imam sledecu tabelu u MySql bazi:

Code:

CREATE TABLE categories (
  id int(11) NOT NULL AUTO_INCREMENT,
  parent_id int(11) DEFAULT NULL,
  lft int(11) DEFAULT NULL,
  rght int(11) DEFAULT NULL,
  name varchar(45) NOT NULL,
  PRIMARY KEY (id),
);

za cuvanje hierarhijske strukture podataka tzv "nested set".

sa sledecim podacima:

Code:

id    parent_id    lft    rght    name
-----------------------------------------
1     NULL         1      2       Item 1
2     NULL         3      24      Item 2
3     NULL         25     26      Item 3
4     NULL         27     28      Item 4
5     NULL         29     40      Item 5
6     NULL         41     42      Item 6
7     2            4      9       Item 7
8     2            10     11      Item 8
9     2            12     13      Item 9
10    2            14     21      Item 10
11    2            22     23      Item 11
12    5            30     31      Item 12
13    5            32     37      Item 13
14    5            38     39      Item 14
15    7            5      6       Item 15
16    7            7      8       Item 16
17    10           15     16      Item 17
18    10           17     18      Item 18
19    10           19     20      Item 19
20    13           33     34      Item 20
21    13           35     36      Item 21

Da li posotij algoritam da ove podatke prikaze u nesortirajucu listu (ul li) sa jednim citanjem podataka iz tabele i sa sto manje petlji (loops)?

Treba da se dobije ovakva forma:

Code:

<ul>
    <li class="first">Item 1</li>
    <li>Item 2
        <ul>
            <li>Item 7
                <ul>
                    <li>Item 15</li>
                    <li>Item 16</li>
                </ul>
            </li>
            <li>Item 8</li>
            <li>Item 9</li>
            <li>Item 10
                <ul>
                    <li>Item 17</li>
                    <li>Item 18</li>
                    <li>Item 19</li>
                </ul>
            </li>
            <li>Item 11</li>
        </ul>
    </li>
    <li>Item 3</li>
    <li>Item 4</li>
    <li>Item 5
        <ul>
            <li>Item 12</li>
            <li>Item 13
                <ul>
                    <li>Item 20</li>
                    <li>Item 21</li>
                </ul>
            </li>
            <li>Item 14</li>
        </ul>
    </li class="last">Item 6</li>
</ul>

tj da predstavljaju navigacioni meni na web starni.
Pozeljna je implementacija u PHP.

[ Goran Rakić @ 22.08.2010. 10:39 ] @

Na Sitepointu postoji primer kako da sa dva upita možeš da izvučeš podstablo iz slično predstavljenog stabla http://articles.sitepoint.com/...e/hierarchical-data-database/2 Ako preskočiš prvi upit i iz drugog izbaciš WHERE dobićeš celo stablo jednim upitom. Praviš levi obilazak koristeći lft kolonu, brojiš izlaženje po rght.

[ b0ris @ 22.08.2010. 11:10 ] @

Tesko da to mozes da uradis sa samo jednim citanjem i jednim loop. Mislim da je najvise sto bi mogao da podrzis sa jednim citanjem i jednim loop 2 dubine, to jest root parent i child.

Code (php):

$result = mysql_query('SELECT id, parent_id, lft, rght, `name` FROM categories');

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

  // Znamo zasigurno da je root redak onaj koji ima null kao parent_id

  if($row['parent_id']){

    if(array_key_exists($row['parent_id'], $categories))

      $categories[$row['parent_id']]['child'][$row['id']] = $row;  // Imamo child prvog reda

    else

      foreach($categories as &$category) // Jedini loop kroz root retke

        if(array_key_exists($row['parent_id'], $category['child'] ? $category['child'] : array()))

          $category['child'][$row['parent_id']]['child'][$row['id']] = $row;  // Imamo child drugog reda

  }

  else

    $categories[$row['id']] = $row; // Imamo parent redak

}  

// Sad imas citav niz u categories bitno je samo kako ces da ga ispises

var_dump($categories);

?>

Mada razmisljam kako bi mozda nekom drugacijom konstrukcijom child-a mozda i mogao da izbegnem ovaj loop

modedit: Obeležen code:php za bojenje sintakse, skraćen nepotreban kod.

_{[Ovu poruku je menjao Goran Rakić dana 22.08.2010. u 14:19 GMT+1]}

[ Nikola Poša @ 22.08.2010. 12:14 ] @

Ja sam baš pre nekog vremena pravio klasu koja predstavlja API za rad sa Nested set podacima. Ovde je direktan link za njeno preuzimanje. Ta klasa (NestedSetDbTable_Abstract) je apstraktna, i iz nje treba da izvedeš neki svoj model, i da pritom redefinišeš članove $_name (ime tabele sa kojom radiš), $_primary (naziv kolone koja je primarni ključ), $_left i $_right (nazivi left i right kolona). Takođe, na ovu klasu moraš da "nakačiš" i db adapter, a to mora da bude klasa koja implementira NestedSetDbTable_DbAdapter_Interface, jer naravno, ova klasa treba da radi sa podacima u bazi, pa sam napravio taj intrefejs koji propisuje koje metode taj adapter mora da implementira kako bi mogao da se koristi u okviru NestedSetDbTable_Abstract instanci.

Ako ti treba verzija za Zend Framework, link za preuzimanje je ovde. Na ovoj stranici ćeš naći članak koji sam napisao o mojoj klasi (verzija za ZF), a tu imaš i primere za njeno korišćenje.

A sad odgovor na ovo tvoje pitanje, pa naravno da može sve samo sa jednim upitom, i sa jednom jedinom petljom. U okviru ove moje klase imaš jedan metod getTree(). Ako ti je suviše komplikovano da ideš sa mojom klasom, pogledaj bar kako izgleda upit u tom metodu, pa ga onda implementiraj kod sebe. Uglavnom, on će vratiti nešto ovog tipa:

Code:
id   name    depth
1    foo         0
2    foo1        0
3    foo2        1
4    foo3        1
5    foo4        2
6    foo5        0

Dakle, za svaki vraćeni red, dobićeš i informaciju o "dubini" na kojoj se on nalazi. I ti sad onda pri ispisu možeš da uradiš ovako nešto:

Code (php):

echo '<ul>';

foreach ($podaci as $key=>$podatak) {

     echo '<li>' . $podatak['name'];

     if ($podaci[$key+1]['depth'] > $podatak['depth']) { //Sledi podatak na većoj dubini? Otvori ul.

          echo '<ul>';

     }

     elseif ($podaci[$key+1]['depth'] < $podatak['depth']) { //Manja dubina? 

          $razlika = (int)$podatak['depth'] - (int)$podaci[$key+1]['depth'];

          for ($i=0; $i < $razlika; $i++) { //Zatvaramo onoliko puta koliko je dubina manja.

               echo '</ul>

                    </li>';

          }

     }

     else {

          echo '</li>';

     }

}

echo '</ul>';

Možda sam napravio neku sinstaksnu (a možda i logičku

) grešku, nemoj mi zameriti, hteo sam samo da ti dam ideju.

_{[Ovu poruku je menjao Goran Rakić dana 22.08.2010. u 14:20 GMT+1]}

[ agvozden @ 22.08.2010. 12:55 ] @

Ima i fino objasnjenje ovde:
http://dev.mysql.com/tech-reso...rticles/hierarchical-data.html

Doduse, nije php, ali primeri upita mogu biti korisni kada se radi sa ovakvom organizacijom podataka.

[ Goran Rakić @ 22.08.2010. 13:16 ] @

b0ris, ako izdvojiš „insert u niz“ kao posebnu funkciju tvoje rešenje može da podrži proizvoljnu dubinu. Na primer mogao bi da pamtiš heš tabelu referenci na odgovarajući podniz po roditeljskom čvoru. Onda tačno znaš gde treba novi element ubaciti na osnovu njegovog roditelja. Za takvu implementaciju nisu potrebni ugnježdeni podskupovi, dovoljan je id,parrent par. Mana je što ne možeš da pročitaš samo deo (na primer samo od nekog elementa podstabla). Zato se i koristi struktura koju je Dalibor napisao.

Nikola, ova tvoja klasa radi CROSS JOIN:

Code:
SELECT node.*, (COUNT(parent.parrent) - 1) AS 'depth'
        FROM table as node, table as parent
        WHERE node.lft BETWEEN parent.lft AND parent.rght
        GROUP BY node.id
        ORDER BY node.lft

Meni to deluje kao nepotrebno, tj. možeš da odradiš samo jedno čitanje. Umesto da računaš dubinu, praviš stek po rhgt koloni. Kada naiđeš na veću vrednost, znači da si iskočio iz stabla, izbaciš poslednji iz steka i count($stek) u PHP kodu ti daje dubinu tako da obrazuješ listu. Trebalo bi da bude dosta brže.

Naravno, hajde i da budemo realni i ne bavimo se preranim optimizacijama. Ako je ovo relativno statični meni sajta koji se često prikazuje, keširaj HTML izlaz u posebnu datoteku, i samo je include()-uj ako je keš validan.

[ Nikola Poša @ 22.08.2010. 13:43 ] @

Nisam ja izmislio taj upit, video sam ga čini mi se baš u članku čiji si link ostavio u tvom prethodnom post-u.

Da budem precizniji, u pitanju su ovi tekstovi:
http://www.phpro.org/tutorials...l-Data-with-PHP-and-MySQL.html
http://dev.mysql.com/tech-reso...rticles/hierarchical-data.html
(sad sam se setio da ih imam u bookmark-u

)

Cela klasa je u stvari implementacija stvari koje sam video čitajući sve te članke o Nested Set modelu.

[ Goran Rakić @ 22.08.2010. 14:23 ] @

Za ovu strukturu, predlažem drugačiji upit SELECT * FROM table ORDER BY lft uz opciono WHERE lft BETWEEN :parent_lft: AND :parent_rght: ako se traži samo podstablo ispod nekog roditeljskog elementa.

Zatim imamo PHP kod za lepo uvlačenje koji pamti desne granice podskupa u steku i na taj način usput računa dubinu. Dakle, čitamo stablo u levom obilasku i kada je desni kraj manji od prethodnog znači da smo ušli u dubinu pa pamtimo prethodni kao granicu. Ako naiđe veći, na istom smo nivou ako nije veći od granice, inače izlazimo na gore i sklanjamo granicu iz steka.

Code (php):

$dept = array(); $last = -1;

while($row = $r->fetch_row())

{

   $bound_ind = count($dept)-1;

   if($bound_ind < 0 || $row['rght'] < $last) {

      // desna granica manja od prethodnog, pamtimo i ulazimo nivo ispod

      array_push($dept, $last);

      echo "<ul><li>$row[name]";

   }

   else {

      $bound = $dept[$bound_ind];

      if($bound != -1 && $row['rght'] > $bound) {

         // desna granica veca od ruba prethodnog nivoa, brisemo i izlazimo

         array_pop($dept);

         echo "</ul></li><li>$row[name]";

      }

      else {

         // isti nivo

         echo "</li><li>$row[name]";

      }

   }

   $last = $row['rght'];

}

echo "</li></ul>";

Zbog razdvajanja na pogled, podaci se mogu samo pročitati iz baze i zapakovati u niz, pa prikazati kasnije u šablonu pogleda iteracijom kroz niz umesto kroz MySQL rezultat. Kompletan primer je u prilogu.

izmena: malo ispravljen kod da lepo radi i kada meni nema jedan koren, testiran i ispravljeno nekoliko greškica. Dodat kod u prilogu.

_{[Ovu poruku je menjao Goran Rakić dana 22.08.2010. u 16:14 GMT+1]}

[ Milan M. Radovic @ 23.08.2010. 10:04 ] @

E sad imam ja jedno potpitanje.... A kako sa smartijem ispisati lepo sve to :) ?

[ Goran Rakić @ 23.08.2010. 10:07 ] @

Kao u ovom priloženom kodu (test.php u prethodnoj poruci).

Kod za ispis koji umesto while($row = ... mysql ...) ima foreach($data as $row) staviš u šablon (ili podšablon). On sada ne zavisi od baze podataka, modela,... samo ispisuje neki niz.

Spolja van šablona odradiš upit ka bazi SELECT * FROM ... i petljom while($row = ... mysql ...) $data[] = $row; sve redove ubaciš u niz.

Niz preneseš u šablon kao promenljivu i gotovo.

[ Milan M. Radovic @ 23.08.2010. 11:30 ] @

@dalibor_zdravkovic je sa ovom temom uboo ko prstom u BEEP jer mi je bas to bilo potrebno i ovih dana se trudim da savladam Nested set...

[ dalibor_zdravkovic @ 23.08.2010. 14:36 ] @

E sad kad smo nasli nacin kako da upakujemo podatke u <ul> <li> tagove, javlja se jos jedan problem. Treba staviti klasu "first" na <li> za element sa njamanjom vrednosti za "rght", sto je jednostavno lako jer je to prvi element, a klasu last na elemnet sa najvecom vrednosti "rght". E sad ja za to korisitm dodatni ciklus koji prolazi kroz sve lement i nalazi mi taj element sto naravno podize vreme izvrsavanja na vise od 500ms i to na mom kompijuteru koji nije opterecen poput servera, sto znaci da ce se na serveru to vreme znatno uvecati i ici preko sekunde pa ce se strana sporo ucitavati. Da li postoji resenje da se i ovo odradi u istom ciklusu gde se vrsi i pakovanje u <ul> <li> tagove ili cu na kraju taj roblem morati da resim javascriptom.

_{[Ovu poruku je menjao dalibor_zdravkovic dana 23.08.2010. u 15:46 GMT+1]}