vendor/gems/diff-lcs-1.1.2/lib/diff/lcs.rb
# #traverse_balanced is an alternative to #traverse_sequences. It
# uses a different algorithm to iterate through the entries in the
# computed longest common subsequence. Instead of viewing the changes as
# insertions or deletions from one of the sequences, #traverse_balanced
# will report <em>changes</em> between the sequences. To represent a
#
# The arguments to #traverse_balanced are the two sequences to traverse
# and a callback object, like this:
#
#   traverse_balanced(seq1, seq2, Diff::LCS::ContextDiffCallbacks.new)
#
# #sdiff is implemented with #traverse_balanced.
#
# == 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#change</em>::     Called when +a+ and +b+ are pointing
#                                 to the same relative position, but
#                                 <tt>A[a]</tt> and <tt>B[b]</tt> are
#                                 not the same; a <em>change</em> has
#                                 occurred.
#
# #traverse_balanced might be a bit slower than #traverse_sequences,
# noticable only while processing huge amounts of data.
#
# The +sdiff+ function of this module is implemented as call to
# #traverse_balanced.
#
# == 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---+
#
# === Matches
# 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.
#
# === Discards
# 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.
#
# === Changes
# If both +a+ and +b+ point to elements that are not part of the longest
# common subsequence, then #traverse_sequences will try to call
# <tt>callbacks#change</tt> and advance both arrows. If
# <tt>callbacks#change</tt> is not implemented, then
# <tt>callbacks#discard_a</tt> and <tt>callbacks#discard_b</tt> will be
# called in turn.
#
# The methods for <tt>callbacks#match</tt>, <tt>callbacks#discard_a</tt>,
# <tt>callbacks#discard_b</tt>, and <tt>callbacks#change</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_balanced.
#
# === Context
# Note that +ii+ and +jj+ may not be the same index position, even if
# +a+ and +b+ are considered to be pointing to matching or changed
# elements.


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



sdiff is implemented with #traverse_balanced.

Callback Methods
Optional callback methods are emphasized.



traverse_balanced might be a bit slower than #traverse_sequences,
noticable only while processing huge amounts of data.

The +sdiff+ function of this module is implemented as call to
traverse_balanced.





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

Changes
If both +a+ and +b+ point to elements that are not part of the longest
common subsequence, then #traverse_sequences will try to call
callbacks#change and advance both arrows. If
callbacks#change is not implemented, then
callbacks#discard_a and callbacks#discard_b will be
called in turn.




The arguments to #traverse_balanced are the two sequences to traverse and a callback object like this . sdiff is implemented with #traverse_balanced . Callback Methods Optional callback methods are emphasized . traverse_balanced might be a bit slower than #traverse_sequences noticable only while processing huge amounts of data . The + sdiff + function of this module is implemented as call to traverse_balanced . Discards 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 . Changes If both + a + and + b + point to elements that are not part of the longest common subsequence then #traverse_sequences will try to call callbacks#change and advance both arrows . If callbacks#change is not implemented then callbacks#discard_a and callbacks#discard_b will be called in turn .
def traverse_balanced(seq1, seq2, callbacks = Diff::LCS::BalancedCallbacks)
      matches = Diff::LCS.__lcs(seq1, seq2)
      a_size = seq1.size
      b_size = seq2.size
      ai = bj = mb = 0
      ma = -1
      string = seq1.kind_of?(String)
      loop do
        loop do
          ma += 1
          break unless ma < matches.size and matches[ma].nil?
        end
        break if ma >= matches.size 
        mb = matches[ma]
        while (ai < ma) or (bj < mb)
          ax = string ? seq1[ai, 1] : seq1[ai]
          bx = string ? seq2[bj, 1] : seq2[bj]
          case [(ai < ma), (bj < mb)]
          when [true, true]
            if callbacks.respond_to?(:change)
              event = Diff::LCS::ContextChange.new('!', ai, ax, bj, bx)
              event = yield event if block_given?
              callbacks.change(event)
              ai += 1
              bj += 1
            else
              event = Diff::LCS::ContextChange.new('-', ai, ax, bj, bx)
              event = yield event if block_given?
              callbacks.discard_a(event)
              ai += 1
              ax = string ? seq1[ai, 1] : seq1[ai]
              event = Diff::LCS::ContextChange.new('+', ai, ax, bj, bx)
              event = yield event if block_given?
              callbacks.discard_b(event)
              bj += 1
            end
          when [true, false]
            event = Diff::LCS::ContextChange.new('-', ai, ax, bj, bx)
            event = yield event if block_given?
            callbacks.discard_a(event)
            ai += 1
          when [false, true]
            event = Diff::LCS::ContextChange.new('+', ai, ax, bj, bx)
            event = yield event if block_given?
            callbacks.discard_b(event)
            bj += 1
          end
        end
        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.match(event)
        ai += 1
        bj += 1
      end
      while (ai < a_size) or (bj < b_size)
        ax = string ? seq1[ai, 1] : seq1[ai]
        bx = string ? seq2[bj, 1] : seq2[bj]
        case [(ai < a_size), (bj < b_size)]
        when [true, true]
          if callbacks.respond_to?(:change)
            event = Diff::LCS::ContextChange.new('!', ai, ax, bj, bx)
            event = yield event if block_given?
            callbacks.change(event)
            ai += 1
            bj += 1
          else
            event = Diff::LCS::ContextChange.new('-', ai, ax, bj, bx)
            event = yield event if block_given?
            callbacks.discard_a(event)
            ai += 1
            ax = string ? seq1[ai, 1] : seq1[ai]
            event = Diff::LCS::ContextChange.new('+', ai, ax, bj, bx)
            event = yield event if block_given?
            callbacks.discard_b(event)
            bj += 1
          end
        when [true, false]
          event = Diff::LCS::ContextChange.new('-', ai, ax, bj, bx)
          event = yield event if block_given?
          callbacks.discard_a(event)
          ai += 1
        when [false, true]
          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_balanced ( seq1 , seq2 , callbacks = Diff :: LCS :: BalancedCallbacks ) matches = Diff :: LCS . __lcs ( seq1 , seq2 ) a_size = seq1 . size b_size = seq2 . size ai = bj = mb = 0 ma = - 1 string = seq1 . kind_of? ( String ) loop do loop do ma += 1 break unless ma < matches . size and matches [ ma ] . nil? end break if ma >= matches . size mb = matches [ ma ] while ( ai < ma ) or ( bj < mb ) ax = string ? seq1 [ ai , 1 ] : seq1 [ ai ] bx = string ? seq2 [ bj , 1 ] : seq2 [ bj ] case [ ( ai < ma ) , ( bj < mb ) ] when [ true , true ] if callbacks . respond_to? ( :change ) event = Diff :: LCS :: ContextChange . new ( '!' , ai , ax , bj , bx ) event = yield event if block_given? callbacks . change ( event ) ai += 1 bj += 1 else event = Diff :: LCS :: ContextChange . new ( '-' , ai , ax , bj , bx ) event = yield event if block_given? callbacks . discard_a ( event ) ai += 1 ax = string ? seq1 [ ai , 1 ] : seq1 [ ai ] event = Diff :: LCS :: ContextChange . new ( '+' , ai , ax , bj , bx ) event = yield event if block_given? callbacks . discard_b ( event ) bj += 1 end when [ true , false ] event = Diff :: LCS :: ContextChange . new ( '-' , ai , ax , bj , bx ) event = yield event if block_given? callbacks . discard_a ( event ) ai += 1 when [ false , true ] event = Diff :: LCS :: ContextChange . new ( '+' , ai , ax , bj , bx ) event = yield event if block_given? callbacks . discard_b ( event ) bj += 1 end end 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 . match ( event ) ai += 1 bj += 1 end while ( ai < a_size ) or ( bj < b_size ) ax = string ? seq1 [ ai , 1 ] : seq1 [ ai ] bx = string ? seq2 [ bj , 1 ] : seq2 [ bj ] case [ ( ai < a_size ) , ( bj < b_size ) ] when [ true , true ] if callbacks . respond_to? ( :change ) event = Diff :: LCS :: ContextChange . new ( '!' , ai , ax , bj , bx ) event = yield event if block_given? callbacks . change ( event ) ai += 1 bj += 1 else event = Diff :: LCS :: ContextChange . new ( '-' , ai , ax , bj , bx ) event = yield event if block_given? callbacks . discard_a ( event ) ai += 1 ax = string ? seq1 [ ai , 1 ] : seq1 [ ai ] event = Diff :: LCS :: ContextChange . new ( '+' , ai , ax , bj , bx ) event = yield event if block_given? callbacks . discard_b ( event ) bj += 1 end when [ true , false ] event = Diff :: LCS :: ContextChange . new ( '-' , ai , ax , bj , bx ) event = yield event if block_given? callbacks . discard_a ( event ) ai += 1 when [ false , true ] event = Diff :: LCS :: ContextChange . new ( '+' , ai , ax , bj , bx ) event = yield event if block_given? callbacks . discard_b ( event ) bj += 1 end end end
traverse_balanced is an alternative to #traverse_sequences.
traverse_balanced is an alternative to #traverse_sequences .
# Process all the lines in the match vector. # Find next match indices +ma+ and +mb+ # end of matches? # Change(seq2) # Match
seq1
seq2
callbacks