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