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