php parse relative url strings into one array/object

Question

What is the best solution to split these relative links

folder-1/folder-2/item-a.txt
folder-1/folder-2/item-b.txt
folder-1/folder-3/item-c.txt
folder-1/folder-3/item-a.txt
folder-1/item-f.txt
folder-1/folder-2
folder-1/folder-3
folder-1
item-b.txt
item-g.txt

into php array?

$testArray = array(
    "folder-1/" => array(
        "folder-2" => array(
            "item-a.txt",
            "item-b.txt"
        ),
        "folder-3" => array(
            "item-a.txt",
            "item-c.txt"
        ),
        "item-f.txt"
    ),
    "item-b.txt",
    "item-g.txt",
);

possible duplicate of [Multidimensional array from string](http://stackoverflow.com/questions/10123604/multidimensional-array-from-string) — Giacomo1968, Jun 16 '14 at 03:30

score 2 · Answer 1 · edited Jun 16 '14 at 00:43

Given the depth d of the deepest path and the number of paths you can do it quite simply in worst-case O (nk), given a lookup is constant (which is the case in PHP):

$root = array();

foreach ($I as $i) {
    $d =& $root;
    $P = explode("/", $i);

    foreach ($P as $p) {
        if (!array_key_exists($p, $d))
            $d[$p] = array();

        $d =& $d[$p];
    }
}

You could further optimize this by preprocessing your input by sorting it in a way that you’re sure the parent directories appear before any child’s.

Then you're certain each next entry has to be added (so the array_key_exists-condition is redundant). Then you just need a clever way to know where to place your 'cursor' in $r. This code could be a bit more complicated.

Also I’m not entirely sure at which point the cost of the preprocessing and the navigation through $r will benefit the general time complexity.

I probably should add that the given complexity doesn't take splitting the string into account. Still, the split would be necessary at some point, so it's not really relevant. — Dennis Degryse, Jun 16 '14 at 00:23

php parse relative url strings into one array/object

1 Answers1