Move @lib/diff.rb@ to @lib/redmine/string_array_diff@ and extract @Diffable@ class to its own file (#29914, #32938).

git-svn-id: http://svn.redmine.org/redmine/trunk@21262 e93f8b46-1217-0410-a6f0-8f06a7374b81

4 files changed, 327 insertions, 283 deletions

diff --git a/lib/diff.rb b/lib/diff.rb
deleted file mode 100644
index 4630af107..000000000
--- a/lib/diff.rb
+++ /dev/null
@@ -1,282 +0,0 @@
-# frozen_string_literal: true
-
-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
diff --git a/lib/redmine/helpers/diff.rb b/lib/redmine/helpers/diff.rb
index 5df25b33e..2a58dce91 100644
--- a/lib/redmine/helpers/diff.rb
+++ b/lib/redmine/helpers/diff.rb
@@ -17,7 +17,7 @@
 # along with this program; if not, write to the Free Software
 # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 
-require 'diff'
+require 'redmine/string_array_diff/diff'
 
 module Redmine
   module Helpers
diff --git a/lib/redmine/string_array_diff/diff.rb b/lib/redmine/string_array_diff/diff.rb
new file mode 100644
index 000000000..4b54fb740
--- /dev/null
+++ b/lib/redmine/string_array_diff/diff.rb
@@ -0,0 +1,195 @@
+# frozen_string_literal: true
+
+=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
+
+module Redmine
+  module StringArrayDiff
+    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
+end
+
+class Array
+  include Redmine::StringArrayDiff::Diffable
+end
+
+class String
+  include Redmine::StringArrayDiff::Diffable
+end
diff --git a/lib/redmine/string_array_diff/diffable.rb b/lib/redmine/string_array_diff/diffable.rb
new file mode 100644
index 000000000..e09afc3db
--- /dev/null
+++ b/lib/redmine/string_array_diff/diffable.rb
@@ -0,0 +1,131 @@
+# frozen_string_literal: true
+
+=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
+
+module Redmine
+  module StringArrayDiff
+    module Diffable
+      def diff(b)
+        Redmine::StringArrayDiff::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
+  end
+end