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