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 indexes +i+ and +j+, and the
callbacks#discard_b are invoked with an event comprising the
The methods for callbacks#match, callbacks#discard_a, and

callback.
appropriate callback, then it will advance arrow +b+ and call the appropriate
subsequence, then #traverse_sequences will advance arrow +a+ 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.is_a?(String)
  a_size = seq1.size
  b_size = seq2.size
  ai = bj = 0
  matches.each do |b_line|
    if b_line.nil?
      unless seq1[ai].nil?
        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)
      end
    else
      ax = string ? seq1[ai, 1] : seq1[ai]
      loop do
        break unless bj < b_line
        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
      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)
      bj += 1
    end
    ai += 1
  end
  # 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) || (bj < b_size)
    # last A?
    if ai == a_size && bj < b_size
      if callbacks.respond_to?(:finished_a) && !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 && ai < a_size
      if callbacks.respond_to?(:finished_b) && !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