Une autre façon, plus simplifiée, de convertir la structure plate dans le fichier $tree dans une hiérarchie. Un seul tableau temporaire est nécessaire pour l'exposer :
// add children to parents
$flat = array(); # temporary array
foreach ($tree as $name => $parent)
{
$flat[$name]['name'] = $name; # self
if (NULL === $parent)
{
# no parent, is root element, assign it to $tree
$tree = &$flat[$name];
}
else
{
# has parent, add self as child
$flat[$parent]['children'][] = &$flat[$name];
}
}
unset($flat);
C'est tout pour obtenir la hiérarchie dans un tableau multidimensionnel :
Array
(
[children] => Array
(
[0] => Array
(
[children] => Array
(
[0] => Array
(
[name] => H
)
[1] => Array
(
[name] => F
)
)
[name] => G
)
[1] => Array
(
[name] => E
[children] => Array
(
[0] => Array
(
[name] => A
)
[1] => Array
(
[children] => Array
(
[0] => Array
(
[name] => B
)
)
[name] => C
)
)
)
)
[name] => D
)
La sortie est moins triviale si vous voulez éviter la récursion (peut être un fardeau avec de grandes structures).
J'ai toujours voulu résoudre le "dilemme" UL/LI pour la sortie d'un tableau. Le dilemme est que chaque élément ne sait pas si des enfants suivront ou non ou combien d'éléments précédents doivent être fermés. Dans une autre réponse, j'ai déjà résolu ce problème en utilisant une fonction RecursiveIteratorIterator et à la recherche de getDepth() et d'autres méta-informations que mes propres écrits Iterator fourni : Obtenir un modèle d'ensemble imbriqué dans un <ul> mais en cachant les sous-arbres "fermés". . Ce réponse montre aussi qu'avec les itérateurs, on est assez souple.
Cependant, il s'agissait d'une liste pré-triée, qui ne conviendrait pas à votre exemple. De plus, j'ai toujours voulu résoudre ce problème pour une sorte de structure arborescente standard et pour le langage HTML. <ul> y <li> éléments.
Le concept de base auquel j'ai abouti est le suivant :
-
TreeNode - Abstraite chaque élément dans un simple TreeNode qui peut fournir sa valeur (par ex. Name ) et s'il a ou non des enfants.
-
TreeNodesIterator - A RecursiveIterator qui est capable d'itérer sur un ensemble (tableau) de ces éléments. TreeNodes . C'est assez simple puisque le TreeNode sait déjà s'il a des enfants et lesquels.
-
RecursiveListIterator - A RecursiveIteratorIterator qui a tous les événements nécessaires lorsqu'il itère récursivement sur n'importe quel type de RecursiveIterator :
-
beginIteration / endIteration - Début et fin de la liste principale.
-
beginElement / endElement - Début et fin de chaque élément.
-
beginChildren / endChildren - Début et fin de chaque liste d'enfants. Ce site RecursiveListIterator ne fournit ces événements que sous la forme d'appels de fonction. les listes d'enfants, comme il est typique pour les <ul><li> sont ouverts et fermés à l'intérieur de son parent. <li> élément. Par conséquent, le endElement est déclenché après que l'événement endChildren événement. Cela pourrait être modifié ou rendu configurable pour élargir l'utilisation de cette classe. Les événements sont distribués comme des appels de fonction à un objet décorateur alors, pour garder les choses séparées.
-
ListDecorator - Une classe "décorateur" qui est juste un récepteur des événements de RecursiveListIterator .
Je commence par la logique de sortie principale. Prenant le maintenant hiérarchique $tree le code final ressemble à ce qui suit :
$root = new TreeNode($tree);
$it = new TreeNodesIterator(array($root));
$rit = new RecursiveListIterator($it);
$decor = new ListDecorator($rit);
$rit->addDecorator($decor);
foreach($rit as $item)
{
$inset = $decor->inset(1);
printf("%s%s\n", $inset, $item->getName());
}
Examinons d'abord le ListDecorator qui ne fait qu'envelopper le <ul> y <li> et décide de la manière dont la structure de la liste est éditée :
class ListDecorator
{
private $iterator;
public function __construct(RecursiveListIterator $iterator)
{
$this->iterator = $iterator;
}
public function inset($add = 0)
{
return str_repeat(' ', $this->iterator->getDepth()*2+$add);
}
Le constructeur prend l'itérateur de liste sur lequel il travaille. inset est juste une fonction d'aide pour une bonne indentation de la sortie. Les autres sont juste les fonctions de sortie pour chaque événement :
public function beginElement()
{
printf("%s<li>\n", $this->inset());
}
public function endElement()
{
printf("%s</li>\n", $this->inset());
}
public function beginChildren()
{
printf("%s<ul>\n", $this->inset(-1));
}
public function endChildren()
{
printf("%s</ul>\n", $this->inset(-1));
}
public function beginIteration()
{
printf("%s<ul>\n", $this->inset());
}
public function endIteration()
{
printf("%s</ul>\n", $this->inset());
}
}
Avec ces fonctions de sortie à l'esprit, voici à nouveau la boucle principale de sortie, que je parcours étape par étape :
$root = new TreeNode($tree);
Créer la racine TreeNode qui sera utilisé pour commencer l'itération :
$it = new TreeNodesIterator(array($root));
Ce site TreeNodesIterator est un RecursiveIterator qui permet une itération récursive sur l'unique $root nœud. Il est passé sous la forme d'un tableau parce que cette classe a besoin de quelque chose sur lequel itérer et permet la réutilisation avec un ensemble d'enfants qui est également un tableau de TreeNode éléments.
$rit = new RecursiveListIterator($it);
Ce site RecursiveListIterator est un RecursiveIteratorIterator qui fournit les dits événements. Pour l'utiliser, il suffit d'un ListDecorator doit être fournie (la classe ci-dessus) et affectée à l'aide de addDecorator :
$decor = new ListDecorator($rit);
$rit->addDecorator($decor);
Ensuite, tout est mis en place pour juste foreach sur elle et sortir chaque nœud :
foreach($rit as $item)
{
$inset = $decor->inset(1);
printf("%s%s\n", $inset, $item->getName());
}
Comme le montre cet exemple, toute la logique de sortie est encapsulée dans l'élément ListDecorator et cette unique foreach . L'ensemble de la traversée récursive a été entièrement encapsulée dans des itérateurs récursifs SPL qui fournissent une procédure empilée, ce qui signifie qu'en interne, aucun appel de fonction récursive n'est effectué.
L'événement basé sur ListDecorator vous permet de modifier la sortie de manière spécifique et de fournir plusieurs types de listes pour la même structure de données. Il est même possible de modifier l'entrée, car les données du tableau ont été encapsulées dans des fichiers TreeNode .
L'exemple de code complet :
<?php
namespace My;
$tree = array('H' => 'G', 'F' => 'G', 'G' => 'D', 'E' => 'D', 'A' => 'E', 'B' => 'C', 'C' => 'E', 'D' => null);
// add children to parents
$flat = array(); # temporary array
foreach ($tree as $name => $parent)
{
$flat[$name]['name'] = $name; # self
if (NULL === $parent)
{
# no parent, is root element, assign it to $tree
$tree = &$flat[$name];
}
else
{
# has parent, add self as child
$flat[$parent]['children'][] = &$flat[$name];
}
}
unset($flat);
class TreeNode
{
protected $data;
public function __construct(array $element)
{
if (!isset($element['name']))
throw new InvalidArgumentException('Element has no name.');
if (isset($element['children']) && !is_array($element['children']))
throw new InvalidArgumentException('Element has invalid children.');
$this->data = $element;
}
public function getName()
{
return $this->data['name'];
}
public function hasChildren()
{
return isset($this->data['children']) && count($this->data['children']);
}
/**
* @return array of child TreeNode elements
*/
public function getChildren()
{
$children = $this->hasChildren() ? $this->data['children'] : array();
$class = get_called_class();
foreach($children as &$element)
{
$element = new $class($element);
}
unset($element);
return $children;
}
}
class TreeNodesIterator implements \RecursiveIterator
{
private $nodes;
public function __construct(array $nodes)
{
$this->nodes = new \ArrayIterator($nodes);
}
public function getInnerIterator()
{
return $this->nodes;
}
public function getChildren()
{
return new TreeNodesIterator($this->nodes->current()->getChildren());
}
public function hasChildren()
{
return $this->nodes->current()->hasChildren();
}
public function rewind()
{
$this->nodes->rewind();
}
public function valid()
{
return $this->nodes->valid();
}
public function current()
{
return $this->nodes->current();
}
public function key()
{
return $this->nodes->key();
}
public function next()
{
return $this->nodes->next();
}
}
class RecursiveListIterator extends \RecursiveIteratorIterator
{
private $elements;
/**
* @var ListDecorator
*/
private $decorator;
public function addDecorator(ListDecorator $decorator)
{
$this->decorator = $decorator;
}
public function __construct($iterator, $mode = \RecursiveIteratorIterator::SELF_FIRST, $flags = 0)
{
parent::__construct($iterator, $mode, $flags);
}
private function event($name)
{
// event debug code: printf("--- %'.-20s --- (Depth: %d, Element: %d)\n", $name, $this->getDepth(), @$this->elements[$this->getDepth()]);
$callback = array($this->decorator, $name);
is_callable($callback) && call_user_func($callback);
}
public function beginElement()
{
$this->event('beginElement');
}
public function beginChildren()
{
$this->event('beginChildren');
}
public function endChildren()
{
$this->testEndElement();
$this->event('endChildren');
}
private function testEndElement($depthOffset = 0)
{
$depth = $this->getDepth() + $depthOffset;
isset($this->elements[$depth]) || $this->elements[$depth] = 0;
$this->elements[$depth] && $this->event('endElement');
}
public function nextElement()
{
$this->testEndElement();
$this->event('{nextElement}');
$this->event('beginElement');
$this->elements[$this->getDepth()] = 1;
}
public function beginIteration()
{
$this->event('beginIteration');
}
public function endIteration()
{
$this->testEndElement();
$this->event('endIteration');
}
}
class ListDecorator
{
private $iterator;
public function __construct(RecursiveListIterator $iterator)
{
$this->iterator = $iterator;
}
public function inset($add = 0)
{
return str_repeat(' ', $this->iterator->getDepth()*2+$add);
}
public function beginElement()
{
printf("%s<li>\n", $this->inset(1));
}
public function endElement()
{
printf("%s</li>\n", $this->inset(1));
}
public function beginChildren()
{
printf("%s<ul>\n", $this->inset());
}
public function endChildren()
{
printf("%s</ul>\n", $this->inset());
}
public function beginIteration()
{
printf("%s<ul>\n", $this->inset());
}
public function endIteration()
{
printf("%s</ul>\n", $this->inset());
}
}
$root = new TreeNode($tree);
$it = new TreeNodesIterator(array($root));
$rit = new RecursiveListIterator($it);
$decor = new ListDecorator($rit);
$rit->addDecorator($decor);
foreach($rit as $item)
{
$inset = $decor->inset(2);
printf("%s%s\n", $inset, $item->getName());
}
Outpupt :
<ul>
<li>
D
<ul>
<li>
G
<ul>
<li>
H
</li>
<li>
F
</li>
</ul>
</li>
<li>
E
<ul>
</li>
<li>
A
</li>
<li>
C
<ul>
<li>
B
</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
Démonstration (variante PHP 5.2)
Une variante possible serait un itérateur qui itère sur n'importe quel RecursiveIterator et fournit une itération sur tous les événements qui peuvent se produire. Un switch / case à l'intérieur de la boucle foreach pourrait alors traiter les événements.
En rapport :
