[RESOLVED] nested <ul> list recursive

[Reiners]

Hello all!
I want to display a <ul> list with PHP recursive with the following properties.
Lets say I have an array with these numbers:

$output = array(1, 2, 3, 2, 3);

Now I have created a recursive function so far to display them kind of nested:

function print_output($output)
{
	echo "<UL><LI>";
		echo $output[0];
		array_shift($output);

	if(!empty($output[0]))
		print_output($output);

echo "</UL>";
}

The function displays my numbers in the array like this:

1
	2
		3
			2
				3

Now the point where I need your help is to modify my function to display these numbers like the following:

1
	2
		3
	2
		3

Here is the HTML Code that should be created:

<UL>
<LI>1	<UL>
	<LI>2		<UL>
			<LI>3
			</UL>
	</UL>
	<UL>
	<LI>2		<UL>
			<LI>3
			</UL>
	</UL>
</UL>

So I need to check if the next number is smaller than the first and kind of abort the recursion and restart it at this point again, or something like this. But I couldn't figure out any working solution 🙁

Thanks for any hints!
greetings,
Reiners

[laserlight]

It sounds like you want to create a tree and print it depth first. The question then, is what kind of tree you want to create.

The example you gave is pretty simple: 1 2 3 2 3 becomes the tree:

   1
 2   2
3   3

Suppose we have: 1 2 3 2 3 3
Does this become the tree:

   1
 2   2
3   3 3

or perhaps:

   1
 2   2
3   3
   3

Basically, you need to be very clear on how to construct the tree. According to your rules: "if the next number is smaller than the first and kind of abort the recursion and restart it at this point again", your original example should result in the "tree":

1 2 3 2 3

Which in turn would be printed as:

1
2
3
2
3

... since none of the subsequent numbers are less than the first.

[Reiners]

thanks for your reply, laserlight. Your point with the tree is quite interesting. Your first tree is what I need I guess, but the numbers in the array are mostly not the same.
What I'm actually doing is scanning PHP Code for function calls and then tracing their variables.
example:

1 $var1 = "test";
2 $var2 = "the ".$var1;
3 $var3 = exec($var2);

will output where it found the function and the traced variables:

found function exec() [3]: $var3 = exec($var2);
				2 $var2 = "the ".$var1;
					1 $var1 = "test";

if we have the following PHP code to scan:

1 $var1 = "test";
2 $var2 = "the";
3 $var3 = $var1 . $var2;
4 $var4 = "code";
5 $var5 = exec($var3 . $var4);

I would like to have:

found function exec(): 5 $var5 = exec($var3 . $var4);
				3 $var3 = $var1 . $var2;
					2 $var2 = "test";
					1 $var1 = "test"; (hard to accomplish I think)
				4 $var4 = "code";

I now that I probably cant always have a correct tree with line numbers only, but since the parameter tracing is recursive too, I dont know if it makes more sense to add the HTML code there.

I hope this is not too confusing, if so, please stick to the first example with the numbers, but consider that these are line numbers and I dont care if the tree is not always 100% correct if there are line numbers equally in some cases.

[laserlight]

I found this interesting, so I decided to come up with an example:

<?php
class MultiwayTreeNode {
    private $value;
    private $children;

function __construct($value = null) {
    $this->value = $value;
    $this->children = array();
}

function getValue() {
    return $this->value;
}

function setValue($value) {
    $this->value = $value;
}

function addChild(MultiwayTreeNode $child) {
    $this->children[] = $child;
}

function getChild($index) {
    return $this->children[$index];
}

function getChildren() {
    return $this->children;
}

function removeChild(MultiwayTreeNode $child) {
    if (($key = array_search($child, $this->children)) !== false) {
        unset($this->children[$key]);
        $this->children = array_values($this->children);
    } else {
        throw new InvalidChildException("Could not remove non-existent child.");
    }
}
}

class InvalidChildException extends Exception {
    public function __construct($message = null, $code = 0) {
        parent::__construct($message, $code);
    }
}

function depthFirstTraverse(MultiwayTreeNode $tree, $visit, $unvisit = null) {
    $visit($tree->getValue());

foreach ($tree->getChildren() as $child) {
    depthFirstTraverse($child, $visit, $unvisit);
}

if ($unvisit !== null) {
    $unvisit($tree->getValue());
}
}

function startList($value) {
    echo '<ul><li>' . $value;
}

function endList($value) {
    echo "</li></ul>\n";
}

$symbols = array();
$symbols['$var1'] = new MultiwayTreeNode('1 $var1 = "test";'); // Found $var1
$symbols['$var2'] = new MultiwayTreeNode('2 $var2 = "the";');   // Found $var2
// Found $var3, but it uses $var1 and $var2
$symbols['$var3'] = new MultiwayTreeNode('3 $var3 = $var1 . $var2;');
$symbols['$var3']->addChild($symbols['$var1']);
$symbols['$var3']->addChild($symbols['$var2']);
$symbols['$var4'] = new MultiwayTreeNode('4 $var4 = "code";'); // Found $var4
// Found exec, and it uses $var3 and its return value is assigned to $var5
$symbols['exec'] = new MultiwayTreeNode('5 $var5 = exec($var3);');
$symbols['exec']->addChild($symbols['$var3']);
$symbols['$var5'] = new MultiwayTreeNode('5 $var5 = exec($var3);');
$symbols['$var5']->addChild($symbols['exec']);

echo 'found function exec():';
depthFirstTraverse($symbols['exec'], 'startList', 'endList');
?>

The output differs from your sample output because, in my opinion, $var4 has nothing to do with exec().

[Reiners]

oh, I forgot to change the PHP code (now edited).
I will look at your code, looks very promising.
thank you very much for your time and help so far !

[Reiners]

it works fantastic, thank you very much again. I totally forgot about using objects 😉

[laserlight]

it works fantastic, thank you very much again.

You're welcome, I am quite proud of it, actually 🙂

Just a word of warning though: whenever you detect assignment to a variable, create a new MultiwayTreeNode to assign to that variable's entry in the symbol table. If you use setValue() instead, you would end up changing the references to that variable that have already been recorded elsewhere.

For example:

$symbols = array();
// $var1 = "test";
$symbols['$var1'] = new MultiwayTreeNode('1 $var1 = "test";');
// $var2 = "the";
$symbols['$var2'] = new MultiwayTreeNode('2 $var2 = "the";');
// $var3 = $var1 . $var2;
$symbols['$var3'] = new MultiwayTreeNode('3 $var3 = $var1 . $var2;');
$symbols['$var3']->addChild($symbols['$var1']);
$symbols['$var3']->addChild($symbols['$var2']);
// $var4 = "code";
$symbols['$var4'] = new MultiwayTreeNode('4 $var4 = "code";');
// $var1 = $var4;
$symbols['$var1']->setValue('5 $var1 = $var4;');
// $var5 = exec($var3);
$symbols['exec'] = new MultiwayTreeNode('6 $var5 = exec($var3);');
$symbols['exec']->addChild($symbols['$var3']);
$symbols['$var5'] = new MultiwayTreeNode('6 $var5 = exec($var3);');
$symbols['$var5']->addChild($symbols['exec']);

echo 'found function exec():';
depthFirstTraverse($symbols['exec'], 'startList', 'endList');

The correct version will have:

$symbols['$var1'] = new MultiwayTreeNode('5 $var1 = $var4;');

instead of:

$symbols['$var1']->setValue('5 $var1 = $var4;');