On Monday, 17 September 2012 at 23:55:17 UTC, Ben Davis wrote:
> On 17/09/2012 19:47, Jesse Phillips wrote:
>> a/1.txt
>> a/2.txt
>> a/b
>> a/b\1.txt
>> a/b\2.txt
>> a/c
>> a/c\1.txt
>> a/c\z
>> a/c\z\1.txt
>
> These results also show a correct preorder depth-first search.
>
> The bug report as it stands is misleading; should I post a follow-up on the bug tracker, or should we close it and start again?

You can probably just update. But I fail to see what is missleading? Did I get the expected results wrong?  Pre-order depth first does not satisfy breadth first so what am I missin? Sorry Im on a tablet making organization hard.

On Monday, 17 September 2012 at 23:27:22 UTC, Ben Davis wrote:

> 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...?

Ah sorry, yes. I didn't pay too close attention as I've never wanted to traverse a tree in that manner.

I'll update the title of the issue, add your comments.

> 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...?

Actually I prefer breadth-first search when searching the file system. When I search an entire volume, inevitably the (depth-first) search gets stuck in a few giant, deep directories like the source code of Mono or some other cave of source code, you know, something 12 directories deep with 100,000 files in it. A breadth-first search would be more likely to find the thing I'm looking for BEFORE going spelunking in these 12-deep caves.

On Tuesday, 18 September 2012 at 14:24:30 UTC, David Piepgrass wrote:
>> 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...?
>
> Actually I prefer breadth-first search when searching the file system. When I search an entire volume, inevitably the (depth-first) search gets stuck in a few giant, deep directories like the source code of Mono or some other cave of source code, you know, something 12 directories deep with 100,000 files in it. A breadth-first search would be more likely to find the thing I'm looking for BEFORE going spelunking in these 12-deep caves.

We really need iterative deepening.

On 9/18/12 10:25 AM, David Piepgrass wrote:
>> 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...?
>
> Actually I prefer breadth-first search when searching the file system.
> When I search an entire volume, inevitably the (depth-first) search gets
> stuck in a few giant, deep directories like the source code of Mono or
> some other cave of source code, you know, something 12 directories deep
> with 100,000 files in it. A breadth-first search would be more likely to
> find the thing I'm looking for BEFORE going spelunking in these 12-deep
> caves.

Yes, that was my intent too.

Andrei

On 18/09/2012 15:25, David Piepgrass wrote:
>> 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...?
>
> Actually I prefer breadth-first search when searching the file system.
> When I search an entire volume, inevitably the (depth-first) search gets
> stuck in a few giant, deep directories like the source code of Mono or
> some other cave of source code, you know, something 12 directories deep
> with 100,000 files in it. A breadth-first search would be more likely to
> find the thing I'm looking for BEFORE going spelunking in these 12-deep
> caves.

Fair point. :)

So there is a case for implementing breadth-first iteration (or as Mehrdad suggests, iterative deepening - it's just a CPU-memory tradeoff). However, the currently implemented 'breadth' (preorder depth-first) is probably used a lot, and someone might be relying on its current behaviour (e.g. to create a tree view). So how do we proceed without silently breaking existing code? Do we use 'breadthFirst' instead of 'breadth'? Do we just gulp and change it? Do we rename 'SpanMode' to 'TreeMode' or something?

On 18/09/2012 21:08, Ben Davis wrote:
> On 18/09/2012 15:25, David Piepgrass wrote:
>>> 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...?
>>
>> Actually I prefer breadth-first search when searching the file system.
>> When I search an entire volume, inevitably the (depth-first) search gets
>> stuck in a few giant, deep directories like the source code of Mono or
>> some other cave of source code, you know, something 12 directories deep
>> with 100,000 files in it. A breadth-first search would be more likely to
>> find the thing I'm looking for BEFORE going spelunking in these 12-deep
>> caves.
>
> Fair point. :)
>
> So there is a case for implementing breadth-first iteration (or as
> Mehrdad suggests, iterative deepening - it's just a CPU-memory
> tradeoff). However, the currently implemented 'breadth' (preorder
> depth-first) is probably used a lot, and someone might be relying on its
> current behaviour (e.g. to create a tree view). So how do we proceed
> without silently breaking existing code? Do we use 'breadthFirst'
> instead of 'breadth'? Do we just gulp and change it? Do we rename
> 'SpanMode' to 'TreeMode' or something?

So maybe we'd have:

enum SpanMode {
  shallow,
  depthFirstPreorder,
  depthFirstPostorder,
  breadthFirst;

  @deprecated alias depthFirstPostorder depth;
  @deprecated alias depthFirstPreorder breadth;
}

Also don't forget the intent conveyed by the current docs:

"depth
Spans the directory depth-first, i.e. the content of any subdirectory is spanned before that subdirectory itself. Useful e.g. when recursively deleting files.

breadth
Spans the directory breadth-first, i.e. the content of any subdirectory is spanned right after that subdirectory itself."

This would need to be rewritten to say something like:

"depthFirstPostorder
Spans the directory depth-first postorder, i.e. the content of any subdirectory is spanned before that subdirectory itself. Useful e.g. when recursively deleting files.

depthFirstPreorder
Spans the directory depth-first preorder, i.e. the content of any subdirectory is spanned right after that subdirectory itself.

breadthFirst
Spans the directory breadth-first, i.e. all children are returned first, followed by all grandchildren, followed by all great-grandchildren, and so on. Useful e.g. when searching for a file that is likely not to be very deep."

I personally won't object if everyone feels comfortable with reusing 'breadth' and changing existing behaviour. I just have a feeling it's generally considered a bad thing. Otherwise I'm all for shortening the names (perhaps by just omitting 'First' from the depth ones).

:)

Another thing worth mentioning occurred to me today.

Whoever implements breadth-first - don't get caught out by symlinks. For the depth-first variants, you can just detect them by looking in the stack. For the breadth-first, you won't be able to detect them by looking in the queue that replaced the stack. :)

On Tuesday, 18 September 2012 at 15:19:08 UTC, Andrei Alexandrescu wrote:
> On 9/18/12 10:25 AM, David Piepgrass wrote:
>> Actually I prefer breadth-first search when searching the file system. When I search an entire volume, inevitably the (depth-first) search gets stuck in a few giant, deep directories like the source code of Mono or some other cave of source code, you know, something 12 directories deep with 100,000 files in it. A breadth-first search would be more likely to find the thing I'm looking for BEFORE going spelunking in these 12-deep caves.
>
> Yes, that was my intent too.
>
> Andrei



I just wanted to point out, BFS is generally a pretty BAD idea for searching a file system.

You instead probably want to implement DFS, and then alter it slightly to use iterative deepening instead of doing plain breadth-first search.

That way you won't be keeping open a million OS file handles.