Method: Diff::LCS.traverse_balanced

Defined in:
lib/gems/diff-lcs-1.1.2/lib/diff/lcs.rb

.traverse_balanced(seq1, seq2, callbacks = Diff::LCS::BalancedCallbacks) ⇒ Object

#traverse_balanced is an alternative to #traverse_sequences. It uses a different algorithm to iterate through the entries in the computed longest common subsequence. Instead of viewing the changes as insertions or deletions from one of the sequences, #traverse_balanced will report changes between the sequences. To represent a

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

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

#sdiff is implemented with #traverse_balanced.

Callback Methods

Optional callback methods are emphasized.

callbacks#match

Called when a and b are pointing to common elements in A and B.

callbacks#discard_a

Called when a is pointing to an element not in B.

callbacks#discard_b

Called when b is pointing to an element not in A.

callbacks#change

Called when a and b are pointing to the same relative position, but A[a] and B[b] are not the same; a change has occurred.

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

The sdiff function of this module is implemented as call to #traverse_balanced.

Algorithm

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

Matches

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

Discards

Otherwise, one of the arrows is pointing to an element of its sequence that is not part of the longest common subsequence. #traverse_sequences will advance that arrow and will call callbacks#discard_a or callbacks#discard_b, depending on which arrow it advanced.

Changes

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

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

Context

Note that ii and jj may not be the same index position, even if a and b are considered to be pointing to matching or changed elements.



585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
 
# File 'lib/gems/diff-lcs-1.1.2/lib/diff/lcs.rb', line 585

def traverse_balanced(seq1, seq2, callbacks = Diff::LCS::BalancedCallbacks)
  matches = Diff::LCS.__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