global

def traverse_sequences(seq1, seq2, callbacks = Diff::LCS::SequenceCallbacks) #:yields change events:

:yields change events:
reached the end of +B+.
is reached, if +a+ has not yet reached the end of +A+ or +b+ has not yet
callbacks#discard_b will be called after the end of the sequence
There is a chance that one additional callbacks#discard_a or

and B[-1]).
each element of +A+ until the end of the sequence is reached (A[i]
the callback object, then callbacks#discard_a will be called on
(A[-1]). Again, if callbacks#finished_b does not exist on
element of +A+ (A[i]) and the last index and element of +B+
callbacks#finished_b will be called with the current index and
If +b+ reaches the end of +B+ before +a+ reaches the end of +A+,

A[-1] and B[j] for each element).
+B+ until the end of the sequence is reached (the call will be done with
exist, then callbacks#discard_b will be called on each element of
element of +B+ (B[j]). If callbacks#finished_a does not
last index and element of +A+ (A[-1]) and the current index and
#traverse_sequence will try to call callbacks#finished_a with the
If arrow +a+ reaches the end of its sequence before arrow +b+ does,

=== End of Sequences

#traverse_sequences.
elements A[i] and B[j]. Return values are discarded by
action ("=", "+", or "-", respectively), the indicies +i+ and +j+, and the
callbacks#discard_b are invoked with an event comprising the
The methods for callbacks#match, callbacks#discard_a, and

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

then it will advance both arrows.
this happens, #traverse_sequences will call callbacks#match and
pointing to A[i] and arrow +b+ is pointing to B[j]. When
moment during the execution of #traverse_sequences when arrow +a+ is
both equal and part of the longest common subsequence, there will be some
way that if there are elements A[i] and B[j] which are
callback object before each advance. It will advance the arrows in such a
the sequences one element at a time, calling a method on the user-specified
respective sequences. #traverse_sequences will advance the arrows through
and +B+, the arrows will initially point to the first elements of their
If there are two arrows (+a+ and +b+) pointing to elements of sequences +A+

b---+
^
B = b c d e f j k l m r s t
A = a b c e h j l m n p
v
a---+

== Algorithm

sequence +B+.
callbacks#finished_b:: Called when +b+ has reached the end of
sequence +A+.
callbacks#finished_a:: Called when +a+ has reached the end of
element not in +A+.
callbacks#discard_b:: Called when +b+ is pointing to an
element not in +B+.
callbacks#discard_a:: Called when +a+ is pointing to an
common elements in +A+ and +B+.
callbacks#match:: Called when +a+ and +b+ are pointing to

Optional callback methods are emphasized.

== Callback Methods

traverse_sequences(seq1, seq2, Diff::LCS::ContextDiffCallbacks.new)

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

#diff and #lcs are implemented as calls to it.
#traverse_sequences is the most general facility provided by this module; 
def traverse_sequences(seq1, seq2, callbacks = Diff::LCS::SequenceCallbacks) #:yields change events:
  callbacks ||= Diff::LCS::SequenceCallbacks
  matches = Diff::LCS::Internals.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 |i|
    b_line = matches[i]
    ax = string ? seq1[i, 1] : seq1[i]
    bx = string ? seq2[bj, 1] : seq2[bj]
    if b_line.nil?
      unless ax.nil? or (string and ax.empty?)
        event = Diff::LCS::ContextChange.new('-', i, 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('+', i, 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('=', i, ax, bj, bx)
      event = yield event if block_given?
      callbacks.match(event)
      bj += 1
    end
    ai = i
  end
  ai += 1
  # The last entry (if any) processed was a match. +ai+ and +bj+ point just
  # past the last matching lines in their sequences.
  while (ai < a_size) or (bj < b_size)
    # last A?
    if ai == a_size and bj < b_size
      if callbacks.respond_to?(:finished_a) and !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
    # last B?
    if bj == b_size and ai < a_size
      if callbacks.respond_to?(:finished_b) and !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
    next unless 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