global

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

+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+ and

=== Context

Return values are discarded by #traverse_balanced.
the indexes +i+ and +j+, and the elements A[i] and B[j].
with an event comprising the action ("=", "+", "-", or "!", respectively),
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.
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

=== Discards

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+

=== 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

noticeable 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)

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

changes between the sequences.
deletions from one of the sequences, #traverse_balanced will report
common subsequence. Instead of viewing the changes as insertions or
different algorithm to iterate through the entries in the computed longest
#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.is_a?(String)
  # Process all the lines in the match vector.
  loop do
    # Find next match indexes +ma+ and +mb+
    loop do
      ma += 1
      break unless ma < matches.size && matches[ma].nil?
    end
    break if ma >= matches.size # end of matches?
    mb = matches[ma]
    # Change(seq2)
    while (ai < ma) || (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
        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)
        end
        bj += 1
      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) || (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
      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)
      end
      bj += 1
    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