Redmine

module RedmineDiff

  class Diff

      astart = 0

      bstart = 0

      afinish = a.length-1

      bfinish = b.length-1

      mvector = []

      while (astart <= afinish && bstart <= afinish && a[astart] == b[bstart])

        mvector[astart] = bstart

        astart += 1

        bstart += 1

      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 = []

        aelem = a[aindex]

        next unless bmatches.has_key? aelem

        k = nil

        bmatches[aelem].reverse.each { |bindex|

            thresh[k] = bindex

          else

            k = thresh.replacenextlarger(bindex, k)

          end

          links[k] = [ (k==0) ? nil : links[k-1], aindex, bindex ] if k

        link = links[thresh.length-1]

        while link

          link = link[0]

      return mvector

      mvector = Diff.lcs(a, b)

      ai = bi = 0

      while ai < mvector.length

        bline = mvector[ai]

        if bline

            discardb(bi, b[bi])

            bi += 1

          end

          match(ai, bi)

          bi += 1

        ai += 1

        discarda(ai, a[ai])

        ai += 1

      end

      while bi < b.length

        discardb(bi, b[bi])

        bi += 1

      end

      match(ai, bi)

      1

    end

      diffs = []

      @diffs.each { |df|

        i = 0

        curdiff = []

        while i < df.length

          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]

        diffs.push curdiff

      }

      return diffs

    end

    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

      @diffs.push @curdiffs unless @curdiffs.empty?

    end

      @curdiffs.push ['-', i, elem]

    end

      @curdiffs.push ['+', i, elem]

    end

      return Diff.new(compactdiffs)

    end

      @diffs = compactdiffs

    end

      @diffs.inspect

    end

end

module Diffable

  def diff(b)

  # 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

    }

    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

    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|

        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.rb})) - computes the differences between two arrays or

  strings. Copyright (C) 2001 Lars Christensen

      b = a.patch(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|))

  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.

  integer indices, (({<<})) to append elements to the object and

  (({ClassName#new})) should accept 0 arguments to create a new empty

  object.

  --- 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.