[PHP] Alle kinderen van een node uit array halen

[Reveller]

Ik heb de volgende code:

PHP:

$menuItems[1] = Array('parent'=> 0, 'title'=>'Home'     ); 
$menuItems[2] = Array('parent'=> 1, 'title'=>'Producten');
$menuItems[3] = Array('parent'=> 2, 'title'=>'Groenten' );
$menuItems[4] = Array('parent'=> 2, 'title'=>'Fruit'    );
$menuItems[5] = Array('parent'=> 3, 'title'=>'Zomer'    );
$menuItems[6] = Array('parent'=> 3, 'title'=>'Winter'   );
$menuItems[7] = Array('parent'=> 4, 'title'=>'Rood'     );

/**
 * Fetch all descendants of a node
 */
function getAllChildNodes($menuItems, $activeItem)
{
  $childNodes = array();
  foreach ($menuItems as $itemKey=>$item)
    if ($item['parent'] == $activeItem)
      $childNodes[] = $itemKey;

  return $childNodes;
}

$allChildren = getAllChildNodes($menuItems, 2);
print_r($allChildren);

De bedoeling is dat de functie getAllChildNodes alle kinderen van een node ophaalt. Met andere woorden: als ik de kinderen van Producten wil hebben, moet de functie 3, 4, 5, 6, 7 retourneren (in een array).

Ik ben zover dat ik van een node uit de array de directe kinderen kan bepalen. Mijn vraag is hoe ik efficient verder langs de array kan lopen om de overige kinderen eruit te halen. Het zou kunnen door deze functie zichzelf aan te laten roepen voor elke node (recursie), maar dat lijkt me wat inefficient als de $menuItems array groter wordt. Heeft iemand een andere oplossing?

[X-Lars]

Dit kan toch mooi recursief? Dus voor elke "distinct" $itemKey de functie aanroepen met getAllChildNodes($menuItems, $itemKey).

[Reveller]

Als het niet teveel performance kost - maar dat moet ik misschien eens meten. Gek trouwens - ik had verwacht dat dit zou werken:

PHP:

/**
 * Fetch all descendants of a node
 */
function getAllChildNodes($menuItems, $activeItem)
{
  foreach ($menuItems as $itemKey=>$item)
  {
    if ($item['parent'] == $activeItem)
    {
      $childNodes[] = $itemKey;
      getAllChildNodes($menuItems, $itemKey);
    }  
  }
  return $childNodes;
}

Maar er is hierbij geen verschil met de functie uit de topicstart. Dit is toch een goede recursieve functie?

[pjotrk]

Qua recursie moet dat inderdaad gewoon zo werken, echter moeten de arrays natuurlijk nog wel worden samengevoegd, anders heeft de recursieve functie weinig zin

zoiets dus:

PHP:

$childNodes=array_merge($childNodes,getAllChildNodes($menuItems,$itemKey));

De performance bij grote trees zal hierbij inderdaad niet zo hoog zijn omdat voor elke node weer de volledige tree doorlopen moet worden om te bepalen of deze subnodes heeft. In o.a. de topic [rml][ php] Recursieve boomstructuur efficienter maken[/rml] is hiervoor een snellere en toch nog redelijk eenvoudige methode gebruikt om een tree op te bouwen in een array.

[Reveller]

Dank je! Ik heb hier (werk) geen PHP omgeving, maar ga het vanavond zeker testen!

pjotrk schreef op donderdag 09 december 2004 @ 00:20:
In o.a. de topic [rml][ php] Recursieve boomstructuur efficienter maken[/rml] is hiervoor een snellere en toch nog redelijk eenvoudige methode gebruikt om een tree op te bouwen in een array.

Dat topic had ik inderdaad al gevonden en doorgekeken, maar stijgt momenteel nog boven mijn niveau uit. Ik stond wel te kijken van de performance-winst, en wil het zeker nog eens implementeren. Maar eerst is mijn doel om het ueberhaupt werkende te krijgen - het is voor het eerst dat ik met 1 query alle nodes ophaal uit de database, in een array giet en vervolgens telkens die array bewerk. Ik voel me wel ontzettend cool op het moment

Mark Twain:
"Continuous improvement is better than delayed perfection"

[ Voor 15% gewijzigd door Reveller op 09-12-2004 11:01 . Reden: quotes rule :) ]

[Reveller]

Ik heb de oplossing van pjotrk in mijn functie verwerkt:

PHP:

/**
 * Fetch all descendants of a node
 */
function getAllChildNodes($menuItems, $activeItem)
{
  foreach ($menuItems as $itemKey=>$item)
  {
    if ($item['parent'] == $activeItem)
    {
      $childNodes[] = $itemKey;
      $childNodes   = array_merge($childNodes,getAllChildNodes($menuItems,$itemKey));
    }  
  }
  return $childNodes;
}

Raar is alleen dat de array die gereturned wordt, er zo uitziet:

code:

Array
(
    [0] => 3
    [1] => 5
    [2] => 6
    [3] => 4
    [4] => 7
)

Niet op volgorde dus. Als de array van voor naar achteren wordt doorgelopen, zou je in dit geval een output verwachten als volgt:

code:

Array
(
    [0] => 3
    [1] => 4
    [2] => 5
    [3] => 6
    [4] => 7
)

Of niet? En zo ja, waar zit hem de fout?

[ Voor 15% gewijzigd door Reveller op 09-12-2004 15:09 ]

[pjotrk]

Niet persé raar, de sleutel van een node geeft hoogstens de volgorde van het toevoegen van de nodes aan de array weer, maar niet noodzakelijk ook de daadwerkelijk volgorde van de nodes in de boom.

Wanneer je de nodes in de array als een boom zou weergeven zullen de nodes als volgt worden gerangschikt.

PHP:

$menuItems[3] = Array('parent'=> 2, 'title'=>'Groenten' ); 
    $menuItems[5] = Array('parent'=> 3, 'title'=>'Zomer'); 
    $menuItems[6] = Array('parent'=> 3, 'title'=>'Winter');
$menuItems[4] = Array('parent'=> 2, 'title'=>'Fruit'); 
    $menuItems[7] = Array('parent'=> 4, 'title'=>'Rood');

Ook de recursieve functie zal de nodes dus in die volgorde toevoegen aan de array. Aangezien deze ook gewoon de boom opbouwt, startende bij de aangegeven parent node.

[Reveller]

Dank je voor de uitleg! Logisch eigenlijk.

Mijn laatste probleem dit: ik wil graag de $itemKey als key van de nieuwe $childNodes array:

PHP:

/**
 * Fetch all descendants of a node
 */
function getAllChildNodes($menuItems, $activeItem)
{
  foreach ($menuItems as $itemKey=>$item)
  {
    if ($item['parent'] == $activeItem)
    {
      $childNodes[$itemKey] = $item;
      $childNodes   = array_merge($childNodes,getAllChildNodes($menuItems,$itemKey));
    }  
  }  
  return $childNodes;
}

(Regel 10). Toch blijft de array stug beginnen met [0]. Volgens mij is regel 10 toch valide PHP?

[pjotrk]

Regel 10 klopt inderdaad wel. Het herindexen wordt gedaan door array_merge.

http://nl2.php.net/manual/nl/function.array-merge.php

array array_merge ( array array1, array array2 [, array ...])

array_merge() voegt de elementen van twee of meer arrays samen zodat de waarden van de ene worden toegevoegd aan het einde van de vorige. De functie geeft de resulterende array terug.

Als de input arrays dezelfde string keys hebben zal de latere waarde bij die key de eerdere overschrijven. Als de arrays echter numerieke keys hebben, zal de latere waarde de originele waarde niet overschrijven, maar in plaats daarvan worden toegevoegd.

ipv array_merge zou je dus gewoon de 2 arrays moeten samenvoegen met de + operator, wat in dit geval ook wel zou kunnen, aangezien de itemKey uniek in elke boom:

PHP:

/**
 * Fetch all descendants of a node
 */
function getAllChildNodes($menuItems, $activeItem)
{
  $childNodes = array();
  foreach ($menuItems as $itemKey=>$item)
  {
    if ($item['parent'] == $activeItem)
    {
      $childNodes[$itemKey] = $item;
      $childNodes += getAllChildNodes($menuItems,$itemKey);
    }
  }
  return $childNodes;
}

[Reveller]

Pjotrk - dank je! Ik ga eens wat meer lezen over array_merge en arrays in het algemeen, want mijn kennis is blijkbaar ver onder de maat op dit gebied

[ Voor 9% gewijzigd door Reveller op 09-12-2004 17:33 ]