2

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.

Improve this question
1
  • Have you tried anything? Commented Feb 20, 2014 at 8:34

4 Answers 4

Reset to default
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.'
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

This worked perfectly - I'm not sure how, but it works. Thanks.
0

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.

Improve this answer

Comments

0

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

Improve this answer

4 Comments

I think this looks like a good solution, - however I'm not so used to call and pass by reference. I've tried this: $list_docs = array(); foreach($docs as $doc) { $list_docs = createVirtualDirectory($list_docs,$doc['virtual_path']); } ` But it doesn't really work.
Also, sorry about not posting any of my solutions. None of them got got close to what I wanted.
@mikklar in order to return reference from a function we should use & in both function declaration and function call. See the usage at the bottom of my code above
@mikklar Looks like you have overlooked the part of my code which goes after createVirtualDirectory function :)
0

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;
}
Improve this answer

2 Comments

Your solution adds "children" part to files
No, tested. You get the expected Array ( [type] => file [name] => for_new_employees.txt )

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.