diff lib/diff.rb @ 0:513646585e45

* Import Redmine trunk SVN rev 3859

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lib/diff.rb	Fri Jul 23 15:52:44 2010 +0100
@@ -0,0 +1,282 @@
+module RedmineDiff
+  class Diff
+
+    VERSION = 0.3
+
+    def Diff.lcs(a, b)
+      astart = 0
+      bstart = 0
+      afinish = a.length-1
+      bfinish = b.length-1
+      mvector = []
+      
+      # 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
+      
+      # now the end
+      while (astart <= afinish && bstart <= bfinish && a[afinish] == b[bfinish])
+        mvector[afinish] = bfinish
+        afinish -= 1
+        bfinish -= 1
+      end
+
+      bmatches = b.reverse_hash(bstart..bfinish)
+      thresh = []
+      links = []
+      
+      (astart..afinish).each { |aindex|
+        aelem = a[aindex]
+        next unless bmatches.has_key? aelem
+        k = nil
+        bmatches[aelem].reverse.each { |bindex|
+    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
+        }
+      }
+
+      if !thresh.empty?
+        link = links[thresh.length-1]
+        while link
+    mvector[link[1]] = link[2]
+    link = link[0]
+        end
+      end
+
+      return mvector
+    end
+
+    def makediff(a, b)
+      mvector = Diff.lcs(a, b)
+      ai = bi = 0
+      while ai < mvector.length
+        bline = mvector[ai]
+        if bline
+    while bi < bline
+      discardb(bi, b[bi])
+      bi += 1
+    end
+    match(ai, bi)
+    bi += 1
+        else
+    discarda(ai, a[ai])
+        end
+        ai += 1
+      end
+      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
+
+    def compactdiffs
+      diffs = []
+      @diffs.each { |df|
+        i = 0
+        curdiff = []
+        while i < df.length
+    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]
+        end
+        diffs.push curdiff
+      }
+      return diffs
+    end
+
+    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
+    
+    def match(ai, bi)
+      @diffs.push @curdiffs unless @curdiffs.empty?
+      @curdiffs = []
+    end
+
+    def discarda(i, elem)
+      @curdiffs.push ['-', i, elem]
+    end
+
+    def discardb(i, elem)
+      @curdiffs.push ['+', i, elem]
+    end
+
+    def compact
+      return Diff.new(compactdiffs)
+    end
+
+    def compact!
+      @diffs = compactdiffs
+    end
+
+    def inspect
+      @diffs.inspect
+    end
+
+  end
+end
+
+module Diffable
+  def diff(b)
+    RedmineDiff::Diff.new(self, b)
+  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
+  revmap[elem].push i
+      else
+  revmap[elem] = [i]
+      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
+  low = index + 1
+      else
+  high = index
+      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|
+  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
+      }
+    }
+    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
+  = Diff
+  (({diff.rb})) - computes the differences between two arrays or
+  strings. Copyright (C) 2001 Lars Christensen
+
+  == Synopsis
+
+      diff = Diff.new(a, b)
+      b = a.patch(diff)
+
+  == 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|))
+
+  == 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.
+
+  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.
+
+  === 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.
+=end