Hierarchie in Array packen

[nero_85]

Jo ich glaub vom Grund her versteh ichs jetzt! thx!

 

[hpvw]

@Mik3e:
Ja, das ist eine gute Möglichkeit.
Ich würde das ganze aber noch dahingehend erweitern, dass an den passenden Stellen <ul>, </ul>, <li> und </li> ausgegeben werden.

Die wichtigste Rekursion, die durch das MPTT vermieden wird, ist das rekursive (und damit mehrfache) Abfragen der Datenbank. Die Queries an die Datenbank zu schicken und das Ergebnis auszulesen kostet ungleich mehr Zeit, als ein paar Array-Spielereien in PHP zu machen und im Gegenzug nur ein Query zu senden. Die Rekursion, die ich im Beispiel zur Ausgabe verwende fällt (im Vergleich zu dem rekursiven Auslesen der Datenbank) kaum ins Gewicht und ist vermutlich auch nur unwesentlich langsamer, als das Durchlaufen eines 2-dimensionalen Arrays.

Wenn Du mit dem 2-dimensionalen Array die Ausgabe erzeugen kannst, die Du vorhast, ist das sicher eine effiziente Möglichkeit, die Du nutzen solltest. Dein Eingangspost deutete an, dass Du unbedingt ein mehrdimensionales Array haben willst. Da Du die entsprechende Ausgabe schon realisiert hattest, gab es keine Veranlassung daran zu zweifeln.

Ich werde mir weiterhin das multidimensionale Array zusammenbauen, da mein Templatesystem mir ermöglicht, dieses Array einfach reinzuwerfen und der Rest automatisch passiert. Mit dem 2-dimensionalen Array könnte mein Templatesystem nicht so umgehen, wie ich es mir wünsche.

Viele Wege führen nach Rom...

Gruß hpvw

 

[Mik3e]

@hp

Klar, (fast) alle Wege führen nach Rom.. Die einen halt über eine mehrspurige Autobahn (CPU Load < 2%), die anderen über den Mount Everest (CPU Load >400%)

Das mit der Rekursion habe ich im MPTT Tutorial gelesen... Angeblich können die meisten OOP und Prozeduralen Sprachen schlecht mit Rekursion umgehen (unabhängig von der SQL Abfrage, obwohl die natürlich das größte Problem ist, da geb ich Dir absolut Recht).

Ich verwende meinen Array auch in Verbindung mit einem Template System. Einerseits über ein Backend, mit dem man die Struktur bearbeiten kann (davor fürchte ich mich schon), andererseits über ein Produktkatalog-Frontend, das in unterschiedlichen Layouts abgebildet werden kann.

Möglicherweise stoße ich dabei dann auf grobe Probleme mit diesem Array.. Falls Dir dahingehend etwas bekannt ist, bitte um Info

Für das Bearbeiten der Struktur (ist der nächste Schritt) werde ich dich sicher noch ein paar mal quälen müssen Werde mir mal deinen Pseudo-Code mit den Berechnungen zu Gemüte führen.

Danke,
Mike

 

[hpvw]

Für das Bearbeiten der Struktur (ist der nächste Schritt) werde ich dich sicher noch ein paar mal quälen müssen Werde mir mal deinen Pseudo-Code mit den Berechnungen zu Gemüte führen.

Zum Entwickeln und Nachvollziehen habe ich immer an diesem Bild von Hand und im Kopf rumgeschoben. Vielleicht hilft Dir das ja auch.

Gruß hpvw

 

[Mik3e]

Hi,

Ich steh schon vorm nächsten Problem (früher als erwartet).
Für den Administrationsbereich möchte ich die Hierarchie gerne in Tabellenform ausgeben.
Sollte im Endeffekt so aussehen:

--------------------------------------
Auto        |           |            |
--------------------------------------
            |  Opel     |            |
--------------------------------------
            |  Audi     |            |
--------------------------------------
Motorrad    |           |            |
--------------------------------------
            | Yamaha    |            |
--------------------------------------
            |           |   YZF R1   |
--------------------------------------
            |           |    Tomcat  |
--------------------------------------

Damit das möglich ist, muss ich vorweg wissen, aus wievielen Zeilen und Spalten die Tabelle bestehen muss.

Zu Erinnerung der Aufbau des Arrays:

$categoryArray[n]["id"]=ID des Knotens (PK der DB)
$categoryArray[n]["name"]=Name des Knotens
$categoryArray[n]["layer"]=Ebene des Knotens

Tabellen-Zeilen:
Die Zeilen sind easy zu berechnen (einfach die Anzahl der Elemente im Array zählen). Jedes Element hat ja eine eigene Spalte

Tabellen-Spalten (PROBLEM):
Hier ist mein Problem! Die Anzahl an Spalten entspricht der tiefsten Ebene. Diese kann ich ermitteln, indem ich sage::

// PSEUDOCODE
getMaxValue($categoryArray[*]["layer"].

Gesucht:
Kennst Du eine Funktion, die mir den Maximalwert aus den Elementen eines Array bei Index n ausliest? Also prinzipiell sowas wie die Pseudo-Funktion getMaxValues()

Ciao,
Mike

 

[hpvw]

Nein, so eine Funktion kenne ich nicht.
Du müßtest das gesamte Array vorher einmal durchlaufen (was Du vermutlich eh tust) und dann die tiefste Ebene ermitteln. Definiere vor der Schleife $deepestLayer=0; und nach dem Du in der Schleife die Ebene des aktuellen Node ermittelt hast, setzt Du $deepestLayer ggf. neu: $deepestLayer = max($deepestLayer,$actualLayerDeepth);

Gruß hpvw

 

[Mik3e]

Hab es schon gelöst.. Danke jedenfalls.. (Sieht schon ganz nett aus)

Jetzt wirds ernst!
Bevor ich mich ums verschieben kümmere, möchte ich INSERT und DELETE realisieren.
Zuerst möchte ich INSERT umsetzen...

Ich habe das Diagramm nun um die Primary Keys (ID) der einzelnen Knoten erweitert (grüne Zahl).

Angedachte GUI:
Die Oberfläche sollte dem User folgende Möglichkeit bieten (so denk ich mir das es logisch ist, vielleicht hast Du ne bessere Idee:

1. Neue Kategorie (Child-Node) UNTER |<Liste aller Knoten>| anlegen
2. Position in Ebene:
- Am Anfang
- Am Ende
- Nach |<Knoten>|

Wobei <Liste aller Knoten> ein Drop-Down Menü mit allen bisherigen Knoten ist.

Damit weiß ich folgendes:
1. Unter welchem Elternknoten soll ein neuer Knoten eingefügt werden.
2. In welcher horizontalen Position der Ebene soll sich der neue Knoten befinden
3 Ich kenne dadurch folgende Daten:
a) Primary Key des Elternelements
b) LEFT/RIGHT Order des Elternelements
c) Primary Key des Bruders
d) LEFT/RIGHT Order des Bruders

Beispiel:
Ich möchte neben Yamaha die Motorradmarke "Suzuki" einfügen (Siehe Mutationsbeispiel im Anhang).
Der User wählt:
1) Neue Kategorie UNTER "Motorrad" einfügen
2) Neue Kategorie VOR Yamaha einfügen

Lösungsansatz:
Damit ist mal klar, dass sich LEFT/RIGHT Order aller Elemente im Baum "Motorrad" (und mögliche folgende) sowie das ROOT Element ändern.

Dann ist aber schon Ende im Gelände..
Hast Du irgendeine Formel für diese Berechnung? Da gibts sicher auch schon was.. Ich werd mich mal im Internet umsehen ob ich was finde...

Ciao,
Mike

 

[Mik3e]

Hi,

So, habe für INSERT schon ein Tut gefunden:

5. The nested set model has an implied ordering of siblings which the
adjacency list model does not. 
To insert a new node, G1, under part G.  
We can insert one node at a time like this:

BEGIN ATOMIC
DECLARE right_most_sibling INTEGER;

SET right_most_sibling 
    = (SELECT rgt 
         FROM Frammis 
        WHERE part = 'G');
UPDATE Frammis
   SET lft = CASE WHEN lft > right_most_sibling
                  THEN lft + 2
                  ELSE lft END,
       rgt = CASE WHEN rgt >= right_most_sibling
                  THEN rgt + 2
                  ELSE rgt END
 WHERE rgt >= right_most_sibling;

 INSERT INTO Frammis (part, qty, wgt, lft, rgt)
 VALUES ('G1', 3, 4, parent, (parent + 1));
 COMMIT WORK;
END;

Was mir nicht klar ist:
Die Zeile:
VALUES ('G1', 3, 4, parent, (parent + 1));
Welchen Wert hat parent Ist das Right von Parent?
Ansonsten ist es eigentlich ganz logisch..

Den ganzen Artikel findest Du übrigens hier:
http://www.developersdex.com/gurus/articles/112.asp?Page=3

Ciao,
Mik

 

[hpvw]

Was mir nicht klar ist:
Die Zeile:
VALUES ('G1', 3, 4, parent, (parent + 1));
Welchen Wert hat parent Ist das Right von Parent?

Ja, parent ist in dem Beispiel gleich right_most_sibling.

Die Funktion setzt das neue Element immer als letztes Unterelement des Elternelements ein.

Gruß hpvw

 

[Mik3e]

Hi,

Habs grad nachgerechnet und bin auch zu dem Schluss gekommen...
Allerdings hab ich eine wesentlich einfachere Variante gefunden (bei der ich Lock und Commit gleich testen kann :

The second way to add, and delete nodes is to update the left and right values of all nodes to the right of the new node. Let’s have a look at an example. We want to add a new type of fruit, a ‘Strawberry’, as the last node and a child of ‘Red’. First, we’ll have to make some space. The right value of ‘Red’ should be changed from 6 to 8, the 7-10 ‘Yellow’ node should be changed to 9-12 etc. Updating the ‘Red’ node means that we’ll have to add 2 to all left and right values greater than 5. 

We’ll use the query:

UPDATE tree SET rgt=rgt+2 WHERE rgt>5; 
UPDATE tree SET lft=lft+2 WHERE lft>5;

Now we can add a new node ‘Strawberry’ to fill the new space. This node has left 6 and right 7.

INSERT INTO tree SET lft=6, rgt=7, title='Strawberry';

Der ganze Artikel:
http://www.sitepoint.com/article/hierarchical-data-database/3

Danke & Ciao,
Mike