Module: Diff::LCS

Included in:
Array, String
Defined in:
lib/diff/lcs.rb,
lib/diff/lcs.rb,
lib/diff/lcs/callbacks.rb

Overview

Diff::LCS 1.2.5

Computes “intelligent” differences between two sequenced Enumerables. This is an implementation of the McIlroy-Hunt “diff” algorithm for Enumerable objects that include Diffable.

Based on Mario I. Wolczko's Smalltalk version (1.2, 1993) and Ned Konz's Perl version (Algorithm::Diff 1.15).

Synopsis

require 'diff/lcs'

seq1 = %w(a b c e h j l m n p)
seq2 = %w(b c d e f j k l m r s t)

lcs = Diff::LCS.lcs(seq1, seq2)
diffs = Diff::LCS.diff(seq1, seq2)
sdiff = Diff::LCS.sdiff(seq1, seq2)
seq = Diff::LCS.traverse_sequences(seq1, seq2, callback_obj)
bal = Diff::LCS.traverse_balanced(seq1, seq2, callback_obj)
seq2 == Diff::LCS.patch(seq1, diffs)
seq2 == Diff::LCS.patch!(seq1, diffs)
seq1 == Diff::LCS.unpatch(seq2, diffs)
seq1 == Diff::LCS.unpatch!(seq2, diffs)
seq2 == Diff::LCS.patch(seq1, sdiff)
seq2 == Diff::LCS.patch!(seq1, sdiff)
seq1 == Diff::LCS.unpatch(seq2, sdiff)
seq1 == Diff::LCS.unpatch!(seq2, sdiff)

Alternatively, objects can be extended with Diff::LCS:

seq1.extend(Diff::LCS)
lcs = seq1.lcs(seq2)
diffs = seq1.diff(seq2)
sdiff = seq1.sdiff(seq2)
seq = seq1.traverse_sequences(seq2, callback_obj)
bal = seq1.traverse_balanced(seq2, callback_obj)
seq2 == seq1.patch(diffs)
seq2 == seq1.patch!(diffs)
seq1 == seq2.unpatch(diffs)
seq1 == seq2.unpatch!(diffs)
seq2 == seq1.patch(sdiff)
seq2 == seq1.patch!(sdiff)
seq1 == seq2.unpatch(sdiff)
seq1 == seq2.unpatch!(sdiff)

Default extensions are provided for Array and String objects through the use of 'diff/lcs/array' and 'diff/lcs/string'.

Introduction (by Mark-Jason Dominus)

The following text is from the Perl documentation. The only changes have been to make the text appear better in Rdoc.

I once read an article written by the authors of diff; they said that they hard worked very hard on the algorithm until they found the right one.

I think what they ended up using (and I hope someone will correct me, because I am not very confident about this) was the `longest common subsequence' method. In the LCS problem, you have two sequences of items:

a b c d f g h j q z
a b c d e f g i j k r x y z

and you want to find the longest sequence of items that is present in both original sequences in the same order. That is, you want to find a new sequence S which can be obtained from the first sequence by deleting some items, and from the second sequence by deleting other items. You also want S to be as long as possible. In this case S is:

a b c d f g j z

From there it's only a small step to get diff-like output:

e   h i   k   q r x y
+   - +   +   - + + +

This module solves the LCS problem. It also includes a canned function to generate diff-like output.

It might seem from the example above that the LCS of two sequences is always pretty obvious, but that's not always the case, especially when the two sequences have many repeated elements. For example, consider

a x b y c z p d q
a b c a x b y c z

A naive approach might start by matching up the a and b that appear at the beginning of each sequence, like this:

a x b y c         z p d q
a   b   c a b y c z

This finds the common subsequence a b c z. But actually, the LCS is +a x b y c z+:

      a x b y c z p d q
a b c a x b y c z

Author

This version is by Austin Ziegler <[email protected]>.

It is based on the Perl Algorithm::Diff (1.15) by Ned Konz , copyright &copy; 2000&ndash;2002 and the Smalltalk diff version by Mario I. Wolczko, copyright &copy; 1993. Documentation includes work by Mark-Jason Dominus.

Licence

Copyright &copy; 2004&ndash;2013 Austin Ziegler This program is free software; you can redistribute it and/or modify it under the same terms as Ruby, or alternatively under the Perl Artistic licence.

Credits

Much of the documentation is taken directly from the Perl Algorithm::Diff implementation and was written originally by Mark-Jason Dominus and later by Ned Konz. The basic Ruby implementation was re-ported from the Smalltalk implementation, available at st.cs.uiuc.edu/pub/Smalltalk/MANCHESTER/manchester/4.0/diff.st

#sdiff and #traverse_balanced were written for the Perl version by Mike Schilli <[email protected]>.

“The algorithm is described in A Fast Algorithm for Computing Longest Common Subsequences, CACM, vol.20, no.5, pp.350-353, May 1977, with a few minor improvements to improve the speed.”

Defined Under Namespace

Modules: Internals, Ldiff Classes: Block, Change, ContextChange, ContextDiffCallbacks, DefaultCallbacks, DiffCallbacks, HTMLDiff, Hunk, SDiffCallbacks

Constant Summary collapse

VERSION =
'1.2.5'
PATCH_MAP =

:nodoc:

{ #:nodoc:
  :patch => { '+' => '+', '-' => '-', '!' => '!', '=' => '=' },
  :unpatch => { '+' => '-', '-' => '+', '!' => '!', '=' => '=' }
}
SequenceCallbacks =

An alias for DefaultCallbacks that is used in Diff::LCS#traverse_sequences.

Diff::LCS.LCS(seq1, seq2, Diff::LCS::SequenceCallbacks)
DefaultCallbacks
BalancedCallbacks =

An alias for DefaultCallbacks that is used in Diff::LCS#traverse_balanced.

Diff::LCS.LCS(seq1, seq2, Diff::LCS::BalancedCallbacks)
DefaultCallbacks

Class Method Summary collapse

Instance Method Summary collapse

Class Method Details

.callbacks_for(callbacks) ⇒ Object


49
50
51
# File 'lib/diff/lcs/callbacks.rb', line 49

def self.callbacks_for(callbacks)
  callbacks.new rescue callbacks
end

.diff(seq1, seq2, callbacks = nil, &block) ⇒ Object

#diff computes the smallest set of additions and deletions necessary to turn the first sequence into the second, and returns a description of these changes.

See Diff::LCS::DiffCallbacks for the default behaviour. An alternate behaviour may be implemented with Diff::LCS::ContextDiffCallbacks. If a Class argument is provided for callbacks, #diff will attempt to initialise it. If the callbacks object (possibly initialised) responds to #finish, it will be called.


245
246
247
248
# File 'lib/diff/lcs.rb', line 245

def diff(seq1, seq2, callbacks = nil, &block) # :yields diff changes:
  diff_traversal(:diff, seq1, seq2, callbacks || Diff::LCS::DiffCallbacks,
                 &block)
end

.diff_traversal(method, seq1, seq2, callbacks, &block) ⇒ Object


4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# File 'lib/diff/lcs/internals.rb', line 4

def diff_traversal(method, seq1, seq2, callbacks, &block)
  callbacks = callbacks_for(callbacks)
  case method
  when :diff
    traverse_sequences(seq1, seq2, callbacks)
  when :sdiff
    traverse_balanced(seq1, seq2, callbacks)
  end
  callbacks.finish if callbacks.respond_to? :finish

  if block
    callbacks.diffs.map do |hunk|
      if hunk.kind_of? Array
        hunk.map { |hunk_block| block[hunk_block] }
      else
        block[hunk]
      end
    end
  else
    callbacks.diffs
  end
end

.lcs(seq1, seq2, &block) ⇒ Object Also known as: LCS

:yields seq1 for each matched:


221
222
223
224
225
226
227
228
229
230
231
232
233
# File 'lib/diff/lcs.rb', line 221

def lcs(seq1, seq2, &block) #:yields seq1[i] for each matched:
  matches = Diff::LCS::Internals.lcs(seq1, seq2)
  ret = []
  string = seq1.kind_of? String
  matches.each_with_index do |e, i|
    unless matches[i].nil?
      v = string ? seq1[i, 1] : seq1[i]
      v = block[v] if block
      ret << v
    end
  end
  ret
end

.patch(src, patchset, direction = nil) ⇒ Object

Applies a patchset to the sequence src according to the direction (:patch or :unpatch), producing a new sequence.

If the direction is not specified, Diff::LCS::patch will attempt to discover the direction of the patchset.

A patchset can be considered to apply forward (:patch) if the following expression is true:

patch(s1, diff(s1, s2)) -> s2

A patchset can be considered to apply backward (:unpatch) if the following expression is true:

patch(s2, diff(s1, s2)) -> s1

If the patchset contains no changes, the src value will be returned as either src.dup or src. A patchset can be deemed as having no changes if the following predicate returns true:

patchset.empty? or
  patchset.flatten.all? { |change| change.unchanged? }

Patchsets

A patchset is always an enumerable sequence of changes, hunks of changes, or a mix of the two. A hunk of changes is an enumerable sequence of changes:

[ # patchset
  # change
  [ # hunk
    # change
  ]
]

The patch method accepts patchsets that are enumerable sequences containing either Diff::LCS::Change objects (or a subclass) or the array representations of those objects. Prior to application, array representations of Diff::LCS::Change objects will be reified.


689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
# File 'lib/diff/lcs.rb', line 689

def patch(src, patchset, direction = nil)
  # Normalize the patchset.
  has_changes, patchset = Diff::LCS::Internals.analyze_patchset(patchset)

  if not has_changes
    return src.dup if src.respond_to? :dup
    return src
  end

  string = src.kind_of?(String)
  # Start with a new empty type of the source's class
  res = src.class.new

  direction ||= Diff::LCS::Internals.intuit_diff_direction(src, patchset)

  ai = bj = 0

  patch_map = PATCH_MAP[direction]

  patchset.flatten.each do |change|
    # Both Change and ContextChange support #action
    action = patch_map[change.action]

    case change
    when Diff::LCS::ContextChange
      case direction
      when :patch
        el = change.new_element
        op = change.old_position
        np = change.new_position
      when :unpatch
        el = change.old_element
        op = change.new_position
        np = change.old_position
      end

      case action
      when '-' # Remove details from the old string
        while ai < op
          res << (string ? src[ai, 1] : src[ai])
          ai += 1
          bj += 1
        end
        ai += 1
      when '+'
        while bj < np
          res << (string ? src[ai, 1] : src[ai])
          ai += 1
          bj += 1
        end

      res << el
      bj += 1
      when '='
        # This only appears in sdiff output with the SDiff callback.
        # Therefore, we only need to worry about dealing with a single
        # element.
        res << el

        ai += 1
        bj += 1
      when '!'
        while ai < op
          res << (string ? src[ai, 1] : src[ai])
          ai += 1
          bj += 1
        end

      bj += 1
      ai += 1

      res << el
      end
    when Diff::LCS::Change
      case action
      when '-'
        while ai < change.position
          res << (string ? src[ai, 1] : src[ai])
          ai += 1
          bj += 1
        end
      ai += 1
      when '+'
        while bj < change.position
          res << (string ? src[ai, 1] : src[ai])
          ai += 1
          bj += 1
        end

      bj += 1

      res << change.element
      end
    end
  end

  while ai < src.size
    res << (string ? src[ai, 1] : src[ai])
    ai += 1
    bj += 1
  end

  res
end

.patch!(src, patchset) ⇒ Object

Given a set of patchset, convert the current version to the next version. Does no auto-discovery.


802
803
804
# File 'lib/diff/lcs.rb', line 802

def patch!(src, patchset)
  patch(src, patchset, :patch)
end

.sdiff(seq1, seq2, callbacks = nil, &block) ⇒ Object

#sdiff computes all necessary components to show two sequences and their minimized differences side by side, just like the Unix utility sdiff does:

old        <     -
same             same
before     |     after
-          >     new

See Diff::LCS::SDiffCallbacks for the default behaviour. An alternate behaviour may be implemented with Diff::LCS::ContextDiffCallbacks. If a Class argument is provided for callbacks, #diff will attempt to initialise it. If the callbacks object (possibly initialised) responds to #finish, it will be called.


264
265
266
267
# File 'lib/diff/lcs.rb', line 264

def sdiff(seq1, seq2, callbacks = nil, &block) #:yields diff changes:
  diff_traversal(:sdiff, seq1, seq2, callbacks || Diff::LCS::SDiffCallbacks,
                 &block)
end

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

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.

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[i] and B[j] 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[i] and arrow b is pointing to B[j]. 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 i and j, and the elements A[i] and B[j]. Return values are discarded by #traverse_balanced.

Context

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


541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
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
# File 'lib/diff/lcs.rb', line 541

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

.traverse_sequences(seq1, seq2, callbacks = Diff::LCS::SequenceCallbacks, &block) ⇒ Object

#traverse_sequences is the most general facility provided by this module; #diff and #lcs are implemented as calls to it.

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

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

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#finished_a

Called when a has reached the end of sequence A.

callbacks#finished_b

Called when b has reached the end of sequence B.

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

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[i] and B[j] 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[i] and arrow b is pointing to B[j]. When this happens, #traverse_sequences will call callbacks#match and then it will advance both arrows.

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. If both arrows point to elements that are not part of the longest common subsequence, then #traverse_sequences will advance one of them and call the appropriate callback, but it is not specified which it will call.

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

End of Sequences

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

If b reaches the end of B before a reaches the end of A, callbacks#finished_b will be called with the current index and element of A (A[i]) and the last index and element of B (A[-1]). Again, if callbacks#finished_b does not exist on the callback object, then callbacks#discard_a will be called on each element of A until the end of the sequence is reached (A[i] and B[-1]).

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


350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
# File 'lib/diff/lcs.rb', line 350

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

.unpatch!(src, patchset) ⇒ Object

Given a set of patchset, convert the current version to the prior version. Does no auto-discovery.


796
797
798
# File 'lib/diff/lcs.rb', line 796

def unpatch!(src, patchset)
  patch(src, patchset, :unpatch)
end

Instance Method Details

#diff(other, callbacks = nil, &block) ⇒ Object

Returns the difference set between self and other. See Diff::LCS#diff.


149
150
151
# File 'lib/diff/lcs.rb', line 149

def diff(other, callbacks = nil, &block)
  Diff::LCS.diff(self, other, callbacks, &block)
end

#lcs(other, &block) ⇒ Object

Returns an Array containing the longest common subsequence(s) between self and other. See Diff::LCS#LCS.

lcs = seq1.lcs(seq2)

143
144
145
# File 'lib/diff/lcs.rb', line 143

def lcs(other, &block) #:yields self[i] if there are matched subsequences:
  Diff::LCS.lcs(self, other, &block)
end

#patch(patchset) ⇒ Object

Attempts to patch self with the provided patchset. A new sequence based on self and the patchset will be created. See Diff::LCS#patch. Attempts to autodiscover the direction of the patch.


177
178
179
# File 'lib/diff/lcs.rb', line 177

def patch(patchset)
  Diff::LCS.patch(self, patchset)
end

#patch!(patchset) ⇒ Object

Attempts to patch self with the provided patchset. A new sequence based on self and the patchset will be created. See Diff::LCS#patch. Does no patch direction autodiscovery.


185
186
187
# File 'lib/diff/lcs.rb', line 185

def patch!(patchset)
  Diff::LCS.patch!(self, patchset)
end

#patch_me(patchset) ⇒ Object

Attempts to patch self with the provided patchset, using #patch!. If the sequence this is used on supports #replace, the value of self will be replaced. See Diff::LCS#patch. Does no patch direction autodiscovery.


199
200
201
202
203
204
205
# File 'lib/diff/lcs.rb', line 199

def patch_me(patchset)
  if respond_to? :replace
    replace(patch!(patchset))
  else
    patch!(patchset)
  end
end

#sdiff(other, callbacks = nil, &block) ⇒ Object

Returns the balanced (“side-by-side”) difference set between self and other. See Diff::LCS#sdiff.


155
156
157
# File 'lib/diff/lcs.rb', line 155

def sdiff(other, callbacks = nil, &block)
  Diff::LCS.sdiff(self, other, callbacks, &block)
end

#traverse_balanced(other, callbacks = nil, &block) ⇒ Object

Traverses the discovered longest common subsequences between self and other using the alternate, balanced algorithm. See Diff::LCS#traverse_balanced.


169
170
171
172
# File 'lib/diff/lcs.rb', line 169

def traverse_balanced(other, callbacks = nil, &block)
  traverse_balanced(self, other, callbacks ||
                    Diff::LCS.YieldingCallbacks, &block)
end

#traverse_sequences(other, callbacks = nil, &block) ⇒ Object

Traverses the discovered longest common subsequences between self and other. See Diff::LCS#traverse_sequences.


161
162
163
164
# File 'lib/diff/lcs.rb', line 161

def traverse_sequences(other, callbacks = nil, &block)
  traverse_sequences(self, other, callbacks ||
                     Diff::LCS.YieldingCallbacks, &block)
end

#unpatchObject

Attempts to patch self with the provided patchset. A new sequence based on self and the patchset will be created. See Diff::LCS#patch. Attempts to autodiscover the direction of the patch.


180
181
182
# File 'lib/diff/lcs.rb', line 180

def patch(patchset)
  Diff::LCS.patch(self, patchset)
end

#unpatch!(patchset) ⇒ Object

Attempts to unpatch self with the provided patchset. A new sequence based on self and the patchset will be created. See Diff::LCS#unpatch. Does no patch direction autodiscovery.


192
193
194
# File 'lib/diff/lcs.rb', line 192

def unpatch!(patchset)
  Diff::LCS.unpatch!(self, patchset)
end

#unpatch_me(patchset) ⇒ Object

Attempts to unpatch self with the provided patchset, using #unpatch!. If the sequence this is used on supports #replace, the value of self will be replaced. See Diff::LCS#unpatch. Does no patch direction autodiscovery.


211
212
213
214
215
216
217
# File 'lib/diff/lcs.rb', line 211

def unpatch_me(patchset)
  if respond_to? :replace
    replace(unpatch!(patchset))
  else
    unpatch!(patchset)
  end
end