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

- %u <wfunction hotmail.com> Mar 12 2011
- spir <denis.spir gmail.com> Mar 12 2011
- %u <wfunction hotmail.com> Mar 12 2011
- Stewart Gordon <smjg_1998 yahoo.com> Mar 18 2011

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