I have a feeling most people have missed the point here. Thanks for the
example - it's a good one to work with. The 'expected approximation' was
a bit of a mix of traversal strategies, so I've snipped it out below and
put my own examples. Hope this helps clarify what I was getting at:
On 17/09/2012 06:30, Jesse Phillips wrote:
What would be an example illustrating that "breadth" is doing the
wrong thing?
Andrei
Linux 64bit:
import std.file;
import std.stdio;
void main() {
mkdir("a");
mkdir("a/b");
mkdir("a/c");
mkdir("a/c/z");
std.file.write("a/1.txt", "");
std.file.write("a/2.txt", "");
std.file.write("a/b/1.txt", "");
std.file.write("a/b/2.txt", "");
std.file.write("a/c/1.txt", "");
std.file.write("a/c/z/1.txt", "");
foreach(string file; dirEntries("a/", SpanMode.breadth))
writeln(file);
rmdirRecurse("a");
[snip]
Here are the CORRECT tree traversal patterns:
Breadth-first (probably never required):
a/b
a/c
a/1.txt
a/2.txt
a/b/1.txt
a/b/2.txt
a/c/z
a/c/1.txt
a/c/z/1.txt
Defining property: number of /'s increases monotonically. Note how the
deeper you go, the more spread out the children become. It's ALL
children, then ALL grandchildren, then ALL great-grandchildren, etc.
I wouldn't bother implementing breadth-first. It's doubtful that anyone
would want it, surely...?
Depth-first search has two useful variants, preorder and postorder.
Preorder depth-first (currently wrongly called SpanMode.breadth):
a/b
a/b/1.txt
a/b/2.txt
a/c
a/c/z
a/c/z/1.txt
a/c/1.txt
a/1.txt
a/2.txt
Defining property: every directory is immediately followed by all its
children.
Postorder depth-first (currently only called SpanMode.depth):
a/b/1.txt
a/b/2.txt
a/b
a/c/z/1.txt
a/c/z
a/c/1.txt
a/c
a/1.txt
a/2.txt
Defining property: every directory is immediately *preceded* by all its
children.
Going back to the 'actual' output you quoted:
// Actual
// a/c
// a/c/z
// a/c/z/1.txt
// a/c/1.txt
// a/b
// a/b/2.txt
// a/b/1.txt
// a/2.txt
// a/1.txt
This looks like a preorder depth-first iteration (albeit with child
order reversed at each level). The implementation is correct in that it
matches the spec as documented. The problem is that the spec is using
the term 'breadth' wrongly.
Here is what I would do to fix it (sorry if I got the syntax wrong):
enum SpanMode {
shallow,
preorder,
postorder;
@deprecated alias preorder breadth;
@deprecated alias postorder depth;
}
I initially said that possibly preorder and postorder weren't clear, but
they grew on me very quickly. I think people could learn that "preorder
means parents first" or "preorder is the one I usually want". Also,
these are the standard terms (refer to the Wikipedia link), so once you
know them, you can use them for everything, both in and outside of :D.
Thanks,
Ben :)
