## digitalmars.D - SpanMode.breadth -- misnomer?

- %u (29/29) Mar 12 2011 It seems to me that the SpanMode.breadth option when enumerating a
- spir (11/40) Mar 12 2011 You are right about depth / breadth.
- %u (7/7) Mar 12 2011 So apparently, it's incredibly hard (if not impossible) to have a true
- Stewart Gordon (9/15) Mar 18 2011 I agree. Basically:

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

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

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

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