Hierarchie in Array packen

Mik3e · 19. Oktober 2005

Hierarchie in Array packen (MPTT - Modified Preorder Tree Traversal Algorithmus)

Hi zusammen,

Grundlegendes:
Ich habe einen Hierarchiebaum (in diesem Beispiel einen mini-produktkatalog) nach den Regeln des "Modified Preorder Tree Traversal (MPTT)" Algorithmus in der Datenbank hinterlegt. (siehe auch http://www.sitepoint.com/print/hierarchical-data-database).
Alle in diesem Thread angesprochenen Werte beziehen sich auf die beigefügte Skizze!

Methode: getCategoryTree($startNode);
Nun bin ich gerade dabei mir eine Klasse zu schreiben, die mir unter anderem eine Methode "getCategoryTree($startNode)" bietet. Diese Methode soll (wie der Name schon verrät) den Hierarchiebaum unterhalb von $startNode in Form eines mehrdimensionalen Arrays aus der DB zurückliefern.

Returns: Array
Der Array der zurückgeliefert wird, soll folgendermaßen aussehen (auf der Skizze entspricht dies den grünen Zahlen rechts oberhalb der Elemente):

Code:

$returnedArray[0]="Auto"
$returnedArray[0][0]="Opel"
$returnedArray[0][1]="Audi"
$returnedArray[1]="Motorrad"
$returnedArray[1][0]="Yamaha"
$returnedArray[1][0][0]="YZF R1"
$returnedArray[1][0][1]="Tomcat"

Das hat den Sinn, dass der Array jederzeit einfach (und vor allem schnell) mittels [phpf]foreach[/phpf] abgebildet werden kann.

Mein Problem:
Die Methode funktioniert bereits einwandfrei. Die Hierarchische Struktur wird einwandfrei durchlaufen und das Ergebnis wird mit den korrekten Einrückungen angezeigt.

ABER: Wie bekomme ich das nun in einen mehrdimensionalen Array? (Weil mit der Anzeige kann ich nicht viel anfangen). Ich kenne die Ebene auf der sich ein Element befindet (entspricht der Elementanzahl des $layerStack).

Vielleicht habt Ihr auch eine andere Lösung für den Aufbau des Arrays...

Hier die Methode für das Auslesen der Hierarchie:

PHP:

// getCategoryTree: Liefert die gesamte hierarchische Struktur unter
	// $startNode. Um das gesamte Verzeichnis zu listen, muss der
	// ROOT-Node als $startNode übergeben werden.
	//-------------------------------------------------------------------
	function getCategoryTree($startNode) { 
		
		$startNodeLft=0;
		$startNodeRgt=0;
		
		// Hilfs-Stack zum bestimmen der Ebenen initialisieren
		//-------------------------------------------------------------------
		$layerStack=array(); // Hilfs-Stack zum bestimmen der Ebenen
		
		// LEFT & RIGHT Order von $startNode einlesen
		//-------------------------------------------------------------------
		$sql = ' SELECT '
			. ' tbl_product_category.`product_category_lft_order` AS `product_category_lft_order`, '
			. ' tbl_product_category.`product_category_rgt_order` AS `product_category_rgt_order` '
			. ' FROM `tbl_product_category` AS `tbl_product_category` '
			. ' WHERE tbl_product_category.`pk_product_category_id`=\''.$startNode.'\' '
			. ' ORDER BY tbl_product_category.`product_category_lft_order` ASC '
			. ' LIMIT 0,1 ';
		$result =$this->_db->query($sql);
		$row = $result->fetchRow(DB_FETCHMODE_ASSOC);
		
		$startNodeLft=$row['product_category_lft_order'];
		$startNodeRgt=$row['product_category_rgt_order'];
		
		// Auslesen aller Child-Nodes von $startNode
		//-------------------------------------------------------------------
		$sql = ' SELECT '
			. ' tbl_product_category.`product_category_lft_order` AS `product_category_lft_order`, '
			. ' tbl_product_category.`product_category_rgt_order` AS `product_category_rgt_order`, '
			. ' tbl_product_category.`testtext` AS `testtext` '
			. ' FROM `tbl_product_category` AS `tbl_product_category` '
			. ' WHERE '
			. ' tbl_product_category.`product_category_lft_order`>=\''.$startNodeLft.'\' '
			. ' AND tbl_product_category.`product_category_lft_order`<=\''.$startNodeRgt.'\' '
			. ' ORDER BY tbl_product_category.`product_category_lft_order` ASC ';
		$result =$this->_db->query($sql);

		// Gefundene Child-Nodes durchlaufen
		//-------------------------------------------------------------------
		while ($row = $result->fetchRow(DB_FETCHMODE_ASSOC)) { 
			
			// Prüfen, ob der (Hilfs-) layerStack bereits gefüllt ist
			// (Dies ist erst ab dem zweiten Durchlauf der Fall)
			//-------------------------------------------------------------------
			if (count($layerStack)>0) { 
		
				// Prüfen, ob dem Layer-Stack das letzte Element "weggepoppt" werden soll :o)
				// (Entspricht dem Retour-Sprung in eine Parent-Ebene)
				//-------------------------------------------------------------------
				while ($layerStack[count($layerStack)-1]<$row['product_category_rgt_order']) { 
					array_pop($layerStack); 
				} 
			} 

			// Gefundene Knoten mit Einrückungen anzeigen
			//-------------------------------------------------------------------
			echo str_repeat('&nbsp;---&nbsp;|&nbsp;',count($layerStack)).$row['testtext']."<br>"; 

			// Den aktuellen Node auf den Stack legen (LIFO)
			//-------------------------------------------------------------------
			$layerStack[] = $row['product_category_rgt_order'];
	   }
	}

Und hier das derzeitige Ergebnis:

Code:

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

Anlagen:
1. Das hier verwendete Beispiel als Diagramm zum leichteren Verständnis
2. Ein Snapshot der verwendeten Test-Tabelle "tbl_product_category"

Vielen Dank vorab für die Hilfe.. ich steh wahrscheinlich nach dem langen Arbeitstag im Moment nur total auf der Leitung

Ciao,
Mike

hpvw · 19. Oktober 2005

Nested Sets treiben einem ganz schöne Knoten ins Gehirn

Mein Ansatz war ein etwas anderer. Ich habe mir die Tiefe des Nodes im Query ermitteln lassen und arbeite in der Funktion damit.
Ich habe das mal zu einem Beispiel zusammengestrickt. Die verwendete Funktion der Datenbankklasse macht im Prinzip folgendes:

PHP:

$res=mysql_query(/*...*/);
$returnValue=array();
while ($row=mysql_fetch_assoc($res)) {
    $returnValue[]=$row;
}

Das nur als kurze Vorbemerkung. Direkt in der dargestellten Funktion kannst Du natürlich auch die Daten auslesen. Ändere einfach die foreach-Schleife in das bekannte while-mysql_fetch-Konstrukt. Das Array, was ich erzeuge ist etwas umständlicher aufgebaut, als Du dargestellt hast. Dein Array wäre allerdings auch nicht möglich, da ein Arrayelement nicht gleichzeitig ein String und ein Array sein kann.
Mein erzeugtes Array anhand Deines Beispiels:

Code:

$returnedArray[0]['node']="Auto"
$returnedArray[0]['subnodes'][0]['node']="Opel"
$returnedArray[0]['subnodes'][1]['node']="Audi"
$returnedArray[1]['node']="Motorrad"
$returnedArray[1]['subnodes'][0]['node']="Yamaha"
$returnedArray[1]['subnodes'][0]['subnodes'][0]['node']="YZF R1"
$returnedArray[1]['subnodes'][0]['subnodes'][1]['node']="Tomcat"

Ich hoffe, der Code erklärt sich selbst. In das, was in der Funktion passiert, muss ich mich auch erst wieder reindenken:

PHP:

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
    "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="de">
<head>
<meta http-equiv="Content-Type"
    content="application/xhtml+xml; charset=UTF-8" />
<title>MPTT to multidimensional array</title>
</head>

<body>
<?
    include "../DB.singleton.php";
    
    $count=DB::getInstance()->query2AssocArray("SELECT
                title,
                (SELECT COUNT(*)
                    FROM `mptt` i
                    WHERE m.lft>i.lft
                    AND m.rgt<i.rgt) AS ld
            FROM `mptt` m
            ORDER BY m.lft",$rows);

    /* makeMultiDimensionalArrayOfMPTTArray
     *
     * Generates a multidimensional Array with a given result set
     * of a query that gets the nodes from a table using the
     * MPTT-Modell. Every row must indicate its depth in the
     * tree.
     *
     * @param mpttArray 2 dimensional array
     *      Contains the result set of the query. Any field is
     *      optional, except that one field must indicate the
     *      depth of the row in the layer. The rows must be
     *      ordered by its left values.
     *      Sample such an array:
     *      mpttArray=array (   array(
     *                              'name'=>'root',
     *                              layerDepth'=>0),
     *                          array(
     *                              'name'=>'node1',
     *                              layerDepth'=>1),
     *                          array(
     *                              'name'=>'node1.1',
     *                              layerDepth'=>2),
     *                          array(
     *                              'name'=>'node2',
     *                              layerDepth'=>1)
     *                      )
     *      This is, what your query should get for the
     *      following structure saved in the database:
     *          root (lft=1,rgt=8)
     *              node1 (lft=2,rgt=5)
     *                  node1.1 (lft=4,rgt=4)
     *              node2 (lft=6,rgt=7)
     *
     * @param levelDepthField string
     *      The name of the field indicating the depth
     *      of the node in the tree.
     *      The depth can be calculated with the following
     *      subquery in the projection, where outer is the alias
     *      of the structure table in the main query:
     *      (SELECT COUNT(*)
     *          FROM `structureTable` inner
     *          WHERE outer.lft>i.lft
     *          AND outer.rgt<i.rgt) AS depth
     *
     * @return multidimensional array
     *      An array containing all given nodes.
     *      Every node is represented by an array. This array
     *      has two items, one called 'node', which contains
     *      the row as array, with elements representing the
     *      fields and one called subnodes, which contains the
     *      subnodes the same way. The array with the sample
     *      data above:
     *          array (
     *              0=>array(
     *                  'node'=>array(
     *                      'name'=>root,
     *                      'layerDepth'=>0),
     *                  'subnodes'=>array(
     *                      0=>array(
     *                          'node'=>array(
     *                              'name'=>node1,
     *                              'layerDepth'=>1),
     *                          'subnodes'=>array(
     *                              0=>array(
     *                                  'node'=>array(
     *                                      'name'=>node1.1,
     *                                      'layerDepth'=>1),
     *                                  'subnodes'=>array()
     *                              )
     *                          )
     *                      ),
     *                      1=>array(
     *                          'node'=>array(
     *                              'name'=>node2,
     *                              'layerDepth'=>1),
     *                          'subnodes'=>array()
     *                      )
     *                  )
     *              )
     *          )
     *
     *
     *
     *
     */
    function makeMultiDimensionalArrayOfMPTTArray(
            $mpttArray,
            $levelDepthField) {
        $tree=array();
    
        $tempStack=array(&$tree);
    
        $lnld=0; //last node layer depth
    
        $last=null;
    
        foreach($mpttArray as $r) {
            echo "\n";
            if ($lnld == $r[$levelDepthField]) {
                array_push($tempStack[count($tempStack)-1],
                        array(
                            'node'=>$r,'subnodes'=>array()
                        )
                    );
                $last=&$tempStack[count($tempStack)-1]
                        [count($tempStack[count($tempStack)-1])-1]
                        ['subnodes'];
                $lnld=$r[$levelDepthField];
            } else if ($lnld < $r[$levelDepthField]) {
                $tempStack[]=&$last;
                array_push($tempStack[count($tempStack)-1],
                        array(
                            'node'=>$r,
                            'subnodes'=>array()
                        )
                );
                $last=&$tempStack[count($tempStack)-1]
                        [count($tempStack[count($tempStack)-1])-1]
                        ['subnodes'];
                $lnld=$r[$levelDepthField];
            } else if ($lnld > $r[$levelDepthField]) {
                for ($i=0; $i<$lnld-$r[$levelDepthField]; $i++) {
                    array_pop($tempStack);
                }
                array_push($tempStack[count($tempStack)-1],
                        array(
                            'node'=>$r,
                            'subnodes'=>array()
                        )
                );
                $last=&$tempStack[count($tempStack)-1]
                        [count($tempStack[count($tempStack)-1])-1]
                        ['subnodes'];
                $lnld=$r[$levelDepthField];
            }
        }
        return $tree;
    }
    /* END makeMultiDimensionalArrayOfMPTTArray */

    $tree=makeMultiDimensionalArrayOfMPTTArray($rows,'ld');
    
    /*
     * just to validate the generated array
     */
    function recursiveOutput($nodeArray) {
        echo "<ul>";
        foreach($nodeArray as $n) {
            echo "<li>";
            echo $n['node']['title'] . " (";
            echo $n['node']['ld'] . ")";
            if (count($n['subnodes'])>0) {
                recursiveOutput($n['subnodes']);
            }
            echo "</li>";
        }
        echo "</ul>";
    }

    recursiveOutput($tree);
?>
</body>
</html>

Gruß hpvw

PS: Sorry, dass meine Kommentare in (schlechtem) englisch sind, aber mit nicht-englischen Kommentaren sind schon viele auf die Schnauze gefallen, wenn sie doch mal mit anderen zusammenarbeiten wollen.

Mik3e · 19. Oktober 2005

Knoten? Ich hab schon nen ganzen Wollknäuel im Kopf

Die Sinnhaftigkeit des Aufbaus deines Arrays habe ich noch nicht ganz durchblickt.
Im Prinzip wäre doch ein mehrdimensionaler Array (z.B: 3 Dimensionen [x][y][z] für 3 Ebenen) wesentlich eleganter. Das war eigentlich mein erster Gedanke...

Nur mein Problem ist, dass ich zu unfähig bin um in der Schleife den Array dementsprechend zu bilden..

Von der Lösung mit dem Layer-Stack (als Hilfsvariable für die Ebenen) möchte ich eigentlich nicht abkommen.

Vielleicht hast Du eine Idee, wie der Array aussehen könnte den ich zurück liefere? Und vor allem wie man diesen dann dynamisch aufbaut

Danke & Ciao,
Mike

hpvw · 19. Oktober 2005

Mik3e hat gesagt.:
Knoten? Ich hab schon nen ganzen Wollknäuel im Kopf
Die Sinnhaftigkeit des Aufbaus deines Arrays habe ich noch nicht ganz durchblickt.
Im Prinzip wäre doch ein mehrdimensionaler Array (z.B: 3 Dimensionen [x][y][z] für 3 Ebenen) wesentlich eleganter. Das war eigentlich mein erster Gedanke...

Der Sinn meines Arrays besteht eigentlich nur darin, dass es auch möglich ist, es zu erzeugen.
Das Array, was Du darstellst ist nicht möglich. Nehmen wir Deine ersten beiden Zeilen:

Code:

$returnedArray[0]="Auto"
$returnedArray[0][0]="Opel"

Diese sind identisch mit Folgendem:

PHP:

$returnedArray[0]="Auto";
$returnedArray[0]=array("Opel");

Mit der zweiten Zeile ist der Inhalt (Auto), der in der ersten zugewiesen wurde überschrieben. Daher habe ich den etwas umständlicheren Aufbau verwendet, in dem das Element selbst von der Liste seiner Unterelemente getrennt wird.

Mik3e hat gesagt.:
Nur mein Problem ist, dass ich zu unfähig bin um in der Schleife den Array dementsprechend zu bilden..

Von der Lösung mit dem Layer-Stack (als Hilfsvariable für die Ebenen) möchte ich eigentlich nicht abkommen.

Vielleicht hast Du eine Idee, wie der Array aussehen könnte den ich zurück liefere? Und vor allem wie man diesen dann dynamisch aufbaut

Was am Ende Deiner Schleife count($layerStack) ist, ist in meiner Schleife $r[$levelDepthField], also die im Query ermittelte Ebene. Das ist (neben einer Wollfabrik) alles, was Du benötigst, um den Inhalt der Schleife in meiner Funktion am Ende Deiner Schleife zu verwenden (plus die Hilfsvariablen, die vor der Schleife definiert werden). Ich hoffe, das hilft Dir erstmal weiter, da ich mich gerade geistig nicht in der Lage sehe, meine eigene Funktion Zeile für Zeile zu verstehen.

Gruß hpvw

nero_85 · 20. Oktober 2005

Ich bin zwar immer noch Anfänger aber muss denn das Ganze mit 0en und 1en sein!? Warum nicht einfach so:

PHP:

$returnedArray["Auto"];
$returnedArray["Auto" ]["Opel"];

Bitte jetzt nicht hauen, aber das Thema interessiert mich einfach!!

hpvw · 20. Oktober 2005

nero_85 hat gesagt.:
Ich bin zwar immer noch Anfänger aber muss denn das Ganze mit 0en und 1en sein!?

Es sind ja nicht binäre 0en und 1en. In einer richtigen Anwendung kann da auch gerne mal eine 7 stehen, je nach dem, wie viele Unterknoten ein Knoten hat.

nero_85 hat gesagt.:
Warum nicht einfach so:

PHP:

$returnedArray["Auto"]; $returnedArray["Auto" ]["Opel"];

Das wäre eine Möglichkeit, wenn zu jedem Knoten nur ein Feld gehört. In der Regel hat so ein Knoten aber noch weitere Attribute, zum Beispiel eine ID oder eine Beschreibung. Diese könntest Du in der Struktur nicht abbilden. Sie müßten in irgendeiner Form an den Index (z.B. Auto) angehängt werden. Meiner Meinung nach müßte das als Array geschehen, womit sie nicht mehr von den Unterknoten (z.B. Opel) zu unterscheiden wären. Eine weitere Möglichkeit wäre, die Daten in einem zweiten Array unterhalb des gleichen Schlüssels abzulegen, welches dann nur 2 dimensional ist. Das führt jedoch zu Problemen, wenn Suzuki Autos und Motorräder baut. Mir widerstrebt es auch, Daten als Schlüssel zu verwenden. Sicherlich gibt es auch andere funktionsfähige Abbildungsmöglichkeiten, als das Array, was ich dargestellt habe, mir fällt jedoch keine ein. Vielleicht bin ich da auch etwas festgefahren, weil ich hierarchische Strukturen schon seit Jahren so abbilde, wenn sie in ein Array sollen.

@Mik3e:
Ich habe Deinen Ansatz mal mit meinem zusammengeführt. Möglicherweise ist das etwas ineffizient, da jetzt mit zwei Stacks gearbeitet wird, aber ich steige durch die Logik in Deiner Funktion nicht ausreichend durch, um Deinen Code einfach zu erweitern.

Wie bereits erwähnt, habe ich nur herausgefunden, an welcher Stelle bei Dir die Ebenentiefe abzugreifen ist und das nutze ich. Der Vorteil ist jetzt, dass im Query keine Ebenentiefe mehr berechnet werden muss, was ein Subquery erspart und somit auch in älteren MySQL-Versionen funktionieren sollte.

Als kleinen Bonus schreibt die Funktion jetzt auf Wunsch die Ebenentiefe zum Result-Set dazu.

Bei der Arraystruktur, die ich vorgeschlagen habe, bleibe ich, weil ich andere Strukturen nicht sinnvoll anwenden kann oder zu verbohrt bin. Den Grund kannst Du Dir aussuchen.

Ich habe meinen Code jetzt soweit wieder verstanden, dass ich vielleicht ein paar grundsätzliche Ideen dazu posten kann:
In dem von mir verwendeten Stack (LIFO am Ende) stehen immer die Arrays, in die Subnodes eingefügt werden.
Das zuletzt im Rückgabearray eingefügte Subnode-Array wird als Referenz in $last gespeichert.
Wenn es im nächsten Durchlauf eine Ebene tiefer geht, wird $last als Referenz und damit das letzte Subnode-Array in den Stack eingetragen.
Es wird also nur indirekt in das Rückgabearray eingetragen, nämlich in die im Stack vorhandene Referenz.
Geht es im nächsten Durchlauf wieder ein oder mehr Ebenen nach oben, werden entsprechend viele Referenzen vom Stack entfernt.

So weit ich mich erinnere, liegt diese etwas unübersichtliche Arrayindizierung im Stack daran, dass PHP etwas merkwürdig mit Referenzen auf Variablen umgeht. Ursprünglich wollte ich nur mit array_push, _pop, _shift und _unshift arbeiten, aber die Funktionen erlauben seit irgendeiner PHP-Version keine Übergabe des einzufügenden Wertes als Referenz mehr (PHP erlaubt das bei keiner Funktion mehr, wenn sie nicht selbst entsprechend deklariert ist).

Nun aber mal wieder der Code (Die Teile, die ich von Dir übernommen habe, habe ich nochmal kenntlich gemacht, ich hoffe, ich habe sie alle wiedergefunden. Dort, wo Du das ganze auf "Auslesen eines Resultsets" umstellen kannst, habe ich auch noch einen Kommentar eingefügt.):

PHP:

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
    "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="de">
<head>
<meta http-equiv="Content-Type"
    content="application/xhtml+xml; charset=UTF-8" />
<title>MPTT to multidimensional array</title>
</head>

<body>
<?
    include "../DB.singleton.php";

    $count=DB::getInstance()->query2AssocArray("SELECT
                title,
                lft,
                rgt
            FROM `mptt`
            ORDER BY lft",$rows);

    /* makeMultiDimensionalArrayOfMPTTArray
     *
     * Generates a multidimensional Array with a given result set
     * of a query that gets the nodes from a table using the
     * MPTT-Modell. Every row must indicate its depth in the
     * tree.
     *
     * @param mpttArray 2 dimensional array
     *      Contains the result set of the query. Any field is
     *      optional, except that the left and right values
     *      of each node must be in the result set.
     *      The rows must be ordered by their left values.
     *      Sample of such an array:
     *      mpttArray=array (   array(
     *                              'name'=>'root',
     *                              'lft'=>1,
     *                              'rgt'=>8),
     *                          array(
     *                              'name'=>'node1',
     *                              'lft'=>2,
     *                              'lft'=>5),
     *                          array(
     *                              'name'=>'node1.1',
     *                              'lft'=>3,
     *                              'lft'=>4),
     *                          array(
     *                              'name'=>'node2',
     *                              'lft'=>6,
     *                              'lft'=>7)
     *                      )
     *      This is, what your query should get for the
     *      following structure saved in the database:
     *          root (lft=1,rgt=8)
     *              node1 (lft=2,rgt=5)
     *                  node1.1 (lft=4,rgt=4)
     *              node2 (lft=6,rgt=7)
     *
     * @param lftField string
     *      The name of the field ,containing the left value
     *      of each node in the result set
     *
     * @param rgtField string
     *      The name of the field ,containing the right value
     *      of each node in the result set
     *
     * @param layerDepthFieldnameToAdd String
     *      The funktion will add a field to every row of
     *      the result set named like the value of this
     *      parameter containing an int with the depth of
     *      the node in the structure.
     *      If this paramter is null, the field won't be
     *      added.
     *
     * @return multidimensional array
     *      An array containing all given nodes.
     *      Every node is represented by an array. This array
     *      has two items, one called 'node', which contains
     *      the row as array, with elements representing the
     *      fields and one called subnodes, which contains the
     *      subnodes the same way. The array with the sample
     *      data above:
     *          array (
     *              0=>array(
     *                  'node'=>array(
     *                      'name'=>root,
     *                      'theOtherFields'=>otherData),
     *                  'subnodes'=>array(
     *                      0=>array(
     *                          'node'=>array(
     *                              'name'=>node1,
     *                              'theOtherFields'=>otherData),
     *                          'subnodes'=>array(
     *                              0=>array(
     *                                  'node'=>array(
     *                                      'name'=>node1.1,
     *                                      'theOtherFields'=>otherData),
     *                                  'subnodes'=>array()
     *                              )
     *                          )
     *                      ),
     *                      1=>array(
     *                          'node'=>array(
     *                              'name'=>node2,
     *                              'theOtherFields'=>otherData),
     *                          'subnodes'=>array()
     *                      )
     *                  )
     *              )
     *          )
     */
    function makeMultiDimensionalArrayOfMPTTArray(
            $mpttArray,
            $lftField,
            $rgtField,
            $layerDepthFieldnameToAdd = null) {
        if (count($mpttArray)==0) {
            return array();
        }

        $tree=array();

        $tempStack=array(&$tree);

        $lnld=0; //last node layer depth

        $last=null;

        //Mik3e:
        $startNodeLft=$mpttArray[0][$lftField];
        $startNodeRgt=$mpttArray[0][$rgtField];
        $layerStack=array();
        //End Mik3e:

        foreach($mpttArray as $r) { /* <- Wenn man mit einer
                                     * ressource id arbeitet,
                                     * kann hier auch
                                     * while($r=mysql_fetch_*($res)) {
                                     * stehen.
                                     */

            //Mik3e:
            if (count($layerStack) > 0) {
                while ($layerStack[count($layerStack)-1]
                        < $r[$rgtField]) {
                    array_pop($layerStack);
                }
            }

            $ld=count($layerStack);

            $layerStack[] = $r[$rgtField];
            //End Mik3e

            if ($layerDepthFieldnameToAdd !== null) {
                $r[$layerDepthFieldnameToAdd] = $ld;
            }

            if ($lnld == $ld) {
                array_push($tempStack[count($tempStack)-1],
                        array(
                            'node'=>$r,'subnodes'=>array()
                        )
                    );
                $last=&$tempStack[count($tempStack)-1]
                        [count($tempStack[count($tempStack)-1])-1]
                        ['subnodes'];
                $lnld=$ld;
            } else if ($lnld < $ld) {
                $tempStack[]=&$last;
                array_push($tempStack[count($tempStack)-1],
                        array(
                            'node'=>$r,
                            'subnodes'=>array()
                        )
                );
                $last=&$tempStack[count($tempStack)-1]
                        [count($tempStack[count($tempStack)-1])-1]
                        ['subnodes'];
                $lnld=$ld;
            } else if ($lnld > $ld) {
                for ($i=0; $i<$lnld-$ld; $i++) {
                    array_pop($tempStack);
                }
                array_push($tempStack[count($tempStack)-1],
                        array(
                            'node'=>$r,
                            'subnodes'=>array()
                        )
                );
                $last=&$tempStack[count($tempStack)-1]
                        [count($tempStack[count($tempStack)-1])-1]
                        ['subnodes'];
                $lnld=$ld;
            }
        }
        return $tree;
    }
    /* END makeMultiDimensionalArrayOfMPTTArray */

    $tree=makeMultiDimensionalArrayOfMPTTArray($rows,'lft','rgt','ld');

    /*
     * just to validate the generated array
     */
    function recursiveOutput($nodeArray) {
        echo "<ul>\n";
        foreach($nodeArray as $n) {
            echo "<li>";
            echo $n['node']['title']." (";
            echo $n['node']['ld'].")";
            if (count($n['subnodes'])>0) {
                recursiveOutput($n['subnodes']);
            }
            echo "</li>\n";
        }
        echo "</ul>\n";
    }

    recursiveOutput($tree);
?>
</body>
</html>

Gruß hpvw

nero_85 · 20. Oktober 2005

Naja mit 1en und 0en hab ich nicht eine Binäre zeichenfolge gemeint! Aber ihr habt hier nur 1 und 0 verwendet und daher....!
Aber das mit der ID und der Beschreibung könnte man anundfürsich auch wieder so machen oder nicht(?):

PHP:

$returnedArray["Auto"]; 
$returnedArray["Auto"]["Opel"];
$returnedArray["Auto"]["Opel"]["ID"];
$returnedArray["Auto"]["Opel"]["Beschreibung"];
$returnedArray["Auto"]["Honda"];
$returnedArray["Motorrad"]
$returnedArray["Motorrad"]["Honda"];
.
.
.

Naja, wahrscheinlich ist mir das noch zu hoch gegriffen!

</FONT>

Mik3e · 20. Oktober 2005

Mojn Hp

So.. ich vermute mal wir beide denken einfach zu komplex...
Prinzipiell: Der Sinn von MPTT ist doch, die Performance bei Lese-Lastigen Applikationen zu verbessern. Ein ziemlicher Performance-Killer sind Rekursionen, die mit diesem Modell vermieden werden sollen (sonst könnte ich das wesentlich einfachere Parent-Child-Relationship Modell verwenden).

Der Sinn hinter der getCategoryTree() Methode ist, das Menü in irgendeiner Form eines Arrays zu bekommen, den man dann einfach (und vor allem hoch-perform) mit einer foreach() durchlaufen kann ohne Rekursion zu benötigen.

Daher mein neuer Denkansatz für den Aufbau des Arrays:
Man baut einfach einen 0815 2-Dimensionalen Array, wobei der erste Index die eine laufende Indexierung ist und die zweite bestimmte Attribute enthält (was Du auch schon angesprochen hast).

PHP:

// Diesen Array kann man leicht in der getCategoryTree Methode bilden (da man einen
// Zähler hat und die Ebene des aktuellen Elements kennt (sowie den Namen)
$retrievedTreeData=array();
$retrievedTreeData[0]["name"]="Auto"
$retrievedTreeData[0]["layer"]="0"
$retrievedTreeData[1]["name"]="Opel"
$retrievedTreeData[1]["layer"]="1"
$retrievedTreeData[2]["name"]="Audi"
$retrievedTreeData[2]["layer"]="1"
etc....

Möchte man den Array z.B. in Menüform abbilden (was auch die Hauptaufgabe sein wird), könnte man dies beispielsweise so bewerkstelligen:

PHP:

// Durchlaufen des $retrievedTreeData Arrays (eleganter mit foreach, zur besseren
// Verständlichkeit hier mit einer simplen For-Schleife
for($i=0; $i<$count($retrievedTreeData;$i++) {
    echo str_repeat('----',$retrievedTreeData[$i]["layer"]).$retrievedTreeData[$i]["name"]."<br>";
}

That's it...Sieht für mich nach einer sehr Laufzeitfreundlichen

und eleganten Lösung aus...

Mit den Array() Funktionen von PHP kann man dann natürlich noch einiges anstellen (umsortieren, rückwärts durchlaufen etc...).

Was hältst Du von der Idee HP?

Ciao,
Mike

hpvw · 20. Oktober 2005

@nero_85:
Das dargestellte Array besitzt ein Problem:

PHP:

$returnedArray["Auto"]; 
$returnedArray["Auto"]["Opel"];
$returnedArray["Auto"]["Opel"]["ID"];
$returnedArray["Auto"]["Opel"]["Beschreibung"];
$returnedArray["Auto"]["Opel"]["Vectra"];
$returnedArray["Auto"]["Opel"]["Vectra"]["ID"];
$returnedArray["Auto"]["Opel"]["Vectra"]["Beschreibung"];
$returnedArray["Auto"]["Opel"]["Corsa"];
$returnedArray["Auto"]["Opel"]["Corsa"]["ID"];
$returnedArray["Auto"]["Opel"]["Corsa"]["Beschreibung"];
$returnedArray["Auto"]["Honda"];
$returnedArray["Motorrad"]
$returnedArray["Motorrad"]["Honda"];
.
.
.

Wie erkennst Du in einer dynamischen Umgebung, dass ID und Beschreibung die Attribute zu Opel und Vectra und Corsa Unterknoten sind? Das einzige, was mir einfällt, ist, das jeweilige Arrayelement auf is_array zu prüfen. In der von mir geposteten Struktur, weiß ich, worauf ich zugreifen muss, um die Felder auszulesen und was ich durchlaufen muss, um die Unterknoten zu erhalten.

Möglich ist vieles, jeder kann so programmieren, wie er es für richtig hält, aber ich komme mit der Struktur, die ich seit Jahren verwende nun mal am besten klar. Ich habe auch nie behauptet, dass es die einzige oder gar beste Möglichkeit ist, hierarchische Daten in einem Array abzubilden, aber es ist die einzige, mit der ich vernünftig arbeiten kann.

Gruß hpvw

Mik3e · 20. Oktober 2005

@nero:
Ich glaub du siehst da etwas falsch.. Die Objekte "Auto", "Opel" etc. sind Werte! Und kein Array-Index.

Ein Array besteht immer aus der Array-Variable (in Deinem Fall $returnArray), dem Index (bei uns [0][1] usw.) und einem Wert der dem aktuellen Element (hängt von dem Index ab) des Arrays zugewiesen wird.

Prinzipiell verwendet man IMMER (außer bei speziellen Attributen) Ganzzahlen für die Indexierung. Einfach gesagt hat das den Grund, dass die meisten Array-Funktionen mit Strings nicht viel anfangen können...

Beispiele:
1-Dimensionaler Array (Stack):
$array[0]=Apfel
$array[1]=Birne

2-Dimensionaler Array:
$array[0]=Obst
$array[0][0]=Birne
$array[0][1]=Apfel

Dann gibt es wie von HP angesprochen natürlich auch sehr komplexe Konstrukte, bei denen ein Array-Element beispielsweise wiederum einen Array oder sogar ein Objekt enthalten...

Ich hoffe es ist halbwegs verständlich und ich hab keinen Müll geschrieben in meinem Array-Wahn den ich seit der Diskussion gestern mit HP habe

Ciao,
Mike

Hierarchie in Array packen

Mik3e

Erfahrenes Mitglied

Anhänge

hpvw

Erfahrenes Mitglied

Mik3e

Erfahrenes Mitglied

hpvw

Erfahrenes Mitglied

nero_85

Erfahrenes Mitglied

hpvw

Erfahrenes Mitglied

nero_85

Erfahrenes Mitglied

Mik3e

Erfahrenes Mitglied

hpvw

Erfahrenes Mitglied

Mik3e

Erfahrenes Mitglied

Neue Beiträge