[Issue 8680] SpanMode.breadth is incorrectly named and implementation fails in Linux

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=8680



--- Comment #7 from entheh at cantab.net 2012-09-19 17:10:02 PDT ---
(In reply to comment #5)
> I know, but they are descriptive of the two most useful traversal types I can
> think of.

I think they are unambiguous, but I have a feeling I know what traversal you
want.

> > What behaviour do you want?
> 
> I have only had two types of traversals.
> 
> I don't care: In this type of traversal I just need all the files and couldn't
> care less when they come to me. In all cases I've never wished to have the
> directory name (but don't wish for a traversal that leaves it out).

I suspect we don't need to offer the 'I don't care' option explicitly. People
may as well be specific. Could add a documentation note that the depth-first
options will generally be slightly cheaper than breadth-first.

> Parent First: Give me everything in the Parent First, then you can traverse the
> children. Almost as you described, except it would be starting a breadth first
> from each child.

There are two ways you could get this effect. You could do this:

recurse(dir) {
  foreach (file; dirEntries(dir, shallow)) {
    result~=file;
  }
  foreach (file; dirEntries(dir, shallow)) {
    if (file.isDir()) recurse(file);
  }
}

Or you could do this, which is equivalent if you (the user) are ignoring
directories themselves and only care about files:

recurse(dir) {
  auto list=dirEntries(dir, shallow);
  sortDirectoriesLast(list);
  foreach (file; list) {
    result~=file;
    if (file.isDir()) recurse(file);
  }
}

This is the 'standard preorder depth-first with sorting' that I described
before.

Or you could offer both these implementations (and the corresponding reversed
ones). For the sorting case, I was merely suggesting that the sort could be put
in the user's control, so they can sort alphabetically or by timestamp or
however they want.

> The other traversal types are likely useful in other situations. I was close to
> instead of using Parent First choosing
> 
> Child First: Give me what is in the Child First before that in the parent. This
> turns the Parent First on its head.

So the above options can be reversed in all possible permutations to give what
you want here.

> > I would argue that that's very specific, not
> > intuitive in the general case, and best implemented using two separate calls to
> > the function with different arguments:
> > 
> > auto firstLevel = dirEntries("a", SpanMode.shallow);
> > foreach (file; firstLevel) {
> >   if (file.isDir()) {
> >     ... = dirEntries(file, SpanMode.preorder);
> >   }
> > }
> 
> This isn't as you described nor what I want. You'll notice all you did was
> create a preorder search where you'll never see the top level directories.

I see, you're reading it as if "..." is the final result, but I guess I meant
to imply that this was user-code and would make use of "firstLevel" directly as
well as later recursing into it. I can't actually remember :)

But yes, I thought you were describing shallow first level followed by preorder
for each child - and if not, then by describing it, I helped you understand
what I misunderstood, so you could help me understand what you actually wanted.
Hopefully. :)

(In reply to comment #6)
> Sorry, you can ignore my code, that's what I get for copy pasting a guess at
> what it would be.

We're even :)

> That would be breadth first, which is close, instead they'd
> need to be some loop that when finished with the files do the same thing for
> the first subdirectory.

Presumably for each subdirectory in turn?

So to conclude, I'd recommend making do with my second example above if it fits
your needs - with obviously the sorting more customisable. But if you think
there's a strong case for the first example, then do it. Remember though that
anyone can get any of these results by writing their own recursive function and
repeatedly calling 'shallow', so I wouldn't go too overboard with different
options. (Consider whether you even want the sorting callback, since again, the
effect can be achieved by just writing it out.)

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------