`Object#by_depth`

`child_spec`=`nil`, *`args`, &`child_proc``Object#by_breadth`

`child_spec`=`nil`, *`args`, &`child_proc`

Allows use of `Enumerable`

methods, such as `each`

, `collect`

,
`select`

, etc., to iterate over objects which have a caller-specified tree
structure (or, more generally, directed acyclic graph structure). The caller
defines this structure by providing a way of calculating the children of each
object, such as an accessor method for the array of children of a node in a
tree.

In order to yield a sequence of objects, the nonlinear structure of the tree is
linearized in either a depth-first or a breadth-first way, depending on the
method used, `by_depth`

or `by_breadth`

. In a depth-first
linearization, the iteration visits a node's children before continuing with
the node's successive siblings. In a breadth-first linearization, the iteration
visits all siblings before visiting any of their children. In either case, the
parent is visited before its children, and the children are visited in an order
consistent with their order in the sequence of children provided by their
parent.

Speaking loosely, one can think of a depth-first iteration as working branch by branch and a breadth-first iteration as working level by level, where a level consists of nodes of equal depth.

require 'enum/tree' for node in root.by_depth :a_method, ... for node in root.by_depth a_proc, ... for node in root.by_depth { |node| ... return children } # by_breadth has the same form

The means of accessing the children of each node is specified in the
argument list with a method name, a block, or an object that responds to
`[]`

, such as a proc or a hash. In any case, the value returned must be an
`Enumerable`

object, typically an array.

If `child_spec`

is a string or symbol, `child_proc`

is ignored and
`child_spec`

is treated as a method name. This method name is sent, along
with arguments `args`

, to each node to generate the children. The node is
considered childless when the method returns `nil`

or `false`

or an empty collection.

If `child_spec`

is anything else, except `nil`

, `child_proc`

is
ignored and `child_spec`

is required to be an object that responds to
`[]`

, such as a proc or a hash. The `[]`

method of `child_spec`

is
called with each node as an argument, along with `args`

, to generate the
children. The node is considered childless when `[]`

returns `nil`

or
`false`

or an empty collection.

If `child_spec`

is not given, or is `nil`

, a block is required. In this
case, the block is converted to a proc and iteration proceeds as in the
preceding paragraph.

The return value is not an array, but an `Enumerable`

object that refers
to the original objects. In this sense, `Object#by_depth`

and
`Object#by_breadth`

are *delegators*. Typically, `by_depth`

and
`by_breadth`

are used with the `for ... in ...`

construct, or
(equivalently) with `each`

, or with `collect`

, `select`

, and so on.
In these cases, the dependence on the original data structure does not matter.
To get the array of entries produced by `by_depth`

or `by_breadth`

as
an independent data structure, use `Enumerable#entries`

or
`Enumerable#to_a`

.

If a node occurs as the child of two different parent nodes, the structure is
not a tree. As long as no node is its own ancestor, these methods still produce
a useful interation (it is the caller's responsibility to avoid cycles). The
structure in this case is sometimes called a *directed acyclic graph*. In a
depth-first iteration, a node with two parents will be reached twice. In a
breadth-first iteration, a node with two parents will be reaced once if the
parents are at the same depth in the graph, but twice otherwise.

The `Object#by_depth`

method accepts two modifiers that affect the yielded
values, but not the order of iteration:

for node, ancestors in tree.by_depth(...).with_ancestors for branch in tree.by_depth(...).branches

The `with_ancestors`

modifier results in the same linearization, but
returns, along with each node, the node's array of ancestors, starting with the
root of the tree and ending with the immediate parent. In the non-tree case, the
ancestor list doesn't contain all ancestors, but just one path from the root to
the node. Each such path will occur once during the `by_depth`

iteration.

With the `branches`

modifier, the iteration yields all branches of the tree
(or directed acyclic graph). A *branch* is a path from the root to a leaf
node.

Note that a `with_ancestors`

iteration yields at every node, but a
`branches`

iteration yields only at leaf nodes.

Pruning the iteration means skipping a node and its descendants and continuing
with the nodes that would normally follow them in the iteration. This can be
done anywhere in dynamic scope during the iteration by simply throwing the
`:prune`

symbol:

throw :prune

If an additional integer argument is supplied:

throw :prune, n

then the pruning occurs not at the current node, but at the node `n`

levels
above the current node in the current ancestor list.

Note that `prune`

cannot used with the `each_branch`

modifier discussed
above; `prune`

simply has no useful meaning in this context.

require 'enum/tree' # Define a proc to compute the subclasses of a class # It would probably be better to make this a method of Class # and to implement it more efficiently, but for illustration... subclasses = proc { |cl| subs = [] ObjectSpace.each_object(Class) { |sub| if sub.superclass == cl then subs << sub end } subs } print "Subclasses of Numeric:\n" for node in Numeric.by_depth subclasses print node, " " end # prints: # Subclasses of Numeric: # Numeric Float Integer Bignum Fixnum puts "\n\nBranches:" for branch in Numeric.by_depth(subclasses).branches p branch end # prints: # Branches: # [Numeric, Float] # [Numeric, Integer, Bignum] # [Numeric, Integer, Fixnum] puts "\nNodes with ancestors:" for x, a in Numeric.by_depth(subclasses).with_ancestors print "\t"*a.size, "node is #{x}, ancestors is #{a.inspect}.\n" end # prints: # Nodes with ancestors: # node is Numeric, ancestors is []. # node is Float, ancestors is [Numeric]. # node is Integer, ancestors is [Numeric]. # node is Bignum, ancestors is [Numeric, Integer]. # node is Fixnum, ancestors is [Numeric, Integer].

See the end of the source file for more examples.

Enumerable tools 1.4

The current version of this software can be found at http://redshift.sourceforge.net/enum .

This software is distributed under the Ruby license. See http://www.ruby-lang.org.

Joel VanderWerf, vjoel@sourceforge.net