# 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):

```
$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:*

```
// 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:*

```
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:
	
	
	



```
$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:
	
	
	



```
$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:
	
	
	



```
<!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:
	
	
	



```
$returnedArray[0]="Auto"
$returnedArray[0][0]="Opel"
```
 Diese sind identisch mit Folgendem:
	
	
	



```
$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:


```
$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:
> 
> 
> ```
> ...


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.):
	
	
	



```
<!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(?):

```
$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).

```
// 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:

```
// 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:

```
$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


----------



## nero_85 (20. Oktober 2005)

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


----------



## hpvw (20. Oktober 2005)

@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 (20. Oktober 2005)

@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 (20. Oktober 2005)

Mik3e hat gesagt.:
			
		

> 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 (20. Oktober 2005)

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 (20. Oktober 2005)

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 (20. Oktober 2005)

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 (20. Oktober 2005)

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 (20. Oktober 2005)

Mik3e hat gesagt.:
			
		

> *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 (20. Oktober 2005)

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


----------



## hpvw (20. Oktober 2005)

Da wird im Grunde dasselbe gemacht, nur dass die Berechnungen vorrausgesetzt werden bzw. erwartet wird, dass diese korrekt in PHP durchgeführt werden. Aber darauf basiert meine Einfüge-Funktion auch. Ich hatte das ja schon mal angedeutet.
In Ergänzung dazu: 
Ist parent == previous, dann nehme lft des parent + 1 als lft des neuen Elements,
sonst nehme rgt des previous + 1 als lft des neuen Elements.

rgt des neuen Elements ist dann lft des neuen Elements + 1.

Damit kannst Du dann die beiden updates und das insert ausführen.

Gruß hpvw


----------



## Mik3e (20. Oktober 2005)

Ok.. danke vielmals.. Die INSERT Funktion habe ich schon mal fertig 
Nachem ich nun schon INNODB verwende, möchte ich die 3 SQL Queries die für den Insert nötig sind in eine atomare Funktion bündeln (mittels Transaktionssteuerung).

*Transaction-Lock*
Habe mir das auf mysql.com angesehen, werde aber nicht schlau daraus...
Kannst Du mir einen Tipp geben, wo Du welchen Befehl (BEGIN, COMMIT, ROLLBACK)  und die Fehlerabfragen setzen würdest? Wenn ich das mal haben, durchschau ich wenigstens das ganze Prinzip 

Hier die SQL Queries (ohne Fehlerabfrage und ohne Transaction-Lock):

```
// 1. Platz für den neuen Knoten erzeugen
		//-------------------------------------------------------------------
		$sql = ' UPDATE '
			. ' `tbl_product_category` '
			. ' SET '
			. ' `product_category_rgt_order`=(`product_category_rgt_order`+2) '
			. ' WHERE `product_category_rgt_order`>=\''.$startParentNodeRgt.'\' ';
		$this->_db->query($sql);
		
		$sql = ' UPDATE '
			. ' `tbl_product_category` '
			. ' SET '
			. ' `product_category_lft_order`=(`product_category_lft_order`+2) '
			. ' WHERE `product_category_lft_order`>=\''.$startParentNodeRgt.'\' ';
		$this->_db->query($sql);
		
		// 2. Neuen Knoten in die Datenbank einfügen
		//-------------------------------------------------------------------
		$sql = ' INSERT INTO '
			. ' `tbl_product_category` '
			. ' (`product_category_lft_order`, `product_category_rgt_order`, `testtext`) '
			. ' VALUES '
			. ' (\''.$startParentNodeRgt.'\', \''.($startParentNodeRgt+1).'\', \''.$nodeName.'\') ';
		echo $sql;
		$this->_db->query($sql);
```

Wie Du siehst wird jeder Query einzeln ausgeführt.

*Mein Ziel wäre in etwa (sofern mein Gedankengang dahinter richtig ist):*
1. Tabellen sperren
2. Begin Transaction
3. Update Query 1
4. Update Query 2
5. Insert Query
6. On Error: Rollback
7. Else: Commit
8 Tabellen freigeben

Nur hab ich keinen Plan ob das semantisch stimmt und ob wie ich es syntaktisch angehen kann!?

Ciao,
Mike


----------



## hpvw (20. Oktober 2005)

Ich habe es so gemacht:
Am Anfang 3 Queries ausführen:
LOCK TABLE
SET AUTOCOMMIT=0
BEGIN

Dann habe ich bei jedem weiteren Query geprüft, ob es false zurückliefert.
In dem Fall:
ROLLBACK
SET AUTOCOMMIT=1
UNLOCK TABLE
Ausstieg aus der Funktion (return false)

Am Ende der Funktion:
COMMIT
SET AUTOCOMMIT=1
UNLOCK TABLE
return: die neue id

Du kannst natürlich auch mitprotokollieren, ob irgendwo ein Fehler aufgetreten ist und dann am Ende wahlweise einen ROLLBACK oder ein COMMIT machen.

Gruß hpvw


----------



## Mik3e (20. Oktober 2005)

Hi,

Danke, so weit habe ich das verstanden..
Mich wundert nur eines: Warum machst Du einen TABLE LOCK und keinen ROW LEVEL LOCK?

Hat das irgendeinen speziellen Sinn (Außer das man möglichen Deadlocks vorbeugt)?
Weil eigentlich bremsen Table Locks ein System ja unnötig aus (da ja alle Datensätze somit für andere Transaktionen gesperrt sind).
Wenn Du z.B. eine Tabelle mit 10.000 Datensätzen hast, mit deiner Transaktion aber nur 3 änderst, blockst Du trotzdem die restlichen 99.997 Datensätze für andere Requests!?

LG
Mike


----------



## hpvw (20. Oktober 2005)

Gründe:
Mit dem TABLE LOCK bin ich auf der sicheren Seite.
In den Anwendungen, die ich bisher mit dem MPTT gemacht habe und die ich noch so im Kopf habe, gibt es sehr wenig Updates, so dass man die kurzfristige totale Blockade verschmerzen kann.
Bei den Updates sind im Mittel mehr als die Hälfte der Datensätze des Baumes betroffen, so dass ich mir weitere Gedanken spare und nicht viel verliere, wenn ich einfach die ganze Tabelle sperre.
Gruß hpvw


----------



## Mik3e (20. Oktober 2005)

Ok.. Verstehe..
Soll ich Dir was trauriges sagen?:
Wir hätten uns die letzten beiden Tage sparen könne.. Schau was ich gefunden habe (ich verwende ja das DB Object von Pear wie Du sicher schon gesehen hast):
http://pear.php.net/package/DB_NestedSet

ES IST ZUM HEULEN! 

Was hältst Du davon?


----------



## Mik3e (20. Oktober 2005)

Es ist wirklich so traurig...
Bin gespannt ob ich das zum Laufen bekomm.. Aber das Teil stellt echt kongeniale Methoden zur verfügung.. Hier ein kleiner Auszug:

DB_NestedSet::createLeftNode() 
Creates a node before a given node

DB_NestedSet::createRightNode() 
Creates a node after a given node

DB_NestedSet::deleteNode() 
Deletes a node

DB_NestedSet::createSubNode() 
Creates a subnode

DB_NestedSet::moveTree() 
Wrapper for node moving and copying

etc. etc....


----------



## hpvw (20. Oktober 2005)

Mik3e hat gesagt.:
			
		

> Was hältst Du davon?


Das kann ich nicht beurteilen. Ich bin immer ganz schlecht darin, mich mit fremdem Code zu beschäftigen bzw. solch umfangreiche Pakete in meine Anwendungen zu integrieren. Daher und wegen des Lerneffekts baue ich mir die Dinge, die ich brauche, lieber selbst. Ich will das Modell auch richtig verstehen, wenn ich damit umgehe.

Gruß hpvw


----------



## Mik3e (21. Oktober 2005)

Hi HP..

Noch ne Möglichkeit um festzustellen, ob ein Knoten Kiner hat:
rgt-lft > 1 ............ Hat Kinder (true)

Anbei noch ein Screenshot vom Nested Set Output.. Ist schon ganz nett und vor allem verdammt schnell (da es nur ein einziges SQL Statement ohne jegliche Rekursion ist 

Ciao,
Mike


----------



## Mik3e (2. November 2005)

Hi,

Hier ist das ganze besser untergebracht 
Ich bin mir noch nicht ganz im Klaren, wie ich die Oberfläche für den Benutzer gestalten soll...

*Bisher bin ich von drei verschiedenen Möglickeiten der Verschiebung ausgegangen:*
1. Teilbaum als NEUES KIND VON Knoten XY anlegen
2. Teilbaum EINE POSITION VOR Knoten XY verschieben
3. Teilbaum EINE POSITION NACH Knoten XY verschieben

Der User muss ja die Möglichkeit haben, Knoten vertikal und horizontal zu verschieben.

*Anbei eine kleine Grafik zum Verschieben eines Knotens ALS NEUES KIND VON xy..*
Damit meine ich eine vertikale Verschiebung.
Horizontal wäre z.B. die beiden Bäume "Auto" und "Motorrad" zu drehen... (d.h. zuerst kommt "Motorrad" und dann "Auto".

Ciao,
Mike


----------



## hpvw (2. November 2005)

Oh ja, kaum hat man etwas einigermaßen im Griff, muss man dafür auch noch eine Benutzeroberfläche schreiben, eine lästige Aufgabe.

Ich drück' mich im Moment auch etwas davor.
Meine derzeitige Idee ist, mit Parent und Previous zu arbeiten. Dem Nutzer würde ich dann eine Liste mit entsprechenden Links zur Auswahl anbieten.
Ungefähr so (id, titel), die roten Pfeile sollen dann die Links sein:
	
	
	



```
# (1, Food)
|   <- [parent=1, previous=1]
+---# (2, Fruit)
|   |   <- [parent=2, previous=2]
|   +---# (3, Cherry)
|   |   <- [parent=2, previous=3]
|   +---# (4, Banana)
|       <- [parent=2, previous=4]
|   <- [parent=1, previous=2]
+---# (5, Meat)
    |   <- [parent=5, previous=5]
    +---# (6, Pork)
    |   <- [parent=5, previous=6]
    +---# (7, Beef)
        <- [parent=5, previous=7]
    <- [parent=1, previous=5]
```
Wenn Parent==Previous, ist der neue lft-Wert=lft des parent + 1
sonst ist der neue lft-Wert=rgt des Previous + 1

Zu prüfen ist, ob es die Elemente mit den IDs gibt und ob parent==previous oder ob der Vater des Previous-Element wirklich die mit Parent übergebene ID hat.

Soweit im Moment meine Idee, nach der ich zumindest schon mal das Insert habe. Über das Userinterface denke ich aber noch nach. Das muss man natürlich deutlich übersichtlicher, als hier in den Code-Tags darstellen, aber wie?

Gruß hpvw


----------



## Mik3e (2. November 2005)

Hi,

Also ich habe es im Moment in zwei Sites gesplittet...
Die erste gefällt mir schon ganz gut (und erscheint auch logisch), aber die zweite macht mir noch Sorgen... Ein 0815 Anwender kann mit Begriffen wie "Kind" wahrscheinlich nichts anfangen. Anbei die beiden Screenshots.

Und die Sache mit verschieben habe ich auch schon (halbwegs) gelöst. Ich nutze einfach eine eigenes Flag "temporary_disabled" in der DB für den zu verschiebenden Baum. Damit werden diese Knoten in die Berechnung nicht mit einbezogen und ich kann sie sauber nummerieren.

*Vielleicht kommen wir ja gemeinsam auf einen grünen Zweig was die GUI angeht?*

Ciao,
Mike


----------



## hpvw (2. November 2005)

Mik3e hat gesagt.:
			
		

> Also ich habe es im Moment in zwei Sites gesplittet...


So hatte ich es auch gedacht.


			
				Mik3e hat gesagt.:
			
		

> Die erste gefällt mir schon ganz gut (und erscheint auch logisch), aber die zweite macht mir noch Sorgen... Ein 0815 Anwender kann mit Begriffen wie "Kind" wahrscheinlich nichts anfangen. Anbei die beiden Screenshots.


Die erste Ansicht gefällt mir auch. Allerdings würde ich in einer finalen Version die Anzeige von ID und Parent weglassen.

In der zweiten Ansicht würde ich den Baum erneut darstellen und, wie oben (miserabel) angedeutet, entsprechende Links mit Pfeilen oder Beschriftung "hier hin verschieben" zwischen die Elemente setzen. Als weitere Idee schwebt mir noch vor, den Baum in einem Drop-Down-Menü mit Einrückungen darzustellen und das was in dem anderen Beispiel die Links waren, als eingerückte Options-Punkte in das Drop-Down-Menü einzufügen.

Die "Vor-Nach-Kind-Variante" finde ich sehr unübersichtlich. In irgendeiner Anwendung hatte ich mal etwas ähnliches und fand es sehr mühsam mich damit zurecht zu finden. Außerdem glaube ich, dass es nicht eindeutig ist und unterschiedlich verstanden werden kann.



			
				Mik3e hat gesagt.:
			
		

> Und die Sache mit verschieben habe ich auch schon (halbwegs) gelöst. Ich nutze einfach eine eigenes Flag "temporary_disabled" in der DB für den zu verschiebenden Baum. Damit werden diese Knoten in die Berechnung nicht mit einbezogen und ich kann sie sauber nummerieren.


Kleine Warnung: Verenn' Dich nicht. Am Ende kommt ein Verwaltungsattribut nach dem anderen hinzu.

Gruß hpvw


----------



## Mik3e (2. November 2005)

Ja, wie gesagt.. ich finde diese VOR-NACH Geschichte auch nicht optimal...
Aber angenommen der Anwender hat 150 Knoten und möchte den letzen in die erste Kategorie verschieben... Der klickt sich dann einen Wolf bis es dort ist wo es sein soll 
Natürlich würde mir eine Variante mit kleine netten Pfeilchen auch besser gefallen...

Die Hierarchie (in vertikaler Form) wir derzeit auch schon in einem Drop-Down Feld abgebildet (siehe aktuellen Screenshot, hat im alten gefehlt).

Hat Du das Problem schon irgendwie in einer Art GUI gelöst oder bisher gar nicht?

Ich schreib mir übrigens grad selbst ein umfangreiches Tutorial zur MOVE-Funktion  Könnten wir ja hier im Tuts-Bereich veröffentlichen!?

Ciao,
Mike


----------



## hpvw (2. November 2005)

Mik3e hat gesagt.:
			
		

> Ja, wie gesagt.. ich finde diese VOR-NACH Geschichte auch nicht optimal...
> Aber angenommen der Anwender hat 150 Knoten und möchte den letzen in die erste Kategorie verschieben... Der klickt sich dann einen Wolf bis es dort ist wo es sein soll
> Natürlich würde mir eine Variante mit kleine netten Pfeilchen auch besser gefallen...


Man könnte auch mit CSS oder JavaScript die Unterkategorien aufklappen lassen. Ist aber auch nur eine Idee. Klicken muss er bei meiner Idee übrigens nicht ewig, eher noch viel mehr scrollen... Nicht, dass wir uns falsch verstanden haben.



			
				Mik3e hat gesagt.:
			
		

> Hat Du das Problem schon irgendwie in einer Art GUI gelöst oder bisher gar nicht?


Nein, ich habe bisher in meinen Testklassen immer manuell die Parent- und Previous-IDs in Formularfelder eingetragen

Gruß hpvw


----------



## Mik3e (2. November 2005)

Hm.. am optimalsten wäre natürlich eine Drag&Drop Lösung wie sie z.B. bei der Directory Struktur vom Explorer implementiert ist.. Das geht aber leider nicht... (oder nur sehr eingeschränkt mit mächtig großen Javascripts...

Ansonsten bin ich mit meinem Latein eigentlich ziemlich am Ende....


----------



## hpvw (2. November 2005)

Eine Idee hab' ich noch:
Man könnte noch eine weitere "Entscheidungsstufe" einführen. Im ersten Schritt wird der Parent ausgewählt, dann werden nur dessen direkte Kinder (den Begriff musst Du dem User gegenüber ja nicht erwähnen) angezeigt und die Position unter Brüdern festgelegt.

Gruß hpvw

EDIT:





			
				Mik3e hat gesagt.:
			
		

> Hm.. am optimalsten wäre natürlich eine Drag&Drop Lösung ...


Die Idee hatte ich auch schon mal. Dafür hatte ich auch schon eine Testseite, allerdings nur innerhalb einer Ebene und bestimmt noch nicht optimal dargestellt. Außerdem ist es noch nicht valide, weil ich die Idee doch verworfen und nicht mehr zuende gearbeitet habe. Hier mein Code-Ansatz, falls Du die Idee weiter verfolgen willst:
	
	
	



```
<!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>Drag-Drop-Test</title>
<style type="text/css" media="screen">
body,html {
    margin:0;
    padding:0;
    font-family:Arial, sans-serif;
}
h1 {
    margin:10px;
}
#dragdrop {
    list-style-type:none;
    margin:10px;
    padding:0;
    border:2px #000 solid;
}
#dragdrop li {
    margin:0;
    padding:0;
}
#dragdrop div.item {
    display:block;
    background:#eee;
    margin:0;
    padding:0.1em;
    line-height:1em;
}
#dragdrop div.drop {
    display:block;
    margin:0;
    padding:0.3em 0 0 0;
    background:#ddd;
}
#dragdrop div.lastDrop {
    display:block;
    margin:0;
    padding:0;
    height:0.3em;
    line-height:0.3em;
    background:#ddd;
    overflow:hidden;
}
</style>
<script type="text/javascript">
var dropactive=false;
var dropid=null;
var oldpos=null;

function startDrag(id,pos,sender) {
    dropactive=true;
    dropid=id;
    oldpos=pos;
    document.getElementsByTagName("body")[0].style.cursor="move";
}
function drop (pos,sender) {
    if (dropactive && pos!=oldpos && pos!=oldpos+1) {
        sender.style.background="#ddd";
        document.getElementsByTagName("body")[0]
            .style.cursor="default";
        
        Check = confirm("Move id ("+dropid
            +") from position ("+oldpos
            +") before position ("+pos+")?");
        if (Check) {
            /* Hier neue Seite mit Parameter aufrufen! */
            alert("doit");
        }
        stopDrag();
    }
}
function dragOver (pos,sender) {
    if (dropactive && pos!=oldpos && pos!=oldpos+1) {
        sender.style.background="#000";
    }
}
function dragOut (pos,sender) {
    if (dropactive && pos!=oldpos && pos!=oldpos+1) {
        sender.style.background="#ddd";
    }
}
function stopDrag() {
    dropactive=false;
    dropid=null;
    oldpos=null;
    document.getElementsByTagName("body")[0]
        .style.cursor="default";
}
document.onmouseup=stopDrag;
</script>
</head>
<body onselectstart="if (dropactive) return false;">
<h1>Edit the Menu</h1>
<ul id="dragdrop"><li>
<div class="drop"
    onmouseout="javascript:dragOut(1,this);"
    onmouseover="javascript:dragOver(1,this);"
    onmouseup="javascript:drop(1,this);"><div
    id="item1"
    class="item"
    onmousedown="javascript:startDrag(1,1,this);">Item
    1</div></div></li>
<li><div class="drop"
    onmouseout="javascript:dragOut(2,this);"
    onmouseover="javascript:dragOver(2,this);"
    onmouseup="javascript:drop(2,this);"><div
    id="item2"
    class="item"
    onmousedown="javascript:startDrag(2,2,this);">Item
    2</div></div></li>
<li><div class="drop"
    onmouseout="javascript:dragOut(3,this);"
    onmouseover="javascript:dragOver(3,this);"
    onmouseup="javascript:drop(3,this);"><div
    id="item3"
    class="item"
    onmousedown="javascript:startDrag(3,3,this);">Item
    3</div></div></li>
<li><div class="drop"
    onmouseout="javascript:dragOut(4,this);"
    onmouseover="javascript:dragOver(4,this);"
    onmouseup="javascript:drop(4,this);"><div
    id="item4"
    class="item"
    onmousedown="javascript:startDrag(4,4,this);">Item
    4</div></div><div
    class="lastDrop"
    onmouseout="javascript:dragOut(5,this);"
    onmouseover="javascript:dragOver(5,this);"
    onmouseup="javascript:drop(5,this);"></div></li>
</ul>
</body>
</html>
```


----------



## Mik3e (2. November 2005)

Hm..
Noch eine Idee (die auf Deiner aufbaut):

Der User wählt zuerst jenen Knoten, den er verschieben möchte. Danach bekommt er alle Kategorien Pro Ebene angezeigt und kann sich dann bis zu der Ebene durchklicken, auf der er den Knoten einfügen möchte (ähnlich Explorer).

Ich hab übrigens das Tut für "MOVE 2 NEW CHILD OF...." fertig.. Kann ich dir das irgendwie mailen?

Ciao


----------



## hpvw (2. November 2005)

Zum "durch hierarchische Strukturen klicken" gibt es ja bereits diverse JavaScripts und als alternative eine PHP-Variante anzubieten sollte auch kein Problem sein. Bei besonders vielen Elementen ist das sicher keine schlechte Idee, um die Länge der Auswahlseite zu reduzieren.

Gruß hpvw


----------



## Mik3e (2. November 2005)

Stimmt.. Der Nachteil: Wenn Du nicht auswendig weißt, unter welchen Knoten sich der gewünschte befindet, kannst Du Dich auf die Suche machen... Wenn würde es nur mit einer "doppelten Ansicht" ähnlich Explorer gehen....

Ich hab dir das TUT per Mail geschickt.. die Algorithmen können sicher noch verbessert werden...


----------



## Mik3e (3. November 2005)

Hi Hp,

Ich habe es (oh wunder) geschafft.. das Verschieben eines Teilbaums in ein neues Kind eines anderen Baums funktioniert... Einzig wenn ich es als neues Kind des Root-Nodes anlegen möchte, stellt es ihn auf...

Dabei entsteht auch das Problem, denn ich habe folgende Kriterien eingeführt:

1. Der Zielknoten darf nicht gleich dem zu verschiebenden Knoten sein
2. Der Zielknoten darf kein Kind n-ter Ebene des zu verschiebenden Knotens sein

Ist eigentlich logisch, aber beim Root-Knoten stellt das ein Problem dar, da ja JEDER Knoten ein Kind n-ter Ebene von Root ist...

Grübel Grübel....
Ciao,
Mike


----------



## hpvw (3. November 2005)

Jeder Knoten ist zwar Kind, Enkel, etc. des Root, aber der Root ist ja das Kind von keinem Knoten und somit ergibt sich eigentlich kein Problem.

Du musst ja nur verhindern, dass Du einen Knoten in seinen eigenen Teilbaum schiebst.

Das tust Du, wenn ich es richtig verstanden habe mit Deiner zweiten Bedingung. Wenn der Rootknoten der Zielknoten ist, ist die 2. Bedinung immer zulässig. Es wiederspricht lediglich der 1. Bedingung, wenn auch der zu verschiebene Knoten der Rootknoten ist. Das ist auch wunderbar, da dieser Knoten ohnehin nicht verchoben werden kann. Wohin auch? Es wäre vollkommen undefiniert, was man seinen Kindern passiert, da Du ihn nur in seinen eigenen Teilbaum schieben könntest.

Deine Bedingungen sind korrekt. wenn Fehler entstehen, habe ich Dein Dilemma entweder nicht verstanden oder Du hast einen Fehler in der Implementierung.

Gruß hpvw


----------

