[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