module Bisect

A direct port of the Python bisect standard library.

svn.python.org/view/python/branches/py3k/Lib/bisect.py?view=markup&pathrev=70846

Public Class Methods

bisect(a, x, lo=0, hi=a.size)
Alias for: bisect_right
bisect_left(a, x, lo=0, hi=a.size) click to toggle source

Return the index where to insert item x in list a, assuming a is sorted.

The return value i is such that all e in a have e < x, and all e in a have e >= x. So if x already appears in the list, a.insert(x) will insert just before the leftmost x already there.

Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched.

# File lib/bisect.rb, line 63
def bisect_left(a, x, lo=0, hi=a.size)
  raise ArgumentError, "lo must be non-negative" if lo < 0

  while lo < hi
    mid = (lo + hi) / 2
    if a[mid] < x
      lo = mid + 1
    else
      hi = mid
    end
  end

  lo
end
bisect_right(a, x, lo=0, hi=a.size) click to toggle source

Return the index where to insert item x in list a, assuming a is sorted.

The return value i is such that all e in a have e <= x, and all e in a have e > x. So if x already appears in the list, a.insert(x) will insert just after the rightmost x already there.

Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched.

# File lib/bisect.rb, line 28
def bisect_right(a, x, lo=0, hi=a.size)
  raise ArgumentError, "lo must be non-negative" if lo < 0

  while lo < hi
    mid = (lo + hi) / 2
    if x < a[mid]
      hi = mid
    else
      lo = mid + 1
    end
  end

  lo
end
Also aliased as: bisect
insort(a, x, lo=0, hi=a.size)
Alias for: insort_right
insort_left(a, x, lo=0, hi=a.size) click to toggle source

Insert item x in list a, and keep it sorted assuming a is sorted.

If x is already in a, insert it to the left of the leftmost x.

Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched.

# File lib/bisect.rb, line 50
def insort_left(a, x, lo=0, hi=a.size)
  index = bisect_left(a, x, lo, hi)
  a.insert(index, x)
end
insort_right(a, x, lo=0, hi=a.size) click to toggle source

Insert item x in list a, and keep it sorted assuming a is sorted.

If x is already in a, insert it to the right of the rightmost x.

Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched.

# File lib/bisect.rb, line 14
def insort_right(a, x, lo=0, hi=a.size)
  index = bisect_right(a, x, lo, hi)
  a.insert(index, x)
end
Also aliased as: insort