У вас уже есть отсортированный список деревьев.Каждая следующая строка является либо дочерней по отношению к предыдущей строке, либо родным братом.Таким образом, вы можете обработать список, получить имя элемента, получить уровень, на котором находится элемент, с помощью отступа и создать элемент из него.
1 Line <=> 1 Element (level, name)
Таким образом, каждый элемент имеет имя и ноль.или больше детей.Из входных данных также можно сказать, к какому уровню он принадлежит.
Элемент может быть представлен в виде массива, в котором его первое значение является именем, а второе значение является массивом для дочерних элементов.
Поскольку список отсортирован, мы можем использовать простую карту, которая для каждого уровня является псевдонимом для детей определенного уровня.Таким образом, с уровнем, который имеет каждый элемент, мы можем добавить его в стек:
$self = array($element, array());
$stack[$level][] = &$self;
$stack[$level + 1] = &$self[1];
Как показывает этот пример кода, стек / карта для текущего уровня получает $self как добавленные дочерние элементы:
$stack[$level][] = &$self;
Стек для первого уровня, получить ссылку на потомков $self (index 1):
$stack[$level + 1] = &$self[1];
Итак, теперь для каждой строки нам нужнонайти уровень.Как показывает этот стек, уровень последовательно нумеруется: 0, 1, 2, ..., но во входных данных это просто количество пробелов.
Маленький вспомогательный объект может выполнять работу по сбору / группировке количества символов в строкек уровням, следя за тем, чтобы - если уровень еще не существует для отступа - он добавляется, но только если он выше.
Это решает проблему, заключающуюся в том, что в ваших входных данных нет отношения 1: 1 междуразмер отступа и его индекс.По крайней мере, не очевидный.
Этот вспомогательный объект является образцовым именем Levels и реализует __invoke, чтобы обеспечить уровень для отступа при прозрачном добавлении нового уровня при необходимости:
$levels = new Levels();
echo $levels(''); # 0
echo $levels(' '); # 1
echo $levels(' '); # 1
echo $levels(' '); # 2
echo $levels(' '); # Throws Exception, this is smaller than the highest one
Так что теперь мы можем превратить отступ в уровень.Этот уровень позволяет нам запускать стек.Стек позволяет строить дерево.Fine.
Строковый разбор можно легко выполнить с помощью регулярного выражения.Поскольку я ленивый, я просто использую preg_match_all и возвращаю - в каждой строке - отступ и имя.Поскольку я хочу иметь больше комфорта, я заключаю его в функцию, которая всегда возвращает мне массив, поэтому я могу использовать его в итераторе:
$matches = function($string, $pattern)
{
return preg_match_all($pattern, $string, $matches, PREG_SET_ORDER)
? $matches : array();
};
Использование при вводе с шаблоном, подобным
/^(?:(\s*)=> )?(.*)$/m
даст мне массив для каждой строки, то есть:
array(whole_line, indent, name)
Вы видите образец здесь?Это близко к
1 Line <=> 1 Element (level, name)
С помощью объекта Levels это может быть отображено, поэтому просто вызов функции отображения:
function (array $match) use ($levels) {
list(, $indent, $name) = $match;
$level = $levels($indent);
return array($level, $name);
};
От array(line, indent, name) до array(level, name).Чтобы сделать это доступным, его возвращает другая функция, в которую можно ввести Levels:
$map = function(Levels $levels) {
return function ...
};
$map = $map(new Levels());
Итак, все для чтения со всех строк.Тем не менее, это должно быть помещено в дерево.Запоминание добавления в стек:
function($level, $element) use (&$stack) {
$self = array($element, array());
$stack[$level][] = &$self;
$stack[$level + 1] = &$self[1];
};
($element - это имя здесь).Для этого фактически нужен стек, а стек - это дерево.Итак, давайте создадим другую функцию, которая возвращает эту функцию и позволяет помещать каждую строку в стек для построения дерева:
$tree = array();
$stack = function(array &$tree) {
$stack[] = &$tree;
return function($level, $element) use (&$stack) {
$self = array($element, array());
$stack[$level][] = &$self;
$stack[$level + 1] = &$self[1];
};
};
$push = $stack($tree);
Итак, последнее, что нужно сделать, это просто обработать один элемент за другим:
foreach ($matches($input, '/^(?:(\s*)=> )?(.*)$/m') as $match) {
list($level, $element) = $map($match);
$push($level, $element);
}
Итак, теперь с учетом $input создается массив с только (корневыми) дочерними узлами на первом уровне, а затем array с двумя записями на каждый узел:
array(name, children)
Здесь имя - строка, потомки - массив.Так что это уже сделал список для массива / дерева здесь технически.Но это довольно обременительно, потому что вы хотите иметь возможность выводить и древовидную структуру.Вы можете сделать это путем выполнения рекурсивных вызовов функций или путем реализации рекурсивного итератора.
Позвольте мне привести рекурсивный итератор Пример:
class TreeIterator extends ArrayIterator implements RecursiveIterator
{
private $current;
public function __construct($node)
{
parent::__construct($node);
}
public function current()
{
$this->current = parent::current();
return $this->current[0];
}
public function hasChildren()
{
return !empty($this->current[1]);
}
public function getChildren()
{
return new self($this->current[1]);
}
}
Это просто итератор массива (как и все узлыявляются массивом, а также все дочерние узлы) и для текущего узла он возвращает имя.Если спросить детей, он проверяет, есть ли они, и снова предлагает их как TreeIterator.Это упрощает использование, например, вывод в виде текста:
$treeIterator = new RecursiveTreeIterator(
new TreeIterator($tree));
foreach ($treeIterator as $val) echo $val, "\n";
Вывод:
\-cat, true cat
|-domestic cat, house cat, Felis domesticus, Felis catus
| |-kitty, kitty-cat, puss
| |-mouser
| |-alley cat
| |-tom, tomcat
| | \-gib
| |-Angora, Angora cat
| \-Siamese cat, Siamese
| \-blue point Siamese
\-wildcat
|-sand cat
|-European wildcat, catamountain, Felis silvestris
|-cougar, puma, catamount, mountain lion, painter, panther, Felis concolor
|-ocelot, panther cat, Felis pardalis
|-manul, Pallas's cat, Felis manul
\-lynx, catamount
|-common lynx, Lynx lynx
\-Canada lynx, Lynx canadensis
Если вы ищете дополнительные элементы управления выводом HTML в сочетании с рекурсивным итератором, см. Следующий вопрос, содержащий пример вывода HTML на основе <ul><li>:
Так как это выглядит все вместе? Код для просмотра сразу как гист на github .