diff.rb 6.16 KB
Newer Older
1
# frozen_string_literal: true
2

3 4
module RedmineDiff
  class Diff
jplang's avatar
jplang committed
5

6
    VERSION = 0.3
jplang's avatar
jplang committed
7

8 9 10 11 12 13
    def Diff.lcs(a, b)
      astart = 0
      bstart = 0
      afinish = a.length-1
      bfinish = b.length-1
      mvector = []
14

15 16 17 18 19 20
      # First we prune off any common elements at the beginning
      while (astart <= afinish && bstart <= afinish && a[astart] == b[bstart])
        mvector[astart] = bstart
        astart += 1
        bstart += 1
      end
21

22 23 24 25 26 27
      # now the end
      while (astart <= afinish && bstart <= bfinish && a[afinish] == b[bfinish])
        mvector[afinish] = bfinish
        afinish -= 1
        bfinish -= 1
      end
jplang's avatar
jplang committed
28

29 30 31
      bmatches = b.reverse_hash(bstart..bfinish)
      thresh = []
      links = []
32

33 34 35 36
      (astart..afinish).each { |aindex|
        aelem = a[aindex]
        next unless bmatches.has_key? aelem
        k = nil
37
        bmatches[aelem].reverse_each { |bindex|
38 39 40 41 42 43
          if k && (thresh[k] > bindex) && (thresh[k-1] < bindex)
            thresh[k] = bindex
          else
            k = thresh.replacenextlarger(bindex, k)
          end
          links[k] = [ (k==0) ? nil : links[k-1], aindex, bindex ] if k
44
        }
jplang's avatar
jplang committed
45 46
      }

47 48 49
      if !thresh.empty?
        link = links[thresh.length-1]
        while link
50 51
          mvector[link[1]] = link[2]
          link = link[0]
52
        end
jplang's avatar
jplang committed
53 54
      end

55
      return mvector
jplang's avatar
jplang committed
56
    end
57 58 59 60 61 62 63

    def makediff(a, b)
      mvector = Diff.lcs(a, b)
      ai = bi = 0
      while ai < mvector.length
        bline = mvector[ai]
        if bline
64 65 66 67 68 69
          while bi < bline
            discardb(bi, b[bi])
            bi += 1
          end
          match(ai, bi)
          bi += 1
70
        else
71
          discarda(ai, a[ai])
72 73
        end
        ai += 1
jplang's avatar
jplang committed
74
      end
75 76 77 78 79 80 81 82 83 84 85
      while ai < a.length
        discarda(ai, a[ai])
        ai += 1
      end
      while bi < b.length
        discardb(bi, b[bi])
        bi += 1
      end
      match(ai, bi)
      1
    end
jplang's avatar
jplang committed
86

87 88 89 90 91 92
    def compactdiffs
      diffs = []
      @diffs.each { |df|
        i = 0
        curdiff = []
        while i < df.length
93 94 95 96 97 98 99 100 101 102 103
          whot = df[i][0]
          s = @isstring ? df[i][2].chr : [df[i][2]]
          p = df[i][1]
          last = df[i][1]
          i += 1
          while df[i] && df[i][0] == whot && df[i][1] == last+1
            s << df[i][2]
            last  = df[i][1]
            i += 1
          end
          curdiff.push [whot, p, s]
104 105 106 107 108
        end
        diffs.push curdiff
      }
      return diffs
    end
jplang's avatar
jplang committed
109

110 111 112 113 114 115 116 117 118 119 120 121 122
    attr_reader :diffs, :difftype

    def initialize(diffs_or_a, b = nil, isstring = nil)
      if b.nil?
        @diffs = diffs_or_a
        @isstring = isstring
      else
        @diffs = []
        @curdiffs = []
        makediff(diffs_or_a, b)
        @difftype = diffs_or_a.class
      end
    end
123

124 125
    def match(ai, bi)
      @diffs.push @curdiffs unless @curdiffs.empty?
jplang's avatar
jplang committed
126 127 128
      @curdiffs = []
    end

129 130 131
    def discarda(i, elem)
      @curdiffs.push ['-', i, elem]
    end
jplang's avatar
jplang committed
132

133 134 135
    def discardb(i, elem)
      @curdiffs.push ['+', i, elem]
    end
jplang's avatar
jplang committed
136

137 138 139
    def compact
      return Diff.new(compactdiffs)
    end
jplang's avatar
jplang committed
140

141 142 143
    def compact!
      @diffs = compactdiffs
    end
jplang's avatar
jplang committed
144

145 146 147
    def inspect
      @diffs.inspect
    end
jplang's avatar
jplang committed
148

149
  end
jplang's avatar
jplang committed
150 151 152 153
end

module Diffable
  def diff(b)
154
    RedmineDiff::Diff.new(self, b)
jplang's avatar
jplang committed
155 156 157 158 159 160 161 162 163 164
  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
165
        revmap[elem].push i
jplang's avatar
jplang committed
166
      else
167
        revmap[elem] = [i]
jplang's avatar
jplang committed
168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185
      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
186
        low = index + 1
jplang's avatar
jplang committed
187
      else
188
        high = index
jplang's avatar
jplang committed
189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210
      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|
211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229
        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
jplang's avatar
jplang committed
230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249
      }
    }
    while ai < self.length
      newary << self[ai]
      ai += 1
      bi += 1
    end
    return newary
  end
end

class Array
  include Diffable
end

class String
  include Diffable
end

=begin
250 251 252
  = Diff
  (({diff.rb})) - computes the differences between two arrays or
  strings. Copyright (C) 2001 Lars Christensen
jplang's avatar
jplang committed
253

254
  == Synopsis
jplang's avatar
jplang committed
255

256 257
      diff = Diff.new(a, b)
      b = a.patch(diff)
jplang's avatar
jplang committed
258

259 260 261 262 263 264 265 266
  == 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|))
jplang's avatar
jplang committed
267

268 269 270 271
  == 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.
jplang's avatar
jplang committed
272

273 274 275 276
  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.
jplang's avatar
jplang committed
277

278 279 280 281 282 283
  === 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.
jplang's avatar
jplang committed
284
=end