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