vendor/gems/diff-lcs-1.1.2/lib/diff/lcs.rb
# Diff::LCS.traverse_sequences is the most general facility provided by this
# module; +diff+ and +LCS+ are implemented as calls to it.
#
# The arguments to #traverse_sequences are the two sequences to
# traverse, and a callback object, like this:
#
#   traverse_sequences(seq1, seq2, Diff::LCS::ContextDiffCallbacks.new)
#
# #diff is implemented with #traverse_sequences.
#
# == Callback Methods
# Optional callback methods are <em>emphasized</em>.
#
# callbacks#match::               Called when +a+ and +b+ are pointing
#                                 to common elements in +A+ and +B+.
# callbacks#discard_a::           Called when +a+ is pointing to an
#                                 element not in +B+.
# callbacks#discard_b::           Called when +b+ is pointing to an
#                                 element not in +A+.
# <em>callbacks#finished_a</em>:: Called when +a+ has reached the end of
#                                 sequence +A+.
# <em>callbacks#finished_b</em>:: Called when +b+ has reached the end of
#                                 sequence +B+.
#
# == Algorithm
#       a---+
#           v
#       A = a b c e h j l m n p
#       B = b c d e f j k l m r s t
#           ^
#       b---+
#
# If there are two arrows (+a+ and +b+) pointing to elements of
# sequences +A+ and +B+, the arrows will initially point to the first
# elements of their respective sequences. #traverse_sequences will
# advance the arrows through the sequences one element at a time,
# calling a method on the user-specified callback object before each
# advance. It will advance the arrows in such a way that if there are
# elements <tt>A[ii]</tt> and <tt>B[jj]</tt> which are both equal and
# part of the longest common subsequence, there will be some moment
# during the execution of #traverse_sequences when arrow +a+ is pointing
# to <tt>A[ii]</tt> and arrow +b+ is pointing to <tt>B[jj]</tt>. When
# this happens, #traverse_sequences will call <tt>callbacks#match</tt>
# and then it will advance both arrows.
#
# Otherwise, one of the arrows is pointing to an element of its sequence
# that is not part of the longest common subsequence.
# #traverse_sequences will advance that arrow and will call
# <tt>callbacks#discard_a</tt> or <tt>callbacks#discard_b</tt>, depending
# on which arrow it advanced. If both arrows point to elements that are
# not part of the longest common subsequence, then #traverse_sequences
# will advance one of them and call the appropriate callback, but it is
# not specified which it will call.
#
# The methods for <tt>callbacks#match</tt>, <tt>callbacks#discard_a</tt>,
# and <tt>callbacks#discard_b</tt> are invoked with an event comprising
# the action ("=", "+", or "-", respectively), the indicies +ii+ and
# +jj+, and the elements <tt>A[ii]</tt> and <tt>B[jj]</tt>. Return
# values are discarded by #traverse_sequences.
#
# === End of Sequences
# If arrow +a+ reaches the end of its sequence before arrow +b+ does,
# #traverse_sequence try to call <tt>callbacks#finished_a</tt> with the
# last index and element of +A+ (<tt>A[-1]</tt>) and the current index
# and element of +B+ (<tt>B[jj]</tt>). If <tt>callbacks#finished_a</tt>
# does not exist, then <tt>callbacks#discard_b</tt> will be called on
# each element of +B+ until the end of the sequence is reached (the call
# will be done with <tt>A[-1]</tt> and <tt>B[jj]</tt> for each element).
#
# If +b+ reaches the end of +B+ before +a+ reaches the end of +A+,
# <tt>callbacks#finished_b</tt> will be called with the current index
# and element of +A+ (<tt>A[ii]</tt>) and the last index and element of
# +B+ (<tt>A[-1]</tt>). Again, if <tt>callbacks#finished_b</tt> does not
# exist on the callback object, then <tt>callbacks#discard_a</tt> will
# be called on each element of +A+ until the end of the sequence is
# reached (<tt>A[ii]</tt> and <tt>B[-1]</tt>).
#
# There is a chance that one additional <tt>callbacks#discard_a</tt> or
# <tt>callbacks#discard_b</tt> will be called after the end of the
# sequence is reached, if +a+ has not yet reached the end of +A+ or +b+
# has not yet reached the end of +B+.
:LCS.traverse_sequences is the most general facility provided by this
module; +diff+ and +LCS+ are implemented as calls to it.

The arguments to #traverse_sequences are the two sequences to
traverse, and a callback object, like this.



diff is implemented with #traverse_sequences.

Callback Methods
Optional callback methods are emphasized.







Otherwise, one of the arrows is pointing to an element of its sequence
that is not part of the longest common subsequence.
traverse_sequences will advance that arrow and will call
callbacks#discard_a or callbacks#discard_b, depending
on which arrow it advanced. If both arrows point to elements that are
not part of the longest common subsequence, then #traverse_sequences
will advance one of them and call the appropriate callback, but it is
not specified which it will call.








: LCS . traverse_sequences is the most general facility provided by this module ; + diff + and + LCS + are implemented as calls to it . The arguments to #traverse_sequences are the two sequences to traverse and a callback object like this . diff is implemented with #traverse_sequences . Callback Methods Optional callback methods are emphasized . Otherwise one of the arrows is pointing to an element of its sequence that is not part of the longest common subsequence . traverse_sequences will advance that arrow and will call callbacks#discard_a or callbacks#discard_b depending on which arrow it advanced . If both arrows point to elements that are not part of the longest common subsequence then #traverse_sequences will advance one of them and call the appropriate callback but it is not specified which it will call .
def traverse_sequences(seq1, seq2, callbacks = Diff::LCS::SequenceCallbacks, &block) 
      matches = Diff::LCS.__lcs(seq1, seq2)
      run_finished_a = run_finished_b = false
      string = seq1.kind_of?(String)
      a_size = seq1.size
      b_size = seq2.size
      ai = bj = 0
      (0 .. matches.size).each do |ii|
        b_line = matches[ii]
        ax = string ? seq1[ii, 1] : seq1[ii]
        bx = string ? seq2[bj, 1] : seq2[bj]
        if b_line.nil?
          unless ax.nil?
            event = Diff::LCS::ContextChange.new('-', ii, ax, bj, bx)
            event = yield event if block_given?
            callbacks.discard_a(event)
          end
        else
          loop do
            break unless bj < b_line
            bx = string ? seq2[bj, 1] : seq2[bj]
            event = Diff::LCS::ContextChange.new('+', ii, ax, bj, bx)
            event = yield event if block_given?
            callbacks.discard_b(event)
            bj += 1
          end
          bx = string ? seq2[bj, 1] : seq2[bj]
          event = Diff::LCS::ContextChange.new('=', ii, ax, bj, bx)
          event = yield event if block_given?
          callbacks.match(event)
          bj += 1
        end
        ai = ii
      end
      ai += 1
      while (ai < a_size) or (bj < b_size)
        if ai == a_size and bj < b_size
          if callbacks.respond_to?(:finished_a) and not run_finished_a
            ax = string ? seq1[-1, 1] : seq1[-1]
            bx = string ? seq2[bj, 1] : seq2[bj]
            event = Diff::LCS::ContextChange.new('>', (a_size - 1), ax, bj, bx)
            event = yield event if block_given?
            callbacks.finished_a(event)
            run_finished_a = true
          else
            ax = string ? seq1[ai, 1] : seq1[ai]
            loop do
              bx = string ? seq2[bj, 1] : seq2[bj]
              event = Diff::LCS::ContextChange.new('+', ai, ax, bj, bx)
              event = yield event if block_given?
              callbacks.discard_b(event)
              bj += 1
              break unless bj < b_size
            end
          end
        end
        if bj == b_size and ai < a_size
          if callbacks.respond_to?(:finished_b) and not run_finished_b
            ax = string ? seq1[ai, 1] : seq1[ai]
            bx = string ? seq2[-1, 1] : seq2[-1]
            event = Diff::LCS::ContextChange.new('<', ai, ax, (b_size - 1), bx)
            event = yield event if block_given?
            callbacks.finished_b(event)
            run_finished_b = true
          else
            bx = string ? seq2[bj, 1] : seq2[bj]
            loop do
              ax = string ? seq1[ai, 1] : seq1[ai]
              event = Diff::LCS::ContextChange.new('-', ai, ax, bj, bx)
              event = yield event if block_given?
              callbacks.discard_a(event)
              ai += 1
              break unless bj < b_size
            end
          end
        end
        if ai < a_size
          ax = string ? seq1[ai, 1] : seq1[ai]
          bx = string ? seq2[bj, 1] : seq2[bj]
          event = Diff::LCS::ContextChange.new('-', ai, ax, bj, bx)
          event = yield event if block_given?
          callbacks.discard_a(event)
          ai += 1
        end
        if bj < b_size
          ax = string ? seq1[ai, 1] : seq1[ai]
          bx = string ? seq2[bj, 1] : seq2[bj]
          event = Diff::LCS::ContextChange.new('+', ai, ax, bj, bx)
          event = yield event if block_given?
          callbacks.discard_b(event)
          bj += 1
        end
      end
    end
def traverse_sequences ( seq1 , seq2 , callbacks = Diff :: LCS :: SequenceCallbacks , & block ) matches = Diff :: LCS . __lcs ( seq1 , seq2 ) run_finished_a = run_finished_b = false string = seq1 . kind_of? ( String ) a_size = seq1 . size b_size = seq2 . size ai = bj = 0 ( 0 .. matches . size ) . each do | ii | b_line = matches [ ii ] ax = string ? seq1 [ ii , 1 ] : seq1 [ ii ] bx = string ? seq2 [ bj , 1 ] : seq2 [ bj ] if b_line . nil? unless ax . nil? event = Diff :: LCS :: ContextChange . new ( '-' , ii , ax , bj , bx ) event = yield event if block_given? callbacks . discard_a ( event ) end else loop do break unless bj < b_line bx = string ? seq2 [ bj , 1 ] : seq2 [ bj ] event = Diff :: LCS :: ContextChange . new ( '+' , ii , ax , bj , bx ) event = yield event if block_given? callbacks . discard_b ( event ) bj += 1 end bx = string ? seq2 [ bj , 1 ] : seq2 [ bj ] event = Diff :: LCS :: ContextChange . new ( '=' , ii , ax , bj , bx ) event = yield event if block_given? callbacks . match ( event ) bj += 1 end ai = ii end ai += 1 while ( ai < a_size ) or ( bj < b_size ) if ai == a_size and bj < b_size if callbacks . respond_to? ( :finished_a ) and not run_finished_a ax = string ? seq1 [ - 1 , 1 ] : seq1 [ - 1 ] bx = string ? seq2 [ bj , 1 ] : seq2 [ bj ] event = Diff :: LCS :: ContextChange . new ( '>' , ( a_size - 1 ) , ax , bj , bx ) event = yield event if block_given? callbacks . finished_a ( event ) run_finished_a = true else ax = string ? seq1 [ ai , 1 ] : seq1 [ ai ] loop do bx = string ? seq2 [ bj , 1 ] : seq2 [ bj ] event = Diff :: LCS :: ContextChange . new ( '+' , ai , ax , bj , bx ) event = yield event if block_given? callbacks . discard_b ( event ) bj += 1 break unless bj < b_size end end end if bj == b_size and ai < a_size if callbacks . respond_to? ( :finished_b ) and not run_finished_b ax = string ? seq1 [ ai , 1 ] : seq1 [ ai ] bx = string ? seq2 [ - 1 , 1 ] : seq2 [ - 1 ] event = Diff :: LCS :: ContextChange . new ( '<' , ai , ax , ( b_size - 1 ) , bx ) event = yield event if block_given? callbacks . finished_b ( event ) run_finished_b = true else bx = string ? seq2 [ bj , 1 ] : seq2 [ bj ] loop do ax = string ? seq1 [ ai , 1 ] : seq1 [ ai ] event = Diff :: LCS :: ContextChange . new ( '-' , ai , ax , bj , bx ) event = yield event if block_given? callbacks . discard_a ( event ) ai += 1 break unless bj < b_size end end end if ai < a_size ax = string ? seq1 [ ai , 1 ] : seq1 [ ai ] bx = string ? seq2 [ bj , 1 ] : seq2 [ bj ] event = Diff :: LCS :: ContextChange . new ( '-' , ai , ax , bj , bx ) event = yield event if block_given? callbacks . discard_a ( event ) ai += 1 end if bj < b_size ax = string ? seq1 [ ai , 1 ] : seq1 [ ai ] bx = string ? seq2 [ bj , 1 ] : seq2 [ bj ] event = Diff :: LCS :: ContextChange . new ( '+' , ai , ax , bj , bx ) event = yield event if block_given? callbacks . discard_b ( event ) bj += 1 end end end
Diff::LCS.traverse_sequences is the most general facility provided by this
module; +diff+ and +LCS+ are implemented as calls to it.
Diff :: LCS . traverse_sequences is the most general facility provided by this module ; + diff + and + LCS + are implemented as calls to it .
#:yields change events: # The last entry (if any) processed was a match. +ai+ and +bj+ point # just past the last matching lines in their sequences. # last A? # last B?
seq1
seq2
callbacks
block