SpanMode uses incorrect terminology (breadth)

Ben Davis entheh at cantab.net
Tue Sep 18 13:21:46 PDT 2012


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

:)


More information about the Digitalmars-d mailing list