1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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
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
|
# frozen_string_literal: true
require_relative 'tdiff'
module TDiff
#
# Calculates the differences between two trees, without respecting the
# order of children nodes.
#
module Unordered
#
# Includes {TDiff}.
#
def self.included(base)
base.send :include, TDiff
end
#
# Finds the differences between `self` and another tree, not respecting
# the order of the nodes.
#
# @param [#tdiff_each_child] tree
# The other tree.
#
# @yield [change, node]
# The given block will be passed the added or removed nodes.
#
# @yieldparam [' ', '+', '-'] change
# The state-change of the node.
#
# @yieldparam [Object] node
# A node from one of the two trees.
#
# @return [Enumerator]
# If no block is given, an Enumerator object will be returned.
#
# @since 0.2.0
#
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
yield ' ', self
tdiff_recursive_unordered(tree,&block)
return self
end
protected
#
# Recursively compares the differences between the children nodes,
# without respecting the order of the nodes.
#
# @param [#tdiff_each_child] tree
# The other tree.
#
# @yield [change, node]
# The given block will be passed the added or removed nodes.
#
# @yieldparam [' ', '+', '-'] change
# The state-change of the node.
#
# @yieldparam [Object] node
# A node from one of the two trees.
#
# @since 0.3.2
#
def tdiff_recursive_unordered(tree,&block)
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 do |xi,yj|
xi.tdiff_recursive_unordered(yj,&block)
end
unchanged = nil
end
end
end
|
