» Convert anything to Tree Structures in PHP

3 Tree Manipulation

PHP Recursive functions

Yep, that's a tree alright.In real life I do not consider myself to be a tree-hugger, but as a developer: tree data structures and recursive technology totally get me going ;) Seriously though, they are very powerful ways to solve problems and often lead to elegant & reusable solutions.

In this series I am going to share a couple of functions and ways of approaching recursive problems in PHP.

I recently faced a programming challenge that almost broke my brain. I needed to create a function that could explode any single-dimensional array into a full blown tree structure, based on the delimiters found in it's keys. Tricky part was size of the tree could be infinite. I called the function: explodeTree. And maybe it's best to first look at an example.

The Directory Example

Here I will give an example what the explodeTree function could be used for. Let's say we need a recursive directory listing of /etc/php5, and for that we execute:

if(exec("find /etc/php5", $files)){
    // the $files array now holds the path as it's values,
    // but we also want the paths as keys:
    $key_files = array_combine(array_values($files), array_values($files));
 
    // show the array
    print_r($key_files);
}

Which will return something like:

Array
(
    [/etc/php5] => /etc/php5
    [/etc/php5/cli] => /etc/php5/cli
    [/etc/php5/cli/conf.d] => /etc/php5/cli/conf.d
    [/etc/php5/cli/php.ini] => /etc/php5/cli/php.ini
    [/etc/php5/conf.d] => /etc/php5/conf.d
    [/etc/php5/conf.d/mysqli.ini] => /etc/php5/conf.d/mysqli.ini
    [/etc/php5/conf.d/curl.ini] => /etc/php5/conf.d/curl.ini
    [/etc/php5/conf.d/snmp.ini] => /etc/php5/conf.d/snmp.ini
    [/etc/php5/conf.d/gd.ini] => /etc/php5/conf.d/gd.ini
    [/etc/php5/apache2] => /etc/php5/apache2
    [/etc/php5/apache2/conf.d] => /etc/php5/apache2/conf.d
    [/etc/php5/apache2/php.ini] => /etc/php5/apache2/php.ini
)

Now if we want to transform this list into a tree structure with each directory as a nested node, a child of another directory, all we would have to do is run:

// let '/' be our delimiter
$tree = explodeTree($key_files, "/");
// show the array
print_r($tree);

And that single command would give the totally awesome:

Array
(
    [etc] => Array
        (
            [php5] => Array
                (
                    [cli] => Array
                        (
                            [conf.d] => /etc/php5/cli/conf.d
                            [php.ini] => /etc/php5/cli/php.ini
                        )
 
                    [conf.d] => Array
                        (
                            [mysqli.ini] => /etc/php5/conf.d/mysqli.ini
                            [curl.ini] => /etc/php5/conf.d/curl.ini
                            [snmp.ini] => /etc/php5/conf.d/snmp.ini
                            [gd.ini] => /etc/php5/conf.d/gd.ini
                        )
 
                    [apache2] => Array
                        (
                            [conf.d] => /etc/php5/apache2/conf.d
                            [php.ini] => /etc/php5/apache2/php.ini
                        )
 
                )
 
        )
 
)

Wow! So this would make it very easy to visually layout a tree structure of the directory /etc/php5. But remember this is just an example. The function now explodes on the '/' character, but you can use any delimiter to explode a single-dimensional array into a Tree. So how does this explodeTree function work?

The Function: explodeTree()

The key to my original approach was not to use static PHP code, but to generate PHP code, and to later execute it using the eval() function. Though it did the job  and posed an fresh approach to the problem, I wouldn't be surprised if someone told me that the piece of code secretly spawned gateways to hell ;)

My blog visitors agreed on the evil part and came with other neat approaches. Now thanks to Lachlan Donald and Takkie, here's the new explodeTree() function.

<?php
/**
 * Explode any single-dimensional array into a full blown tree structure,
 * based on the delimiters found in it's keys.
 *
 * @author  Kevin van Zonneveld <kevin@vanzonneveld.net>
 * @author  Lachlan Donald
 * @author  Takkie
 * @copyright 2008 Kevin van Zonneveld (http://kevin.vanzonneveld.net)
 * @license   http://www.opensource.org/licenses/bsd-license.php New BSD Licence
 * @version   SVN: Release: $Id: explodeTree.inc.php 89 2008-09-05 20:52:48Z kevin $
 * @link    http://kevin.vanzonneveld.net/
 *
 * @param array   $array
 * @param string  $delimiter
 * @param boolean $baseval
 *
 * @return array
 */
function explodeTree($array, $delimiter = '_', $baseval = false)
{
  if(!is_array($array)) return false;
  $splitRE   = '/' . preg_quote($delimiter, '/') . '/';
  $returnArr = array();
  foreach ($array as $key => $val) {
    // Get parent parts and the current leaf
    $parts  = preg_split($splitRE, $key, -1, PREG_SPLIT_NO_EMPTY);
    $leafPart = array_pop($parts);
 
    // Build parent structure
    // Might be slow for really deep and large structures
    $parentArr = &$returnArr;
    foreach ($parts as $part) {
      if (!isset($parentArr[$part])) {
        $parentArr[$part] = array();
      } elseif (!is_array($parentArr[$part])) {
        if ($baseval) {
          $parentArr[$part] = array('__base_val' => $parentArr[$part]);
        } else {
          $parentArr[$part] = array();
        }
      }
      $parentArr = &$parentArr[$part];
    }
 
    // Add the final part to the structure
    if (empty($parentArr[$leafPart])) {
      $parentArr[$leafPart] = $val;
    } elseif ($baseval && is_array($parentArr[$leafPart])) {
      $parentArr[$leafPart]['__base_val'] = $val;
    }
  }
  return $returnArr;
}

The first to arguments of explodeTree() are clear I guess. But what about that 3rd parameter: $baseval?

The baseval argument

In the first example you see that only leafs (the bottom nodes that don't have any children) maintain their original values (the filepaths in this case). If you want higher nodes (parents) to also maintain their values, you'll have to tell explodeTree to do so like this:

// now the 3rd argument, the baseval, is true
$tree = explodeTree($key_files, "/", true);

And then explodeTree will preserve the node's original value in the __base_val items. Like this:

Array
(
    [etc] => Array
        (
            [__base_val] => 
            [php5] => Array
                (
                    [__base_val] => /etc/php5
                    [cli] => Array
                        (
                            [__base_val] => /etc/php5/cli
                            [conf.d] => /etc/php5/cli/conf.d
                            [php.ini] => /etc/php5/cli/php.ini
                        )
 
                    [conf.d] => Array
                        (
                            [__base_val] => /etc/php5/conf.d
                            [mysqli.ini] => /etc/php5/conf.d/mysqli.ini
                            [curl.ini] => /etc/php5/conf.d/curl.ini
                            [snmp.ini] => /etc/php5/conf.d/snmp.ini
                            [gd.ini] => /etc/php5/conf.d/gd.ini
                        )
 
                    [apache2] => Array
                        (
                            [__base_val] => /etc/php5/apache2
                            [conf.d] => /etc/php5/apache2/conf.d
                            [php.ini] => /etc/php5/apache2/php.ini
                        )
 
                )
 
        )
 
)

See what happens? Baseval creates a placeholder. A semi-node for the original value of it's parent. The value: '/etc/php5' is now saved, without baseval this value would be lost because there was no place to store it in. Now that might come in handy!

So you've got a tree. Now what?

Trees with unlimited levels of nodes require recursive functions that can traverse the entire structure. Recursive functions are functions that call themselves every time they find more items to process. Here's one to layout the directories:

function plotTree($arr, $indent=0, $mother_run=true){
    if($mother_run){
        // the beginning of plotTree. We're at rootlevel
        echo "startn";
    }
 
    foreach($arr as $k=>$v){
        // skip the baseval thingy. Not a real node.
        if($k == "__base_val") continue;
        // determine the real value of this node.
        $show_val = ( is_array($v) ? $v["__base_val"] : $v );
 
        // show the indents
        echo str_repeat("  ", $indent);
        if($indent == 0){
            // this is a root node. no parents
            echo "O ";
        } elseif(is_array($v)){
            // this is a normal node. parents and children
            echo "+ ";
        } else{
            // this is a leaf node. no children
            echo "- ";
        }
 
        // show the actual node
        echo $k . " (".$show_val.")"."n";
 
        if(is_array($v)){
            // this is what makes it recursive, rerun for childs
            plotTree($v, ($indent+1), false);
        }
    }
 
    if($mother_run){
        echo "endn";
    }
}

And this would output:

start
O etc ()
+ php5 (/etc/php5)
+ cli (/etc/php5/cli)
- conf.d (/etc/php5/cli/conf.d)
- php.ini (/etc/php5/cli/php.ini)
+ conf.d (/etc/php5/conf.d)
- mysqli.ini (/etc/php5/conf.d/mysqli.ini)
- curl.ini (/etc/php5/conf.d/curl.ini)
- snmp.ini (/etc/php5/conf.d/snmp.ini)
- gd.ini (/etc/php5/conf.d/gd.ini)
+ apache2 (/etc/php5/apache2)
- conf.d (/etc/php5/apache2/conf.d)
- php.ini (/etc/php5/apache2/php.ini)
end

If I overlooked a standard PHP function that can already do this, or you have other improvements/ideas leave a comment!

Thanks again: Lachlan Donald & Tokkie for insightful comments and great effort.

You probably shouldn't follow me


Like this Article?

I'd appreciate it if you leave a comment, spread the word, or consider a small donation


tags: php, programming, recursion, hierarchy, tree data structure, array, delimiter
category: Programming - PHP - Tree Manipulation
read: 117,837 times

Add comment

(required, shown)(required, not shown)for syntax highlighting

[CODE="Javascript"]
your_code_here();
[/CODE]

Replace "Javascript"
with "php", "text", etc.
code (to make sure you are not a spammer)

 Track replies: rss feed comments feed

Comments

#56. Eric Dostie on 18 January 2012

Gravatar.com: Eric DostieFound the problem.

When setting __base_val, we require the folders to be in the format "/etc/php5". This means if you use a "find ./ -type f" to populate your array __base_val will never be set. This could probably be fixed in the explodeTree code but in my case it's easier to just populate the array with more/better information.

#55. Eric Dostie on 18 January 2012

Gravatar.com: Eric DostieI hate to resurrect this article almost 3 years later, but it seems like the __base_val code does not work in your posted code. I've been trying to work through why that may be but I've come up with nothing. It simply never reaches the if-statement where we check if $baseval is set to true. I can prove that the $baseval is being passed to the function correctly but it seems to not be triggering if-statements further down in the code.

I'm sure I am missing something but I have very little experience with PHP's idiosyncrasies. In general code sense I feel the program should be working and I cannot understand why it is failing.

Any thoughts? I'd assume this code works with PHP5 since I'm running it under that, but could it have introduced quirks that might be causing my issue?

#54. Shibby - Web Development on 10 September 2011

Gravatar.com: Shibby - Web DevelopmentVery usefull one. i needed to do something similliar and almost shat my pants untill i saw this one.
Thanks m8

#53. Neven on 01 September 2011

Gravatar.com: NevenThis is what I'm loking for a 3 day and for some reason it dosen't work why??? this code dosen't work below... sou you see I'm using my ovn directorys path and I don't know why it dosen't work ...can you help :)

if(exec("store/555555", $files)){
// the $files array now holds the path as it's values,
// but we also want the paths as keys:
... [more] $key_files = array_combine(array_values($files), array_values($files));

// show the array
print_r($key_files);
}

#52. Richard on 08 August 2011

Gravatar.com: RichardThanks for posting the explodeTree function, very handy as well as avoiding the headaches of dealing with multi-dimensional arrays!

I've implemented a more compact (less versatile) version of explodeTree as part of a wider preorder tree traversal script that puts data into MySQL. I've tested it with the root of my drive (200K filenames) and the DMOZ category RDF (~700K category names), simply bumping up the memory limit does the trick ;o)

For reference my script is here http://www.innvo.com/c/PHP/1312794035-directory-tree-php-mysql ... credits to you are in the comments and a link to this page.

#51. Ina Ivanova on 30 July 2011

Gravatar.com: Ina IvanovaThank you so much, great code! :P

#50. Kevin on 19 April 2011

Twitter.com: kvz@ Hans: Si SeƱor : )

#49. Hans on 19 April 2011

Gravatar.com: HansVery good article.
Must be from Amsterdam ;-).

#48. Deepak on 05 March 2011

Gravatar.com: DeepakGreat Work boss,really helpful :)

#47. Martin on 17 January 2011

Gravatar.com: MartinGreat peace of code! Thank You!

#46. lariso on 29 November 2010

Gravatar.com: larisoThanks for this, saved me a lot of work! Very handy to turn an alphabetical list of URLs into a ol/ul sitemap tree

#45. Kevin on 08 September 2010

Twitter.com: kvz@ Karen: Looks like Dan is interested to help you out. If not, graphviz can be installed like this on Ubuntu:

aptitude install graphviz



then you need bindings for your programming language. For PHP:

pear install -f  Image_GraphViz


There are some examples online of how to call the class next.

#44. Dan on 25 August 2010

Gravatar.com: Dan@Karen: I'm getting pretty close at thebookofross.com (lamp platform). I'm dan at ross dash clan dot net.

#43. Karen on 13 August 2010

Gravatar.com: KarenHi,
I created my site with Drupal and did look at Graphviz a while back, but couldn't get it to install. I can try again. I have all the data and all my nodes connected, I just need an output report. I have tried views, but can't get lines/boxes etc. and can only display the parent and children, not the children of the children and the children of their children, etc. I am using Node Hierarchy. Node Hierarchy displays a really nice outline, but it is in the navigation window and I don't know how to put it on a page. It also lists every node in the database, not just the node associated with related nodes. I have asked for repeated request for help, offered money and no takers. If you change your mind, let me know.

#42. Kevin on 13 August 2010

Twitter.com: kvz@ Karen: Well I'm not for hire at the moment, but maybe you could have a look at Graphviz? They have a simple language that you can build such charts with.

#41. Karen on 13 August 2010

Gravatar.com: KarenI need a family tree/pedigree chart made from the hierarchial nodes I have on my site. Would you be able to help with that?

#40. Kevin on 10 June 2010

Twitter.com: kvz@ Django Developers: Thanks for sharing though!

@ Ringo: You'd have to pay me for such a thing ; ) Oh wait, already have a job, sorry

@ ali: Not making any sense to me?

#39. ali on 02 June 2010

Gravatar.com: alifunction my_debug($arr)
{
echo '<pre>';
print_r($arr);
echo '</pre>';
... [more] }
function xml2arr($file)
{

if(file_exists($file))
$handle=fopen($file,'r');
else
print "file does not exists";
$xml = fread($handle, filesize($file));
fclose($handle);

$xml = new SimpleXMLElement($xml);
//my_debug($xml);
return $xml;
}
$file='Test_reo_precision_nonprime_req_20100525113003_01.xml';
$arr=xml2arr($file);
my_debug($arr);

#38. Ringo on 22 May 2010

Gravatar.com: RingoKevin,
the script that you have provided is awesome! I did get stuck a bit though and wonder if you can give me an idea of how to proceed. In essence, I have 2 arrays as per below where the array_values of array1 are key for array2. I need to break it down on categories and subcategories as well as sum up and roll the totals from array2 leaf categories into parent categories. The output that I am trying to get would look similar to:

o FX (sum of all the previous levels: FX)
+ FX (sum of all of the previous levels: EBSS & HT)
... [more] - EBSS (sum of all the corresponding leaf nodes from array2)
- HT (sum of all the corresponding leaf nodes from array2)
o IR (sum of BOND & FUT levels)
+ BOND (sum of all the corresponding levels: BTest & CME)
+ FUT (sum of all the corresponding levels: BTest & CME)
- BTest (sum of all the corresponding leaf nodes from array2)
- CME (sum of all the corresponding leaf nodes from array2)


Array
(
[0] => FX###FX###EBSS
[1] => FX###FX###EBSS
[2] => FX###FX###HT
[3] => FX###FX###HT
[4] => IR###BOND###BTest
[5] => IR###FUT###CME
[6] => IR###BOND###BTest
[7] => IR###FUT###CME
[8] => IR###BOND###BTest
[9] => IR###FUT###CME
[10] => IR###FUT###CME
[11] => IR###FUT###CME
[12] => IR###FUT###CME
)
Array
(
[0] => 0|3|6|530240000|-0|-0|-0|-0|0|0|
[1] => 0|3|6|8116100|-24.3483|-60.87075|-0|-0|-300|-385.21905|
[2] => 1|4|7|9468090|-28.40427|-47.34045|-0|-0|-1351670|-1351745.74472|
[3] => 0|3|6|6119940|-18|-30|-0|-0|0|-48|
[4] => -1|2|5|4889062.5|-0|-0|-10|-0|977500|977490|
[5] => 0|47|94|10926281.32|-5.64|-23.5|-7.52|-0|31.24|-5.42000000001|
[6] => 0|4|8|7867656.25|-0|-0|-16|-0|-156.25|-172.25|
[7] => 0|3|6|696375|-0.36|-1.5|-0.48|-0|0|-2.34|
[8] => 0|2|4|3893281.25|-0|-0|-8|-0|-468.75|-476.75|
[9] => 4|5|6|695812.5|-0.36|-1.5|-0.48|-0|-463750|-463752.34|
[10] => 3|17|31|3609250.13|-1.86|-7.75|-2.48|-0|-348625.01|-348637.1|
[11] => -3|0|3|348218.75|-0.18|-0.75|-0.24|-0|348218.75|348217.58|
[12] => -4|0|4|465453.14|-0.24|-1|-0.32|-0|465453.14|465451.58|
)

#37. Django Developers on 10 May 2010

Gravatar.com: Django DevelopersThis is a nice article, I found a similar one at a Django website. but it wasn't about PHP. It was about Django which is for Python. Python is good too, but Django takes a bit more learning than Python.

http://www.nuovolabs.com was the website but I can't find the actual URL to the article now.

#36. Kevin on 14 March 2010

Twitter.com: kvz@ Alex: Hey, could you provide a code sample of what you are trying to do? That would help a lot. thx

#35. Alex on 28 February 2010

Gravatar.com: AlexThanks Kevin, this is great and almost what I've been looking for! :)

I'm having a hard time trying to add nodes to a children array inside the parent instead of adding then directly.

If you wouldn't mind I could really use the help! Thanks! :)
... [more]
Alex

#34. Kevin on 28 February 2010

Twitter.com: kvz@ Tang: Haven't used it with jQuery Treeview yet, but I'm sure some people will find your info useful. Thanks!

#33. Tang on 27 February 2010

Gravatar.com: TangThis is a good source of solution.. It is exactly what I am looking for to expand a treeview... Thanks Kevin ..

Also I've used Ash Ketchum on 27 July 2009 codes to combine it with the jQuery Treeview ..Big thanks to Ash that save huge amount of my time ... :-)

Not sure if some of you came accross a problem in IE6 when implementing the codes with the jQuery treeview.(It works fine with Firefox and Opera). The expanded list become transparent (or disappear) when expanded.. If you do, try remove the html comment tags (example : <!--subfolder-->) in the codes.. I removed it and solved the disssapearing list in IE6...
... [more]
Kevin and Ash save me lots of time (big thanks to you guys), so I hope my finding could help someone else save their time as well..

#32. Kevin on 04 September 2009

Twitter.com: kvz@ Shubhadeep: That's way to much credit : )

#31. Shubhadeep on 31 August 2009

Gravatar.com: ShubhadeepYou are a GOD to me :)

#30. Kevin on 28 July 2009

Twitter.com: kvz@ Ash Ketchum: Very kind of you to share Ash, thank you very much.
I do think there's an issue when your array has identical values though as it seems you're checking if it's the last item by checking it's value.
It may be better to use a counter or sth.

Wouldn't it be possible to modify the plotTree() function to use tags instead of symbols like + and - ?

#29. Ash Ketchum on 27 July 2009

Gravatar.com: Ash KetchumThanks for this awesome function. Just what I was looking for.

But I had a really hard time trying to get the array to display the way I wanted (In an unordered list, so that I can make a nice graphical tree out of it using css). Anyway, I came up with the following function, which displays the array contents in an unordered list.

function plotNewTree($array, $is_sub = false, $first_run = true) {
if ($first_run) {
echo "<ul class=\"contents\">\r\n";
}

$items = count($array);
$lastval = end($array);
// apparently the following may not work as expected. but works for me :D
$lastkey = end(array_keys($array));

foreach($array as $key=>$value) {
if($key == "__base_val") continue;

if ($is_sub && is_array($value)) {
if ($lastval == $value) {
echo "<ul class=\"subfolder lastnode\">\r\n";
} else {
echo "<ul class=\"subfolder\">\r\n";
}
}

if ($first_run || ($is_sub && is_array($value))) {
if ($first_run && !is_array($value) && $items == 1) {
$file_ext = pathinfo(basename($key), PATHINFO_EXTENSION);
echo "<li><span class=\"file ext-$file_ext\">$key</span>\r\n";
} else if ($lastval == $value) {
echo "<li class=\"lastnode\"><span class=\"folder\">$key</span>\r\n";
} else {
echo "<li><span class=\"folder\">$key</span>\r\n";
}
}

if (is_array($value)) {
plotNewTree($value, true, false);
if ($is_sub && is_array($value)) {
echo "</li></ul><!--subfolder-->\r\n";
}
}

if (!$first_run && !is_array($value)) {
if (!isset($firstfiledone)) {
echo "<ul class=\"files\">\r\n";
}
$firstfiledone = true;
$file_ext = pathinfo(basename($key), PATHINFO_EXTENSION);
if ($value == $lastval && $key == $lastkey) {
echo "<li class=\"lastnode\"><span class=\"file ext-$file_ext\">$key</span> (".bytestostring($value).")</li>\r\n";
echo "</ul><!--files ul-->\r\n";
} else {
echo "<li><span class=\"file ext-$file_ext\">$key</span> (".bytestostring($value).")</li>\r\n";
}
}
 
}

if ($first_run) {
echo "</li></ul>\r\n";
}
}


The "bytestostring" function (which I came across in another site) formats file size in bytes to a string like "1.56 MB". Here's the "bytestostring" function.

function bytestostring( $size,$precision = 2 ) {
$sizes=array( 'YB','ZB','EB','PB','TB','GB','MB','KB','Bytes' );
$total=count( $sizes );
 
while( $total-- && $size > 1024 ) $size /= 1024;
return round( $size,$precision )." ".$sizes[$total];
}


Anyway, thanks again Kevin.

#28. Kevin on 25 July 2009

Twitter.com: kvz@ Morten Slott Hansen & Sandro Frenzel: Thanks for the kind words.

#27. Sandro Frenzel on 17 July 2009

Gravatar.com: Sandro FrenzelThanks for this create article! I was searching a long time to create a treeview like this http://jquery.bassistance.de/treeview/demo/?1

I simply add some HTML-Tags to generate the right structure and it works!

Great!
... [more]
Thank you for sharing your knowledge :))!

#26. Morten Slott Hansen on 10 July 2009

Gravatar.com: Morten Slott HansenIndeed awesome stuff - Have been trying something like this the whole week and have so far been unsuccessful - this just saved my entire week!
Now I can finally make a WEB frontend for digikam!

#25. Kevin on 26 June 2009

Twitter.com: kvz@ Andrei: You could write a recursive function that uses UL and LI HTML elements. You could have a look at the plotTree() function above for inspiration, google for one, or have a hack at it :)

#24. Andrei on 18 June 2009

Gravatar.com: AndreiGreat function plotTree. I want to use it on a table witch looks like this:
id | id_parent | page
1 | 0 | home
2 | 1 | page1
3 | 0 | page2
... [more] 4 | 1 | page3
5 | 3 | page4
6 | 1 | page5
7 | 4 | page6
8 | 7 | page7
9 | 5 | page8
Using this table I want to generate a sitemap. Cand someone give me a hint?

#23. Kevin on 18 June 2009

Twitter.com: kvz@ Matt: Thanks for sharing!

#22. Matt on 17 June 2009

Gravatar.com: MattGreat function, I've used it a few times. I agree that with many problems where it seems my brain is about to break I realize that this is probably the solution.
The only thing I needed to add was a limit parameter for a recent project but it was easy as all that was changed was the -1 to a default of $limit=-1 on the preg_split.

Thanks!

#21. EllisGL on 17 October 2008

Gravatar.com: EllisGLI found this while trying to figure out what kind of tree scheme PHP array's use, so I can do multidimensional associative arrays in C/C++ like PHP does.

#20. Kevin on 10 September 2008

Twitter.com: kvz@ steve: My mistake, fixed it. Thanks for telling me!

#19. steve on 09 September 2008

Gravatar.com: steveI read your article with great interest, but it looks like the actual code for the function in included on your site via a non-valid url in PHP.

I get this:
/var/www/web5/web/code/kvzlib/code/php/functions/explodeTree.inc.php

... [more] instead of the script. Any chance I can peek at this code? ;-)

#18. Robert on 06 May 2008

Default avatar:RobertYou may have saved my life... I was thinking of killing myself because I had some seriously problems with getting this to work! Thanks!

#17. Emacs on 06 April 2008

Default avatar:EmacsNice snippet :) Thanks a lot ^^

#16. http://www.sezgioto.com on 26 December 2007

Default avatar:http://www.sezgioto.comthanks man

#15. Takkie on 12 October 2007

Default avatar:Takkie@ Kevin: Thanks, but my site first needs to contain some content before anybody should link to it ;)

#14. Kevin on 12 October 2007

Default avatar:Kevin@ Lachlan: I've included a link to your site.
@ Takkie: If you have site you want listed here just say so.

#13. Lachlan on 12 October 2007

Default avatar:Lachlan@Takkie Oh your right, it is order dependent :) Although my code doesn't generate notices, the isset guard in it should prevent those.

Although not quite as succinct, here is a version that works with any array order:

function expand($array,$delim='/')
... [more] {
$newArray = array();
$delim = preg_quote($delim,'/');

foreach($array as $key=>$value)
{
$current = &$newArray;
$stack = preg_split("/$delim/",$key,-1,PREG_SPLIT_NO_EMPTY);

// iterate down the array, leaving $current as the leaf
foreach($stack as $item)
{
// clobber leafs, replace this for baseval support
if(isset($current[$item]) && !is_array($current[$item]))
{
$current[$item] = array();
}

$current =& $current[$item];
}

// don't overwrite existing branches
if(!is_array($current) || count($current) == 0)
{
$current = $value;
}
}

return $newArray;
}

I haven't implemented baseval support, but it would be fairly straightforward, see the comments in the inner for loop.

- Lachlan Donald http://www.lachlandonald.com

#12. Kevin on 10 October 2007

Default avatar:Kevin@ Takkie: I think we all agree on the evil part ;)

But that's some awesome code you wrote. I've updated the article and replaced the original function with yours.
Thanks a lot you guys, you've really contributed powerful stuff.

#11. Kevin on 10 October 2007

Default avatar:Kevin@ Craig: Your function is indeed good for the pure purpose of recursively indexing a directory. However, I feel that the explodeTree() function is more generic and could be used for a lot of other things as well. Thanks for your comment.

#10. Takkie on 10 October 2007

Default avatar:TakkieI agree with lachlan on the evil eval part. Besides that your code depends heavily on the given array being sorted (parents first), which conflicts with your goal: explode _any_ single-dimensional array into a tree.The code lachlan proposes also depends on the same ordering btw.

Also, your code makes use of undefined variables and indices. Just for fun: add shuffle($files); right after if(exec("find /etc/php5", $files)){ and run the code with a configuration that shows notices.


... [more] Another possible solution could be (independend of ordering):

function explodeTree($array, $delimiter = '_', $baseval = false)
{
$splitRE = '/' . preg_quote($delimiter, '/') . '/';
$returnArr = array();
foreach ($array as $key => $val) {
// Get parent parts and the current leaf
$parts = preg_split($splitRE, $key, -1, PREG_SPLIT_NO_EMPTY);
$leafPart = array_pop($parts);

// Build parent structure (might be slow for really deep and large structures)
$parentArr = &$returnArr;
foreach ($parts as $part) {
if (!isset($parentArr[$part])) {
$parentArr[$part] = array();
} elseif (!is_array($parentArr[$part])) {
$parentArr[$part] = $baseval ? array('__base_val' => $parentArr[$part]) : array();
}
$parentArr = &$parentArr[$part];
}

// Add the final part to the structure
if (empty($parentArr[$leafPart])) {
$parentArr[$leafPart] = $val;
} elseif ($baseval && is_array($parentArr[$leafPart])) {
$parentArr[$leafPart]['__base_val'] = $val;
}
}
return $returnArr;
}

#9. Craig Francis on 10 October 2007

Default avatar:Craig FrancisAlthough your implementation does seem to work on a more general setup, when it comes to listing a directory, I do prefer to use the native directory listing functions (not 'eval'), which work on all operating systems, and in this case, with a recursive function call.


<?php

... [more] function printFolder($folder, $prefix = '') {

$folder = str_replace('\\', '/', $folder);
if (substr($folder, -1) != '/') {
$folder .= '/';
}

if ($handle = opendir($folder)) {
while (false !== ($file = readdir($handle))) {
if (!preg_match('/^\./', $file)) {

if (is_dir($folder . $file)) {

echo $prefix . '+ ' . $file . "\n";

printFolder($folder . $file . '/', ' ' . $prefix);

} else {

echo $prefix . '- ' . $file . "\n";

}

}
}
closedir($handle);
}

}

printFolder('/etc/php5/');

?>

#8. Kevin on 10 October 2007

Default avatar:Kevin@ Andrew: Thanks, But this article aims at forming tree structures, not breaking them down (into single-dimensional arrays).
And yes, such a tree could be passed on nicely with serialize, but that's a bit outside this article's scope.

#7. Kevin on 10 October 2007

Default avatar:Kevin@ lachlan: Wow that's an awesome piece of code! I totally agree that my way is evil, nevertheless it does the trick and I think it brings an interesting approach.

I would like to include your function in this article however, shall I credit it to: 'lachlan' ?

btw, yours currently does not have a real 'baseval' replacement. In the original function baseval is used to store the values of parent nodes as well as leafs. In the example look at: '/etc/php5', this value isn't saved by expand().
... [more]
Thanks for your effort!

#6. Andrew on 10 October 2007

Default avatar:AndrewIt's a bad idea to pass around trees represented as 'single-dimensional arrays', consider something like XML, JSON, or serialized arrays.

If you haven't already, take a look at RecursiveIterators (SPL) and SimpleXML.

http://cvs.php.net/viewvc.cgi/php-src/ext/spl/examples/

#5. lachlan on 10 October 2007

Default avatar:lachlanUsing eval like this is really, really evil. Not to mention slow and error prone. This sort of usage results in evals bad reputation as its so easy to make a mistake and end up with a remote code execution bug.

Try this:

function expand($array,$delim='/')
... [more] {
$newArray = array();
$delim = preg_quote($delim,'/');

foreach($array as $key=>$value)
{
$current = &$newArray;
$stack = preg_split("/$delim/",$key,-1,PREG_SPLIT_NO_EMPTY);

// iterate down the array, leaving $current as the leaf
foreach($stack as $item)
{
// this actually clobbers non-leafs, replace for baseval
if(isset($current[$item]) && !is_array($current[$item]))
{
$current[$item] = array();
}
$current =& $current[$item];
}

// set the leaf value
$current = $value;
}

return $newArray;
}

#4. Kevin on 09 October 2007

Default avatar:Kevin@ Charles + guigouz: I gave it some more thought and you'll be happy to know that I've changed the article. I hope this will make the it a bit easier on the eyes and it may illustrate the need for such a function better. Thanks guys.

#3. Kevin on 09 October 2007

Default avatar:Kevin@ Charles: You're right. In that specific example there are other ways to do it. So maybe I'll replace it with something else.
However the example's main purpose is to illustrate how the function works and just one of it's many possible uses. My first thought was to use the POST example because everyone is familiar with that technology. Thanks for your comment, I'll think about updating the article.

#2. guigouz on 09 October 2007

Default avatar:guigouzyou know you can use something like
<input type="text" name="serverinfo[1][hostname]"/>
<input type="text" name="serverinfo[2][ip_address]"/> ?

even if you use multiple name="serverinfo[]" attrs php will turn those in an ordered array

#1. Charles on 09 October 2007

Default avatar:CharlesHuh?

You don't need a function for this.

Since PHP3 or so, PHP automagically turns input into arrays if you use square brackets.
... [more]
&lt;input name="serverinfo[1][hostname]" value="server1.example.com" />
&lt;input name="serverinfo[1][ipaddress]" value="123.123.123.123" />
&lt;input name="serverinfo[2][hostname]" value="server2.another.com" />
&lt;input name="serverinfo[2][ipaddress]" value="234.234.234.234" />