Array mit Nested Set Werten zu Html-Liste/Menu verarbeiten

[Peter L.]

Hallo!

Ich habe ein Array der Form:

$arrNested =  
array(  
  0=>array(  
       'leftKey'      =>0,  
       'rightKey'     =>3,  
       'menuSection'  =>'foo',  
       'menuItem'     =>'bar'  
     ),  
  1=>array(  
       'leftKey'      =>1,  
       'rightKey'     =>2,  
       'menuSection'  =>'foobar',  
       'menuItem'     =>'bla'  
     ),  
  2=>array(  
       'leftKey'      =>4,  
       'rightKey'     =>5,  
       'menuSection'  =>'blub',  
       'menuItem'     =>'blob'  
     )  
);

Als Ausgabe hätte ich gern folgendes:

<h4>foo</h4>  
<ul>  
  <li>bar</li>  
  <li><h4>foobar</h4>  
      <ul>  
        <li>bla</li>  
      </ul>  
  </li>  
</ul>  
<h4>blub</h4>  
<ul>  
  <li>blob</li>  
</ul>

Das Array durchlaufe ich in einer foreach()-Schleife aber ehrlich gesagt, bin ich nicht weiter gekommen als bis zu dem Punkt mir alle Einträge in einer einfachen Liste ausgeben zu lassen :D
Ich habe so meine Schwierigkeiten dabei wieder auf "höhere Ebenen" zu springen. In dem Beispiel von "menuSection=>foobar" mit dem Eintrag "bla" auf "menusection=>blub" mit dem Eintrag "blob".
Ich weiß auch nicht so genau wie ich die neue "menuSection" erkenne. Bzw. wie ich das mit meinen anderen "Erkenntnissen" in Html "pressen" kann.

Meine Erkenntnisse soweit sind:
Wenn 'menuSection' ungleich dem letzten Wert ist, muss ich die Überschrift ausgeben und eine neue Liste öffnen.
Wenn 'rightKey' größer als der letzte 'rightKey' ist, muss ich n Ebenen "höher".
Wenn 'leftKey' größer als der letzte 'rightKey' ist, muss ich n Ebenen "höher".
Wenn 'leftKey' kleiner als der letzte 'rightKey' ist, muss ich 1 Ebene "tiefer".

Ist das falsch, fehlt da noch irgendwas oder kriege ich das damit hin? Mir fehlt der Ansatz woher ich weiß wieviel Ebenen ich jeweils nach "oben" springen muss wenn sich der nächste sich in einer übergeordneten oder neuen Liste befindet. Mir brummt mittlerweile ganz schön der Schädel.^^

Könnte mich bitte jemand in die richtige Richtung schubsen und mir einen Hinweis geben wie ich das am besten angehen kann?

Herlichen Dank schonmal!

[dedlfix]

Tach!

Ich habe ein Array der Form:

$arrNested =

array(
  0=>array(
       'leftKey'      =>0,
       'rightKey'     =>3,
       'menuSection'  =>'foo',
       'menuItem'     =>'bar'
     ),
  1=>array(
       'leftKey'      =>1,
       'rightKey'     =>2,
       'menuSection'  =>'foobar',
       'menuItem'     =>'bla'
     ),
  2=>array(
       'leftKey'      =>4,
       'rightKey'     =>5,
       'menuSection'  =>'blub',
       'menuItem'     =>'blob'
     )
);

  
Warum hast du das in der Form? In PHP kannst du das doch so schachteln, wie du es brauchst. Nested Sets nimmt man für eine flache Datenbanktabelle. Oder kommt das so aus einem DBMS?  
  

> Könnte mich bitte jemand in die richtige Richtung schubsen und mir einen Hinweis geben wie ich das am besten angehen kann?  
  
Schau dir mal den Artikel [Tree in SQL Database: The Nested Set Model](http://falsinsoft.blogspot.de/2013/01/tree-in-sql-database-nested-set-model.html) und dort den Abschnitt "Finding the Depth of the Nodes" an. Damit bekommst du die Tiefeninformation beim SQL-Abfragen mitgeliefert und siehst du recht einfach, wann du ab- und wieder aufzusteigen oder in der Ebene bleiben musst. Dazu musst du nur den Tiefenwert mit dem gemerkten vom vorhergehenden Datensatz vergleichen.  
  
  
dedlfix.

[Peter L.]

Hallo!

Warum hast du das in der Form? In PHP kannst du das doch so schachteln, wie du es brauchst. Nested Sets nimmt man für eine flache Datenbanktabelle. Oder kommt das so aus einem DBMS?

Ja, ich bekomme das Array von einem DBMS. Ich habe mir mal die Abfrage dazu angeschaut und die ist nicht unbedingt sehr kurz. Die Abfrage geht über mehrere Tabellen: Benutzer, Gruppen, Rechte, Inhalte...

Ich würde daran nur ungern etwas ändern aus Angst, dass die Abfrage am Ende nicht mehr stimmt. Deshalb versuche ich auch das Array zurecht zu biegen anstatt die DB-Abfrage zu manipulieren.

Schau dir mal den Artikel Tree in SQL Database: The Nested Set Model und dort den Abschnitt "Finding the Depth of the Nodes" an.

Schau ich mir trotzdem an. Danke!
Wenn du noch eine Idee hast wie ich es ohne Änderung der DB-Abfrage hinkriege, immer her damit! ;)

[dedlfix]

Tach!

Wenn du noch eine Idee hast wie ich es ohne Änderung der DB-Abfrage hinkriege, immer her damit! ;)

Ist die Left-Right-Kette durchgängig, oder sind da aufgrund von Abfragebedingungen Lücken drin? (Ist aber nicht tragisch, nur im Lösungsweg etwas ungünstiger.) Ich würde jedenfalls nicht von den Rechts-Werten sondern hauptsächlich von den Links-Werten ausgehen. Die müssen auch aufsteigend sortiert sein (in jedem Fall, auch bei Lücken).

Bei lückenlos:

• Wenn Links +1 kleiner als Rechts bleibt, dann (nach der Ausgabe) absteigen (Rechts-Wert als Parent-Rechts-Parameter mitgeben), ansonsten hast du ein Blatt (Links +1 = Rechts).
• Ist Rechts gleich Parent-Rechts -1, dann nach oben zurückkehren.
  Rekursion hilft dir, die Parent-Rechts-Werte in lokalen Variablen abzulegen, und wieder auf sie zugreifen zu können, egal wie oft du inzwischen abgestiegen bist. Ansonten brauchst du einen Stack, um die jeweiligen Parent-Werte abzulegen.

Ich würde nicht versuchen wollen, in der Schleife vorwärts zu laufen und dann erst feststellen, dass ich mich nun in einem Nachbarn vom Parent befinde und eigentlich vorher hätte zurückkehren müssen. Das lässt sich allerdings nicht vermeiden, wenn du Lücken in den Links-Rechts-Werten hast. Denn mit Lücken kannst du teilweise nicht feststellen, dass du das letzte Blatt des aktuellen Zweiges vorliegen hast (sprich: der Vergleich auf Gleichheit von Rechts +1 mit dem Parent-Rechts ist nicht durchführbar). In dem Fall wirst du feststellen, dass Links größer als Parent-Rechts ist und solltest daraufhin in deiner Schleife über das Array einen Schritt zurückgehen sowie die aktuelle Rekusionsebene verlassen. Eine weiter oben gehst du wieder vorwärst, stellst fest, ob du ein Blatt hast oder immer noch der Parent-Rechts kleiner ist, und machst dann dasselbe: Blatt ausgeben oder wie bereits beschrieben einen Stufe nach oben gehen.

Das heißt, immer schön in Einzelschritten laufen und nicht mehrere Ebenen nach oben zu springen versuchen. Falls durch Bedingungen Parent-Nodes fehlen, aber dessen Kinder enthalten sind, hast du ein Problem. Du kannst (meines Erachtens) nicht feststellen, wieviel Parents fehlen und hättest auch ein Problem, die Kinder an die passende Ebene in deiner Ausgabe einzubauen, denn auch da fehlen ja die Eltern. Die Kinder rutschen dann zwangsläufig nach oben, je fehlendem Elter eine Ebene.

dedlfix.

[Peter L.]

Ist die Left-Right-Kette durchgängig, oder sind da aufgrund von Abfragebedingungen Lücken drin?

Es sind leider auch Lücken drin weil nicht jeder Benutzer zugriff auf alle Seiten hat.
Wie wäre es, wenn man Kinder ohne Eltern einfach irgendwie "überspringt"? Waisen sollten/müssen nicht im Menü auftauchen. Ich denke solche Seiten werden dann an anderer Stelle verlinkt.

Ich werde mal schauen wie weit ich mit deinem Vorschlag komme aber ich wollte erstmal deine Rückfrage beantworten weil ich nicht weiß wie lange ich mit der Umsetzung brauchen werde.

Dank dir für deine Hilfe!

[dedlfix]

Tach!

Wie wäre es, wenn man Kinder ohne Eltern einfach irgendwie "überspringt"? Waisen sollten/müssen nicht im Menü auftauchen.

Waisen erkennen ist vermutlich nicht ganz einfach. Meiner Meinung nach kann man sie nur an ihren jüngsten und ältesten Geschwistern erkennen, denn da besteht über ihren Links- beziehungsweise Rechts-Wert eine unmittelbare Beziehung zum Elter. Ein mittleres Geschwist erkennt man nur dann als Waisen, wenn die Kette aller Geschwister mindestens in einer Richtung vollständig ist und dann der Elter fehlt. Ansonsten kann man schlecht sagen, an welcher Stelle der Baum überall Lücken hat. Die Waisen haben üblicherweise einen Großelter oder noch weiter entfernte Vorfahren. Die Links-Rechts-Werte vom Großelter und so weiter sind immer um mehr als einen Zähler außerhalb der Kind-Links-Rechts. Bei einem Elter ist das ebenfalls der Fall, wenn das Kind Geschwister hat. Eine Aussage über den nächstgelegenen Vorfahren ist noch recht einfach herauszufinden, aber nicht, in welchem Level-Abstand der sich befindet, ohne sich den gesamten lückenlosen Baum entlangzuhangeln. Vielleicht bekommt man noch irgendwelche Aussagen über gerade und ungerade Werte und andere Rechenwege, aber das will ich grad nicht weiterdenken, weil es nichts bringt. Entweder hängst du die Waisen beim nächsten Vorfahren rein oder du versuchst sie gleich ganz aus der DBMS-Ergebnismenge fernzuhalten.

dedlfix.

[Peter L.]

Hallo!

Waisen erkennen ist vermutlich nicht ganz einfach. Meiner Meinung nach kann man sie nur an ihren jüngsten und ältesten Geschwistern erkennen, denn da besteht über ihren Links- beziehungsweise Rechts-Wert eine unmittelbare Beziehung zum Elter. Ein mittleres Geschwist erkennt man nur dann als Waisen, wenn die Kette aller Geschwister mindestens in einer Richtung vollständig ist und dann der Elter fehlt. Ansonsten kann man schlecht sagen, an welcher Stelle der Baum überall Lücken hat. Die Waisen haben üblicherweise einen Großelter oder noch weiter entfernte Vorfahren. Die Links-Rechts-Werte vom Großelter und so weiter sind immer um mehr als einen Zähler außerhalb der Kind-Links-Rechts. Bei einem Elter ist das ebenfalls der Fall, wenn das Kind Geschwister hat. Eine Aussage über den nächstgelegenen Vorfahren ist noch recht einfach herauszufinden, aber nicht, in welchem Level-Abstand der sich befindet, ohne sich den gesamten lückenlosen Baum entlangzuhangeln. Vielleicht bekommt man noch irgendwelche Aussagen über gerade und ungerade Werte und andere Rechenwege, aber das will ich grad nicht weiterdenken, weil es nichts bringt. Entweder hängst du die Waisen beim nächsten Vorfahren rein oder du versuchst sie gleich ganz aus der DBMS-Ergebnismenge fernzuhalten.

Puh, ich sehe schon. Das wird nicht einfach für mich. Vermutlich ist es doch das einfachste wenn ich die Datenbankabfrage zerlege. Mist, genau das wollte ich vermeiden.

Da ich sowieso noch keine Zeit hatte deinen anderen Vorschlag zu probieren, werf ich einfach mal gut gelaunt die Abfrage in die Runde. Vielleicht kommen "wir" ja damit weiter.

Also zunächst wohl erstmal die Tabellen. Die Spalten kürze ich hier mal zugunsten der Übersichtlichkeit.

  
/* Menü-Namen */  
CREATE TABLE `cms_menues` (  `id` int(11) NOT NULL AUTO_INCREMENT,  
`name` varchar(250) COLLATE utf8_bin NOT NULL,  
PRIMARY KEY (`id`),  UNIQUE KEY `name` (`name`))  
ENGINE=InnoDB AUTO_INCREMENT=3 DEFAULT CHARSET=utf8 COLLATE=utf8_bin  
  
/* Seiten */  
CREATE TABLE `cms_pages` (  `id` int(11) NOT NULL AUTO_INCREMENT,  
`name` varchar(20) COLLATE utf8_bin NOT NULL,  
PRIMARY KEY (`id`),  
UNIQUE KEY `name` (`name`))  
ENGINE=InnoDB AUTO_INCREMENT=3 DEFAULT CHARSET=utf8 COLLATE=utf8_bin  
  
/* Beziehung zwischen Menüs und Seiten */  
CREATE TABLE `cms_menu_pages` (  `id` int(11) NOT NULL AUTO_INCREMENT,  
`leftkey` int(11) NOT NULL,  
`rightkey` int(11) NOT NULL,  
`menu_id` int(11) NOT NULL,  
`page_id` int(11) NOT NULL,  
PRIMARY KEY (`id`),  
KEY `menu_id` (`menu_id`),  
KEY `page_id` (`page_id`),  
CONSTRAINT `cms_menu_pages_ibfk_1` FOREIGN KEY (`menu_id`) REFERENCES `cms_menues` (`id`) ON DELETE CASCADE,  
CONSTRAINT `cms_menu_pages_ibfk_2` FOREIGN KEY (`page_id`) REFERENCES `cms_pages` (`id`) ON DELETE CASCADE)  
ENGINE=InnoDB AUTO_INCREMENT=3 DEFAULT CHARSET=utf8 COLLATE=utf8_bin  
  
/* Benutzer */  
CREATE TABLE `cms_user` (  `id` int(11) NOT NULL AUTO_INCREMENT,  
PRIMARY KEY (`id`))  
ENGINE=InnoDB AUTO_INCREMENT=2 DEFAULT CHARSET=utf8 COLLATE=utf8_bin  
  
/* Gruppen */  
CREATE TABLE `cms_groups` (  `id` int(11) NOT NULL AUTO_INCREMENT,  
PRIMARY KEY (`id`),  UNIQUE KEY `name` (`name`))  
ENGINE=InnoDB AUTO_INCREMENT=5 DEFAULT CHARSET=utf8 COLLATE=utf8_bin  
  
/* Beziehung zwischen Benutzern und Gruppen */  
CREATE TABLE `cms_user_groups` (  `id` int(11) NOT NULL AUTO_INCREMENT,  
`user_id` int(11) NOT NULL,  
`group_id` int(11) NOT NULL,  
PRIMARY KEY (`id`),  
KEY `user_id` (`user_id`),  
KEY `group_id` (`group_id`),  
CONSTRAINT `cms_user_groups_ibfk_1` FOREIGN KEY (`user_id`) REFERENCES `cms_user` (`id`) ON DELETE CASCADE,  
CONSTRAINT `cms_user_groups_ibfk_2` FOREIGN KEY (`group_id`) REFERENCES `cms_groups` (`id`) ON DELETE CASCADE)  
ENGINE=InnoDB AUTO_INCREMENT=4 DEFAULT CHARSET=utf8 COLLATE=utf8_bin  
  
/* Inhalte */  
CREATE TABLE `cms_content` (  `id` int(11) NOT NULL AUTO_INCREMENT,  
`page_id` int(11) NOT NULL,  
`module_id` int(11) NOT NULL,  
PRIMARY KEY (`id`),  KEY `page_id` (`page_id`),  
KEY `module_id` (`module_id`),  KEY `field` (`field`),  
CONSTRAINT `cms_content_ibfk_1` FOREIGN KEY (`page_id`) REFERENCES `cms_pages` (`id`) ON DELETE CASCADE ON UPDATE CASCADE,  
CONSTRAINT `cms_content_ibfk_2` FOREIGN KEY (`module_id`) REFERENCES `cms_modules` (`id`) ON DELETE CASCADE ON UPDATE CASCADE)  
ENGINE=InnoDB AUTO_INCREMENT=5 DEFAULT CHARSET=utf8 COLLATE=utf8_bin  
  
/* Rechte */  
CREATE TABLE `cms_rights` (  `id` int(11) NOT NULL AUTO_INCREMENT,  
`table_row_id` int(11) DEFAULT NULL,  
`tablefield_name` varchar(250) COLLATE utf8_bin DEFAULT NULL,  
`group_id` int(11) NOT NULL,  
`content_id` int(11) NOT NULL,  
`rights` int(11) NOT NULL,  
PRIMARY KEY (`id`),  
KEY `group_id` (`group_id`),  
KEY `content_id` (`content_id`),  
CONSTRAINT `cms_rights_ibfk_1` FOREIGN KEY (`group_id`) REFERENCES `cms_groups` (`id`) ON DELETE CASCADE,  
CONSTRAINT `cms_rights_ibfk_2` FOREIGN KEY (`content_id`) REFERENCES `cms_content` (`id`) ON DELETE CASCADE)  
ENGINE=InnoDB AUTO_INCREMENT=8 DEFAULT CHARSET=utf8 COLLATE=utf8_bin  

Und Abschließend die Abfrage:

SELECT  
    `cms_menues`.`name` AS `menuName`,  
    `cms_menu_pages`.`leftkey`,  
    `cms_menu_pages`.`rightkey`,  
    `cms_pages`.`id`,  
    `cms_pages`.`name`  
FROM `cms_menu_pages`  
JOIN `cms_pages`  
ON `cms_menu_pages`.`page_id` = `cms_pages`.`id`  
JOIN `cms_menues`  
ON `cms_menu_pages`.`menu_id` = `cms_menues`.`id`  
WHERE `cms_pages`.`id`  
IN(  
    SELECT  
        `cms_content`.`page_id`  
    FROM `cms_content`  
    JOIN `cms_rights`  
    ON `cms_content`.`id` = `cms_rights`.`content_id`  
    WHERE `cms_content`.`page_id`  
    IN(  
        SELECT `cms_pages`.`id`  
        FROM `cms_menu_pages`  
        JOIN `cms_pages`  
        ON `cms_menu_pages`.`page_id` = `cms_pages`.`id`  
        WHERE `cms_menu_pages`.`menu_id` = ?  
    )  
    AND `cms_rights`.`group_id`  
    IN(  
        SELECT `cms_user_groups`.`group_id`  
        FROM `cms_user_groups`  
        WHERE `cms_user_groups`.`user_id` = ?  
    )  
)  
GROUP BY `cms_menu_pages`.`page_id`  
ORDER BY `cms_menu_pages`.`leftKey`

Ich hoffe, dass ich nichts vergessen habe. Natürlich beantworte ich auch gern jede Rückfrage.
Zunächst einmal frage ich mich, wie ich das Problem mit den Waisen löse oder ob es einfach keine Waisen geben darf wie das anderswo gelöst wird.
Und liege ich richtig, wenn ich vermute, dass ich die Beispiele von deinem Link einfach nur in das erste, äusserste SELECT schieben muss? Dann wäre es wohl doch einfacher als gedacht.

An den Tabellen kann ich selbst direkt nichts ändern. Es sollte aber kein Problem sein, es ändern "zu lassen" falls nötig :)
Und ob die Abfrage ideal ist, vermag ich leider auch nicht zu beurteilen.

Was meinst du, ist es sinnvoller mit der Datenbank-Abfrage oder mit dem Array zu spielen? Oder sogar mit der DB bzw. ihrer Tabellen selbst?

Oha... der post ist lang. Sorry und danke nochmals für deine Mühen!

[dedlfix]

Tach!

/* Beziehung zwischen Menüs und Seiten */
CREATE TABLE cms\_menu\_pages (  id int(11) NOT NULL AUTO_INCREMENT,
leftkey int(11) NOT NULL,
rightkey int(11) NOT NULL,
menu\_id int(11) NOT NULL,
page\_id int(11) NOT NULL,

Das ist ja die Nested-Sets-Tabelle. Und sie ist gleichzeitig die Verbindungstabelle einer m:n-Beziehung zwischen Menüs und Seiten. Für das Verständnis ist es wichtig, die Beziehungen zwischen den beiden abseits des Datenbankschemas und mehr aus fachlicher Sicht zu kennen. Ist es so, dass alle Menüpunkte in menues gelistet sind und in menu_pages die hierarchische Struktur abgebildet ist? Andererseits kann ich mir vorstellen, dass die m:n-Beziehung aussagt, welche Menüpunkte auf welcher Seite zu sehen sein soll. Wie aber spielt das mit der Hierarchie zusammen. Ein Menüpunkt kann vermutlich auf mehreren Seiten auftauchen und dann ist er mehrmals in den Nested Sets enthalten, oder nicht? Oder ist das alles ganz anders? Hier sehe ich Aufklärungsbedarf.

SELECT
    cms\_menues.name AS menuName,
    cms\_menu\_pages.leftkey,
    cms\_menu\_pages.rightkey,
    cms\_pages.id,
    cms\_pages.name
FROM cms\_menu\_pages
JOIN cms\_pages
ON cms\_menu\_pages.page\_id = cms\_pages.id
JOIN cms\_menues
ON cms\_menu\_pages.menu\_id = cms\_menues.id

Es joint hier zur m:n-Tabelle die m- und n-Tabelle, um deren Daten zu bekommen.

Zur WHERE-Klausel komme ich gleich noch. Aber du hast da eine Gruppierung,

GROUP BY cms\_menu\_pages.page\_id

mit der du viel mehr Spalten direkt und nicht aggregiert abfragst, als hier gruppiert wurden. Das lässt nur MySQL zu, anderswo wird das als Fehler geahndet. MySQL nimmt dann als Ergebnis pro Gruppe irgendeinen Wert dieser ungruppierten Spalten. Zu jeder Page-Id kommt also irgendeine beliebige Menu-ID ins Ergebnis. Das scheint mir komisch zu sein, aber vielleicht löst sich ja mit Kenntnis der Bedeutung auf. Zurück zum WHERE.

WHERE cms\_pages.id

Wir wollen nur Seiten,

IN(
    SELECT
        cms\_content.page\_id
    FROM cms\_content
    JOIN cms\_rights
    ON cms\_content.id = cms\_rights.content\_id
    WHERE
    cms\_rights.group\_id
    IN(
        SELECT cms\_user\_groups.group\_id
        FROM cms\_user\_groups
        WHERE cms\_user\_groups.user\_id = ?
    )

für deren Content der Nutzer über die Gruppenzugehörigkeit die Berechtigung hat (Ich habs mal umsortiert.)

AND
    cms\_content.page\_id
    IN(
        SELECT cms\_pages.id
        FROM cms\_menu\_pages
        JOIN cms\_pages
        ON cms\_menu\_pages.page\_id = cms\_pages.id
        WHERE cms\_menu\_pages.menu\_id = ?

(Einmal pages unnötigerweise gejoint. Die pages.id ist bereits als menu_pages.page_id verfügbar.)

und die zur übergebenen Menü-ID passen. Aber die Bedeutung dieser Bedingung erschließt sich mir nicht. Warum wird hier die Menu-ID als Parameter übergeben?

)
)

Und liege ich richtig, wenn ich vermute, dass ich die Beispiele von deinem Link einfach nur in das erste, äusserste SELECT schieben muss? Dann wäre es wohl doch einfacher als gedacht.

Das kann ich jetzt noch nicht sagen. Nur soviel: Nested-Sets-Abfragen verwenden oftmals Self-Joins und Gruppierung, so auch die Level-Query. Das mit der jetzigen gejointen und bereits gruppierten Query zu verheiraten wird eine ganz schöne Herausforderung werden.

Was meinst du, ist es sinnvoller mit der Datenbank-Abfrage oder mit dem Array zu spielen?

Bei der Komplexität der Query wird es wohl auf eine Array-Lösung hinauslaufen. Andererseits kann man die Komplexität mit noch mehr Komplexität augenscheinlich verringern. Die ungetestete Idee wäre, die Query in eine View zu bringen, dann wird die Anwendung des Self-Joins und der Gruppierung einfacher, als wenn man das Riesending doppelt notieren muss.

dedlfix.

[Peter L.]

Hallo!

/* Beziehung zwischen Menüs und Seiten */
Ist es so, dass alle Menüpunkte in menues gelistet sind und in menu_pages die hierarchische Struktur abgebildet ist? Andererseits kann ich mir vorstellen, dass die m:n-Beziehung aussagt, welche Menüpunkte auf welcher Seite zu sehen sein soll. Wie aber spielt das mit der Hierarchie zusammen. Ein Menüpunkt kann vermutlich auf mehreren Seiten auftauchen und dann ist er mehrmals in den Nested Sets enthalten, oder nicht? Oder ist das alles ganz anders? Hier sehe ich Aufklärungsbedarf.

Es ist so, dass in cms_menues nur die "internen" Namen der Menüs und Angaben wie "Anzeigen ab" und "...bis", u.ä. Bei einer Person würde ich es am ehesten mit den körperlichen Eigenschaften vergleichen wenn du so willst. Name, Geburts- und Sterbedatum etc..

z.B.
| id | name       |
-------------------
| 1  | topnavi    |
-------------------
| 2  | footernavi |
-------------------

In cms_pages liegen alle Seiten (auch als nested set aber das ist ein anderes Thema) und deren Eigenschaften.

z.B.
| id | name       |
------------------
| 1  | Startseite |
-------------------
| 2  | Kontakt    |
-------------------
In cms_menu_pages stehen alle Seiten die einem Menü zugeordnet wurden. Die Position der Seite in ihrer "eigenen nested set" spielt dabei keine Rolle. Jedes Menü hat sein eigenes Set gespeichert in der Tabelle.

z.B.
|leftKey | rightKey | menu_id | page_id |
-----------------------------------------
| 0      | 1        | 1       | 1       |
-----------------------------------------
| 2      | 3        | 1       | 2       |
-----------------------------------------
| 0      | 1        | 2       | 1       |
-----------------------------------------

Wir haben also 2 Menüs namens "topnavi" und "footernavi".
Topnavi verlinkt auf die Seiten "Startseite" und "Kontakt".
Footernavi verlinkt nur auf die "Startseite".
Die Menü-Ids ihrerseits stehen auch in "cms_content". Die Rechte werden also über die content-Id beschafft.

und die zur übergebenen Menü-ID passen. Aber die Bedeutung dieser Bedingung erschließt sich mir nicht. Warum wird hier die Menu-ID als Parameter übergeben?

Ich hoffe, ich konnte es dir erklären?!

Das kann ich jetzt noch nicht sagen. Nur soviel: Nested-Sets-Abfragen verwenden oftmals Self-Joins und Gruppierung, so auch die Level-Query. Das mit der jetzigen gejointen und bereits gruppierten Query zu verheiraten wird eine ganz schöne Herausforderung werden.

Das Statement zu ändern ist kein Problem, nur an die DB komme ich nicht so einfach ran.
Ich wollte das Statement nur nicht ändern aus Angst etwas kaputt zu machen.

Bei der Komplexität der Query wird es wohl auf eine Array-Lösung hinauslaufen. Andererseits kann man die Komplexität mit noch mehr Komplexität augenscheinlich verringern. Die ungetestete Idee wäre, die Query in eine View zu bringen, dann wird die Anwendung des Self-Joins und der Gruppierung einfacher, als wenn man das Riesending doppelt notieren muss.

Tut mir leid, ich kann dir nicht ganz folgen. "in eine View bringen"? Und wieso doppelt?

best regards

[dedlfix]

Tach!

|leftKey | rightKey | menu_id | page_id |

| 0      | 1        | 1       | 1       |

| 2      | 3        | 1       | 2       |

| 0      | 1        | 2       | 1       |

Das Statement zu ändern ist kein Problem, nur an die DB komme ich nicht so einfach ran.
Ich wollte das Statement nur nicht ändern aus Angst etwas kaputt zu machen.

Das ist schon kaputt und jemand hat es durch die Gruppierung zu reparieren versucht. Mal abgesehen von den Rechten liefert dir dieser Teil

SELECT cms\_pages.id
  FROM cms\_menu\_pages
  JOIN cms\_pages
  ON cms\_menu\_pages.page\_id = cms\_pages.id
  WHERE cms\_menu\_pages.menu\_id = ?

oder einfacher

SELECT cms\_menu\_pages.page\_id
  FROM cms\_menu\_pages
  WHERE cms\_menu\_pages.menu\_id = ?

alle Pages zu einer Menu-ID. Bei Menu-ID 1 und obigen Daten bekommst du also Page 1 und 2. Wenn beide Seiten in Content enthalten sind, liefert das SELECT cms\_content.page\_id FROM cms\_content wieder beide Page-IDs an die nun ganz äußere Query. Und wenn du da Menu-Pages mit diesen beiden Page-IDs befragst, bekommst du Menu 1 _und_ 2 - obwohl du in der Unterabfrage nur nach 1 gefragt hast.

Das heißt also, dass du für die Page-ID 1 topnavi und footernavi geliefert bekommst. Das gruppierst du und erhältst zufällig einen von beiden Werten. (MySQL trifft keine Aussage, welchen von den möglichen Werten es nimmt. Das kann zufällig immer der gewünschte sein, aber verlassen kann man sich nicht darauf.) Und das halte ich für einen Fehler. Die Gruppierung sollte weg und stattdessen die äußere Query um die Bedingung "AND cms\_menu\_pages.menu\_id=?" erweitert werden.

Nested-Sets-Abfragen verwenden oftmals Self-Joins und Gruppierung, so auch die Level-Query. Das mit der jetzigen gejointen und bereits gruppierten Query zu verheiraten wird eine ganz schöne Herausforderung werden.

Bei der Komplexität der Query wird es wohl auf eine Array-Lösung hinauslaufen. Andererseits kann man die Komplexität mit noch mehr Komplexität augenscheinlich verringern. Die ungetestete Idee wäre, die Query in eine View zu bringen, dann wird die Anwendung des Self-Joins und der Gruppierung einfacher, als wenn man das Riesending doppelt notieren muss.
Tut mir leid, ich kann dir nicht ganz folgen. "in eine View bringen"? Und wieso doppelt?

Eine View ist, wenn man ein (umfangreiches) SELECT-Statement in einem CREATE-VIEW-Statement kapselt. Man sagt dann nur noch SELECT viewname und gegebenenfalls WHERE-Bedingungen dazu. Dummerweise kannst du das mit der View in dem Fall gleich wieder vergessen, denn die View ist leider keine Funktion, der man Parameter übergeben kann, die dann an bliebiger Stelle des inneren Statements verwendet werden könnten. Eine Stored Procedure könnte das, die kann man aber nicht so flexibel einsetzen wie eine Tabelle oder View, sondern immer nur einzelstehend. Für den oben erwähnten SELF-Join (der notwendig ist, um das Level zu erhalten) braucht es aber eine doppelte Verwendung. Ich nehme an, dass eine View zweimal im FROM angegeben werden kann (wie Tabellen auch), und bin mir sicher, dass das für CALL nicht geht (das geht gar nicht als Subquery zu verwenden).

Damit ändern sich die Lösungsmöglichkeiten erheblich. Wenn das jetzige SELECT-Statement (abgesehen von den Fehlerkorrekturen) unverändert bleiben soll, bringt es hier nichts, es nur in eine Stored Procedure zu kapseln. Eine SP kann aber trotzdem helfen. Das SELECT-Statement muss sein Ergebnis in einer temporären Tabelle ablegen und die kann man dann in einem weiteren SELECT-Statement selfjoinen (alles innerhalb der SP).

Eine andere Idee ist, das jetzige verschachtelte SELECT zumindest soweit zu entschachteln (und einfache JOINS draus zu machen), dass die Parameter als Bedingungen des außeren Statements formuliert werden können. Dann kann man das Statement (abzüglich der Bedingungen) in einer View ablegen, und die lässt sich dann syntaktisch gesehen relativ einfach selfjoinen.

dedlfix.

[Peter L.]

Hallo!

Das ist schon kaputt und jemand hat es durch die Gruppierung zu reparieren versucht.

"Gut" :/ Ok, dann versuche ich die Query mal zu reparieren.

Wenn [..]
Das heißt also [..] Die Gruppierung sollte weg und stattdessen die äußere Query um die Bedingung "AND cms\_menu\_pages.menu\_id=?" erweitert werden.

Ok, habe ich erledigt.

Damit ändern sich die Lösungsmöglichkeiten erheblich. Wenn das jetzige SELECT-Statement (abgesehen von den Fehlerkorrekturen) unverändert bleiben soll, bringt es hier nichts, es nur in eine Stored Procedure zu kapseln. Eine SP kann aber trotzdem helfen. Das SELECT-Statement muss sein Ergebnis in einer temporären Tabelle ablegen und die kann man dann in einem weiteren SELECT-Statement selfjoinen (alles innerhalb der SP).

Eine andere Idee ist, das jetzige verschachtelte SELECT zumindest soweit zu entschachteln (und einfache JOINS draus zu machen), dass die Parameter als Bedingungen des außeren Statements formuliert werden können. Dann kann man das Statement (abzüglich der Bedingungen) in einer View ablegen, und die lässt sich dann syntaktisch gesehen relativ einfach selfjoinen.

Tut mir leid, dass ich nicht wirklich Ahnung von der Materie habe. Ich kann hier eigentlich nur deinem Rat folgen. Das Problem ist halt, dass ich frei definierte Menüs habe die völlig unabhängig von der eigentlichen Seitenstruktur sind. Trotzdem soll das Menü nur die Seiten anzeigen für deren Betrachtung ein bestimmter Benutzer auch die jeweiligen Rechte hat.

Wie wäre der Ansatz, dass ich doch wieder das Array betrachte und solche Menüs einfach nur "flach" zur Verfügung stelle? Oder meinst du, dass es den Aufwand Wert ist? Vielleicht ist das ja auch einfach überhaupt nicht möglich aus Waisen eine Baumstruktur zu rekonstruieren?

[dedlfix]

Tach!

Tut mir leid, dass ich nicht wirklich Ahnung von der Materie habe. Ich kann hier eigentlich nur deinem Rat folgen. [...]

Wir entfernen uns grade vom eigentlichen Problem, weil ich dachte, mit der Level-Information einfacher zum Ziel zu kommen. Doch auf dem Weg dahin werden die Berge immer höher.

Wie wäre der Ansatz, dass ich doch wieder das Array betrachte und solche Menüs einfach nur "flach" zur Verfügung stelle? Oder meinst du, dass es den Aufwand Wert ist? Vielleicht ist das ja auch einfach überhaupt nicht möglich aus Waisen eine Baumstruktur zu rekonstruieren?

Die Waisen sind kein großes Problem. Sie werden "nach oben fallen" in die Lücken, die ihre Vorfahren hinterlassen haben. Sie bleiben ja durch den "Einschluss" durch die Links-Rechts-Werte der Vorfahren von weiter oben an der richtigen Stelle. Ich denke, du solltest mir dem PHP-Lösungsvorschlag weitermachen. Das Absteigen ist ja einfach, für das Aufsteigen brauchst du, wie schon erwähnt, einen Stack oder Rekursion.

dedlfix.

[Peter L.]

Ich denke, du solltest mir dem PHP-Lösungsvorschlag weitermachen. Das Absteigen ist ja einfach, für das Aufsteigen brauchst du, wie schon erwähnt, einen Stack oder Rekursion.

Also befinden wir uns erstmal wieder hier wenn ich dir richtig folgen kann.
Ok, dann versuche ich mich erst nochmal mit Hilfe deiner Hinweise an der Funktion.

Ich danke!

[Peter L.]

Hallo!

Also ich hab mir jetzt ein paar Tage den Kopf zerbrochen aber ich kriege es absolut nicht hin.
Ich durchlaufe das "lückenhafte" Array und das einzige was ich hinkriege ist, dass ich eine Ebene tiefer muss wenn der left- oder der right-Wert kleiner als der right-Wert vom letzten Elter ist. Nach meinen Fehlversuchen muss ich mir auch eingestehen, dass ich überhaupt nicht weiß wie ich da mit einer Rekursion ansetzen muss. :/

Die Liste lasse ich erstmal weg weil ich glaube, dass es erstmal übersichtlicher ist, wenn ich nur die Ebene ausgebe.

class foo {  
  
// Array mit nested set Werten  
private $arrMenuItems = array();  
	  
private $intLevel = null;  
	  
private $intParentLeft = false;  
private $intParentRight = false;  
  
// Array mit Einträgen setzen  
public function __construct($arrItems){  
    $this->arrMenuItems = $arrItems;  
}  
  
// Level der Einträge ermitteln  
public function foo(){  
    foreach($this->arrMenuItems as $strKey=>&$arrMenuItem){  
        if($this->intParentLeft === false) {  
            $this->intParentLeft = $arrMenuItem['leftkey'];  
            $this->intParentRight = $arrMenuItem['rightkey'];  
            $this->intLevel = 0;  
            $arrMenuItem['level'] = $this->intLevel;  
            continue;  
        }  
		  
        if($arrMenuItem['leftkey'] < $this->intParentRight){  
            $this->intParentLeft = $arrMenuItem['leftkey'];  
            $this->intParentRight = $arrMenuItem['rightkey'];  
            $this->intLevel++;  
            $arrMenuItem['level'] = $this->intLevel;  
            continue;  
        }  
    }  
    print_r($this->arrMenuItems);  
}

Und das ist eigentlich auch schon alles was ich zum laufen gekriegt habe. Wie du siehst, ist es leider nicht sehr viel :(
Wie schon am Anfang gesagt, weiß ich überhaupt nicht wo ich in eine Rekursion springen muss und wann wieder zurück und wie dann weiter... puh, irgendwann habe ich bei deiner Erklärung den Faden verloren.

Könntest du mir nochmal einen Tipp geben? Mir platzt dabei irgendwie der Kopf.

[dedlfix]

Tach!

Ich durchlaufe das "lückenhafte" Array und das einzige was ich hinkriege ist, dass ich eine Ebene tiefer muss wenn der left- oder der right-Wert kleiner als der right-Wert vom letzten Elter ist.

Das dürfte nur die halbe Wahrheit sein. Bei mehreren Geschwistern wäre das ja jedes Mal der Fall. Eigentlich müsstest du immer dann absteigen, wenn L+1 kleiner R bleibt. Aber dann steigst du auch bei blätterlosen Zweigen ab, nur um unverrichteter Dinge wieder hochzusteigen. Damit das keine leeren ul-Elemente hinterlässt, musst du hier einmal vorausschauen, um zu sehen, ob das nächste L kleiner als dein aktuelles R ist. Das wiederum macht sich mit einem foreach nicht besonders gut. Ein indexbasiertes for ist da flexibler.

Nach meinen Fehlversuchen muss ich mir auch eingestehen, dass ich überhaupt nicht weiß wie ich da mit einer Rekursion ansetzen muss. :/

Ein Stack geht auch. Leg mal die Tastatur beiseite und versuch mal mit Bleistift auf Papier das Problem zu lösen. Während du absteigst, musst du dir merken, wer der Elter ist. Und wenn du weiter absteigst, muss der Großelter aufgehoben und mit dem aktuellen Elter weitergemacht werden. Beim Aufsteigen müssen ein oder mehrere Eltern gestrichen werden. Da kommt der Stack ins Spiel (ein normales Array und die Funktionen []= (array_push()), end() und array_pop()).

Bei Rekursion würdest du durch ein globales Array laufen (alternativ durch ein immer wieder/weiter durchgeschleiftes) und statt Stack hättest du eine lokale Variable, die auf den Elter zeigt (oder eine Kopie enthält).

Spielen wir mal die Stack-Variante ausgehend von dem Array deines Eingangspostings durch. i = Element 0, das hat L=0 und R=3, es ist ein Elter. Das kommt auf den Stack, aber erstmal schauen, ob das L vom i+1 kleiner als unser R ist. Das ist der Fall, also gibt es mindestens einen Nachkommen, der Abstieg lohnt sich. (Wenn das L allerdings kleiner als oder gleich unserem L ist, dann hast du einen Nebenbaum - allerdings passt diese Aussage nicht mehr, wenn es Teilbäume ohne Wurzeln gibt - aber vielleicht bekommst du sowas anhand der Menü-ID oder ähnlichem auseinandergehalten.) Nun gehts eins vorwärts im Array, L+1=R, ein Blatt, R < Elter-R, alles in Butter, ausgeben und weiter. Element 2 hat nun L=4 und das ist größer als das Eltern-R. Du musst jetzt vom Stack soviel abbauen bis das R kleiner als das Stack-R wird oder der Stack leer ist. Element 2 kommt aber nicht auf den Stack, weil dessen L+1=R ist, es also nur ein Blatt ist. Angenommen, es gäbe kein E2, dann ist dein Array zu Ende, aber der Stack ist noch nicht leer. Der muss nun noch abgebaut werden und dir offenen ul/li-Elemente geschlossen werden. Das Abbauen am Ende muss keine eigene Routine sein. Du könntest am Array-Ende ein Pseudo-Element erzeugen, dessen L und R = PHP_INT_MAX sind. Damit baut es den Stack auch komplett ab.

dedlfix.

[Peter L.]

Hallo dedlfix!

Spielen wir mal die Stack-Variante ausgehend von dem Array deines Eingangspostings durch. i = Element 0, das hat L=0 und R=3, es ist ein Elter. Das kommt auf den Stack, aber erstmal schauen, ob das L vom i+1 kleiner als unser R ist. Das ist der Fall, also gibt es mindestens einen Nachkommen, der Abstieg lohnt sich.

Ok soweit komme ich fast noch mit. Das bedeutet also, dass die Anzahl der Elemente auf dem Stack = der aktuellen Ebene sind? Also kann ich in jedem Schleifendurchlauf dem aktuellen Array den Wert hinzufügen?
Ich würde die Html-Liste gern erstmal in einer extra Schleife zusammenstellen damit ich den Überblick im Code nicht verliere.

(Wenn das L allerdings kleiner als oder gleich unserem L ist, dann hast du einen Nebenbaum - allerdings passt diese Aussage nicht mehr, wenn es Teilbäume ohne Wurzeln gibt - aber vielleicht bekommst du sowas anhand der Menü-ID oder ähnlichem auseinandergehalten.)

Was meinst du damit? Es gibt keine Menüs innerhalb von Menüs. Also Menüpunkt X von Menü A wird niemals Menü B sein. Oder habe ich dich falsch verstanden?

Ich habe es jetzt erstmal so. Es ist sicher nicht sehr elegant (das werde ich später optimieren) aber es scheint erstmal so zu funktionieren wie ich mir das vorgestellt habe.
Könntest du bitte mal schauen ob ich dich richtig verstanden und es richtig umgesetzt habe?

for($i = 0; $i < count($this->arrMenuItems); $i++){  
    echo 'Name: '.$this->arrMenuItems[$i]['name']." - Level: ";  
    // letzten Elter suchen  
    $arrParent = array_pop($this->arrStack);  
  
    // Element ein Elter, Kinder vorhanden?  
    if(isset($this->arrMenuItems[$i+1]) && $this->arrMenuItems[$i+1]['leftkey'] < $this->arrMenuItems[$i]['rightkey']){  
        echo count($this->arrStack)." \n";  
        $this->arrStack[] = $arrParent;  
        $this->arrStack[] = $this->arrMenuItems[$i];  
        continue;  
    }  
  
    // Element ein Blatt?		  
    if($this->arrMenuItems[$i]['leftkey']+1 == $this->arrMenuItems[$i]['rightkey'] && $this->arrMenuItems[$i]['rightkey'] < $arrParent['rightkey']){  
        echo count($this->arrStack)." \n";  
        $this->arrStack[] = $arrParent;  
        continue;  
    }  
  
    // Element höher oder neben des letzten Elter?			  
    if($this->arrMenuItems[$i]['leftkey'] > $arrParent['rightkey']){  
        $this->arrStack[] = $arrParent;  
        // stack abbauen				  
        while($this->arrMenuItems[$i]['rightkey'] > $arrParent['rightkey'] && count($this->arrStack) != 0){  
            $arrParent = array_pop($this->arrStack);  
        }  
        echo count($this->arrStack)." \n";  
        continue;  
    }  
}

$arrParent ist am Anfang ein leeres Array. Das müsste ich auch noch ändern. Den Stack am Ende zu leeren würde doch auch ein $arrStack = array() oder null am Ende reichen, oder warum überhaupt den Stack leeren? Kommt das zum tragen wenn ich direkt eine Html-Liste ausgebe?

Herzlichen Dank für deine Geduld! :)

[dedlfix]

Tach!

Spielen wir mal die Stack-Variante ausgehend von dem Array deines Eingangspostings durch. i = Element 0, das hat L=0 und R=3, es ist ein Elter. Das kommt auf den Stack, aber erstmal schauen, ob das L vom i+1 kleiner als unser R ist. Das ist der Fall, also gibt es mindestens einen Nachkommen, der Abstieg lohnt sich.

Ok soweit komme ich fast noch mit. Das bedeutet also, dass die Anzahl der Elemente auf dem Stack = der aktuellen Ebene sind? Also kann ich in jedem Schleifendurchlauf dem aktuellen Array den Wert hinzufügen?

In der Lösung brauchst du die Level-Angabe nicht mehr. Anhand des bereits in der Datenbank ermittelten Levels hätten wir sonst ab- und aufsteigen können. Aufgrund der Lücken haben wir aber von der Level-Lösung Abstand genommen. Aber ja, der Füllstand des Stacks repräsentiert auch das Level.

(Wenn das L allerdings kleiner als oder gleich unserem L ist, dann hast du einen Nebenbaum - allerdings passt diese Aussage nicht mehr, wenn es Teilbäume ohne Wurzeln gibt - aber vielleicht bekommst du sowas anhand der Menü-ID oder ähnlichem auseinandergehalten.)
Was meinst du damit? Es gibt keine Menüs innerhalb von Menüs. Also Menüpunkt X von Menü A wird niemals Menü B sein. Oder habe ich dich falsch verstanden?

Ich sah, dass du in der Tabelle mehrere Bäume abgelegt hast (je Menü einen). Wenn deine Abfrage immer nur Elemente eines Baumes/Menüs liefert, kannst du den Klammernsatz unberücksichtigt lassen. (Dürfte der Fall sein, weil du auf menu_id einschränkst.)

Ich habe es jetzt erstmal so. Es ist sicher nicht sehr elegant (das werde ich später optimieren) aber es scheint erstmal so zu funktionieren wie ich mir das vorgestellt habe.

Ja, nein. Wenn ein Elternelement ohne Kinder daherkommt, trifft keine deiner Bedingungen zu. (Zum Testen könntest du vor der das for schließenden Klammer noch eine Ausgabe (oder die()) setzen, wenn das ausgeführt wird, hast du einen Fall noch nicht berücksichtigt.) Ich würde die erste Bedingung so umschreiben, dass sie zunächst nur prüft, ob ein Elternelement vorliegt (L+1<R). Auch dann musst du ja eine Ausgabe vornehmen. Aber nun muss anhand von Kindern entschieden werden, ob abgestiegen werden soll, oder ob man sich das sparen kann. Das heißt, innerhalb des if(Elter)-Blocks kommt nun die Abfrage, ob das nächste Element ein Kind ist.

for($i = 0; $i < count($this->arrMenuItems); $i++){
    echo 'Name: '.$this->arrMenuItems[$i]['name']." - Level: ";

Du hast eine Menge Zugriffe auf das aktuelle Element. Es empfiehlt sich, $this->arrMenuItems[$i] in einer lokalen Variable ($current) abzulegen und die zu verwenden.

// letzten Elter suchen
    $arrParent = array_pop($this->arrStack);

Damit nimmst du den Elter auch vom Stack, was aber nur beim Aufsteigen passieren soll. Nimm an dieser Stelle end() und spar dir das Wiederdrauflegen. Beachte auch, dass array_pop() null und end() false liefert, wenn das Array leer ist.

$arrParent ist am Anfang ein leeres Array. Das müsste ich auch noch ändern.

Ah, das hast du schon bemerkt.

Den Stack am Ende zu leeren würde doch auch ein $arrStack = array() oder null am Ende reichen, oder warum überhaupt den Stack leeren? Kommt das zum tragen wenn ich direkt eine Html-Liste ausgebe?

Es geht nicht darum, die Variable aufzuräumen, sondern dass wenn da nochwas drinliegt, du noch abgestiegen bist. Für jedes Element, das da noch liegt, muss noch eine ul/li-Liste geschlossen werden.

$arrNested = array(  
  0 => array(  
    'leftkey' => 0,  
    'rightkey' => 5,  
    'name' => 'foo',  
  ),  
  1 => array(  
    'leftkey' => 1,  
    'rightkey' => 4,  
    'name' => 'bar',  
  ),  
);

Dieses Array enthält beide Fälle. Element 0 ist ein Elter mit Kind. Dem Element 1 fehlt das Kind (L2,R3). Es muss daher nicht auf den Stack. Nun ist das Array zu Ende und der Stack hat immer noch Element 0 draufliegen, und das muss noch abgebaut werden. Das Abbauen bekommst du quasi automatisch hin, wenn du wie nachfolgend ein Pseudo-Element ans Ende stellst. Das liegt wegen seiner L/R-Werte praktisch immer als Geschwist neben dem Root-Element, und um dahinzugelangen muss immer der Stack abgeräumt werden. Bei diesem Element musst du aber aufpassen, dass du davon nichts ausgibst, nur die Stack-Abbau-Nebenwirkung mitnimmst. Ansonsten müsstest du nach dem for nochmal den Stack-Abbau-Code explizit ausführen.

$arrNested = array(  
  0 => array(  
    'leftkey' => 0,  
    'rightkey' => 5,  
    'name' => 'foo',  
  ),  
  1 => array(  
    'leftkey' => 1,  
    'rightkey' => 4,  
    'name' => 'bar',  
  ),  
  2 => array(  
    'leftkey' => PHP_INT_MAX,  
    'rightkey' => PHP_INT_MAX,  
    'name' => 'nicht ausgeben',  
  ),  
);

dedlfix.

[Peter L.]

Ich würde die erste Bedingung so umschreiben, dass sie zunächst nur prüft, ob ein Elternelement vorliegt (L+1<R). Auch dann musst du ja eine Ausgabe vornehmen. Aber nun muss anhand von Kindern entschieden werden, ob abgestiegen werden soll, oder ob man sich das sparen kann. Das heißt, innerhalb des if(Elter)-Blocks kommt nun die Abfrage, ob das nächste Element ein Kind ist.

Jetzt habe ich alle Elemente auf Level 0!? Ähm...

Mein Test-Array:

$this->arrMenuItems = array(  
    array('leftkey'=> '0',  
          'rightkey'=> '5',  
          'name'=> 'foobar'),  
    array('leftkey'=> '6',  
          'rightkey'=> '7',  
          'name'=>'hauptmenu punkt1'),  
    array('leftkey'=> '8',  
          'rightkey'=> '9',  
          'name'=>'submenu2 punkt1'),  
    array('leftkey'=> '10',  
          'rightkey'=> '11',  
          'name'=>'submenu2 punkt2'),  
    array('leftkey'=> '12',  
          'rightkey'=> '14',  
          'name'=>'hauptmenu punkt2')  
);

Und die Schleife:

$counter = count($this->arrMenuItems);  
for($i = 0; $i < $counter; $i++){  
    echo 'Name: '.$this->arrMenuItems[$i]['name']." - Level: ";  
    $arrParent = array_pop($this->arrStack);  
  
    // Elter gefunden  
    if($this->arrMenuItems[$i]['leftkey']+1 < $this->arrMenuItems[$i]['rightkey']){  
        // Elter hat Kind  
        if(isset($this->arrMenuItems[$i+1]) && $this->arrMenuItems[$i+1]['rightkey'] < $this->arrMenuItems[$i]['rightkey']){  
            echo count($this->arrStack)." \n";  
            $this->arrStack[] = $arrParent;  
            $this->arrStack[] = $this->arrMenuItems[$i];  
        // Elter hat kein Kind mehr ;(  
        }else{  
            echo count($this->arrStack)." \n";  
            $this->arrStack[] = $arrParent;  
        }  
        continue;  
    }  
  
    // Element ein Blatt?  
    if($this->arrMenuItems[$i]['leftkey']+1 == $this->arrMenuItems[$i]['rightkey'] && $this->arrMenuItems[$i]['rightkey'] < $arrParent['rightkey']){  
        echo count($this->arrStack)." \n";  
        $this->arrStack[] = $arrParent;  
        continue;  
    }  
  
    // Element höher oder neben des letzten Elter?  
    if($this->arrMenuItems[$i]['leftkey'] > $arrParent['rightkey']){  
        $this->arrStack[] = $arrParent;  
	// Array abbauen			  
        while($this->arrMenuItems[$i]['rightkey'] > $arrParent['rightkey'] && count($this->arrStack) != 0){  
            $arrParent = array_pop($this->arrStack);  
        }  
        echo count($this->arrStack)." \n";  
        continue;  
    }  
    // irgendwas vergessen?  
    echo 'hund';  
}

Du hast eine Menge Zugriffe auf das aktuelle Element. Es empfiehlt sich, $this->arrMenuItems[$i] in einer lokalen Variable ($current) abzulegen und die zu verwenden.

Ist das in dem Fall nicht egal? Und wenn nicht wo liegt der Unterschied beim Zugriff auf ein "lokales" 2 dimensionales Array und dem auf ein 3 dimensionales Klassenweites?

// letzten Elter suchen
    $arrParent = array_pop($this->arrStack);

Damit nimmst du den Elter auch vom Stack, was aber nur beim Aufsteigen passieren soll. Nimm an dieser Stelle end() und spar dir das Wiederdrauflegen. Beachte auch, dass array_pop() null und end() false liefert, wenn das Array leer ist.

Aber ich lege ihn ja auch immer wieder drauf. Und beim Vergleich als "Blatt" brauch ich ja auch das Elter. Deshalb habe ich es erstmal grundsätzlich abgezogen und immer wieder drauf gelegt. Wie gesagt, der Code ist noch nicht sehr elegant. Ich bin mir grad nicht sicher was du mit "beim Aufsteigen" meinst.
Meinst du meine while-Schleife?

Es geht nicht darum, die Variable aufzuräumen, sondern dass wenn da nochwas drinliegt, du noch abgestiegen bist. Für jedes Element, das da noch liegt, muss noch eine ul/li-Liste geschlossen werden.

Die Geschichte mit dem abbauen des Stacks muss ich mir nochmal durch den Kopf gehen lassen. Ich dachte, das würde ich in der while-Schleife schaffen. Um die Liste würde ich mir auch erst Gedanken machen wenn ich die Level zuverlässig ermitteln kann.

Aber was hab ich denn kaputt gemacht, dass jetzt jedes Level 0 ist? ôO

[Peter L.]

Aber was hab ich denn kaputt gemacht, dass jetzt jedes Level 0 ist? ôO

Ach ich hab es.
"rightkey" von Element 1 sollte 12 sein und der "leftkey" vom letzten Element 13.

Mein Test-Array:

$this->arrMenuItems = array(

array('leftkey'=> '0',
          'rightkey'=> '5',
          'name'=> 'foobar'),
    array('leftkey'=> '6',
          'rightkey'=> '12',
          'name'=>'hauptmenu punkt1'),
    array('leftkey'=> '8',
          'rightkey'=> '9',
          'name'=>'submenu2 punkt1'),
    array('leftkey'=> '10',
          'rightkey'=> '11',
          'name'=>'submenu2 punkt2'),
    array('leftkey'=> '13',
          'rightkey'=> '14',
          'name'=>'hauptmenu punkt2')
);

  
Hab ich jetzt alles?

[Peter L.]

Ok, ich hab schon gesehen, dass ich auch in dem Array noch Fehler hatte.
Ich habe jetzt hoffentlich erstmal alle "groben" Fehler beseitigt.

$this->arrMenuItems = array(  
array('leftkey'=> '0',  
'rightkey'=> '5',  
'name'=> 'foobar'),  
array(	'leftkey'=> '6',  
'rightkey'=> '11',  
'name'=>'hauptmenu punkt1'),  
array(	'leftkey'=> '7',  
'rightkey'=> '8',  
'name'=>'submenu2 punkt1'),  
array(	'leftkey'=> '9',  
'rightkey'=> '10',  
'name'=>'submenu2 punkt2'),  
array(	'leftkey'=> '12',  
'rightkey'=> '15',  
'name'=>'hauptmenu punkt2')  
);  
  
$counter = count($this->arrMenuItems);  
for($i = 0; $i < $counter; $i++){  
	echo 'Name: '.$this->arrMenuItems[$i]['name']." - Level: ";  
	$arrParent = array_pop($this->arrStack);  
	// Elter gefunden  
	if($this->arrMenuItems[$i]['leftkey']+1 < $this->arrMenuItems[$i]['rightkey']){  
		// Elter hat Kind  
		if(isset($this->arrMenuItems[$i+1]) && $this->arrMenuItems[$i+1]['rightkey'] < $this->arrMenuItems[$i]['rightkey']){  
			echo count($this->arrStack)." \n";  
			$this->arrStack[] = $arrParent;  
			$this->arrStack[] = $this->arrMenuItems[$i];  
			// Elter hat kein Kind  
		}else{  
			if($this->arrMenuItems[$i]['leftkey'] > $arrParent['rightkey']){  
				$this->arrStack[] = $arrParent;  
				while($this->arrMenuItems[$i]['rightkey'] > $arrParent['rightkey'] && count($this->arrStack) != 0){  
					$arrParent = array_pop($this->arrStack);  
				}  
				echo count($this->arrStack)." \n";  
			}  
		}  
		continue;  
	}  
	// Blatt gefunden  
	if($this->arrMenuItems[$i]['leftkey']+1 == $this->arrMenuItems[$i]['rightkey'] && $this->arrMenuItems[$i]['rightkey'] < $arrParent['rightkey']){  
		echo count($this->arrStack)." \n";  
		$this->arrStack[] = $arrParent;  
		continue;  
	}  
	echo 'hund';  
}

Scheint wieder alles zu stimmen inklusive Lücken, kinderlosen Eltern, auf- und absteigen.
Bitte lass diesmal alles richtig sein! :D

[Peter L.]

Klappt leider auch nicht. Wenn ich Element 4 L=14 gebe, kommt mein Hund. :/

[dedlfix]

Tach!

Klappt leider auch nicht. Wenn ich Element 4 L=14 gebe, kommt mein Hund. :/

Weil das ein Wurzel-Blatt ist. Du prüfst bei Blättern auf das Eltern-Element. Da muss noch der Fall, dass der Stack leer ist, berücksichtigt werden.

dedlfix.

[Peter L.]

Hey!

Weil das ein Wurzel-Blatt ist. Du prüfst bei Blättern auf das Eltern-Element. Da muss noch der Fall, dass der Stack leer ist, berücksichtigt werden.

Soll ich so tun?

  
$this->arrMenuItems = array(  
	array(	'leftkey'=> '0',  
		'rightkey'=> '5',  
		'name'=> 'foobar'),  
	array(	'leftkey'=> '6',  
		'rightkey'=> '11',  
		'menuName'=>'hauptmenu',  
		'name'=>'hauptmenu punkt1'),  
	array(	'leftkey'=> '7',  
		'rightkey'=> '10',  
		'menuName'=>'submenu2',  
		'name'=>'submenu2 punkt1'),  
	array(	'leftkey'=> '8',  
		'rightkey'=> '9',  
		'menuName'=>'submenu2',  
		'name'=>'submenu2 punkt2'),  
	array(	'leftkey'=> '14',  // oder z.B. 12  
		'rightkey'=> '15',  
		'menuName'=>'hauptmenu',  
		'name'=>'hauptmenu punkt2'),  
	array(	'leftkey'=> '16',  // oder z.B. 18  
		'rightkey'=> '19',  
		'menuName'=>'test',  
		'name'=>'hauptmenu punkt3')  
);  
  
$counter = count($this->arrMenuItems);  
for($i = 0; $i < $counter; $i++){  
	echo 'Name: '.$this->arrMenuItems[$i]['name']." - Level: ";  
	$arrParent = end($this->arrStack);  
	// Elter gefunden  
	if($this->arrMenuItems[$i]['leftkey']+1 < $this->arrMenuItems[$i]['rightkey']){  
		// Elter hat Kind  
		if(isset($this->arrMenuItems[$i+1]) && $this->arrMenuItems[$i+1]['rightkey'] < $this->arrMenuItems[$i]['rightkey']){  
			echo count($this->arrStack)." \n";  
			$this->arrStack[] = $this->arrMenuItems[$i];  
		// Elter hat kein Kind  
		}else{  
			if($this->arrMenuItems[$i]['leftkey'] > $arrParent['rightkey']){  
			  
				while($this->arrMenuItems[$i]['rightkey'] > $arrParent['rightkey'] && count($this->arrStack) != 0){  
					$arrParent = array_pop($this->arrStack);  
				}  
				echo count($this->arrStack)."\n";  
			}  
		}  
		continue;  
	}  
	// Blatt gefunden  
	if($this->arrMenuItems[$i]['leftkey']+1 == $this->arrMenuItems[$i]['rightkey']){  
		// Blatt hat Elter  
		if($this->arrMenuItems[$i]['rightkey'] < $arrParent['rightkey']){  
			echo count($this->arrStack)."\n";  
		// Blatt ist Elternlos und hat keine Kinder  
		}else{  
			$this->arrStack = array();  
			echo count($this->arrStack)."\n";  // sollte wohl immer 0 sein  
		}  
		continue;  
	}  
	echo 'hund';  
}

Scheint mal wieder alles zu funktionieren.

[dedlfix]

Tach!

  // Blatt ist Elternlos und hat keine Kinder  
  }else{  
  	$this->arrStack = array();  
  	echo count($this->arrStack)."\n";  // sollte wohl immer 0 sein  
  }  

Warum löschst du da den Stack? Der muss an der Stelle nicht weiter bearbeitet werden, ist 0 und bleibt 0. Wenn er nicht 0 ist, hast du einen Fehler (ich seh aber grad keinen).

dedlfix.

[Peter L.]

Warum löschst du da den Stack? Der muss an der Stelle nicht weiter bearbeitet werden, ist 0 und bleibt 0. Wenn er nicht 0 ist, hast du einen Fehler (ich seh aber grad keinen).

Normalerweise müsste der Stack an der Stelle abgebaut werden (wegen den ul) - denke ich. Bei mir gibt es ohne das Resetten des Array sonst "2" aus.

[dedlfix]

Tach!

Warum löschst du da den Stack? Der muss an der Stelle nicht weiter bearbeitet werden, ist 0 und bleibt 0. Wenn er nicht 0 ist, hast du einen Fehler (ich seh aber grad keinen).

Normalerweise müsste der Stack an der Stelle abgebaut werden (wegen den ul) - denke ich. Bei mir gibt es ohne das Resetten des Array sonst "2" aus.

Ja, aber der darf nicht einfach gelöscht werden, sondern muss schrittweise abgebaut werden, weil die ullis geschlossen werden müssen.

dedlfix.

[Peter L.]

Ja, aber der darf nicht einfach gelöscht werden, sondern muss schrittweise abgebaut werden, weil die ullis geschlossen werden müssen.

Ich dachte wir sind uns mittlerweile einig, dass ich erstmal nur die Kontrollausgabe mache?^^
Das habe ich also bewusst nicht berücksichtig aber danke trotzdem für den Hinweis (besser zu viel als zu wenig ;) )!

Dann haben wir es jetzt endlich geschafft?
Du kannst dir ja gar nicht vorstellen wie dankbar ich dir gerade bin! :D
Wirklich ganz herzlichen Dank für deine Hilfe und vor allem für deine Geduld!

Ich bin daran sowas von verzweifelt...
Ich werde den Code natürlich auch noch ein bisschen optimieren bzw. Fehlerquellen (z.B. leere Arrays) vermeiden. Und für die Ausgabe als Html-Liste brauch es natürlich auch noch ein paar Zeilen aber das kriege ich selbst hin. Also nochmal herzlichen Dank!

Beste Grüße!

[Peter L.]

Oh, nur um sicher zu gehen, dass ich dich bei der Datenbankabfrage auch richtig verstanden habe...

SELECT  
	`cms_menues`.`name` AS `menuName`,  
	`cms_menu_pages`.`leftkey`,  
	`cms_menu_pages`.`rightkey`,  
	`cms_pages`.`id`,  
	`cms_pages`.`name`  
FROM `cms_menu_pages`  
JOIN `cms_pages`  
ON	`cms_menu_pages`.`page_id` = `cms_pages`.`id`  
JOIN `cms_menues`  
ON `cms_menu_pages`.`menu_id` = `cms_menues`.`id`  
WHERE `cms_pages`.`id`  
IN(  
	SELECT  
		`cms_content`.`page_id`  
	FROM `cms_content`  
	JOIN `cms_rights`  
	ON `cms_content`.`id` = `cms_rights`.`content_id`  
	WHERE `cms_content`.`page_id`  
	IN(  
		SELECT `cms_pages`.`id`  
		FROM `cms_menu_pages`  
		JOIN `cms_pages`  
		ON `cms_menu_pages`.`page_id` = `cms_pages`.`id`  
		WHERE `cms_menu_pages`.`menu_id` = ?  
	)  
	AND `cms_rights`.`group_id`  
	IN(  
		SELECT `cms_user_groups`.`group_id`  
		FROM `cms_user_groups`  
		WHERE `cms_user_groups`.`user_id` = ?  
	)  
)  
AND `cms_menu_pages`.`menu_id` = ?  
ORDER BY `cms_menu_pages`.`leftKey`

Ich habe in der vorletzten Zeile also nur den "GROUP BY"-Teil durch "AND cms\_menu\_pages..." ersetzt. War das richtig?

[dedlfix]

Tach!

Ich habe in der vorletzten Zeile also nur den "GROUP BY"-Teil durch "AND cms\_menu\_pages..." ersetzt. War das richtig?

Ja, und hier

  SELECT `cms\_pages`.`id`  
  FROM `cms\_menu\_pages`  
  JOIN `cms\_pages`  
  ON `cms\_menu\_pages`.`page\_id` = `cms\_pages`.`id`  
  WHERE `cms\_menu\_pages`.`menu\_id` = ?  

gehts auch einfacher. Das JOIN kann weg und dann (nur) cms\_menu\_pages.page\_id selektieren.

dedlfix.

[Peter L.]

Ja, und hier

  SELECT `cms\_pages`.`id`  
  FROM `cms\_menu\_pages`  
  JOIN `cms\_pages`  
  ON `cms\_menu\_pages`.`page\_id` = `cms\_pages`.`id`  
  WHERE `cms\_menu\_pages`.`menu\_id` = ?  

gehts auch einfacher. Das JOIN kann weg und dann (nur) cms\_menu\_pages.page\_id selektieren.

Dann war die Abfrage ja gar nicht mal so sehr "kaputt".
Nochmals herzlichen Dank! Du hast mir wirklich sehr geholfen! :)

[dedlfix]

Tach!

Du hast eine Menge Zugriffe auf das aktuelle Element. Es empfiehlt sich, $this->arrMenuItems[$i] in einer lokalen Variable ($current) abzulegen und die zu verwenden.

Ist das in dem Fall nicht egal? Und wenn nicht wo liegt der Unterschied beim Zugriff auf ein "lokales" 2 dimensionales Array und dem auf ein 3 dimensionales Klassenweites?

Vorteile sind die Einsparung beim Tippen, der sprechendere Name und ganz geringfügig Performance, weil weniger [$i] aufgelöst werden muss.

// letzten Elter suchen
    $arrParent = array_pop($this->arrStack);

Damit nimmst du den Elter auch vom Stack, was aber nur beim Aufsteigen passieren soll. Nimm an dieser Stelle end() und spar dir das Wiederdrauflegen. Beachte auch, dass array_pop() null und end() false liefert, wenn das Array leer ist.
Aber ich lege ihn ja auch immer wieder drauf. Und beim Vergleich als "Blatt" brauch ich ja auch das Elter.

Ja, und da reicht es, wenn du eine Kopie nimmst und nicht ständig das Array bearbeitest.

Ich bin mir grad nicht sicher was du mit "beim Aufsteigen" meinst. Meinst du meine while-Schleife?

Ja, die while-Schleife, oder allgemein gesagt, wenn du in die Ebene des Vorfahren zurückkehrst.

Es geht nicht darum, die Variable aufzuräumen, sondern dass wenn da nochwas drinliegt, du noch abgestiegen bist. Für jedes Element, das da noch liegt, muss noch eine ul/li-Liste geschlossen werden.
Die Geschichte mit dem abbauen des Stacks muss ich mir nochmal durch den Kopf gehen lassen. Ich dachte, das würde ich in der while-Schleife schaffen. Um die Liste würde ich mir auch erst Gedanken machen wenn ich die Level zuverlässig ermitteln kann.

Wie gesagt, die Level-Nummer brauchst du nicht, um die ul/li-Struktur aufzubauen. Die dient dir jetzt nur, um das richtige Entlanghangeln durch das Array zu prüfen. Du kannst ja jetzt schon mithilfe des Stacks ab- und aufsteigen, was übersetzt in das eigentliche Ziel heißt: ein neues ul erzeugen und es am Ende ordentlich schließen. Und um zum Schluss alle geschlossen zu haben, musst du den Stack abgebaut haben.

dedlfix.

[Peter L.]

Vorteile sind die Einsparung beim Tippen, der sprechendere Name und ganz geringfügig Performance, weil weniger [$i] aufgelöst werden muss.

Dem gegenüber stelle ich aber Eindeutigkeit (siehe $name = $_POST['name']). Ich bin mir nicht sicher ob die geringe Performance-Verbesserung (sollte es eine geben, immerhin muss $i sowieso schon vorher aufgelöst werden) das aufwiegt. Ich versuche das aber mal zukünftig zu berücksichtigen wenn es um mehr als nur ein $i geht. Danke für den Hinweis!

Ja, und da reicht es, wenn du eine Kopie nimmst und nicht ständig das Array bearbeitest.

Die Kopie erreiche ich aber nunmal am einfachsten durch das pop oder nicht?
In der while-Schleife brauche ich das pop ja nur um den Stapel abzubauen. Ein unset täte es natürlich auch.

Wie gesagt, die Level-Nummer brauchst du nicht, um die ul/li-Struktur aufzubauen. Die dient dir jetzt nur, um das richtige Entlanghangeln durch das Array zu prüfen. Du kannst ja jetzt schon mithilfe des Stacks ab- und aufsteigen, was übersetzt in das eigentliche Ziel heißt: ein neues ul erzeugen und es am Ende ordentlich schließen. Und um zum Schluss alle geschlossen zu haben, musst du den Stack abgebaut haben.

Ah ok, z.B. wenn das letzte Element im Array ein Ur-Ur-Enkel ist? Ja, das leuchtet ein.

[dedlfix]

Tach!

Ja, und da reicht es, wenn du eine Kopie nimmst und nicht ständig das Array bearbeitest.
Die Kopie erreiche ich aber nunmal am einfachsten durch das pop oder nicht?

Nö, end(...) kopiert das letzte Element eines Arrays, ohne das Array zu verändern.

In der while-Schleife brauche ich das pop ja nur um den Stapel abzubauen. Ein unset täte es natürlich auch.

Beim unset müsstest du den Key des Elements wissen. Den bekommst du zwar über count($array), aber da ist array_pop() einfacher.

dedlfix.