blob: e09afc3db6dc1e7e54f182acbdbac12f8c8de900 (
plain)
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
119
120
121
122
123
124
125
126
127
128
129
130
131
|
# frozen_string_literal: true
=begin
= Diff
(({diff.rb})) - computes the differences between two arrays or
strings. Copyright (C) 2001 Lars Christensen
== Synopsis
diff = Diff.new(a, b)
b = a.patch(diff)
== Class Diff
=== Class Methods
--- Diff.new(a, b)
--- a.diff(b)
Creates a Diff object which represent the differences between
((|a|)) and ((|b|)). ((|a|)) and ((|b|)) can be either be arrays
of any objects, strings, or object of any class that include
module ((|Diffable|))
== Module Diffable
The module ((|Diffable|)) is intended to be included in any class for
which differences are to be computed. Diffable is included into String
and Array when (({diff.rb})) is (({require}))'d.
Classes including Diffable should implement (({[]})) to get element at
integer indices, (({<<})) to append elements to the object and
(({ClassName#new})) should accept 0 arguments to create a new empty
object.
=== Instance Methods
--- Diffable#patch(diff)
Applies the differences from ((|diff|)) to the object ((|obj|))
and return the result. ((|obj|)) is not changed. ((|obj|)) and
can be either an array or a string, but must match the object
from which the ((|diff|)) was created.
=end
module Redmine
module StringArrayDiff
module Diffable
def diff(b)
Redmine::StringArrayDiff::Diff.new(self, b)
end
# Create a hash that maps elements of the array to arrays of indices
# where the elements are found.
def reverse_hash(range = (0...self.length))
revmap = {}
range.each { |i|
elem = self[i]
if revmap.has_key? elem
revmap[elem].push i
else
revmap[elem] = [i]
end
}
return revmap
end
def replacenextlarger(value, high = nil)
high ||= self.length
if self.empty? || value > self[-1]
push value
return high
end
# binary search for replacement point
low = 0
while low < high
index = (high+low)/2
found = self[index]
return nil if value == found
if value > found
low = index + 1
else
high = index
end
end
self[low] = value
# $stderr << "replace #{value} : 0/#{low}/#{init_high} (#{steps} steps) (#{init_high-low} off )\n"
# $stderr.puts self.inspect
# gets
# p length - low
return low
end
def patch(diff)
newary = nil
if diff.difftype == String
newary = diff.difftype.new('')
else
newary = diff.difftype.new
end
ai = 0
bi = 0
diff.diffs.each { |d|
d.each { |mod|
case mod[0]
when '-'
while ai < mod[1]
newary << self[ai]
ai += 1
bi += 1
end
ai += 1
when '+'
while bi < mod[1]
newary << self[ai]
ai += 1
bi += 1
end
newary << mod[2]
bi += 1
else
raise "Unknown diff action"
end
}
}
while ai < self.length
newary << self[ai]
ai += 1
bi += 1
end
return newary
end
end
end
end
|
