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 argument is described in Options.get.

Options Hash (opts):

  • :depth_first (Boolean) —

    depth-first traversal

  • :prune_cycle (Boolean) —

    flag indicating whether to exclude cycles 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) 


71
72
73
74
75
76
77
78
79
80
81
 
# File 'lib/jinx/helpers/visitor.rb', line 71

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 = []
  @visited = {}
  @verbose = Options.get(:verbose, opts, false)
  @exclude = Set.new
end

Instance Attribute Details

#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.



194
195
196
197
198
199
 
# File 'lib/jinx/helpers/visitor.rb', line 194

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

#current ⇒ Object 



118
119
120
 
# File 'lib/jinx/helpers/visitor.rb', line 118

def current
  @lineage.last
end

#cyclic_nodes(root) ⇒ Array (private)

Returns the nodes which occur within a cycle, excluding the cycle entry point.

Examples:

graph.paths #=> a -> b -> a, a -> c -> d -> c
Visitor.new(graph, &navigator).cyclic_nodes(a) #=> [b, d]



234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
 
# File 'lib/jinx/helpers/visitor.rb', line 234

def cyclic_nodes(root)
  copts = @options.reject { |k, v| k == :prune_cycle }
  cyclic = Set.new
  cycler = Visitor.new(copts) do |parent|
    children = @navigator.call(parent)
    # Look for a cycle back to the child.
    children.each do |child|
      index = cycler.lineage.index(child)
      if index then
        # The child is also a parent: add the nodes between
        # the two occurrences of the child in the lineage.
        cyclic.merge!(cycler.lineage[(index + 1)..-1])
      end
    end
    children
  end
  cycler.visit(root)
  cyclic
end

#depth_first? ⇒ Boolean (private) 



211
212
213
 
# File 'lib/jinx/helpers/visitor.rb', line 211

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

Raises:

  • (ArgumentError) —

    if a block is not given to this method



186
187
188
189
 
# File 'lib/jinx/helpers/visitor.rb', line 186

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

#from ⇒ Object Also known as: parent 



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

def from
  @lineage[-2]
end

#node_children(node) ⇒ Object (protected)

Returns the children to visit for the given node.



202
203
204
205
206
 
# File 'lib/jinx/helpers/visitor.rb', line 202

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 



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

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



164
165
166
 
# File 'lib/jinx/helpers/visitor.rb', line 164

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

#to_enum(node) ⇒ Enumerable 



131
132
133
134
135
 
# File 'lib/jinx/helpers/visitor.rb', line 131

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.

Yields:

  • (visited) —

    an operator applied to each visited object

Yield Parameters:

  • visited —

    the object currently being visited



102
103
104
 
# File 'lib/jinx/helpers/visitor.rb', line 102

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

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



289
290
291
 
# File 'lib/jinx/helpers/visitor.rb', line 289

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.

Yields:

  • (visited) —

    an operator applied to each visited object

Yield Parameters:

  • visited —

    the object currently being visited



274
275
276
277
278
279
280
281
282
283
284
285
286
287
 
# File 'lib/jinx/helpers/visitor.rb', line 274

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) 



254
255
256
257
258
259
260
261
262
263
264
 
# File 'lib/jinx/helpers/visitor.rb', line 254

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.
  return @visited[node] if @visited.has_key?(node)
  # 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 subgraph.
  visit_node_and_children(node, &operator)
end

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

Visits the root node and all descendants.



216
217
218
219
220
221
222
223
224
225
 
# File 'lib/jinx/helpers/visitor.rb', line 216

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 



108
109
110
 
# File 'lib/jinx/helpers/visitor.rb', line 108

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