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