SpanMode uses incorrect terminology (breadth)

[Ben Davis]

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 :)