Diff

    # File lib/diff.rb, line 5
 5:   def Diff.lcs(a, b)
 6:     astart = 0
 7:     bstart = 0
 8:     afinish = a.length-1
 9:     bfinish = b.length-1
10:     mvector = []
11:     
12:     # First we prune off any common elements at the beginning
13:     while (astart <= afinish && bstart <= afinish && a[astart] == b[bstart])
14:       mvector[astart] = bstart
15:       astart += 1
16:       bstart += 1
17:     end
18:     
19:     # now the end
20:     while (astart <= afinish && bstart <= bfinish && a[afinish] == b[bfinish])
21:       mvector[afinish] = bfinish
22:       afinish -= 1
23:       bfinish -= 1
24:     end
25: 
26:     bmatches = b.reverse_hash(bstart..bfinish)
27:     thresh = []
28:     links = []
29:     
30:     (astart..afinish).each { |aindex|
31:       aelem = a[aindex]
32:       next unless bmatches.has_key? aelem
33:       k = nil
34:       bmatches[aelem].reverse.each { |bindex|
35:         if k && (thresh[k] > bindex) && (thresh[k-1] < bindex)
36:           thresh[k] = bindex
37:         else
38:           k = thresh.replacenextlarger(bindex, k)
39:         end
40:         links[k] = [ (k==0) ? nil : links[k-1], aindex, bindex ] if k
41:       }
42:     }
43: 
44:     if !thresh.empty?
45:       link = links[thresh.length-1]
46:       while link
47:         mvector[link[1]] = link[2]
48:         link = link[0]
49:       end
50:     end
51: 
52:     return mvector
53:   end

     # File lib/diff.rb, line 109
109:   def initialize(diffs_or_a, b = nil, isstring = nil)
110:     if b.nil?
111:       @diffs = diffs_or_a
112:       @isstring = isstring
113:     else
114:       @diffs = []
115:       @curdiffs = []
116:       makediff(diffs_or_a, b)
117:       @difftype = diffs_or_a.type
118:     end
119:   end

     # File lib/diff.rb, line 134
134:   def compact
135:     return Diff.new(compactdiffs)
136:   end

     # File lib/diff.rb, line 138
138:   def compact!
139:     @diffs = compactdiffs
140:   end

     # File lib/diff.rb, line 84
 84:   def compactdiffs
 85:     diffs = []
 86:     @diffs.each { |df|
 87:       i = 0
 88:       curdiff = []
 89:       while i < df.length
 90:         whot = df[i][0]
 91:         s = @isstring ? df[i][2].chr : [df[i][2]]
 92:         p = df[i][1]
 93:         last = df[i][1]
 94:         i += 1
 95:         while df[i] && df[i][0] == whot && df[i][1] == last+1
 96:           s << df[i][2]
 97:           last  = df[i][1]
 98:           i += 1
 99:         end
100:         curdiff.push [whot, p, s]
101:       end
102:       diffs.push curdiff
103:     }
104:     return diffs
105:   end

     # File lib/diff.rb, line 126
126:   def discarda(i, elem)
127:     @curdiffs.push ['-', i, elem]
128:   end

     # File lib/diff.rb, line 130
130:   def discardb(i, elem)
131:     @curdiffs.push ['+', i, elem]
132:   end

     # File lib/diff.rb, line 142
142:   def inspect
143:     @diffs.inspect
144:   end

    # File lib/diff.rb, line 55
55:   def makediff(a, b)
56:     mvector = Diff.lcs(a, b)
57:     ai = bi = 0
58:     while ai < mvector.length
59:       bline = mvector[ai]
60:       if bline
61:         while bi < bline
62:           discardb(bi, b[bi])
63:           bi += 1
64:         end
65:         match(ai, bi)
66:         bi += 1
67:       else
68:         discarda(ai, a[ai])
69:       end
70:       ai += 1
71:     end
72:     while ai < a.length
73:       discarda(ai, a[ai])
74:       ai += 1
75:     end
76:     while bi < b.length
77:       discardb(bi, b[bi])
78:       bi += 1
79:     end
80:     match(ai, bi)
81:     1
82:   end

     # File lib/diff.rb, line 121
121:   def match(ai, bi)
122:     @diffs.push @curdiffs unless @curdiffs.empty?
123:     @curdiffs = []
124:   end