← Back to branch summary

~ubuntu-branches/ubuntu/karmic/pypy/karmic

« back to all changes in this revision

Viewing changes to lib-python/2.4.1/bisect.py

  • Committer: Bazaar Package Importer
  • Author(s): Alexandre Fayolle
  • Date: 2007-04-13 09:33:09 UTC
  • Revision ID: james.westby@ubuntu.com-20070413093309-yoojh4jcoocu2krz
Tags: upstream-1.0.0
Import upstream version 1.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib-python/2.4.1/bisect.py
 
1
"""Bisection algorithms."""
 
2
 
 
3
def insort_right(a, x, lo=0, hi=None):
 
4
    """Insert item x in list a, and keep it sorted assuming a is sorted.
 
5
 
 
6
    If x is already in a, insert it to the right of the rightmost x.
 
7
 
 
8
    Optional args lo (default 0) and hi (default len(a)) bound the
 
9
    slice of a to be searched.
 
10
    """
 
11
 
 
12
    if hi is None:
 
13
        hi = len(a)
 
14
    while lo < hi:
 
15
        mid = (lo+hi)//2
 
16
        if x < a[mid]: hi = mid
 
17
        else: lo = mid+1
 
18
    a.insert(lo, x)
 
19
 
 
20
insort = insort_right   # backward compatibility
 
21
 
 
22
def bisect_right(a, x, lo=0, hi=None):
 
23
    """Return the index where to insert item x in list a, assuming a is sorted.
 
24
 
 
25
    The return value i is such that all e in a[:i] have e <= x, and all e in
 
26
    a[i:] have e > x.  So if x already appears in the list, i points just
 
27
    beyond the rightmost x already there.
 
28
 
 
29
    Optional args lo (default 0) and hi (default len(a)) bound the
 
30
    slice of a to be searched.
 
31
    """
 
32
 
 
33
    if hi is None:
 
34
        hi = len(a)
 
35
    while lo < hi:
 
36
        mid = (lo+hi)//2
 
37
        if x < a[mid]: hi = mid
 
38
        else: lo = mid+1
 
39
    return lo
 
40
 
 
41
bisect = bisect_right   # backward compatibility
 
42
 
 
43
def insort_left(a, x, lo=0, hi=None):
 
44
    """Insert item x in list a, and keep it sorted assuming a is sorted.
 
45
 
 
46
    If x is already in a, insert it to the left of the leftmost x.
 
47
 
 
48
    Optional args lo (default 0) and hi (default len(a)) bound the
 
49
    slice of a to be searched.
 
50
    """
 
51
 
 
52
    if hi is None:
 
53
        hi = len(a)
 
54
    while lo < hi:
 
55
        mid = (lo+hi)//2
 
56
        if a[mid] < x: lo = mid+1
 
57
        else: hi = mid
 
58
    a.insert(lo, x)
 
59
 
 
60
 
 
61
def bisect_left(a, x, lo=0, hi=None):
 
62
    """Return the index where to insert item x in list a, assuming a is sorted.
 
63
 
 
64
    The return value i is such that all e in a[:i] have e < x, and all e in
 
65
    a[i:] have e >= x.  So if x already appears in the list, i points just
 
66
    before the leftmost x already there.
 
67
 
 
68
    Optional args lo (default 0) and hi (default len(a)) bound the
 
69
    slice of a to be searched.
 
70
    """
 
71
 
 
72
    if hi is None:
 
73
        hi = len(a)
 
74
    while lo < hi:
 
75
        mid = (lo+hi)//2
 
76
        if a[mid] < x: lo = mid+1
 
77
        else: hi = mid
 
78
    return lo
 
79
 
 
80
# Overwrite above definitions with a fast C implementation
 
81
try:
 
82
    from _bisect import bisect_right, bisect_left, insort_left, insort_right, insort, bisect
 
83
except ImportError:
 
84
    pass