simple way in PHP to split path string into breadth-first array

Question

Using PHP 5.2, I'm trying to parse an arbitrary number of path/directory strings into an array, such that they can be processed breadth-first. This is to allow me to script a sparse checkout from a Subversion repository, telescoping the indicated paths. All the paths on the same level have to be specified in the same svn update --depth empty statement.

I get the desired output, but I wonder if there's a cleaner way to do this. (And, yes, I know there are changes needed for efficiency.)

EDIT I modified the original post to handle cases of multiple children in the same parent. My revised code is

$main = array(
    'a/b/c1/',
    'a/b/c2/d/e1',
    'a/b/c2/d/e2',
    'A/B/',
    'alpha/beta/gamma/delta/epsilon'
);

$splits = array();
$max = 0;
for ($i=0; $i<count($main); $i++) {
    $splits[$i] = explode(DIRECTORY_SEPARATOR, trim($main[$i], DIRECTORY_SEPARATOR));
    if (count($splits[$i]) > $max) {
        $max = count($splits[$i]);
    }
}

for ($i=0; $i<$max; $i++) {
    $levels[$i] = array();

    for ($path=0; $path<count($splits); $path++) {
        if (array_key_exists($i, $splits[$path])) {
            $levels[$i][] = implode(DIRECTORY_SEPARATOR, array_slice($splits[$path], 0, $i+1));
        }
    }
    $levels[$i] = array_unique($levels[$i]);
    sort($levels[$i]);  // just to reset indices
}

This changes my output structure to the following, which both provides unique directories at each level and retains sibling nodes.

Array
(
    [0] => Array
        (
            [0] => A
            [1] => a
            [2] => alpha
        )

    [1] => Array
        (
            [0] => A/B
            [1] => a/b
            [2] => alpha/beta
        )

    [2] => Array
        (
            [0] => a/b/c1
            [1] => a/b/c2
            [2] => alpha/beta/gamma
        )

    [3] => Array
        (
            [0] => a/b/c2/d
            [1] => alpha/beta/gamma/delta
        )

    [4] => Array
        (
            [0] => a/b/c2/d/e1
            [1] => a/b/c2/d/e2
            [2] => alpha/beta/gamma/delta/epsilon
        )

)

In my code, I then iterate over the final $levels array. Unfortunately, this still requires two iterations: one for depth empty and one for depth infinity, but I'm sure that could be worked out.

$count = count($levels);
for ($i=0; $i<$count; $i++) {
    echo '<p>', 'svn update --set-depth empty ', implode(' ', $levels[$i]), "</p>\n";
}

$count = count($main);
for ($i=0; $i<$count; $i++) {
    echo '<p>', 'svn update --set-depth infinity ', $main[$i], "</p>\n";
}

This isnt a direct answer but i wonder if whatever your processing is you might just be better off using RecursiveDirectoryIterator to implement it :-) — prodigitalson
– prodigitalson, Commented Feb 4, 2012 at 22:26
Thanks, but I don't think that will help. I added more information. With a sparse checkout, I won't have any directories to iterate. — nshew13
– nshew13, Commented Feb 4, 2012 at 22:31
A clean solution would have involved a PHP function doing that, but there is no such thing in the standard library (eg. there is nothing like array_union_recursive). Either gain some kind of abstraction by coding it yourself (but then you'll have to think about weird edge cases), either keep your code like this. The current code is really easy to read! — Quentin Pradet
– Quentin Pradet, Commented Feb 4, 2012 at 23:08
ALso, do you realize how complicated it would be to handle the case with multiple children? You'd need to duplicate the parent twice, which is difficult. I have a nice hack wich is shorter than your code, but would never handle the multiple children case. — Quentin Pradet
– Quentin Pradet, Commented Feb 4, 2012 at 23:41

Eugen Rieck · Accepted Answer · 2012-02-04 22:49:41Z

2

$levels=array();
$depth=0;
$i=0;
foreach ($main as $m) {
  $m=explode('/',$m);
  while (sizeof($m)<$depth) $m[]=null;
  $d=0;
  foreach ($m as $mm) {
    if ($d>$depth) {
      if (!$mm) break;
      $depth=$d;
      $levels[$d]=array();
      for ($j=0;$j<=$i;$j++) $levels[$d][$j]=null;
    }
    $levels[$d][$i]=$mm;
    $d++;
  }
  $i++;
}

looks like a good alternative with only one traversion of the array. In short you don't use one pass to decide on the depth, but if you encounter a deeper entry, you just fill the relevant places in the array retroactively with nulls.

$depth has the depth-1 after the loop.

Edit:

This does yet handle a case of multiple children in the same parent, but I am unsure if it does so the way you want

edited Feb 4, 2012 at 22:49

answered Feb 4, 2012 at 22:35

Eugen Rieck

65.6k10 gold badges75 silver badges97 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

nshew13 Over a year ago

Thanks, Eugen. Your answer did simplify the original post. Feel free to have a go at the revised version. :)

Quentin Pradet · Accepted Answer · 2012-02-05 22:59:34Z

Here's my implementation (it got easier with your latest request):

$levels = array();

for ($i=0; $i<count($main); $i++) {
        $splits = explode(DIRECTORY_SEPARATOR, trim($main[$i], DIRECTORY_SEPARATOR));
        $current = array();
        /* Load every subpath in an array*/
        for($j=0; $j<count($splits); $j++) {
                $current[$j . "hack"] = implode("/", array_slice($splits, 0, $j+1));
        }
        $levels = array_merge_recursive($levels, $current);
}

/* Removes duplicates and resets indices */
array_walk($levels, function(&$l, $i) { $l = array_unique($l); sort($l); });

What makes this implementation simple is that I handle each path separately. I only have one loop, and join the results with array_merge_recursive. For example, with "a/b" and "a/c", my code :

creates array(0 => array("a"), 1 => array("a/b")) and array(0 => array("a"), 1 => array("a/c"))
joins them with array_merge_recursive which gives array(0 => array("a", "a"), 1 => array("a/b", "a/c"))
removes unique values with array_unique
resets the indices with sort

Note: I need to use $j + "hack", otherwise array_merge_recursive won't merge the values as expected (try it for yourself).

Collectives™ on Stack Overflow

simple way in PHP to split path string into breadth-first array

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related