[Drzewa] Metoda niepowrzucanych węzłów Opcje

[Asmox]

Witajcie
Udało mi się napisać kod, który tworzy wielowymiarową tablicę drzewa. Jest to metoda wymyślona przeze mnie (chyba że ktoś użył jej przede mną, nie wiem po prostu mówię że znikąd nie kopiowałem), więc nie wiem czy ma jakieś szanse w przyszłości. A nóż widelec może by się komuś kiedyś przydało.
Założenia:
1. Baza danych
Baza danych, nie pliki tekstowe, nie XML... bo takie rzeczy się edytuje ręcznie, a w używając bazy można pokombinować z automatyzacją i elementami, które nie wymagają bezpośredniego siedzenia w kodzie
2. Najprostsza tabela drzewa
Potrzebujemy zwykłą tabelę drzewa. Bez żadnych kombinacji, IP, drugiej tabeli powiązań itd... czyli:

Kod

ID | PAR_ID (id rodzica) | LABEL (etykieta elementu, np. nazwa kategorii)

3. Bez rekurencji
W zależności od ustawień serwera PHP, nie można wykonywać funkcji_z_funkcji bez końca. Powodem jest stos przechowujący odwołania do tych wszystkich niedokończonych funkcji, który może się przepełnić. Czasami rekurencja faktycznie się przydaje, ale w moim rozwiązaniu użyłem po prostu while(true)
4. Niepowrzucane węzły
Elementy pośrednie (nie_korzenie i nie_liście, czyli po prostu gałęzie (IMG:style_emoticons/default/biggrin.gif) ) sprawdzają, czy nie są przypadkiem rodzicem dla czegoś w głównej tabeli. Jeżeli są to olewamy, gdyż:
jeśli 1 > 2 > 3
i wrzucimy 2 do 1
to nie będzie jak wrzucić 3 do 2
Podsumowując szukamy i wrzucamy elementy od końca tak, aby zawsze hierarchia była zachowana, czyli
jeśli 3 nie ma dzieci w głównej tabeli to wrzuć 3 do (id_rodzica_trójki), jeżeli nie, to spróbuj z innym elementem
Operujemy tylko na głównej tabeli, jeżeli mamy do przeniesienia rodzica, to razem ze wszystkimi wcześniej utworzonymi zagłębieniami
5. Konwersja na tablicę gotową do wypisania
zgodnie z TYM SPOSOBEM WYPISANIA TABLICY
Czyli że każdy rodzic jest kluczem w tabeli, każdy liść elementem o indeksie typu int
6. Rozbijanie ciągów
Mam świadomość, że coś takiego pewnie znacznie obniża wydajność kodu (w porównaniu z przechowywaniem info jako tablicy), ale to rozwiązanie wiąże się z punktem 5. gdzie wypisanie <li> to zwykłe rozbicie i powkładanie w elementy, a nie szukanie po zagłębionych tablicach


Ok a teraz kod funkcji:

[PHP] pobierz, plaintext 
public function naListe() {
    $tabelka = SimpleMySQL::getTable('kategorie'); // Pobieramy tabele drzewka
    foreach($tabelka as $val) { // Tworzymy tablice jednowymiarowa w stylu: [0] = ID~*~ID_RODZICA~*~ETYKIETA
      $arr[] = "{$val[$this->_tableFields['id']]}~*~{$val[$this->_tableFields['parent']]}~*~{$val[$this->_tableFields['label']]}";
    }
 
    foreach($arr as $val) { // Dokonujemy wstepnej selekcji dzieci koncowych $arr[dane_rodzica] = array([0] = dziecko, [1] = dziecko2 ...)
      $parent = false;      // Na poczatku zakladamy ze obiekt nie jest rodzicem
      $rozbij1 = explode('~*~', $val); // Rozbijanie: 0 = id || 1 = parent || 2 = label
      if($rozbij1[1] == null) $parent = true;
      foreach($arr as $v) {       
        $rozbij2 = explode('~*~', $v); // Rozbijanie analogiczne
        if($rozbij1[0] == $rozbij2[1]) { // Jesli id I elementu jest jak parent II elementu...
          $parent = true; // To I jest rodzicem (bedzie indeksem w tabeli)
          break;
        }
      }
      if($parent == true) {
        $lista[$val] = array();  
      }
      else {
        $lista[] = $val;  
      }
    }
 
    // Wrzucamy dzieci koncowe do rodzicow...
    $doUsuniecia = array();
    foreach($lista as $key => $val) {
      if(is_numeric($key) && !is_array($val)) { // Jezeli element ma zwykly indeks i nie jest tablica to na pewno jest to dziecko
        $rozbij1 = explode('~*~', $val); // Rozbijanie: 0 = id || 1 = parent || 2 = label
        foreach($lista as $k => $v) {
          $rozbij2 = explode('~*~', $k); // Rozbijanie analogiczne
          if($rozbij1[1] == $rozbij2[0]) { // Jesli indeks rodzica I elementu jest taki sam jak id II elementu to jest on rodzicem
            $parent = $k;
            break;
          }  
        }
        $lista[$parent][] = $val; // Wrzucamy dziecko końcowe (liść) do rodzica pod zwykłym indeksem int
        // SORTOWANIE Z TYM MAM PROBLEM
        $doUsuniecia[] = $key; // Oznaczamy do wywalenia z głównej tablicy
      }
    }
    // I wywalamy je z glownej tablicy
    foreach($doUsuniecia as $val) {
      unset($lista[$val]);
    }
 
 
    // Wstepny podzial zrobiony, zabieramy sie za wrzucanie
    while(true) {
      $children = array();
 
      foreach($lista as $key => $val) {
        $parent = false; // Zakładamy na początku, że obiekt nie jest rodzicem, ale to nie istotne bo może się zmienić
        $rozbij1 = explode('~*~', $key); // Rozbijanie: 0 = id || 1 = parent || 2 = label (rozbijamy klucz bo to on przechowuje info)
        if($rozbij1[1] == null) continue; // Elementy glowne...
        foreach($lista as $k => $v) {
          $rozbij2 = explode('~*~', $k); // Rozbijanie analogiczne
          if($rozbij1[0] == $rozbij2[1]) { // Jesli id I elementu jest jak rodzic II elementu...
            $parent = true; // To I jest rodzicem - oznaczamy
            break;
          }
        }
        if($parent != true)
          $children[] = $key; // Jeżeli nie to wrzucamy do tablicy rodziców, którzy nie mają dzieci w głównej tablicy, czyli są jako dzieci
      }
 
      if(empty($children)) break; // BARDZO WAŻNA INSTRUKCJA, jeżeli nie ma już dzieci do powrzucania, TO KOŃCZYMY CAŁĄ FUNKCJĘ ROBOTA SKOŃCZONA
 
      foreach($children as $val) {
        // Znajdujemy pelna nazwe rodzica
        $dziecko = explode('~*~', $val);
        foreach($lista as $k => $v) {
          $mozeRodzic = explode('~*~', $k);
          if($dziecko[1] == $mozeRodzic[0]) { // Jesli id_rodzica dziecka jest takie samo jak id dowolnego elementu, to jest on rodzicem
            $rodzic = $k; // Pobieramy jego klucz
            break;
          }
        }
        // Koniec znajdywania pelnej nazwy rodzica
        $lista[$rodzic][$val] = $lista[$val]; // Wrzucamy element ze wszystkimi wewnętrznymi gałęziami do rodzica...
        unset($lista[$val]); // ... i usuwamy z głównej tablicy
      }
 
    } // END WHILE
    echo '<hr /><pre>';
    print_r($lista);
    echo '</pre>';
  }
[PHP] pobierz, plaintext 

Oto mój wynik:

Kod

Array
(
    [1~*~~*~Komputery] => Array
        (
            [3~*~1~*~Hardware] => Array
                (
                    [0] => 6~*~3~*~P?yty g?ówne
                )

            [2~*~1~*~Software] => Array
                (
                    [0] => 4~*~2~*~Programy
                    [5~*~2~*~Gry] => Array
                        (
                            [0] => 7~*~5~*~RTS
                            [1] => 8~*~5~*~RPG
                        )

                )

        )

    [9~*~~*~Kuchnia] => Array
        (
        )

)

Chętnie poczytam Wasze uwagi i komentarze do tej metody. Jeszcze pracuję nad tym, ale póki co to mam problem z posortowaniem (nawet liści - tam gdzie wstawiłem komentarz o sortowaniu była funkcja sort, która nie działa). Tak więc pomoc mile widziana.
I dzięki że chciało się wam to wszystko czytać (IMG:style_emoticons/default/winksmiley.jpg)

Ten post edytował Asmox 6.08.2010, 07:41:57

[zelu]

Stary, masz w swojej funkcji 10 pętli foreach (w tym zagnieżdżone, a w jednym miejscu nawet podwójnie). Przy drzewku 100 elementowym zajedziesz serwer (IMG:style_emoticons/default/winksmiley.jpg)
Niepotrzebnie przerzucasz te wszystkie tabele z lewej na prawą i odwrotnie.

Chyba trzeba było sprawdzić wcześniej jak inni to zrobili (IMG:style_emoticons/default/smile.gif)

No ale żadna praca w pole nie idzie i zawsze to jakieś doświadczenie (IMG:style_emoticons/default/smile.gif)


Pozdro

[cojack]

O k*rwa. Toś wymyślił. Zobacz sobie na blogu depesza o drzewkach, u mnie na blogu też masz o ltree, a w pierwszym wpisie masz w komentarzach cenne uwagi.

[Asmox]

Ok to tak:
1. Przepraszam za nieobecność w temacie. Mój internet uzależniony jest od pogody :/
2. Dziękuję za krytykę. Zachęciło mnie do napisania funkcji od nowa zachowując założenie.

[PHP] pobierz, plaintext 
public function naListe2() {
    $zaleznosci = array(); // Przechowuje zaleznosci w stylu [dziecko] = rodzic, root ma wartosc null
    $lista = array();      // Przechowuje elementy
    foreach($this->_treeTable as $wpis) {
      $rodzic = $wpis[$this->_tableFields['parent']];  // Zdobywamy nazwe pola w tabeli (rodzic)
      $id = $wpis[$this->_tableFields['id']];          // Zdobywamy nazwe pola w tabeli (id)
      $zaleznosci[$id] = $rodzic;                      
      $lista[$id] = array();
    }
 
   // Zaczynamy robic liste
   $bylyZmiany = true;    // Zeby While ruszylo
   while($bylyZmiany == true) {
    $doWywalenia = array(); // Elementy ktore na koncu beda wywalane
    $bylyZmiany = false;    // Reset zmiennej, aby nie wpadla nieskonczona petla
 
    foreach($zaleznosci as $klucz => $wpis) {
      if($wpis == null) continue; // Olewamy elementy ktore nie maja rodzicow
      if(!in_array($klucz, $zaleznosci)) {  // Sprawdzamy, czy element ma dzieci w glownej tablicy
        $lista[$wpis][$klucz] = $lista[$klucz];  // Jesli nie to transportujemy go do JEGO rodzica
        $doWywalenia[] = $klucz;                 // Oznaczamy do wywalenia z glownej tablicy (bo byl przeniesiony)
        $bylyZmiany = true;                      // Oznaczamy, ze byly zmiany
      }
    }
 
    if(!empty($doWywalenia)) {                    // Jak nie ma nic do wywalenia to po co iterowac
      foreach($doWywalenia as $wpis) {
        unset($zaleznosci[$wpis]);                // Wywalamy zrowno z aktywnych zaleznosci
        unset($lista[$wpis]);                     // Jak i z glownej tablicy
      }
    }
   }
 
   pokazTablice($lista);
   $this->_lista = $lista; 
  }
[PHP] pobierz, plaintext 

Foreach teraz jest tylko 2x w dodatku nie zapętlony oraz zmniejszany po każdej iteracji WHILE'a. Nadal jednak mam problem z sortowaniem alfabetycznym. Próbowałem pobierać dane z bazy w odwrotnej kolejności (wrzucane na stos tablicy powinny się ładnie uporządkować), ale w praktyce elementy nie mają prawidłowej kolejności, gdyż najpierw wrzucane są elementy które mają powrzucane dzieci... Teraz jest wszystko operowane na identyfikatorach, więc nie ma nazw (są pobierane przy listowaniu), więc chyba musiałbym napisać coś to zamiany id na nazwy.
Ale to później. Na razie chciałbym wiedzieć co sądzicie o nowej funkcji?

[cojack]

Tego się czytać nie da. a to: $bylyZmiany mnie rozwaliło (IMG:style_emoticons/default/biggrin.gif)

[Asmox]

Nazwa nie ma tu nic do rzeczy. Pewnie gdybym dał $wasChanging to by nie było tego posta.

[cojack]

Coś Ci pokażę,
{Gora}, {1}
{Gora,Galaz}, {1,1}
{Gora,Galaz,Lisc1}, {1,1,1}
{Gora,Galaz,Lisc2}, {1,1,2}
{Gora,Galaz2}, {1,1,2}
{Gora,Galaz2,Lisc1}, {1,2,1}
{Gora,Galaz2,Lisc2}, {1,2,2}

Pierwsz ścieżka to path, druga to ordering, 3 kolumny w tabeli i masz święto lasu. Tylko te kolumny to mają być typu ARRAY

[Asmox]

Dobra, bo widzę że nie do końca się rozumiemy :-)
Nie szukam innych rozwiązań bo póki co, moje się spisuje nieźle. Pozamieniam tylko kolumnę powiązań żeby obsługiwał gotowe nazwy zamiast ID i będzie ładnie wszystko cacy z sortowaniem. Moim zdaniem w porównaniu z poprzednim kodem drugi wyszedł całkiem całkiem. Póki co dopiero buduję drzewo kategorii. Jak się rozrośnie do dużych rozmiarów to zrobię tylko ładowanie gałęzi, ale wątpię żeby PHP nie nadążyło z dwoma iteracjami, skoro potrafi ładować wielkie serwisy internetowe.
Chciałem tylko poczytać waszych opinii na temat mojego rozwiązania. Jak przekopuję Google to jedni drugich krytykują, że drzewa są trudne w edycji, trudno wyświetlić gałęzie, że nadmiarowość danych itd. Dlatego zrobiłem najprostsze drzewo jak tylko się da, odciążyć serwer xSQL i zrzucić na barki PHP, który wg. mnie ma większe możliwości. Ale nie bierzcie do siebie tego bo jedyne komendy w SQL jakie znam to select, insert, delete (czyli podstawy podstaw). Mimo wszystko prawdą jest, że MySQL nie ma mechanizmów do zarządzania drzewami.

[cojack]

Ale postgresql ma.


@Edit
no to teraz już jestem evil 666 post zuooo!

Ten post edytował cojack 13.08.2010, 08:16:01