global

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

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

(A[i] and B[-1]).
on each element of +A+ until the end of the sequence is reached
on the callback object, then callbacks#discard_a will be called
(A[-1]). Again, if callbacks#finished_b does not exist
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+,

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

=== End of Sequences

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

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

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

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)

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

module; #diff and #lcs are implemented as calls to it.
#traverse_sequences is the most general facility provided by this 
def traverse_sequences(seq1, seq2, callbacks = Diff::LCS::SequenceCallbacks, &block) #: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 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
    # last B?
    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