Method: Diff::LCS.__replace_next_larger

Defined in:
lib/gems/diff-lcs-1.1.2/lib/diff/lcs.rb

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



879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
 
# File 'lib/gems/diff-lcs-1.1.2/lib/diff/lcs.rb', line 879

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