class DocDiff::Diff::Contours::Closest
Public Class Methods
new(arr)
click to toggle source
# File lib/docdiff/diff/contours.rb, line 313 def initialize(arr) @n = arr.length + 1 @table = Array.new arr.each_index {|i| s = arr[i] @table[s] = [-1] unless @table[s] @table[s] << i } @table.each_index {|s| @table[s] = [-1] unless @table[s] @table[s] << @n } end
Public Instance Methods
next(s, i)
click to toggle source
# File lib/docdiff/diff/contours.rb, line 328 def next(s, i) t = @table[s] if t.length < 10 t.each {|j| return j if i < j} return @n end lower = -1 upper = t.length while lower + 1 != upper mid = (lower + upper) / 2 if t[mid] <= i lower = mid else upper = mid end end b = lower + 1 if b < t.length return t[b] else return @n end end
prev(s, i)
click to toggle source
# File lib/docdiff/diff/contours.rb, line 356 def prev(s, i) t = @table[s] if t.length < 10 t.reverse_each {|j| return j if j < i} return -1 end lower = -1 upper = t.length while lower + 1 != upper mid = (lower + upper) / 2 if t[mid] < i lower = mid else upper = mid end end if 0 < upper return t[upper - 1] else return -1 end end