Module: TDiff::Unordered

Defined in:
lib/tdiff/unordered.rb

Overview

Calculates the differences between two trees, without respecting the order of children nodes.

Class Method Summary collapse

Instance Method Summary collapse

Class Method Details

.included(base) ⇒ Object

Includes TDiff.



12
13
14
 
# File 'lib/tdiff/unordered.rb', line 12

def self.included(base)
  base.send :include, TDiff
end

Instance Method Details

#tdiff_unordered(tree) {|change, node| ... } ⇒ Enumerator

Finds the differences between self and another tree, not respecting the ordering of children.

Parameters:

Yields:

  • (change, node) —

    The given block will be passed the added or removed nodes.

Yield Parameters:

  • change (' ', '+', '-') —

    The state-change of the node.

  • node (Object) —

    A node from one of the two trees.

Returns:

  • (Enumerator) —

    If no block is given, an Enumerator object will be returned.

Since:

  • 0.2.0



37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
 
# File 'lib/tdiff/unordered.rb', line 37

def tdiff_unordered(tree,&block)
  return enum_for(:tdiff_unordered,tree) unless block

  # check if the nodes differ
  unless tdiff_equal(tree)
    yield '-', self
    yield '+', tree
    return self
  end

  x = enum_for(:tdiff_each_child,self)
  y = enum_for(:tdiff_each_child,tree)

  unchanged = {}
  changes = []

  x.each_with_index do |xi,i|
    y.each_with_index do |yj,j|
      if (!unchanged.has_value?(yj) && xi.tdiff_equal(yj))
        unchanged[xi] = yj
        changes << [i, ' ', xi]
        break
      end
    end

    unless unchanged.has_key?(xi)
      changes << [i, '-', xi]
    end
  end

  y.each_with_index do |yj,j|
    unless unchanged.has_value?(yj)
      changes << [j, '+', yj]
    end
  end

  # order the changes by index to match the behavior of `tdiff`
  changes.sort_by { |change| change[0] }.each do |index,change,node|
    yield change, node
  end

  # explicitly release the changes variable
  changes = nil

  # recurse down the unchanged nodes
  unchanged.each { |xi,yj| xi.tdiff_unordered(yj,&block) }
  unchanged = nil

  return self
end