annotate .svn/pristine/79/7998baf8e95a22a5aa2950bf21a5c4bff46e87b8.svn-base @ 1298:4f746d8966dd redmine_2.3_integration

Merge from redmine-2.3 branch to create new branch redmine-2.3-integration
author Chris Cannam
date Fri, 14 Jun 2013 09:28:30 +0100
parents 622f24f53b42
children
rev   line source
Chris@1295 1 module RedmineDiff
Chris@1295 2 class Diff
Chris@1295 3
Chris@1295 4 VERSION = 0.3
Chris@1295 5
Chris@1295 6 def Diff.lcs(a, b)
Chris@1295 7 astart = 0
Chris@1295 8 bstart = 0
Chris@1295 9 afinish = a.length-1
Chris@1295 10 bfinish = b.length-1
Chris@1295 11 mvector = []
Chris@1295 12
Chris@1295 13 # First we prune off any common elements at the beginning
Chris@1295 14 while (astart <= afinish && bstart <= afinish && a[astart] == b[bstart])
Chris@1295 15 mvector[astart] = bstart
Chris@1295 16 astart += 1
Chris@1295 17 bstart += 1
Chris@1295 18 end
Chris@1295 19
Chris@1295 20 # now the end
Chris@1295 21 while (astart <= afinish && bstart <= bfinish && a[afinish] == b[bfinish])
Chris@1295 22 mvector[afinish] = bfinish
Chris@1295 23 afinish -= 1
Chris@1295 24 bfinish -= 1
Chris@1295 25 end
Chris@1295 26
Chris@1295 27 bmatches = b.reverse_hash(bstart..bfinish)
Chris@1295 28 thresh = []
Chris@1295 29 links = []
Chris@1295 30
Chris@1295 31 (astart..afinish).each { |aindex|
Chris@1295 32 aelem = a[aindex]
Chris@1295 33 next unless bmatches.has_key? aelem
Chris@1295 34 k = nil
Chris@1295 35 bmatches[aelem].reverse.each { |bindex|
Chris@1295 36 if k && (thresh[k] > bindex) && (thresh[k-1] < bindex)
Chris@1295 37 thresh[k] = bindex
Chris@1295 38 else
Chris@1295 39 k = thresh.replacenextlarger(bindex, k)
Chris@1295 40 end
Chris@1295 41 links[k] = [ (k==0) ? nil : links[k-1], aindex, bindex ] if k
Chris@1295 42 }
Chris@1295 43 }
Chris@1295 44
Chris@1295 45 if !thresh.empty?
Chris@1295 46 link = links[thresh.length-1]
Chris@1295 47 while link
Chris@1295 48 mvector[link[1]] = link[2]
Chris@1295 49 link = link[0]
Chris@1295 50 end
Chris@1295 51 end
Chris@1295 52
Chris@1295 53 return mvector
Chris@1295 54 end
Chris@1295 55
Chris@1295 56 def makediff(a, b)
Chris@1295 57 mvector = Diff.lcs(a, b)
Chris@1295 58 ai = bi = 0
Chris@1295 59 while ai < mvector.length
Chris@1295 60 bline = mvector[ai]
Chris@1295 61 if bline
Chris@1295 62 while bi < bline
Chris@1295 63 discardb(bi, b[bi])
Chris@1295 64 bi += 1
Chris@1295 65 end
Chris@1295 66 match(ai, bi)
Chris@1295 67 bi += 1
Chris@1295 68 else
Chris@1295 69 discarda(ai, a[ai])
Chris@1295 70 end
Chris@1295 71 ai += 1
Chris@1295 72 end
Chris@1295 73 while ai < a.length
Chris@1295 74 discarda(ai, a[ai])
Chris@1295 75 ai += 1
Chris@1295 76 end
Chris@1295 77 while bi < b.length
Chris@1295 78 discardb(bi, b[bi])
Chris@1295 79 bi += 1
Chris@1295 80 end
Chris@1295 81 match(ai, bi)
Chris@1295 82 1
Chris@1295 83 end
Chris@1295 84
Chris@1295 85 def compactdiffs
Chris@1295 86 diffs = []
Chris@1295 87 @diffs.each { |df|
Chris@1295 88 i = 0
Chris@1295 89 curdiff = []
Chris@1295 90 while i < df.length
Chris@1295 91 whot = df[i][0]
Chris@1295 92 s = @isstring ? df[i][2].chr : [df[i][2]]
Chris@1295 93 p = df[i][1]
Chris@1295 94 last = df[i][1]
Chris@1295 95 i += 1
Chris@1295 96 while df[i] && df[i][0] == whot && df[i][1] == last+1
Chris@1295 97 s << df[i][2]
Chris@1295 98 last = df[i][1]
Chris@1295 99 i += 1
Chris@1295 100 end
Chris@1295 101 curdiff.push [whot, p, s]
Chris@1295 102 end
Chris@1295 103 diffs.push curdiff
Chris@1295 104 }
Chris@1295 105 return diffs
Chris@1295 106 end
Chris@1295 107
Chris@1295 108 attr_reader :diffs, :difftype
Chris@1295 109
Chris@1295 110 def initialize(diffs_or_a, b = nil, isstring = nil)
Chris@1295 111 if b.nil?
Chris@1295 112 @diffs = diffs_or_a
Chris@1295 113 @isstring = isstring
Chris@1295 114 else
Chris@1295 115 @diffs = []
Chris@1295 116 @curdiffs = []
Chris@1295 117 makediff(diffs_or_a, b)
Chris@1295 118 @difftype = diffs_or_a.class
Chris@1295 119 end
Chris@1295 120 end
Chris@1295 121
Chris@1295 122 def match(ai, bi)
Chris@1295 123 @diffs.push @curdiffs unless @curdiffs.empty?
Chris@1295 124 @curdiffs = []
Chris@1295 125 end
Chris@1295 126
Chris@1295 127 def discarda(i, elem)
Chris@1295 128 @curdiffs.push ['-', i, elem]
Chris@1295 129 end
Chris@1295 130
Chris@1295 131 def discardb(i, elem)
Chris@1295 132 @curdiffs.push ['+', i, elem]
Chris@1295 133 end
Chris@1295 134
Chris@1295 135 def compact
Chris@1295 136 return Diff.new(compactdiffs)
Chris@1295 137 end
Chris@1295 138
Chris@1295 139 def compact!
Chris@1295 140 @diffs = compactdiffs
Chris@1295 141 end
Chris@1295 142
Chris@1295 143 def inspect
Chris@1295 144 @diffs.inspect
Chris@1295 145 end
Chris@1295 146
Chris@1295 147 end
Chris@1295 148 end
Chris@1295 149
Chris@1295 150 module Diffable
Chris@1295 151 def diff(b)
Chris@1295 152 RedmineDiff::Diff.new(self, b)
Chris@1295 153 end
Chris@1295 154
Chris@1295 155 # Create a hash that maps elements of the array to arrays of indices
Chris@1295 156 # where the elements are found.
Chris@1295 157
Chris@1295 158 def reverse_hash(range = (0...self.length))
Chris@1295 159 revmap = {}
Chris@1295 160 range.each { |i|
Chris@1295 161 elem = self[i]
Chris@1295 162 if revmap.has_key? elem
Chris@1295 163 revmap[elem].push i
Chris@1295 164 else
Chris@1295 165 revmap[elem] = [i]
Chris@1295 166 end
Chris@1295 167 }
Chris@1295 168 return revmap
Chris@1295 169 end
Chris@1295 170
Chris@1295 171 def replacenextlarger(value, high = nil)
Chris@1295 172 high ||= self.length
Chris@1295 173 if self.empty? || value > self[-1]
Chris@1295 174 push value
Chris@1295 175 return high
Chris@1295 176 end
Chris@1295 177 # binary search for replacement point
Chris@1295 178 low = 0
Chris@1295 179 while low < high
Chris@1295 180 index = (high+low)/2
Chris@1295 181 found = self[index]
Chris@1295 182 return nil if value == found
Chris@1295 183 if value > found
Chris@1295 184 low = index + 1
Chris@1295 185 else
Chris@1295 186 high = index
Chris@1295 187 end
Chris@1295 188 end
Chris@1295 189
Chris@1295 190 self[low] = value
Chris@1295 191 # $stderr << "replace #{value} : 0/#{low}/#{init_high} (#{steps} steps) (#{init_high-low} off )\n"
Chris@1295 192 # $stderr.puts self.inspect
Chris@1295 193 #gets
Chris@1295 194 #p length - low
Chris@1295 195 return low
Chris@1295 196 end
Chris@1295 197
Chris@1295 198 def patch(diff)
Chris@1295 199 newary = nil
Chris@1295 200 if diff.difftype == String
Chris@1295 201 newary = diff.difftype.new('')
Chris@1295 202 else
Chris@1295 203 newary = diff.difftype.new
Chris@1295 204 end
Chris@1295 205 ai = 0
Chris@1295 206 bi = 0
Chris@1295 207 diff.diffs.each { |d|
Chris@1295 208 d.each { |mod|
Chris@1295 209 case mod[0]
Chris@1295 210 when '-'
Chris@1295 211 while ai < mod[1]
Chris@1295 212 newary << self[ai]
Chris@1295 213 ai += 1
Chris@1295 214 bi += 1
Chris@1295 215 end
Chris@1295 216 ai += 1
Chris@1295 217 when '+'
Chris@1295 218 while bi < mod[1]
Chris@1295 219 newary << self[ai]
Chris@1295 220 ai += 1
Chris@1295 221 bi += 1
Chris@1295 222 end
Chris@1295 223 newary << mod[2]
Chris@1295 224 bi += 1
Chris@1295 225 else
Chris@1295 226 raise "Unknown diff action"
Chris@1295 227 end
Chris@1295 228 }
Chris@1295 229 }
Chris@1295 230 while ai < self.length
Chris@1295 231 newary << self[ai]
Chris@1295 232 ai += 1
Chris@1295 233 bi += 1
Chris@1295 234 end
Chris@1295 235 return newary
Chris@1295 236 end
Chris@1295 237 end
Chris@1295 238
Chris@1295 239 class Array
Chris@1295 240 include Diffable
Chris@1295 241 end
Chris@1295 242
Chris@1295 243 class String
Chris@1295 244 include Diffable
Chris@1295 245 end
Chris@1295 246
Chris@1295 247 =begin
Chris@1295 248 = Diff
Chris@1295 249 (({diff.rb})) - computes the differences between two arrays or
Chris@1295 250 strings. Copyright (C) 2001 Lars Christensen
Chris@1295 251
Chris@1295 252 == Synopsis
Chris@1295 253
Chris@1295 254 diff = Diff.new(a, b)
Chris@1295 255 b = a.patch(diff)
Chris@1295 256
Chris@1295 257 == Class Diff
Chris@1295 258 === Class Methods
Chris@1295 259 --- Diff.new(a, b)
Chris@1295 260 --- a.diff(b)
Chris@1295 261 Creates a Diff object which represent the differences between
Chris@1295 262 ((|a|)) and ((|b|)). ((|a|)) and ((|b|)) can be either be arrays
Chris@1295 263 of any objects, strings, or object of any class that include
Chris@1295 264 module ((|Diffable|))
Chris@1295 265
Chris@1295 266 == Module Diffable
Chris@1295 267 The module ((|Diffable|)) is intended to be included in any class for
Chris@1295 268 which differences are to be computed. Diffable is included into String
Chris@1295 269 and Array when (({diff.rb})) is (({require}))'d.
Chris@1295 270
Chris@1295 271 Classes including Diffable should implement (({[]})) to get element at
Chris@1295 272 integer indices, (({<<})) to append elements to the object and
Chris@1295 273 (({ClassName#new})) should accept 0 arguments to create a new empty
Chris@1295 274 object.
Chris@1295 275
Chris@1295 276 === Instance Methods
Chris@1295 277 --- Diffable#patch(diff)
Chris@1295 278 Applies the differences from ((|diff|)) to the object ((|obj|))
Chris@1295 279 and return the result. ((|obj|)) is not changed. ((|obj|)) and
Chris@1295 280 can be either an array or a string, but must match the object
Chris@1295 281 from which the ((|diff|)) was created.
Chris@1295 282 =end