Convert a Single Dimensional Array to a Full Blown Tree Structure in PHP

Standard

From a Data Structure perspective, here, I will demonstrate how to convert a single dimensional array to a full blown tree structure in PHP. Array is PHP is really flexible. PHP array is actually ordered dictionary. It can be used to represent arrays, lists, queues, stacks, trees, with use of references even graphs. What is more it’s fast. What more could you want? So, here I start with an example with a directory.

See the following code (I have used a directory from my Macbook, you can use from your computer):

<?php
if(exec("find /etc/apache2", $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);
}
?>

The above code will produce something like:

Array
(
    [/etc/apache2] => /etc/apache2
    [/etc/apache2/extra] => /etc/apache2/extra
    [/etc/apache2/extra/httpd-autoindex.conf] => /etc/apache2/extra/httpd-autoindex.conf
    [/etc/apache2/extra/httpd-dav.conf] => /etc/apache2/extra/httpd-dav.conf
    [/etc/apache2/extra/httpd-default.conf] => /etc/apache2/extra/httpd-default.conf
    [/etc/apache2/extra/httpd-info.conf] => /etc/apache2/extra/httpd-info.conf
    [/etc/apache2/extra/httpd-languages.conf] => /etc/apache2/extra/httpd-languages.conf
    [/etc/apache2/extra/httpd-manual.conf] => /etc/apache2/extra/httpd-manual.conf
    [/etc/apache2/extra/httpd-mpm.conf] => /etc/apache2/extra/httpd-mpm.conf
    [/etc/apache2/extra/httpd-multilang-errordoc.conf] => /etc/apache2/extra/httpd-multilang-errordoc.conf
    [/etc/apache2/extra/httpd-ssl.conf] => /etc/apache2/extra/httpd-ssl.conf
    [/etc/apache2/extra/httpd-userdir.conf] => /etc/apache2/extra/httpd-userdir.conf
    [/etc/apache2/extra/httpd-vhosts.conf] => /etc/apache2/extra/httpd-vhosts.conf
    [/etc/apache2/httpd.conf] => /etc/apache2/httpd.conf
    [/etc/apache2/magic] => /etc/apache2/magic
    [/etc/apache2/mime.types] => /etc/apache2/mime.types
    [/etc/apache2/original] => /etc/apache2/original
    [/etc/apache2/original/extra] => /etc/apache2/original/extra
    [/etc/apache2/original/extra/httpd-autoindex.conf] => /etc/apache2/original/extra/httpd-autoindex.conf
    [/etc/apache2/original/extra/httpd-dav.conf] => /etc/apache2/original/extra/httpd-dav.conf
    [/etc/apache2/original/extra/httpd-default.conf] => /etc/apache2/original/extra/httpd-default.conf
    [/etc/apache2/original/extra/httpd-info.conf] => /etc/apache2/original/extra/httpd-info.conf
    [/etc/apache2/original/extra/httpd-languages.conf] => /etc/apache2/original/extra/httpd-languages.conf
    [/etc/apache2/original/extra/httpd-manual.conf] => /etc/apache2/original/extra/httpd-manual.conf
    [/etc/apache2/original/extra/httpd-mpm.conf] => /etc/apache2/original/extra/httpd-mpm.conf
    [/etc/apache2/original/extra/httpd-multilang-errordoc.conf] => /etc/apache2/original/extra/httpd-multilang-errordoc.conf
    [/etc/apache2/original/extra/httpd-ssl.conf] => /etc/apache2/original/extra/httpd-ssl.conf
    [/etc/apache2/original/extra/httpd-userdir.conf] => /etc/apache2/original/extra/httpd-userdir.conf
    [/etc/apache2/original/extra/httpd-vhosts.conf] => /etc/apache2/original/extra/httpd-vhosts.conf
    [/etc/apache2/original/httpd.conf] => /etc/apache2/original/httpd.conf
    [/etc/apache2/other] => /etc/apache2/other
    [/etc/apache2/other/bonjour.conf] => /etc/apache2/other/bonjour.conf
    [/etc/apache2/other/php5.conf] => /etc/apache2/other/php5.conf
    [/etc/apache2/users] => /etc/apache2/users
    [/etc/apache2/users/anupamsaha.conf] => /etc/apache2/users/anupamsaha.conf
)

Now if we want to convert 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 = treeBreak($key_files, "/"); // I will show treeBreak() function below
// show the array
print_r($tree);

And, this will produce something like:

Array
(
    [etc] => Array
        (
            [apache2] => Array
                (
                    [extra] => Array
                        (
                            [httpd-autoindex.conf] => /etc/apache2/extra/httpd-autoindex.conf
                            [httpd-dav.conf] => /etc/apache2/extra/httpd-dav.conf
                            [httpd-default.conf] => /etc/apache2/extra/httpd-default.conf
                            [httpd-info.conf] => /etc/apache2/extra/httpd-info.conf
                            [httpd-languages.conf] => /etc/apache2/extra/httpd-languages.conf
                            [httpd-manual.conf] => /etc/apache2/extra/httpd-manual.conf
                            [httpd-mpm.conf] => /etc/apache2/extra/httpd-mpm.conf
                            [httpd-multilang-errordoc.conf] => /etc/apache2/extra/httpd-multilang-errordoc.conf
                            [httpd-ssl.conf] => /etc/apache2/extra/httpd-ssl.conf
                            [httpd-userdir.conf] => /etc/apache2/extra/httpd-userdir.conf
                            [httpd-vhosts.conf] => /etc/apache2/extra/httpd-vhosts.conf
                        )

                    [httpd.conf] => /etc/apache2/httpd.conf
                    [magic] => /etc/apache2/magic
                    [mime.types] => /etc/apache2/mime.types
                    [original] => Array
                        (
                            [extra] => Array
                                (
                                    [httpd-autoindex.conf] => /etc/apache2/original/extra/httpd-autoindex.conf
                                    [httpd-dav.conf] => /etc/apache2/original/extra/httpd-dav.conf
                                    [httpd-default.conf] => /etc/apache2/original/extra/httpd-default.conf
                                    [httpd-info.conf] => /etc/apache2/original/extra/httpd-info.conf
                                    [httpd-languages.conf] => /etc/apache2/original/extra/httpd-languages.conf
                                    [httpd-manual.conf] => /etc/apache2/original/extra/httpd-manual.conf
                                    [httpd-mpm.conf] => /etc/apache2/original/extra/httpd-mpm.conf
                                    [httpd-multilang-errordoc.conf] => /etc/apache2/original/extra/httpd-multilang-errordoc.conf
                                    [httpd-ssl.conf] => /etc/apache2/original/extra/httpd-ssl.conf
                                    [httpd-userdir.conf] => /etc/apache2/original/extra/httpd-userdir.conf
                                    [httpd-vhosts.conf] => /etc/apache2/original/extra/httpd-vhosts.conf
                                )

                            [httpd.conf] => /etc/apache2/original/httpd.conf
                        )

                    [other] => Array
                        (
                            [bonjour.conf] => /etc/apache2/other/bonjour.conf
                            [php5.conf] => /etc/apache2/other/php5.conf
                        )

                    [users] => Array
                        (
                            [anupamsaha.conf] => /etc/apache2/users/anupamsaha.conf
                        )
                )
        )
)

The function treeBreak()

<?php
/**
 * Explode any single-dimensional array into a full blown tree structure,
 * based on the delimiters found in it's keys.
 *
 * @param array   $array
 * @param string  $delimiter
 * @param boolean $baseval
 *
 * @return array
 */
function treeBreak($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;
}

I guess, the first two arguments of the function treeBreak() is clear. But, what about the third parameter $baseval?

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 treeBreak to do so like this:

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

And then treeBreak() will preserve the node’s original value in the __base_val items. Like this:

Array
(
    [etc] => Array
        (
            [apache2] => Array
                (
                    [__base_val] => /etc/apache2
                    [extra] => Array
                        (
                            [__base_val] => /etc/apache2/extra
                            [httpd-autoindex.conf] => /etc/apache2/extra/httpd-autoindex.conf
                            [httpd-dav.conf] => /etc/apache2/extra/httpd-dav.conf
                            [httpd-default.conf] => /etc/apache2/extra/httpd-default.conf
                            [httpd-info.conf] => /etc/apache2/extra/httpd-info.conf
                            [httpd-languages.conf] => /etc/apache2/extra/httpd-languages.conf
                            [httpd-manual.conf] => /etc/apache2/extra/httpd-manual.conf
                            [httpd-mpm.conf] => /etc/apache2/extra/httpd-mpm.conf
                            [httpd-multilang-errordoc.conf] => /etc/apache2/extra/httpd-multilang-errordoc.conf
                            [httpd-ssl.conf] => /etc/apache2/extra/httpd-ssl.conf
                            [httpd-userdir.conf] => /etc/apache2/extra/httpd-userdir.conf
                            [httpd-vhosts.conf] => /etc/apache2/extra/httpd-vhosts.conf
                        )

                    [httpd.conf] => /etc/apache2/httpd.conf
                    [magic] => /etc/apache2/magic
                    [mime.types] => /etc/apache2/mime.types
                    [original] => Array
                        (
                            [__base_val] => /etc/apache2/original
                            [extra] => Array
                                (
                                    [__base_val] => /etc/apache2/original/extra
                                    [httpd-autoindex.conf] => /etc/apache2/original/extra/httpd-autoindex.conf
                                    [httpd-dav.conf] => /etc/apache2/original/extra/httpd-dav.conf
                                    [httpd-default.conf] => /etc/apache2/original/extra/httpd-default.conf
                                    [httpd-info.conf] => /etc/apache2/original/extra/httpd-info.conf
                                    [httpd-languages.conf] => /etc/apache2/original/extra/httpd-languages.conf
                                    [httpd-manual.conf] => /etc/apache2/original/extra/httpd-manual.conf
                                    [httpd-mpm.conf] => /etc/apache2/original/extra/httpd-mpm.conf
                                    [httpd-multilang-errordoc.conf] => /etc/apache2/original/extra/httpd-multilang-errordoc.conf
                                    [httpd-ssl.conf] => /etc/apache2/original/extra/httpd-ssl.conf
                                    [httpd-userdir.conf] => /etc/apache2/original/extra/httpd-userdir.conf
                                    [httpd-vhosts.conf] => /etc/apache2/original/extra/httpd-vhosts.conf
                                )

                            [httpd.conf] => /etc/apache2/original/httpd.conf
                        )

                    [other] => Array
                        (
                            [__base_val] => /etc/apache2/other
                            [bonjour.conf] => /etc/apache2/other/bonjour.conf
                            [php5.conf] => /etc/apache2/other/php5.conf
                        )

                    [users] => Array
                        (
                            [__base_val] => /etc/apache2/users
                            [anupamsaha.conf] => /etc/apache2/users/anupamsaha.conf
                        )
                )
        )
)

See what happens? Baseval creates a placeholder. A semi-node for the original value of it’s parent. The value: ‘/etc/apache2’ is now saved, without baseval this value would be lost because there was no place to store it in.

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 treePlotter($arr, $indent=0, $mother_run=true){
    if($mother_run){
        // the beginning of plotTree. We're at rootlevel
        echo "start\n";
    }

    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
            treePlotter($v, ($indent+1), false);
        }
    }

    if($mother_run){
        echo "end\n";
    }
}

And, this would output something like:

start
O etc ()
  + apache2 (/etc/apache2)
    + extra (/etc/apache2/extra)
      - httpd-autoindex.conf (/etc/apache2/extra/httpd-autoindex.conf)
      - httpd-dav.conf (/etc/apache2/extra/httpd-dav.conf)
      - httpd-default.conf (/etc/apache2/extra/httpd-default.conf)
      - httpd-info.conf (/etc/apache2/extra/httpd-info.conf)
      - httpd-languages.conf (/etc/apache2/extra/httpd-languages.conf)
      - httpd-manual.conf (/etc/apache2/extra/httpd-manual.conf)
      - httpd-mpm.conf (/etc/apache2/extra/httpd-mpm.conf)
      - httpd-multilang-errordoc.conf (/etc/apache2/extra/httpd-multilang-errordoc.conf)
      - httpd-ssl.conf (/etc/apache2/extra/httpd-ssl.conf)
      - httpd-userdir.conf (/etc/apache2/extra/httpd-userdir.conf)
      - httpd-vhosts.conf (/etc/apache2/extra/httpd-vhosts.conf)
    - httpd.conf (/etc/apache2/httpd.conf)
    - magic (/etc/apache2/magic)
    - mime.types (/etc/apache2/mime.types)
    + original (/etc/apache2/original)
      + extra (/etc/apache2/original/extra)
        - httpd-autoindex.conf (/etc/apache2/original/extra/httpd-autoindex.conf)
        - httpd-dav.conf (/etc/apache2/original/extra/httpd-dav.conf)
        - httpd-default.conf (/etc/apache2/original/extra/httpd-default.conf)
        - httpd-info.conf (/etc/apache2/original/extra/httpd-info.conf)
        - httpd-languages.conf (/etc/apache2/original/extra/httpd-languages.conf)
        - httpd-manual.conf (/etc/apache2/original/extra/httpd-manual.conf)
        - httpd-mpm.conf (/etc/apache2/original/extra/httpd-mpm.conf)
        - httpd-multilang-errordoc.conf (/etc/apache2/original/extra/httpd-multilang-errordoc.conf)
        - httpd-ssl.conf (/etc/apache2/original/extra/httpd-ssl.conf)
        - httpd-userdir.conf (/etc/apache2/original/extra/httpd-userdir.conf)
        - httpd-vhosts.conf (/etc/apache2/original/extra/httpd-vhosts.conf)
      - httpd.conf (/etc/apache2/original/httpd.conf)
    + other (/etc/apache2/other)
      - bonjour.conf (/etc/apache2/other/bonjour.conf)
      - php5.conf (/etc/apache2/other/php5.conf)
    + users (/etc/apache2/users)
      - anupamsaha.conf (/etc/apache2/users/anupamsaha.conf)
end

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

Advertisements

2 thoughts on “Convert a Single Dimensional Array to a Full Blown Tree Structure in PHP

I will be happy to answer your queries

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s