www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - SpanMode.breadth -- misnomer?

reply %u <wfunction hotmail.com> writes:
It seems to me that the SpanMode.breadth option when enumerating a
directory does not actually do breadth-first search, but rather
performs a kind of depth-first "preorder" traversal.

In other words, to me, this is depth-first "postorder" traversal:

\A
\A\1
\A\1\x
\A\1\y
\A\2
\B
\B\1

whereas this is depth-first "preorder" traversal:

\A\1\x
\A\1\y
\A\1
\A\2
\A
\B\1
\B

and whereas **this** is a true breadth-first traversal:

\A
\B
\A\1
\A\2
\B\1
\A\1\x
\A\1\y


Is that correct, and so is "breadth" actually a misnomer? I found it
really confusing that it didn't work level-by-level.
Mar 12 2011
parent reply spir <denis.spir gmail.com> writes:
On 03/12/2011 10:22 AM, %u wrote:
 It seems to me that the SpanMode.breadth option when enumerating a
 directory does not actually do breadth-first search, but rather
 performs a kind of depth-first "preorder" traversal.

 In other words, to me, this is depth-first "postorder" traversal:

 \A
 \A\1
 \A\1\x
 \A\1\y
 \A\2
 \B
 \B\1

 whereas this is depth-first "preorder" traversal:

 \A\1\x
 \A\1\y
 \A\1
 \A\2
 \A
 \B\1
 \B

 and whereas **this** is a true breadth-first traversal:

 \A
 \B
 \A\1
 \A\2
 \B\1
 \A\1\x
 \A\1\y


 Is that correct, and so is "breadth" actually a misnomer? I found it
 really confusing that it didn't work level-by-level.

You are right about depth / breadth. (But I also have always found preorder/postorder misleading, or rather inversed. For me, the second one should be called postorder, since it postpones app on A after app on A's subnodes. A better, non-misleading, naming may be branch-first (case 1 above) vs children-first (case 2).) Denis -- _________________ vita es estrany spir.wikidot.com
Mar 12 2011
next sibling parent %u <wfunction hotmail.com> writes:
So apparently, it's incredibly hard (if not impossible) to have a true
breadth-first search that scales up reasonably well to, say, an entire
volume of data:
stackoverflow.com/questions/5281626/breadth-first-directory-traversal-
is-it-possible-with-olog-n-memory

I suggest we rename the option to something else and deprecate the
name?
Mar 12 2011
prev sibling parent Stewart Gordon <smjg_1998 yahoo.com> writes:
On 12/03/2011 09:31, spir wrote:
<snip>
 You are right about depth / breadth.

 (But I also have always found preorder/postorder misleading, or rather
inversed. For me,
 the second one should be called postorder, since it postpones app on A after
app on A's
 subnodes.

I agree. Basically: - Preorder means the processing of each node on entry to its subtree (before visiting the children) - Postorder means the processing of each node on exit from its subtree (after visiting the children)
 A better, non-misleading, naming may be branch-first (case 1 above) vs
 children-first (case 2).)

"Branch-first" to me is equally misleading. How about trunk-first and leaves-first? Stewart.
Mar 18 2011