Chris@909: module RedmineDiff
Chris@909:   class Diff
Chris@909: 
Chris@909:     VERSION = 0.3
Chris@909: 
Chris@909:     def Diff.lcs(a, b)
Chris@909:       astart = 0
Chris@909:       bstart = 0
Chris@909:       afinish = a.length-1
Chris@909:       bfinish = b.length-1
Chris@909:       mvector = []
Chris@909: 
Chris@909:       # First we prune off any common elements at the beginning
Chris@909:       while (astart <= afinish && bstart <= afinish && a[astart] == b[bstart])
Chris@909:         mvector[astart] = bstart
Chris@909:         astart += 1
Chris@909:         bstart += 1
Chris@909:       end
Chris@909: 
Chris@909:       # now the end
Chris@909:       while (astart <= afinish && bstart <= bfinish && a[afinish] == b[bfinish])
Chris@909:         mvector[afinish] = bfinish
Chris@909:         afinish -= 1
Chris@909:         bfinish -= 1
Chris@909:       end
Chris@909: 
Chris@909:       bmatches = b.reverse_hash(bstart..bfinish)
Chris@909:       thresh = []
Chris@909:       links = []
Chris@909: 
Chris@909:       (astart..afinish).each { |aindex|
Chris@909:         aelem = a[aindex]
Chris@909:         next unless bmatches.has_key? aelem
Chris@909:         k = nil
Chris@909:         bmatches[aelem].reverse.each { |bindex|
Chris@909:     if k && (thresh[k] > bindex) && (thresh[k-1] < bindex)
Chris@909:       thresh[k] = bindex
Chris@909:     else
Chris@909:       k = thresh.replacenextlarger(bindex, k)
Chris@909:     end
Chris@909:     links[k] = [ (k==0) ? nil : links[k-1], aindex, bindex ] if k
Chris@909:         }
Chris@909:       }
Chris@909: 
Chris@909:       if !thresh.empty?
Chris@909:         link = links[thresh.length-1]
Chris@909:         while link
Chris@909:     mvector[link[1]] = link[2]
Chris@909:     link = link[0]
Chris@909:         end
Chris@909:       end
Chris@909: 
Chris@909:       return mvector
Chris@909:     end
Chris@909: 
Chris@909:     def makediff(a, b)
Chris@909:       mvector = Diff.lcs(a, b)
Chris@909:       ai = bi = 0
Chris@909:       while ai < mvector.length
Chris@909:         bline = mvector[ai]
Chris@909:         if bline
Chris@909:     while bi < bline
Chris@909:       discardb(bi, b[bi])
Chris@909:       bi += 1
Chris@909:     end
Chris@909:     match(ai, bi)
Chris@909:     bi += 1
Chris@909:         else
Chris@909:     discarda(ai, a[ai])
Chris@909:         end
Chris@909:         ai += 1
Chris@909:       end
Chris@909:       while ai < a.length
Chris@909:         discarda(ai, a[ai])
Chris@909:         ai += 1
Chris@909:       end
Chris@909:       while bi < b.length
Chris@909:         discardb(bi, b[bi])
Chris@909:         bi += 1
Chris@909:       end
Chris@909:       match(ai, bi)
Chris@909:       1
Chris@909:     end
Chris@909: 
Chris@909:     def compactdiffs
Chris@909:       diffs = []
Chris@909:       @diffs.each { |df|
Chris@909:         i = 0
Chris@909:         curdiff = []
Chris@909:         while i < df.length
Chris@909:     whot = df[i][0]
Chris@909:     s = @isstring ? df[i][2].chr : [df[i][2]]
Chris@909:     p = df[i][1]
Chris@909:     last = df[i][1]
Chris@909:     i += 1
Chris@909:     while df[i] && df[i][0] == whot && df[i][1] == last+1
Chris@909:       s << df[i][2]
Chris@909:       last  = df[i][1]
Chris@909:       i += 1
Chris@909:     end
Chris@909:     curdiff.push [whot, p, s]
Chris@909:         end
Chris@909:         diffs.push curdiff
Chris@909:       }
Chris@909:       return diffs
Chris@909:     end
Chris@909: 
Chris@909:     attr_reader :diffs, :difftype
Chris@909: 
Chris@909:     def initialize(diffs_or_a, b = nil, isstring = nil)
Chris@909:       if b.nil?
Chris@909:         @diffs = diffs_or_a
Chris@909:         @isstring = isstring
Chris@909:       else
Chris@909:         @diffs = []
Chris@909:         @curdiffs = []
Chris@909:         makediff(diffs_or_a, b)
Chris@909:         @difftype = diffs_or_a.class
Chris@909:       end
Chris@909:     end
Chris@909: 
Chris@909:     def match(ai, bi)
Chris@909:       @diffs.push @curdiffs unless @curdiffs.empty?
Chris@909:       @curdiffs = []
Chris@909:     end
Chris@909: 
Chris@909:     def discarda(i, elem)
Chris@909:       @curdiffs.push ['-', i, elem]
Chris@909:     end
Chris@909: 
Chris@909:     def discardb(i, elem)
Chris@909:       @curdiffs.push ['+', i, elem]
Chris@909:     end
Chris@909: 
Chris@909:     def compact
Chris@909:       return Diff.new(compactdiffs)
Chris@909:     end
Chris@909: 
Chris@909:     def compact!
Chris@909:       @diffs = compactdiffs
Chris@909:     end
Chris@909: 
Chris@909:     def inspect
Chris@909:       @diffs.inspect
Chris@909:     end
Chris@909: 
Chris@909:   end
Chris@909: end
Chris@909: 
Chris@909: module Diffable
Chris@909:   def diff(b)
Chris@909:     RedmineDiff::Diff.new(self, b)
Chris@909:   end
Chris@909: 
Chris@909:   # Create a hash that maps elements of the array to arrays of indices
Chris@909:   # where the elements are found.
Chris@909: 
Chris@909:   def reverse_hash(range = (0...self.length))
Chris@909:     revmap = {}
Chris@909:     range.each { |i|
Chris@909:       elem = self[i]
Chris@909:       if revmap.has_key? elem
Chris@909:   revmap[elem].push i
Chris@909:       else
Chris@909:   revmap[elem] = [i]
Chris@909:       end
Chris@909:     }
Chris@909:     return revmap
Chris@909:   end
Chris@909: 
Chris@909:   def replacenextlarger(value, high = nil)
Chris@909:     high ||= self.length
Chris@909:     if self.empty? || value > self[-1]
Chris@909:       push value
Chris@909:       return high
Chris@909:     end
Chris@909:     # binary search for replacement point
Chris@909:     low = 0
Chris@909:     while low < high
Chris@909:       index = (high+low)/2
Chris@909:       found = self[index]
Chris@909:       return nil if value == found
Chris@909:       if value > found
Chris@909:   low = index + 1
Chris@909:       else
Chris@909:   high = index
Chris@909:       end
Chris@909:     end
Chris@909: 
Chris@909:     self[low] = value
Chris@909:     # $stderr << "replace #{value} : 0/#{low}/#{init_high} (#{steps} steps) (#{init_high-low} off )\n"
Chris@909:     # $stderr.puts self.inspect
Chris@909:     #gets
Chris@909:     #p length - low
Chris@909:     return low
Chris@909:   end
Chris@909: 
Chris@909:   def patch(diff)
Chris@909:     newary = nil
Chris@909:     if diff.difftype == String
Chris@909:       newary = diff.difftype.new('')
Chris@909:     else
Chris@909:       newary = diff.difftype.new
Chris@909:     end
Chris@909:     ai = 0
Chris@909:     bi = 0
Chris@909:     diff.diffs.each { |d|
Chris@909:       d.each { |mod|
Chris@909:   case mod[0]
Chris@909:   when '-'
Chris@909:     while ai < mod[1]
Chris@909:       newary << self[ai]
Chris@909:       ai += 1
Chris@909:       bi += 1
Chris@909:     end
Chris@909:     ai += 1
Chris@909:   when '+'
Chris@909:     while bi < mod[1]
Chris@909:       newary << self[ai]
Chris@909:       ai += 1
Chris@909:       bi += 1
Chris@909:     end
Chris@909:     newary << mod[2]
Chris@909:     bi += 1
Chris@909:   else
Chris@909:     raise "Unknown diff action"
Chris@909:   end
Chris@909:       }
Chris@909:     }
Chris@909:     while ai < self.length
Chris@909:       newary << self[ai]
Chris@909:       ai += 1
Chris@909:       bi += 1
Chris@909:     end
Chris@909:     return newary
Chris@909:   end
Chris@909: end
Chris@909: 
Chris@909: class Array
Chris@909:   include Diffable
Chris@909: end
Chris@909: 
Chris@909: class String
Chris@909:   include Diffable
Chris@909: end
Chris@909: 
Chris@909: =begin
Chris@909:   = Diff
Chris@909:   (({diff.rb})) - computes the differences between two arrays or
Chris@909:   strings. Copyright (C) 2001 Lars Christensen
Chris@909: 
Chris@909:   == Synopsis
Chris@909: 
Chris@909:       diff = Diff.new(a, b)
Chris@909:       b = a.patch(diff)
Chris@909: 
Chris@909:   == Class Diff
Chris@909:   === Class Methods
Chris@909:   --- Diff.new(a, b)
Chris@909:   --- a.diff(b)
Chris@909:         Creates a Diff object which represent the differences between
Chris@909:         ((|a|)) and ((|b|)). ((|a|)) and ((|b|)) can be either be arrays
Chris@909:         of any objects, strings, or object of any class that include
Chris@909:         module ((|Diffable|))
Chris@909: 
Chris@909:   == Module Diffable
Chris@909:   The module ((|Diffable|)) is intended to be included in any class for
Chris@909:   which differences are to be computed. Diffable is included into String
Chris@909:   and Array when (({diff.rb})) is (({require}))'d.
Chris@909: 
Chris@909:   Classes including Diffable should implement (({[]})) to get element at
Chris@909:   integer indices, (({<<})) to append elements to the object and
Chris@909:   (({ClassName#new})) should accept 0 arguments to create a new empty
Chris@909:   object.
Chris@909: 
Chris@909:   === Instance Methods
Chris@909:   --- Diffable#patch(diff)
Chris@909:         Applies the differences from ((|diff|)) to the object ((|obj|))
Chris@909:         and return the result. ((|obj|)) is not changed. ((|obj|)) and
Chris@909:         can be either an array or a string, but must match the object
Chris@909:         from which the ((|diff|)) was created.
Chris@909: =end