global

def traverse_balanced(seq1, seq2, callbacks = Diff::LCS::BalancedCallbacks)

and +b+ are considered to be pointing to matching or changed elements.
Note that +i+ and +j+ may not be the same index position, even if +a+
=== Context

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

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

=== Changes

callbacks#discard_b, depending on which arrow it advanced.
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

=== Discards

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

=== Matches

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

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

occurred.
the same; a change has
A[a] and B[b] are not
the same relative position, but
callbacks#change:: Called when +a+ and +b+ are pointing to
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

#sdiff is implemented with #traverse_balanced.

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

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

changes between the sequences.
or deletions from one of the sequences, #traverse_balanced will report
longest common subsequence. Instead of viewing the changes as insertions
different algorithm to iterate through the entries in the computed
#traverse_balanced is an alternative to #traverse_sequences. It uses a 
def traverse_balanced(seq1, seq2, callbacks = Diff::LCS::BalancedCallbacks)
  matches = Diff::LCS::Internals.lcs(seq1, seq2)
  a_size = seq1.size
  b_size = seq2.size
  ai = bj = mb = 0
  ma = -1
  string = seq1.kind_of?(String)
  # Process all the lines in the match vector.
  loop do
    # Find next match indices +ma+ and +mb+
    loop do
      ma += 1
      break unless ma < matches.size and matches[ma].nil?
    end
    break if ma >= matches.size # end of matches?
    mb = matches[ma]
    # Change(seq2)
    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
    # Match
    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