vendor/gems/diff-lcs-1.1.2/lib/diff/lcs.rb
def __lcs(a, b)
      a_start = b_start = 0
      a_finish = a.size - 1
      b_finish = b.size - 1
      vector = []

        # Prune off any common elements at the beginning...
      while (a_start <= a_finish) and
            (b_start <= b_finish) and
            (a[a_start] == b[b_start])
        vector[a_start] = b_start
        a_start += 1
        b_start += 1
      end

        # Now the end...
      while (a_start <= a_finish) and
            (b_start <= b_finish) and
            (a[a_finish] == b[b_finish])
        vector[a_finish] = b_finish
        a_finish -= 1
        b_finish -= 1
      end

        # Now, compute the equivalence classes of positions of elements.
      b_matches = Diff::LCS.__position_hash(b, b_start .. b_finish)

      thresh = []
      links = []

      (a_start .. a_finish).each do |ii|
        ai = a.kind_of?(String) ? a[ii, 1] : a[ii]
        bm = b_matches[ai]
        kk = nil
        bm.reverse_each do |jj|
          if kk and (thresh[kk] > jj) and (thresh[kk - 1] < jj)
            thresh[kk] = jj
          else
            kk = Diff::LCS.__replace_next_larger(thresh, jj, kk)
          end
          links[kk] = [ (kk > 0) ? links[kk - 1] : nil, ii, jj ] unless kk.nil?
        end
      end

      unless thresh.empty?
        link = links[thresh.size - 1]
        while not link.nil?
          vector[link[1]] = link[2]
          link = link[0]
        end
      end

      vector
    end
# private
# Compute the longest common subsequence between the sequenced Enumerables
# +a+ and +b+. The result is an array whose contents is such that
#
#     result = Diff::LCS.__lcs(a, b)
#     result.each_with_index do |e, ii|
#       assert_equal(a[ii], b[e]) unless e.nil?
#     end
private
Compute the longest common subsequence between the sequenced Enumerables
+a+ and +b+. The result is an array whose contents is such that


private Compute the longest common subsequence between the sequenced Enumerables + a + and + b + . The result is an array whose contents is such that
def __lcs(a, b)
      a_start = b_start = 0
      a_finish = a.size - 1
      b_finish = b.size - 1
      vector = []
      while (a_start <= a_finish) and
            (b_start <= b_finish) and
            (a[a_start] == b[b_start])
        vector[a_start] = b_start
        a_start += 1
        b_start += 1
      end
      while (a_start <= a_finish) and
            (b_start <= b_finish) and
            (a[a_finish] == b[b_finish])
        vector[a_finish] = b_finish
        a_finish -= 1
        b_finish -= 1
      end
      b_matches = Diff::LCS.__position_hash(b, b_start .. b_finish)
      thresh = []
      links = []
      (a_start .. a_finish).each do |ii|
        ai = a.kind_of?(String) ? a[ii, 1] : a[ii]
        bm = b_matches[ai]
        kk = nil
        bm.reverse_each do |jj|
          if kk and (thresh[kk] > jj) and (thresh[kk - 1] < jj)
            thresh[kk] = jj
          else
            kk = Diff::LCS.__replace_next_larger(thresh, jj, kk)
          end
          links[kk] = [ (kk > 0) ? links[kk - 1] : nil, ii, jj ] unless kk.nil?
        end
      end
      unless thresh.empty?
        link = links[thresh.size - 1]
        while not link.nil?
          vector[link[1]] = link[2]
          link = link[0]
        end
      end
      vector
    end
def __lcs ( a , b ) a_start = b_start = 0 a_finish = a . size - 1 b_finish = b . size - 1 vector = [ ] while ( a_start <= a_finish ) and ( b_start <= b_finish ) and ( a [ a_start ] == b [ b_start ] ) vector [ a_start ] = b_start a_start += 1 b_start += 1 end while ( a_start <= a_finish ) and ( b_start <= b_finish ) and ( a [ a_finish ] == b [ b_finish ] ) vector [ a_finish ] = b_finish a_finish -= 1 b_finish -= 1 end b_matches = Diff :: LCS . __position_hash ( b , b_start .. b_finish ) thresh = [ ] links = [ ] ( a_start .. a_finish ) . each do | ii | ai = a . kind_of? ( String ) ? a [ ii , 1 ] : a [ ii ] bm = b_matches [ ai ] kk = nil bm . reverse_each do | jj | if kk and ( thresh [ kk ] > jj ) and ( thresh [ kk - 1 ] < jj ) thresh [ kk ] = jj else kk = Diff :: LCS . __replace_next_larger ( thresh , jj , kk ) end links [ kk ] = [ ( kk > 0 ) ? links [ kk - 1 ] : nil , ii , jj ] unless kk . nil? end end unless thresh . empty? link = links [ thresh . size - 1 ] while not link . nil? vector [ link [ 1 ] ] = link [ 2 ] link = link [ 0 ] end end vector end
private
Compute the longest common subsequence between the sequenced Enumerables
+a+ and +b+.
private Compute the longest common subsequence between the sequenced Enumerables + a + and + b + .
# Prune off any common elements at the beginning... # Now the end... # Now, compute the equivalence classes of positions of elements.
a
b