Redmine

  include Redmine::StringArrayDiff::Diffable

  include Redmine::StringArrayDiff::Diffable

# frozen_string_literal: true

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

# frozen_string_literal: true

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