Module: Bisect

Defined in:
lib/bisect.rb

Overview

A direct port of the Python bisect standard library.

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

Class Method Summary collapse

Class Method Details

.bisect_left(a, x, lo = 0, hi = a.size) ⇒ Object

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.

Raises:

  • (ArgumentError) 


63
64
65
66
67
68
69
70
71
72
73
74
75
76
 
# 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) ⇒ Object Also known as: bisect

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.

Raises:

  • (ArgumentError) 


28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
# 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

.insort_left(a, x, lo = 0, hi = a.size) ⇒ Object

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.



50
51
52
53
 
# 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) ⇒ Object Also known as: insort

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.



14
15
16
17
 
# 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