У вас уже есть отсортированный список деревьев. Каждая следующая строка является либо дочерним элементом предыдущей строки, либо родным братом. Таким образом, вы можете обрабатывать список, получать имя элемента, получать уровень, в котором элемент находится под его отступом, и создать из него элемент.
1 Line <=> 1 Element (level, name)
Таким образом, каждый элемент имеет имя и ноль или более детей. Из ввода можно также сказать, на каком уровне он принадлежит.
Элемент может быть представлен как массив, в котором первым значением является имя, а второе значение - это массив для детей.
Поскольку список отсортирован, мы можем использовать простую карту, которая на уровне является псевдонимом для детей определенного уровня. Таким образом, с уровнем каждый элемент имеет, мы можем добавить его в стек:
$self = array($element, array());
$stack[$level][] = &$self;
$stack[$level + 1] = &$self[1];
Как этот код-пример показывает, стек/карты для текущего уровня становится $self
, как дети добавлены:
$stack[$level][] = &$self;
стек для уровня одного выше, получить это обращение к детям $self
(индекс 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
Итак, теперь мы можем превратить отступы в уровне. Этот уровень позволяет нам запускать стек. Стек позволяет построить дерево. Хорошо.
Разбор строки за строкой может быть легко выполнен с регулярным выражением. Поскольку я ленив, я просто использую preg_match_all
, а return - за строку - отступы и имя.Потому что я хочу, чтобы иметь больше комфорта, я оберните его в функцию, которая делает всегда возвращает мне массив, так что я могу использовать его в качестве итератора:
$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 в сочетании с рекурсивным итератором, пожалуйста, см следующего вопроса, который имеет пример <ul><li>
на основе HTML выход:
Итак, как это выглядит как все вместе? Код для просмотра сразу a gist on github.
У этого есть \ r \ n для новых строк atleast или plaint text single line –
это точно так же, как вставлено в вопрос – dogmatic69
Похожее: [Отметьте список для многомерного массива] (http://stackoverflow.com/questions/8881037/отступ-лист к многомерному массиву) – hakre