php - convert data from database to hierarchical array

Question

I have been puzzling with this problem for days, without any luck. I hope some of you can help. From my database I get a list of files, which various information attached, including a virtual path. Some typical data is:

Array
(
  [0] => Array
         (
           [name] => guide_to_printing.txt
           [virtual_path] => guides/it
         )
  [1] => Array
         (
           [name] => guide_to_vpn.txt
           [virtual_path] => guides/it
         )
  [2] => Array
         (
           [name] => for_new_employees.txt
           [virtual_path] => guides
         )
)

I wish to convert this into a hierarchical array structure from the virtual paths, so the output of the above should be:

Array
(
  [0] => Array
         (
           [type] => dir
           [name] => guides
           [children] => Array
                         (
                           [0] => Array
                                  (
                                    [type] => dir
                                    [name] => it
                                    [children] = Array
                                                 (
                                                   [0] => Array
                                                          (
                                                            [type] => file
                                                            [name] => guide_to_printing.txt
                                                          )
                                                   [1] => Array
                                                          (
                                                            [type] => file
                                                            [name] => guide_to_vpn.txt
                                                          )
                                                 )
                                  )
                           [1] => Array
                                  (
                                    [type] => file
                                    [name] => for_new_employees.txt
                                  )
                         )
         )
)

Where the type property indicates if it is a directory or a file.

Can someone help with creating a function which does this conversion. It will be of great help. Thanks.

My own best solution so far is:

foreach($docs as $doc) {
    $path = explode("/",$doc['virtual_path']);
    $arrayToInsert = array(
                           'name' => $doc['name'],
                           'path' => $doc['virtual_path'],
                          );
    if(count($path)==1) { $r[$path[0]][] = $arrayToInsert; }
    if(count($path)==2) { $r[$path[0]][$path[1]][] = $arrayToInsert; }
    if(count($path)==3) { $r[$path[0]][$path[1]][$path[2]][] = $arrayToInsert; }
}

Of course this only works for a depth of 3 in the directory structure, and the keys are the directory names.

Answer 1

Function

function hierarchify(array $files) {
    /* prepare root node */
    $root = new stdClass;
    $root->children = array();
    /* file iteration */
    foreach ($files as $file) {
        /* argument validation */
        switch (true) {
            case !isset($file['name'], $file['virtual_path']):
            case !is_string($name = $file['name']):
            case !is_string($virtual_path = $file['virtual_path']):
                throw new InvalidArgumentException('invalid array structure detected.');
            case strpos($virtual_path, '/') === 0:
                throw new InvalidArgumentException('absolute path is not allowed.');
        }
        /* virtual url normalization */
        $parts = array();
        $segments = explode('/', preg_replace('@/++@', '/', $virtual_path));
        foreach ($segments as $segment) {
            if ($segment === '.') {
                continue;
            }
            if (null === $tail = array_pop($parts)) {
                $parts[] = $segment;
            } elseif ($segment === '..') {
                if ($tail === '..') {
                    $parts[] = $tail;
                }
                if ($tail === '..' or $tail === '') {
                    $parts[] = $segment;
                }
            } else {
                $parts[] = $tail;
                $parts[] = $segment;
            }
        }
        if ('' !== $tail = array_pop($parts)) {
            // skip empty
            $parts[] = $tail;
        }
        if (reset($parts) === '..') {
            // invalid upper traversal
            throw new InvalidArgumentException('invalid upper traversal detected.');
        }
        $currents = &$root->children;
        /* hierarchy iteration */
        foreach ($parts as $part) {
            while (true) {
                foreach ($currents as $current) {
                    if ($current->type === 'dir' and $current->name === $part) {
                        // directory already exists!
                        $currents = &$current->children;
                        break 2;
                    }
                }
                // create new directory...
                $currents[] = $new = new stdClass;
                $new->type = 'dir';
                $new->name = $part;
                $new->children = array();
                $currents = &$new->children;
                break;
            }
        }
        // create new file...
        $currents[] = $new = new stdClass;
        $new->type = 'file';
        $new->name = $name;
    }
    /* convert into array completely */
    return json_decode(json_encode($root->children), true);
}

Example

Case 1:

$files = array(
    0 => array (
        'name' => 'b.txt',
        'virtual_path' => 'A/B//',
    ),
    1 => array(
        'name' => 'a.txt',
        'virtual_path' => '././A/B/C/../..',
    ),
    2 => array(
        'name' => 'c.txt',
        'virtual_path' => './A/../A/B/C//////',
    ),
    3 => array(
        'name' => 'root.txt',
        'virtual_path' => '',
    ),
);
var_dump(hierarchify($files));

will output...

array(2) {
  [0]=>
  array(3) {
    ["type"]=>
    string(3) "dir"
    ["name"]=>
    string(1) "A"
    ["children"]=>
    array(2) {
      [0]=>
      array(3) {
        ["type"]=>
        string(3) "dir"
        ["name"]=>
        string(1) "B"
        ["children"]=>
        array(2) {
          [0]=>
          array(2) {
            ["type"]=>
            string(4) "file"
            ["name"]=>
            string(5) "b.txt"
          }
          [1]=>
          array(3) {
            ["type"]=>
            string(3) "dir"
            ["name"]=>
            string(1) "C"
            ["children"]=>
            array(1) {
              [0]=>
              array(2) {
                ["type"]=>
                string(4) "file"
                ["name"]=>
                string(5) "c.txt"
              }
            }
          }
        }
      }
      [1]=>
      array(2) {
        ["type"]=>
        string(4) "file"
        ["name"]=>
        string(5) "a.txt"
      }
    }
  }
  [1]=>
  array(2) {
    ["type"]=>
    string(4) "file"
    ["name"]=>
    string(8) "root.txt"
  }
}

Case 2:

$files = array(
    0 => array (
        'name' => 'invalid.txt',
        'virtual_path' => '/A/B/C',
    ),
);
var_dump(hierarchify($files));

will throw...

Fatal error: Uncaught exception 'InvalidArgumentException' with message 'absolute path is not allowed.'

Case 3:

$files = array(
    0 => array (
        'name' => 'invalid.txt',
        'virtual_path' => 'A/B/C/../../../../../../../..',
    ),
);
var_dump(hierarchify($files));

will throw...

Fatal error: Uncaught exception 'InvalidArgumentException' with message 'invalid upper traversal detected.'

Answer 2

With something like this:

foreach ($array as $k => $v) {
    $tmp = explode('/',$v['virtual_path']); 
    if(sizeof($tmp) > 1){
        $array_result[$tmp[0]]['children'][$k]['type'] = 'file';
        $array_result[$tmp[0]]['children'][$k]['name'] = $v['name'];
        $array_result[$tmp[0]]['type'] = 'dir';
        $array_result[$tmp[0]]['name'] = $v['name'];
    }       
}

I get an array like this on:

Array
(
    [guides] => Array
        (
            [children] => Array
                (
                    [0] => Array
                        (
                            [type] => file
                            [name] => guide_to_printing.txt
                        )

                    [1] => Array
                        (
                            [type] => file
                            [name] => guide_to_vpn.txt
                        )

                )

            [type] => dir
            [name] => guide_to_vpn.txt
        )

)

I know that's not exactly what you want but i think that can put you in the right direction.

Answer 3

Event though you should have tried something before you post here, I like your question and think it is a fun one. So here you go

function &createVirtualDirectory(&$structure, $path) {
    $key_parts = $path ? explode('/', $path) : null;

    $last_key = &$structure;
    if (is_array($key_parts) && !empty($key_parts)) {
        foreach ($key_parts as $name) {
            // maybe directory exists?
            $index = null;
            if (is_array($last_key) && !empty($last_key)) {
                foreach ($last_key as $key => $item) {
                    if ($item['type'] == 'dir' && $item['name'] == $name) {
                        $index = $key;
                        break;
                    }
                }
            }

            // if directory not exists - create one
            if (is_null($index)) {
                $last_key[] = array(
                    'type' => 'dir',
                    'name' => $name,
                    'children' => array(),
                );

                $index = count($last_key)-1;
            }

            $last_key =& $last_key[$index]['children'];

        }
    }

    return $last_key;
}

$input = array(
    0 => array (
        'name' => 'guide_to_printing.txt',
        'virtual_path' => 'guides/it',
    ),
    1 => array(
        'name' => 'guide_to_vpn.txt',
        'virtual_path' => 'guides/it',
    ),
    2 => array(
        'name' => 'for_new_employees.txt',
        'virtual_path' => 'guides',
    )
);



$output = array();

foreach ($input as $file) {
    $dir =& createVirtualDirectory($output, $file['virtual_path']);
    $dir[] = array(
        'type' => 'file', 
        'name' => $file['name']
    );

    unset($dir);
}

print_r($output);

Provides the exact output you want

Answer 4

Here is simple way to do this with 2 recursive functions. One function to parse one line of data. Another to merge each parsed line of data.

// Assuming your data are in $data
$tree = array();
foreach ($data as $item) {
    $tree = merge($tree, parse($item['name'], $item['virtual_path']));
}
print json_encode($tree);

// Simple parser to extract data
function parse($name, $path){
    $parts = explode('/', $path);
    $level = array(
        'type' => 'dir',
        'name' => $parts[0],
        'children' => array()
    );
    if(count($parts) > 1){
        $path = str_replace($parts[0] . '/', '', $path);
        $level['children'][] = parse($name, $path);
    }
    else {
        $level['children'][] = array(
            'type' => 'file',
            'name' => $name
        );
    }

    return $level;
}

// Merge a new item to the current tree
function merge($tree, $new_item){
    if(!$tree){
        $tree[] = $new_item;
        return $tree;
    }

    $found = false;
    foreach($tree as $key => &$item) {
        if($item['type'] === $new_item['type'] && $item['name'] === $new_item['name']){
            $item['children'] = merge($item['children'], $new_item['children'][0]);
            $found = true;
            break;
        }
    }

    if(!$found) {
        $tree[] = $new_item;
    }

    return $tree;
}