Class: Jinx::Visitor

Inherits:
Object show all
Defined in:
lib/jinx/helpers/visitor.rb

Overview

Visitor traverses items and applies an operation, e.g.:

class Node
  attr_accessor :children, :value
  def initialize(value, parent=nil)
    @value = value
    @children = []
    @parent = parent
    @parent.children << self if @parent
  end
end
parent = Node.new(1)
child = Node.new(2, parent)
multiplier = 2
Jinx::Visitor.new { |node| node.children }.visit(parent) { |node| node.value *= multiplier } #=> 2
parent.value #=> 2
child.value #=> 4

The visit result is the result of evaluating the operation block on the initial visited node. Visiting a collection returns an array of the result of visiting each member of the collection, e.g. augmenting the preceding example:

parent2 = Node.new(3)
child2 = Node.new(4, parent2)
Jinx::Visitor.new { |node| node.children }.visit([parent, parent2]) { |node| node.value *= multiplier } #=> [2, 6]

Each visit captures the visit result in the visited hash, e.g.:

parent = Node.new(1)
child = Node.new(2, parent)
visitor = Jinx::Visitor.new { |node| node.children }
visitor.visit([parent]) { |node| node.value += 1 }
parent.value #=> 2
visitor.visited[parent] #=> 2
child.value #=> 3
visitor.visited[child] #=> 3

A return from the operation block terminates the visit and exits from the defining scope with the block return value, e.g. given the preceding example:

def increment(parent, limit)
  Jinx::Visitor.new { |node| node.children }.visit(parent) { |node| node.value < limit ? node.value += 1 : return }
end
increment(parent, 2) #=> nil
parent.value #=> 2
child.value #=> 2

The to_enum method allows navigator iteration, e.g.:

Jinx::Visitor.new { |node| node.children }.to_enum(parent).detect { |node| node.value == 2 }

Direct Known Subclasses

ReferenceVisitor, SyncVisitor

Defined Under Namespace

Classes: SyncVisitor, VisitorEnumerator

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(opts = nil) {|parent| ... } ⇒ Visitor

Creates a new Visitor which traverses the child objects returned by the navigator block. The navigator block takes a parent node argument and returns an enumerator on the children to visit.

The options is a symbol, symbol => value hash or nil. A symbol argument is the same as {symbol => true}. Supported options include the following:

  • :depth_first: true, false or a Proc. If the value is a Proc, then value determines whether a child is visited depth-first. See the #visit method for more information.

If the :operator option is set, then the visit operator block is called when a node is visited. The operator block argument is the visited node.

Parameters:

  • opts (Symbol, {Symbol => Object}) (defaults to: nil) —

    the visit options. A symbol argument is the same as symbol => true

Options Hash (opts):

  • :depth_first (String) —

    depth-first traversal

  • :operator (Proc) —

    the operator applied to each visited node

  • :prune_cycle (String) —

    flag indicating whether to exclude cycles to the root in a visit

  • :verbose (Boolean) —

    print navigation log messages

Yields:

  • (parent) —

    returns an enumerator on the children to visit

Yield Parameters:

  • parent —

    the current node

Raises:

  • (ArgumentError) 


82
83
84
85
86
87
88
89
90
91
92
93
 
# File 'lib/jinx/helpers/visitor.rb', line 82

def initialize(opts=nil, &navigator)
  raise ArgumentError.new('Visitor cannot be created without a navigator block') unless block_given?
  @navigator = navigator
  @options = Options.to_hash(opts)
  @depth_first_flag = @options[:depth_first]
  @prune_cycle_flag = @options[:prune_cycle]
  @lineage = []
  @cycles = []
  @visited = {}
  @verbose = Options.get(:verbose, opts, false)
  @exclude = Set.new
end

Instance Attribute Details

#cycles ⇒ Object (readonly)

Returns the value of attribute cycles.



59
60
61
 
# File 'lib/jinx/helpers/visitor.rb', line 59

def cycles
  @cycles
end

#lineage ⇒ Object (readonly)

Returns the value of attribute lineage.



59
60
61
 
# File 'lib/jinx/helpers/visitor.rb', line 59

def lineage
  @lineage
end

#options ⇒ Object (readonly)

Returns the value of attribute options.



59
60
61
 
# File 'lib/jinx/helpers/visitor.rb', line 59

def options
  @options
end

#visited ⇒ Object (readonly)

Returns the value of attribute visited.



59
60
61
 
# File 'lib/jinx/helpers/visitor.rb', line 59

def visited
  @visited
end

Instance Method Details

#clear ⇒ Object (protected)

Resets this visitor’s state in preparation for a new visit.



206
207
208
209
210
211
212
213
 
# File 'lib/jinx/helpers/visitor.rb', line 206

def clear
  # clear the lineage
  @lineage.clear
  # if the visited hash is not shared, then clear it
  @visited.clear unless @options.has_key?(:visited)
  # clear the cycles
  @cycles.clear
end

#current ⇒ Object

Returns the current node being visited.

Returns:

  • the current node being visited



130
131
132
 
# File 'lib/jinx/helpers/visitor.rb', line 130

def current
  @lineage.last
end

#cyclic_nodes(root) ⇒ Array (private)

Returns the non-root nodes in visit cycles.

Examples:

visitor.visit(a)
visit.to_enum #=> [a, b, c, u, v, x, y, z]
visit.cycles #=> [[a, b, u, x, a], [c, z, c]]
visit.cyclic_nodes #=> [b, u, x, c, z]

Returns:

  • (Array) —

    the non-root nodes in visit cycles



247
248
249
250
251
252
253
254
 
# File 'lib/jinx/helpers/visitor.rb', line 247

def cyclic_nodes(root)
  copts = @options.reject { |k, v| k == :prune_cycle }
  cycler = Visitor.new(copts, &@navigator)
  cycler.visit(root)
  cyclic = cycler.cycles.flatten.uniq
  cyclic.delete(root)
  cyclic
end

#depth_first? ⇒ Boolean (private)

Returns whether the depth-first flag is set.

Returns:

  • (Boolean) —

    whether the depth-first flag is set



225
226
227
 
# File 'lib/jinx/helpers/visitor.rb', line 225

def depth_first?
  !!@depth_first_flag
end

#filter {|parent, children| ... } ⇒ Visitor

Returns a new Visitor which determines which nodes to visit by applying the given block to this visitor. The filter block arguments consist of a parent node and an array of children nodes for the parent. The block can return nil, a single node to visit or a collection of nodes to visit.

Examples:

visitor = Jinx::Visitor.new { |person| person.children }
# Joe has age 55 and children aged 17 and 24, who have children aged [1] and [6, 3], resp.
visitor.to_enum(joe) { |person| person.age } #=> [55, 20, 1, 24, 6, 3]
# The filter navigates to the children sorted by age of parents 21 or older.
filter = visitor.filter { |parent, children| children.sort { |c1, c2| c1.age <=> c2.age } if parent.age >= 21 }
filter.to_enum(joe) { |person| person.age } #=> [55, 24, 3, 6]

Yields:

  • (parent, children) —

    the filter to select which of the children to visit next

Yield Parameters:

  • parent —

    the currently visited node

  • children (Array) —

    the nodes slated by this visitor to visit next

Returns:

Raises:

  • (ArgumentError) —

    if a block is not given to this method



198
199
200
201
 
# File 'lib/jinx/helpers/visitor.rb', line 198

def filter
  raise ArgumentError.new("A filter block is not given to the visitor filter method") unless block_given?
  Visitor.new(@options) { |node| yield(node, node_children(node)) }
end

#from ⇒ Object Also known as: parent

Returns the node most recently passed as an argument to this visitor’s navigator block, or nil if visiting the first node.

Returns:

  • the node most recently passed as an argument to this visitor’s navigator block, or nil if visiting the first node



136
137
138
 
# File 'lib/jinx/helpers/visitor.rb', line 136

def from
  @lineage[-2]
end

#node_children(node) ⇒ Object (protected)

Returns the children to visit for the given node.



216
217
218
219
220
 
# File 'lib/jinx/helpers/visitor.rb', line 216

def node_children(node)
  children = @navigator.call(node)
  return Array::EMPTY_ARRAY if children.nil?
  Enumerable === children ? children.to_a.compact : [children]
end

#root ⇒ Object

Returns the top node visited.

Returns:

  • the top node visited



125
126
127
 
# File 'lib/jinx/helpers/visitor.rb', line 125

def root
  @lineage.first
end

#sync {|nodes, others| ... } ⇒ Object

Returns a new visitor that traverses a collection of parent nodes in lock-step fashion using this visitor. The synced #visit method applies the visit operator block to an array of child nodes taken from each parent node, e.g.:

parent1 = Node.new(1)
child11 = Node.new(2, parent1)
child12 = Node.new(3, parent1)
parent2 = Node.new(1)
child21 = Node.new(3, parent2)
Jinx::Visitor.new { |node| node.children }.sync.to_enum.to_a #=> [
 [parent1, parent2],
 [child11, child21],
 [child12, nil]
]

By default, the children are grouped in enumeration order. If a block is given to this method, then the block is called to match child nodes, e.g. using the above example:

visitor = Jinx::Visitor.new { |node| node.children }
synced = visitor.sync { |nodes, others| nodes.to_compact_hash { others.detect { |other| node.value == other.value } } }
synced.to_enum.to_a #=> [
  [parent1, parent2],
  [child11, nil],
  [child12, child21]
]

Yields:

  • (nodes, others) —

    matches node in others (optional)

Yield Parameters:

  • nodes (<Resource>) —

    the visited nodes to match

  • others (<Resource>) —

    the candidates for matching the node



176
177
178
 
# File 'lib/jinx/helpers/visitor.rb', line 176

def sync(&matcher)
  SyncVisitor.new(self, &matcher)
end

#to_enum(node) ⇒ Enumerable

Returns iterator over each visited node.

Returns:

  • (Enumerable) —

    iterator over each visited node



143
144
145
146
147
 
# File 'lib/jinx/helpers/visitor.rb', line 143

def to_enum(node)
  # JRuby could use Generator instead, but that results in dire behavior on any error
  # by crashing with an elided Java lineage trace.
  VisitorEnumerator.new(self, node)
end

#visit(node) {|visited| ... } ⇒ Object

Navigates to node and the children returned by this Visitor’s navigator block. Applies the optional operator block to each child node if the block is given to this method. Returns the result of the operator block if given, or the node itself otherwise.

The nodes to visit from a parent node are determined in the following sequence:

  • Return if the parent node has already been visited.

  • If depth_first, then call the navigator block defined in the initializer on the parent node and visit each child node.

  • Visit the parent node.

  • If not depth-first, then call the navigator block defined in the initializer on the parent node and visit each child node.

The :depth option value constrains child traversal to that number of levels.

This method first clears the visited hash, unless the :visited option was set in the initializer.

Parameters:

  • node —

    the root object to visit

Yields:

  • (visited) —

    an operator applied to each visited object

Yield Parameters:

  • visited —

    the object currently being visited

Returns:

  • the result of the yield block on node, or node itself if no block is given



114
115
116
 
# File 'lib/jinx/helpers/visitor.rb', line 114

def visit(node, &operator)
  visit_root(node, &operator)
end

#visit_children(parent, &operator) ⇒ Object (private) 



298
299
300
 
# File 'lib/jinx/helpers/visitor.rb', line 298

def visit_children(parent, &operator)
  @navigator.call(parent).enumerate { |child| visit_recursive(child, &operator) }
end

#visit_node_and_children(node) {|visited| ... } ⇒ Object (private)

Visits the given node and its children. If this visitor is ##depth_first?, then the operator is applied to the children before the given node. Otherwise, the operator is applied to the children after the given node. The default operator returns the visited node itself.

Parameters:

  • node —

    the node to visit

Yields:

  • (visited) —

    an operator applied to each visited object

Yield Parameters:

  • visited —

    the object currently being visited



283
284
285
286
287
288
289
290
291
292
293
294
295
296
 
# File 'lib/jinx/helpers/visitor.rb', line 283

def visit_node_and_children(node, &operator)
  # set the current node
  @lineage.push(node)
  # if depth-first, then visit the children before the current node
  visit_children(node, &operator) if depth_first?
  # apply the operator to the current node, if given
  result = @visited[node] = block_given? ? yield(node) : node
  logger.debug { "#{self} visited #{node.qp} with result #{result.qp}" } if @verbose
  # if not depth-first, then visit the children after the current node
  visit_children(node, &operator) unless depth_first?
  @lineage.pop
  # return the visit result
  result
end

#visit_recursive(node, &operator) ⇒ Object (private) 



256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
 
# File 'lib/jinx/helpers/visitor.rb', line 256

def visit_recursive(node, &operator)
  # bail if no node or the node is specifically excluded
  return if node.nil? or @exclude.include?(node)
  # return the visited value if the node has already been visited
  if @visited.has_key?(node) then
    #capture a cycle
    index = @lineage.index(node)
    if index then
      cycle = @lineage[index..-1] << node
      @cycles << cycle
    end
    return @visited[node]
  end
  # return nil if the node has not been visited but has been navigated in a depth-first visit
  return if @lineage.include?(node)
  # all systems go: visit the node graph
  visit_node_and_children(node, &operator)
end

#visit_root(node, &operator) ⇒ Object (private)

Visits the root node and all descendants.



230
231
232
233
234
235
236
237
238
239
 
# File 'lib/jinx/helpers/visitor.rb', line 230

def visit_root(node, &operator)
  clear
  # Exclude cycles if the prune cycles flag is set. 
  @exclude.merge!(cyclic_nodes(node)) if @prune_cycle_flag 
  # Visit the root node.
  result = visit_recursive(node, &operator)
  # Reset the exclusions if the prune cycles flag is set.
  @exclude.clear if @prune_cycle_flag 
  result
end

#visited?(node) ⇒ Boolean

Returns whether the node was visited.

Parameters:

  • node —

    the node to check

Returns:

  • (Boolean) —

    whether the node was visited



120
121
122
 
# File 'lib/jinx/helpers/visitor.rb', line 120

def visited?(node)
  @visited.has_key?(node)
end