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



195
196
197
198
199
200
201
202
 
# File 'lib/modular_tree/algorithms.rb', line 195

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



169
170
171
172
173
174
 
# File 'lib/modular_tree/algorithms.rb', line 169

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



182
183
184
185
 
# File 'lib/modular_tree/algorithms.rb', line 182

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



93
94
95
96
97
98
99
100
101
102
103
 
# File 'lib/modular_tree/algorithms.rb', line 93

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



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

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



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

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



123
124
125
126
127
128
129
 
# File 'lib/modular_tree/algorithms.rb', line 123

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



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

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



133
134
135
136
137
138
139
140
141
142
 
# File 'lib/modular_tree/algorithms.rb', line 133

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



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

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



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

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)



75
76
77
78
79
80
81
82
83
84
85
 
# File 'lib/modular_tree/algorithms.rb', line 75

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



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

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)] }



152
153
154
155
156
157
158
159
 
# File 'lib/modular_tree/algorithms.rb', line 152

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