Module: TDiff

Defined in:
lib/tdiff/tdiff.rb,
lib/tdiff/version.rb,
lib/tdiff/unordered.rb

Overview

TDiff adds the ability to calculate the differences between two tree-like objects. Simply include TDiff into the class which represents the tree nodes and define the #tdiff_each_child and #tdiff_equal methods.

Defined Under Namespace

Modules: Unordered

Constant Summary collapse

VERSION = 
'0.3.4'

Instance Method Summary collapse

Instance Method Details

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

Finds the differences between self and another tree.

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.



51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
# File 'lib/tdiff/tdiff.rb', line 51

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

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

  yield ' ', self

  tdiff_recursive(tree,&block)
  return self
end

#tdiff_each_child(node) {|child| ... } ⇒ Object

Default method which will enumerate over every child of a parent node.

Parameters:

  • node (Object) —

    The parent node.

Yields:

  • (child) —

    The given block will be passed each child of the parent node.



16
17
18
 
# File 'lib/tdiff/tdiff.rb', line 16

def tdiff_each_child(node,&block)
  node.each(&block) if node.kind_of?(Enumerable)
end

#tdiff_equal(node) ⇒ Boolean

Default method which compares nodes.

Parameters:

  • node (Object) —

    A node from the new tree.

Returns:

  • (Boolean) —

    Specifies whether the nodes are equal.



29
30
31
 
# File 'lib/tdiff/tdiff.rb', line 29

def tdiff_equal(node)
  self == node
end

#tdiff_recursive(tree) {|change, node| ... } ⇒ Object (protected)

Recursively compares the differences between the children nodes.

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.

Since:

  • 0.3.2



86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
 
# File 'lib/tdiff/tdiff.rb', line 86

def tdiff_recursive(tree,&block)
  c = Hash.new { |hash,key| hash[key] = Hash.new(0) }
  x = enum_for(:tdiff_each_child,self)
  y = enum_for(:tdiff_each_child,tree)

  x.each_with_index do |xi,i|
    y.each_with_index do |yj,j|
      c[i][j] = if xi.tdiff_equal(yj)
                  c[i-1][j-1] + 1
                else
                  if c[i][j-1] > c[i-1][j]
                    c[i][j-1]
                  else
                    c[i-1][j]
                  end
                end
    end
  end

  unchanged = []
  changes = []

  x_backtrack = x.each_with_index.reverse_each
  y_backtrack = y.each_with_index.reverse_each

  next_child = lambda { |children|
    begin
      children.next
    rescue StopIteration
      # end of iteration, return a -1 index
      [nil, -1]
    end
  }

  xi, i = next_child[x_backtrack]
  yj, j = next_child[y_backtrack]

  until (i == -1 && j == -1)
    if (i != -1 && j != -1 && xi.tdiff_equal(yj))
      changes.unshift [' ', xi]
      unchanged.unshift [xi, yj]

      xi, i = next_child[x_backtrack]
      yj, j = next_child[y_backtrack]
    else
      if (j >= 0 && (i == -1 || c[i][j-1] >= c[i-1][j]))
        changes.unshift ['+', yj]

        yj, j = next_child[y_backtrack]
      elsif (i >= 0 && (j == -1 || c[i][j-1] < c[i-1][j]))
        changes.unshift ['-', xi]

        xi, i = next_child[x_backtrack]
      end
    end
  end

  # explicitly discard the c matrix
  c = nil

  # sequentially iterate over the changed nodes
  changes.each(&block)
  changes = nil

  # recurse down through unchanged nodes
  unchanged.each { |a,b| a.tdiff_recursive(b,&block) }
  unchanged = nil
end