Module: Diff::LCS

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

Overview

Diff::LCS 1.1.2

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 <[email protected]> Smalltalk version (1.2, 1993) and Ned Konz’s <[email protected]> Perl version (Algorithm::Diff).

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 by Ned Konz <[email protected]>, copyright &copy; 2000 - 2002 and the Smalltalk diff version by Mario I. Wolczko <[email protected]>, copyright &copy;

  1. Documentation includes work by Mark-Jason Dominus.

Licence

Copyright &copy; 2004 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 <[email protected]> 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: ChangeTypeTests, Ldiff Classes: Block, Change, ContextChange, ContextDiffCallbacks, DefaultCallbacks, DiffCallbacks, Hunk, SDiffCallbacks

Constant Summary collapse

VERSION = 
'1.1.2'
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

.__diff_direction(src, patchset, limit = nil) ⇒ Object

Examine the patchset and the source to see in which direction the patch should be applied.

WARNING: By default, this examines the whole patch, so this could take some time. This also works better with Diff::LCS::ContextChange or Diff::LCS::Change as its source, as an array will cause the creation of one of the above.



958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
 
# File 'lib/watobo/external/diff/lcs.rb', line 958

def __diff_direction(src, patchset, limit = nil)
  count = left = left_miss = right = right_miss = 0
  string = src.kind_of?(String)

  patchset.each do |change|
    count += 1

    case change
    when Diff::LCS::Change
        # With a simplistic change, we can't tell the difference between
        # the left and right on '!' actions, so we ignore those. On '='
        # actions, if there's a miss, we miss both left and right.
      element = string ? src[change.position, 1] : src[change.position]

      case change.action
      when '-'
        if element == change.element
          left += 1
        else
          left_miss += 1
        end
      when '+'
        if element == change.element
          right += 1
        else
          right_miss += 1
        end
      when '='
        if element != change.element
          left_miss += 1
          right_miss += 1
        end
      end
    when Diff::LCS::ContextChange
      case change.action
      when '-' # Remove details from the old string
        element = string ? src[change.old_position, 1] : src[change.old_position]
        if element == change.old_element
          left += 1
        else
          left_miss += 1
        end
      when '+'
        element = string ? src[change.new_position, 1] : src[change.new_position]
        if element == change.new_element
          right += 1
        else
          right_miss += 1
        end
      when '='
        le = string ? src[change.old_position, 1] : src[change.old_position]
        re = string ? src[change.new_position, 1] : src[change.new_position]

        left_miss += 1 if le != change.old_element
        right_miss += 1 if re != change.new_element
      when '!'
        element = string ? src[change.old_position, 1] : src[change.old_position]
        if element == change.old_element
          left += 1
        else
          element = string ? src[change.new_position, 1] : src[change.new_position]
          if element == change.new_element
            right += 1
          else
            left_miss += 1
            right_miss += 1
          end
        end
      end
    end

    break if not limit.nil? and count > limit
  end

  no_left = (left == 0) and (left_miss >= 0)
  no_right = (right == 0) and (right_miss >= 0)

  case [no_left, no_right]
  when [false, true]
    return :patch
  when [true, false]
    return :unpatch
  else
    raise "The provided patchset does not appear to apply to the provided value as either source or destination value."
  end
end

.__inverse_vector(a, vector) ⇒ Object

If vector maps the matching elements of another collection onto this Enumerable, compute the inverse vector that maps this Enumerable onto the collection. (Currently unused.)



931
932
933
934
935
936
937
 
# File 'lib/watobo/external/diff/lcs.rb', line 931

def __inverse_vector(a, vector)
  inverse = a.dup
  (0 ... vector.size).each do |ii|
    inverse[vector[ii]] = ii unless vector[ii].nil?
  end
  inverse
end

.__lcs(a, b) ⇒ Object

Compute the longest common subsequence between the sequenced Enumerables a and b. The result is an array whose contents is such that

result = Diff::LCS.__lcs(a, b)
result.each_with_index do |e, ii|
  assert_equal(a[ii], b[e]) unless e.nil?
end



835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
 
# File 'lib/watobo/external/diff/lcs.rb', line 835

def __lcs(a, b)
  a_start = b_start = 0
  a_finish = a.size - 1
  b_finish = b.size - 1
  vector = []

    # Prune off any common elements at the beginning...
  while (a_start <= a_finish) and
        (b_start <= b_finish) and
        (a[a_start] == b[b_start])
    vector[a_start] = b_start
    a_start += 1
    b_start += 1
  end

    # Now the end...
  while (a_start <= a_finish) and
        (b_start <= b_finish) and
        (a[a_finish] == b[b_finish])
    vector[a_finish] = b_finish
    a_finish -= 1
    b_finish -= 1
  end

    # Now, compute the equivalence classes of positions of elements.
  b_matches = Diff::LCS.__position_hash(b, b_start .. b_finish)

  thresh = []
  links = []

  (a_start .. a_finish).each do |ii|
    ai = a.kind_of?(String) ? a[ii, 1] : a[ii]
    bm = b_matches[ai]
    kk = nil
    bm.reverse_each do |jj|
      if kk and (thresh[kk] > jj) and (thresh[kk - 1] < jj)
        thresh[kk] = jj
      else
        kk = Diff::LCS.__replace_next_larger(thresh, jj, kk)
      end
      links[kk] = [ (kk > 0) ? links[kk - 1] : nil, ii, jj ] unless kk.nil?
    end
  end

  unless thresh.empty?
    link = links[thresh.size - 1]
    while not link.nil?
      vector[link[1]] = link[2]
      link = link[0]
    end
  end

  vector
end

.__normalize_patchset(patchset) ⇒ Object

Normalize the patchset. A patchset is always a sequence of changes, but how those changes are represented may vary, depending on how they were generated. In all cases we support, we also support the array representation of the changes. The formats are:

[ # patchset <- Diff::LCS.diff(a, b)
  [ # one or more hunks
    Diff::LCS::Change # one or more changes
  ] ]

[ # patchset, equivalent to the above
  [ # one or more hunks
    [ action, line, value ] # one or more changes
  ] ]

[ # patchset <- Diff::LCS.diff(a, b, Diff::LCS::ContextDiffCallbacks)
  #       OR <- Diff::LCS.sdiff(a, b, Diff::LCS::ContextDiffCallbacks)
  [ # one or more hunks
    Diff::LCS::ContextChange # one or more changes
  ] ]

[ # patchset, equivalent to the above
  [ # one or more hunks
    [ action, [ old line, old value ], [ new line, new value ] ]
      # one or more changes
  ] ]

[ # patchset <- Diff::LCS.sdiff(a, b)
  #       OR <- Diff::LCS.diff(a, b, Diff::LCS::SDiffCallbacks)
  Diff::LCS::ContextChange # one or more changes
]

[ # patchset, equivalent to the above
  [ action, [ old line, old value ], [ new line, new value ] ]
    # one or more changes
]

The result of this will be either of the following.

[ # patchset
  Diff::LCS::ContextChange # one or more changes
]

[ # patchset
  Diff::LCS::Change # one or more changes
]

If either of the above is provided, it will be returned as such.



1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
 
# File 'lib/watobo/external/diff/lcs.rb', line 1094

def __normalize_patchset(patchset)
  patchset.map do |hunk|
    case hunk
    when Diff::LCS::ContextChange, Diff::LCS::Change
      hunk
    when Array
      if (not hunk[0].kind_of?(Array)) and hunk[1].kind_of?(Array) and hunk[2].kind_of?(Array)
        Diff::LCS::ContextChange.from_a(hunk)
      else
        hunk.map do |change|
          case change
          when Diff::LCS::ContextChange, Diff::LCS::Change
            change
          when Array
              # change[1] will ONLY be an array in a ContextChange#to_a call.
              # In Change#to_a, it represents the line (singular).
            if change[1].kind_of?(Array)
              Diff::LCS::ContextChange.from_a(change)
            else
              Diff::LCS::Change.from_a(change)
            end
          end
        end
      end
    else
      raise ArgumentError, "Cannot normalise a hunk of class #{hunk.class}."
    end
  end.flatten
end

.__position_hash(enum, interval = 0 .. -1)) ⇒ Object

Returns a hash mapping each element of an Enumerable to the set of positions it occupies in the Enumerable, optionally restricted to the elements specified in the range of indexes specified by interval.



942
943
944
945
946
947
948
949
 
# File 'lib/watobo/external/diff/lcs.rb', line 942

def __position_hash(enum, interval = 0 .. -1)
  hash = Hash.new { |hh, kk| hh[kk] = [] }
  interval.each do |ii|
    kk = enum.kind_of?(String) ? enum[ii, 1] : enum[ii]
    hash[kk] << ii
  end
  hash
end

.__replace_next_larger(enum, value, last_index = nil) ⇒ Object

Find the place at which value would normally be inserted into the Enumerable. If that place is already occupied by value, do nothing and return nil. If the place does not exist (i.e., it is off the end of the Enumerable), add it to the end. Otherwise, replace the element at that point with value. It is assumed that the Enumerable’s values are numeric.

This operation preserves the sort order.



898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
 
# File 'lib/watobo/external/diff/lcs.rb', line 898

def __replace_next_larger(enum, value, last_index = nil)
    # Off the end?
  if enum.empty? or (value > enum[-1])
    enum << value
    return enum.size - 1
  end

    # Binary search for the insertion point
  last_index ||= enum.size
  first_index = 0
  while (first_index <= last_index)
    ii = (first_index + last_index) >> 1

    found = enum[ii]

    if value == found
      return nil
    elsif value > found
      first_index = ii + 1
    else
      last_index = ii - 1
    end
  end

    # The insertion point is in first_index; overwrite the next larger
    # value.
  enum[first_index] = value
  return first_index
end

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

Diff::LCS.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.



273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
 
# File 'lib/watobo/external/diff/lcs.rb', line 273

def diff(seq1, seq2, callbacks = nil, &block) # :yields diff changes:
  callbacks ||= Diff::LCS::DiffCallbacks
  if callbacks.kind_of?(Class)
    cb = callbacks.new rescue callbacks
    callbacks = cb
  end
  traverse_sequences(seq1, seq2, callbacks)
  callbacks.finish if callbacks.respond_to?(:finish)

  if block_given?
    res = callbacks.diffs.map do |hunk|
      if hunk.kind_of?(Array)
        hunk = hunk.map { |block| yield block }
      else
        yield hunk
      end
    end
    res
  else
    callbacks.diffs
  end
end

.LCS(seq1, seq2, &block) ⇒ Object

Given two sequenced Enumerables, LCS returns an Array containing their longest common subsequences.

lcs = Diff::LCS.LCS(seq1, seq2)

This array whose contents is such that:

lcs.each_with_index do |ee, ii|
  assert(ee.nil? || (seq1[ii] == seq2[ee]))
end

If a block is provided, the matching subsequences will be yielded from seq1 in turn and may be modified before they are placed into the returned Array of subsequences.



249
250
251
252
253
254
255
256
257
258
259
260
261
262
 
# File 'lib/watobo/external/diff/lcs.rb', line 249

def LCS(seq1, seq2, &block) #:yields seq1[ii] for each matched:
  matches = Diff::LCS.__lcs(seq1, seq2)
  ret = []
  matches.each_with_index do |ee, ii|
    unless matches[ii].nil?
      if block_given?
        ret << (yield seq1[ii])
      else
        ret << seq1[ii]
      end
    end
  end
  ret
end

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

Given a patchset, convert the current version to the new version. If direction is not specified (must be :patch or :unpatch), then discovery of the direction of the patch will be attempted.



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
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
 
# File 'lib/watobo/external/diff/lcs.rb', line 716

def patch(src, patchset, direction = nil)
  string = src.kind_of?(String)
    # Start with a new empty type of the source's class
  res = src.class.new

    # Normalize the patchset.
  patchset = __normalize_patchset(patchset)

  direction ||= Diff::LCS.__diff_direction(src, patchset)
  direction ||= :patch

  ai = bj = 0

  patchset.each do |change|
      # Both Change and ContextChange support #action
    action = PATCH_MAP[direction][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.



823
824
825
 
# File 'lib/watobo/external/diff/lcs.rb', line 823

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

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

Diff::LCS.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.



310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
 
# File 'lib/watobo/external/diff/lcs.rb', line 310

def sdiff(seq1, seq2, callbacks = nil, &block) #:yields diff changes:
  callbacks ||= Diff::LCS::SDiffCallbacks
  if callbacks.kind_of?(Class)
    cb = callbacks.new rescue callbacks
    callbacks = cb
  end
  traverse_balanced(seq1, seq2, callbacks)
  callbacks.finish if callbacks.respond_to?(:finish)

  if block_given?
    res = callbacks.diffs.map do |hunk|
      if hunk.kind_of?(Array)
        hunk = hunk.map { |block| yield block }
      else
        yield hunk
      end
    end
    res
  else
    callbacks.diffs
  end
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. 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.



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
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
 
# File 'lib/watobo/external/diff/lcs.rb', line 604

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

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

Diff::LCS.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)

#diff is implemented with #traverse_sequences.

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

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 ii and jj, and the elements A[ii] and B[jj]. 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 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[jj]). 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[jj] 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[ii]) 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[ii] 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.



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
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
 
# File 'lib/watobo/external/diff/lcs.rb', line 414

def traverse_sequences(seq1, seq2, callbacks = Diff::LCS::SequenceCallbacks, &block) #:yields change events:
  matches = Diff::LCS.__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 |ii|
    b_line = matches[ii]

    ax = string ? seq1[ii, 1] : seq1[ii]
    bx = string ? seq2[bj, 1] : seq2[bj]

    if b_line.nil?
      unless ax.nil?
        event = Diff::LCS::ContextChange.new('-', ii, 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('+', ii, 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('=', ii, ax, bj, bx)
      event = yield event if block_given?
      callbacks.match(event)
      bj += 1
    end
    ai = ii
  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.



817
818
819
 
# File 'lib/watobo/external/diff/lcs.rb', line 817

def unpatch!(src, patchset)
  Diff::LCS.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.



183
184
185
 
# File 'lib/watobo/external/diff/lcs.rb', line 183

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)



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

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

#patch(patchset) ⇒ Object

Attempts to patch a copy of self with the provided patchset. See Diff::LCS#patch.



210
211
212
 
# File 'lib/watobo/external/diff/lcs.rb', line 210

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

#patch!(patchset) ⇒ Object

Attempts to patch self with the provided patchset. See Diff::LCS#patch!. Does no autodiscovery.



222
223
224
 
# File 'lib/watobo/external/diff/lcs.rb', line 222

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

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

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



189
190
191
 
# File 'lib/watobo/external/diff/lcs.rb', line 189

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.



203
204
205
206
 
# File 'lib/watobo/external/diff/lcs.rb', line 203

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.



195
196
197
198
 
# File 'lib/watobo/external/diff/lcs.rb', line 195

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

#unpatch(patchset) ⇒ Object

Attempts to unpatch a copy of self with the provided patchset. See Diff::LCS#patch.



216
217
218
 
# File 'lib/watobo/external/diff/lcs.rb', line 216

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

#unpatch!(patchset) ⇒ Object

Attempts to unpatch self with the provided patchset. See Diff::LCS#unpatch. Does no autodiscovery.



228
229
230
 
# File 'lib/watobo/external/diff/lcs.rb', line 228

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