Module: Tree::DownTreeFilteredAlgorithms

Includes:
BranchesProperty, NodeProperty
Included in:
ArrayTree, DownTreeAlgorithms, FilteredArrayTree
Defined in:
lib/modular_tree/algorithms.rb

Overview

A down tree can only be traversed top-down as it has no reference to its parent. It is also a kind of a graph node

TODO: Turn into class methods to implement array/hash/other adaptors.

#children should then be called as 'children(node)' everywhere

A #node method should also be defined at the top-most level

TODO: Better split between DownTreeAlgorithms and DownTreeFilteredAlgorithms

Class Method Summary collapse

Instance Method Summary collapse

Methods included from BranchesProperty

#bare?, #branches, #each_branch

Methods included from NodeProperty

#node, #node_value

Class Method Details

.filter(*args) ⇒ Object

Create a Tree::Filter object. Can also take an existing filter as argument in which case the given filter will just be passed through



200
201
202
203
204
205
206
207
 
# File 'lib/modular_tree/algorithms.rb', line 200

def self.filter(*args)
  if args.first.is_a?(Filter)
    args.size == 1 or raise ArgumentError
    args.first
  else
    Filter.new(*args)
  end
end

Instance Method Details

#accumulate(*filter, accumulator, this: true, &block) ⇒ Object

Traverse the tree top-down while accumulating information in an accumulator object. The block takes a [accumulator, node] tuple and is responsible for adding itself to the accumulator. The return value from the block is then used as the accumulator for the branch nodes. Note that it returns the original accumulator and not the final result - this makes it different from #inject

#accumulate is a kind of “preorder” algorithm



174
175
176
177
178
179
 
# File 'lib/modular_tree/algorithms.rb', line 174

def accumulate(*filter, accumulator, this: true, &block)
  filter = self.class.filter(*filter)
  block_given? or raise ArgumentError, "Block is required"
  do_accumulate(filter, this, accumulator, &block)
  accumulator
end

#aggregate(*filter, this: true, &block) ⇒ Object

Traverse the tree bottom-up while aggregating information. The block is called with a [current-node, branch-node-results] tuple

#aggregate is a kind of “postorder” algorithm

TODO: Remove this flag - it not used and doesn’t make sense



187
188
189
190
 
# File 'lib/modular_tree/algorithms.rb', line 187

def aggregate(*filter, this: true, &block)
  filter = self.class.filter(*filter)
  do_aggregate(filter, this, &block)
end

#choose(*expr, &block) ⇒ Object

Filter children. Doesn’t recurse. If a block is given, it should return truish to select a child node

The match expression can also be a list of classes (instead of an array of classes)

TODO: Maybe make #children an Array extended with filtering



98
99
100
101
102
103
104
105
106
107
108
 
# File 'lib/modular_tree/algorithms.rb', line 98

def choose(*expr, &block)
  !block_given? || expr.empty? or raise ArgumentError, "Can't use both match expression and block"
  if block_given?
    each_branch.select { |branch| yield branch }
  elsif !expr.empty?
    matcher = Matcher.new(*expr, &block)
    each_branch.select { |branch| matcher.match? branch }
  else
    each
  end
end

#descendants(*filter) ⇒ Object

Enumerator of descendant nodes matching filter. Same as #preorder with :this set to false. TODO: Maybe introduce forrests: tree.forrest.each



67
 
# File 'lib/modular_tree/algorithms.rb', line 67

def descendants(*filter) = each(filter, this: false)

#each(*filter, this: true, &block) ⇒ Object

Implementation of Enumerable#each extended with filters. The block is called with value, key, and parent as arguments but it may choose to ignore the key and/or parent argument. Returns an enumerator of values without a block



73
 
# File 'lib/modular_tree/algorithms.rb', line 73

def each(*filter, this: true, &block) = common_each(*filter, :node_value, :do_each_preorder, this, &block)

#edges(*filter, this: true, &block) ⇒ Object

Enumerator of edges in the tree. Edges are [previous-matching-node, matching-node] tuples. Top-level nodes have previous-matching-node set to nil (the result is a forrest). If the filter matches all nodes the value is an edge-representation of the tree



128
129
130
131
132
133
134
 
# File 'lib/modular_tree/algorithms.rb', line 128

def edges(*filter, this: true, &block)
  if block_given?
    each(*filter, this: this) { |node, _, parent| yield parent, node }
  else
    Pairs.new { |enum| each(*filter, this: this) { |node, _, parent| enum << [parent, node] } }
  end
end

#nodes(*filter, this: true, &block) ⇒ Object

Like #each but the block is called with node, key, and parent instead of value, key, and parent



112
 
# File 'lib/modular_tree/algorithms.rb', line 112

def nodes(*filter, this: true, &block) = common_each(*filter, :node, :do_each_preorder, this, &block)

#pairs(first_match_expr, second_match_expr, this: true) ⇒ Object

Return array of [previous-matching-node, matching-node] tuples. Returns the empty array iff there is no matching set of nodes



138
139
140
141
142
143
144
145
146
147
 
# File 'lib/modular_tree/algorithms.rb', line 138

def pairs(first_match_expr, second_match_expr, this: true)
  first_matcher = Matcher.new(first_match_expr)
  second_matcher = Matcher.new(second_match_expr)
  or_matcher = first_matcher | second_matcher # avoids re-computing this value over and over
  result = []
  nodes(first_matcher, false, this: this) { |node|
    node.do_pairs(result, first_matcher, or_matcher)
  }
  result
end

#postorder(*filter, this: true) ⇒ Object

Post-order enumerator of selected nodes



118
 
# File 'lib/modular_tree/algorithms.rb', line 118

def postorder(*filter, this: true) = common_each(*filter, :node_value, :each_postorder, this)

#preorder(*filter, this: true) ⇒ Object

Pre-order enumerator of selected nodes. Same as #each without a block



115
 
# File 'lib/modular_tree/algorithms.rb', line 115

def preorder(*filter, this: true) = each(*filter, this: this)

#select(*expr, this: true, &block) ⇒ Object

Implementation of Enumerable#select extended with a single filter. As #each, the block is called with value, key, and parent arguments

The match expression can also be a list of classes (instead of an array of classes)



80
81
82
83
84
85
86
87
88
89
90
 
# File 'lib/modular_tree/algorithms.rb', line 80

def select(*expr, this: true, &block)
  !block_given? || expr.empty? or raise ArgumentError, "Can't use both match expression and block"
  if block_given?
    each.select { |branch| yield branch }
  elsif !expr.empty?
    matcher = Matcher.new(*expr, &block)
    each.select { |branch| matcher.match? branch }
  else
    each
  end
end

#size ⇒ Object

The number of nodes in the tree. Note that this can be an expensive operation because every node has to be visited



63
 
# File 'lib/modular_tree/algorithms.rb', line 63

def size = 1 + descendants.to_a.size

#traverse(*filter, this: true, &traverse_block) ⇒ Object

Find nodes matching filter and call traverse_block with a node and a block argument. traverse_block can recurse into children by calling the supplied inner block

An example of how to create a nested array implementation:

root.traverse(true) { |node, inner| [node, inner.call(node)] }



157
158
159
160
161
162
163
164
 
# File 'lib/modular_tree/algorithms.rb', line 157

def traverse(*filter, this: true, &traverse_block)
  filter = self.class.filter(*filter)
  inner_block_proxy = [nil] # Hack because you can't refer to a lambda within its declaration
  inner_block = inner_block_proxy[0] = lambda { |node|
    node.nodes(filter, this: false).map { |n| traverse_block.call(n, inner_block_proxy.first) }
  }
  nodes(filter, this: this).map { |node| traverse_block.call(node, inner_block) }
end