Vega strike Python Modules doc  0.5.1
Documentation of the " Modules " folder of Vega strike
 All Data Structures Namespaces Files Functions Variables
bisect.py
Go to the documentation of this file.
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