ID: 35438
User updated by: csaba at alum dot mit dot edu
Reported By: csaba at alum dot mit dot edu
Status: Open
Bug Type: Unknown/Other Function
Operating System: Win XP Pro
PHP Version: 5CVS-2005-11-28 (snap)
New Comment:
I am able to make a slight simplification. If I assume that each
directory's parent also exists in the array (that is to say, no filter
was applied), then I don't need the while loop. Furthermore, I don't
need the if clause testing for existence either. But the problem still
exists. Hence, the simpler:
<?php
$aDir = array("B/", "file", "B/C/");
var_dump($aDir); print "<br>\n";
bfs2dfs($aDir);
function bfs2dfs(&$aDir) {
foreach ($aDir as $i => $file) {
print "$i: $file<br>\n";
// if top level file or dir, then continue
if (($slashPos = strrpos($file, "/", -2))===false) continue;
$parent=substr($file, 0,$slashPos+1);
$key=array_search($parent,$aDir); // guarenteed to exist
for ($j=$key+1;$j<$i;++$j)
if ($parent!=substr($aDir[$j],0, $slashPos+1)) break;
array_splice($aDir, $j, 0, array_splice($aDir, $i, 1));
print "after splice with (i, j, file) as ($i, $j, $file)<br>\n";
var_dump($aDir);
print "<br>\n";
continue 1; }
}
?>
Previous Comments:
------------------------------------------------------------------------
[2005-11-28 14:10:44] csaba at alum dot mit dot edu
For comparison sake, here is a function (doing a bubble sort) that has
most of the same elements as the original one, but it works as
expected:
<?php
$ar = array ("B/", "file", "B/C/");
function mysort(&$ar) {
foreach ($ar as $i => $file) {
while ($i && ($file<$ar[$i-1])) {
for ($j=0;$j<$i;++$j) if ($ar[$j]>$file) break;
print "(i=>file; j=>ar[j]) => " .
"($i => $file; $j => {$ar[$j]})<br>\n";
array_splice($ar, $j, 0, array_splice($ar, $i, 1));
continue 2; }}
}
mysort($ar);
var_dump ($ar);
?>
------------------------------------------------------------------------
[2005-11-28 13:42:16] csaba at alum dot mit dot edu
Sorry Tony, truly I do not like submitting such a complicated example.
I tried to construct a simpler version before submitting and I wasn't
able to.
I tried to give an overview of how the code is supposed to work in the
three paragraphs just under the code itself in the original posting,
but I'll try a more detailed explanation with example here:
The original array starts off as ["B/", "file", "B/C/"]. Terminating
slashes indicate a directory. So the main directory had "B/" and
"file" in it, and "B/" has an empty subdirectory "B/C/".
I want the array to acquire the form ["B/", "B/C/", "file"] where the
"B/C/" follows the "B/" since it's a subdirectory, but the code has to
deal with more general situations (specifically, there may be filters
to weed out some of the entries in the original array). But all this
is just background in where $aDir is coming from. On to the code,
which which I'll try to illustrate by example.
The foreach starts off with ($i => $file) of
0 => B/
and the while tries to see if there are any directories above 'B/'.
There aren't so we're on to the next iteration.
1 => file
There are again no directories above 'file' so we're on to the next
iteration
2 => B/C/
This time the while sees a '/' (prior to the final one) so it knows
there is a higher level directory above 'B/C/', namely 'B/' (at this
point $slashPos=1).
The if tests to see if this higher level directory ($common='B/') is an
entry in $aDir. It is, with $key=0 (in the more general case, specific
ancestor directories are not guaranteed because of possible filters) so
we get to the body of the if.
Now the entries in $aDir from 0 to $i-1 are in DFS order (because that
is what the function is producing). This means that the descendants of
the (or any given) ancestor will be grouped in a contiguous block just
after said ancestor. We can test for this block by checking for (with
the for loop) the first entry of which $common, the ancester, is not
the initial starting substring (which is what the if is doing). In our
example, this happens right away with "file" so that $j=1 and we break
out of the for loop.
Thus we have identified where the current entry being processed ($i=2;
$file="B/C/") should go (just before position $j=1). So we snip out
the current entry with array_splice($aDir, $i, 1) and we insert it to
position $j with array_splice($aDir, $j, 0, array_splice($aDir, $i,
1))
This correctly gives us $aDir = ["B/", "B/C/", "file"] as the print and
var_dump show. At this point we are ready to continue with the foreach,
hence the continue 2;
Unfortunately, the foreach loop has been reset at this point and gives
($i=0; $file="B/"). We'll wind up in an infinite loop, but that is not
the issue - the resetting of the foreach is what is in question.
Tony, I'm happy to answer further questions, but I can't figure out how
to simplify my example currently, though I wish I could.
Csaba
------------------------------------------------------------------------
[2005-11-28 12:35:08] [EMAIL PROTECTED]
Are you able to understand your code yourself?
Can you make it CLEAR, so I don't have to spend half of the day trying
to get what this code does?
------------------------------------------------------------------------
[2005-11-28 12:32:52] csaba at alum dot mit dot edu
<?php
$aDir = array("B/", "file", "B/C/");
var_dump($aDir); print "<br>\n";
bfs2dfs($aDir);
function bfs2dfs(&$aDir) {
foreach ($aDir as $i => $file) {
print "$i: $file<br>\n";
$slashPos = strlen($file)-1; // final slash pos
while (($slashPos = strrpos($file, "/",
$slashPos-strlen($file)-1))!==false)
if (($key=array_search($common=substr($file,
0,$slashPos+1),$aDir))!==false) {
for ($j=$key+1;$j<$i;++$j)
if ($common!=substr($aDir[$j],0, $slashPos+1)) break;
array_splice($aDir, $j, 0, array_splice($aDir, $i, 1));
print "after splice with (i, j, file) as ($i, $j, $file)<br>\n";
var_dump($aDir);
print "<br>\n";
continue 2; }}
}
?>
------------------------------------------------------------------------
[2005-11-28 12:14:04] [EMAIL PROTECTED]
Thank you for this bug report. To properly diagnose the problem, we
need a short but complete example script to be able to reproduce
this bug ourselves.
A proper reproducing script starts with <?php and ends with ?>,
is max. 10-20 lines long and does not require any external
resources such as databases, etc.
If possible, make the script source available online and provide
an URL to it here. Try to avoid embedding huge scripts into the report.
------------------------------------------------------------------------
The remainder of the comments for this report are too long. To view
the rest of the comments, please view the bug report online at
http://bugs.php.net/35438
--
Edit this bug report at http://bugs.php.net/?id=35438&edit=1
