1 /* Bisection algorithms. Drop in replacement for bisect.py
2
3 Converted to C by Dmitry Vasiliev (dima at hlabs.spb.ru).
4 */
5
6 #define PY_SSIZE_T_CLEAN
7 #include "Python.h"
8
9 /*[clinic input]
10 module _bisect
11 [clinic start generated code]*/
12 /*[clinic end generated code: output=da39a3ee5e6b4b0d input=4d56a2b2033b462b]*/
13
14 #include "clinic/_bisectmodule.c.h"
15
16 _Py_IDENTIFIER(insert);
17
18 static inline Py_ssize_t
internal_bisect_right(PyObject * list,PyObject * item,Py_ssize_t lo,Py_ssize_t hi)19 internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi)
20 {
21 PyObject *litem;
22 Py_ssize_t mid;
23 int res;
24
25 if (lo < 0) {
26 PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
27 return -1;
28 }
29 if (hi == -1) {
30 hi = PySequence_Size(list);
31 if (hi < 0)
32 return -1;
33 }
34 while (lo < hi) {
35 /* The (size_t)cast ensures that the addition and subsequent division
36 are performed as unsigned operations, avoiding difficulties from
37 signed overflow. (See issue 13496.) */
38 mid = ((size_t)lo + hi) / 2;
39 litem = PySequence_GetItem(list, mid);
40 if (litem == NULL)
41 return -1;
42 res = PyObject_RichCompareBool(item, litem, Py_LT);
43 Py_DECREF(litem);
44 if (res < 0)
45 return -1;
46 if (res)
47 hi = mid;
48 else
49 lo = mid + 1;
50 }
51 return lo;
52 }
53
54 /*[clinic input]
55 _bisect.bisect_right -> Py_ssize_t
56
57 a: object
58 x: object
59 lo: Py_ssize_t = 0
60 hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
61
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 beyond the rightmost 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 [clinic start generated code]*/
71
72 static Py_ssize_t
_bisect_bisect_right_impl(PyObject * module,PyObject * a,PyObject * x,Py_ssize_t lo,Py_ssize_t hi)73 _bisect_bisect_right_impl(PyObject *module, PyObject *a, PyObject *x,
74 Py_ssize_t lo, Py_ssize_t hi)
75 /*[clinic end generated code: output=419e150cf1d2a235 input=e72212b282c83375]*/
76 {
77 return internal_bisect_right(a, x, lo, hi);
78 }
79
80 /*[clinic input]
81 _bisect.insort_right
82
83 a: object
84 x: object
85 lo: Py_ssize_t = 0
86 hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
87
88 Insert item x in list a, and keep it sorted assuming a is sorted.
89
90 If x is already in a, insert it to the right of the rightmost x.
91
92 Optional args lo (default 0) and hi (default len(a)) bound the
93 slice of a to be searched.
94 [clinic start generated code]*/
95
96 static PyObject *
_bisect_insort_right_impl(PyObject * module,PyObject * a,PyObject * x,Py_ssize_t lo,Py_ssize_t hi)97 _bisect_insort_right_impl(PyObject *module, PyObject *a, PyObject *x,
98 Py_ssize_t lo, Py_ssize_t hi)
99 /*[clinic end generated code: output=c2caa3d4cd02035a input=d1c45bfa68182669]*/
100 {
101 PyObject *result;
102 Py_ssize_t index = internal_bisect_right(a, x, lo, hi);
103 if (index < 0)
104 return NULL;
105 if (PyList_CheckExact(a)) {
106 if (PyList_Insert(a, index, x) < 0)
107 return NULL;
108 }
109 else {
110 result = _PyObject_CallMethodId(a, &PyId_insert, "nO", index, x);
111 if (result == NULL)
112 return NULL;
113 Py_DECREF(result);
114 }
115
116 Py_RETURN_NONE;
117 }
118
119 static inline Py_ssize_t
internal_bisect_left(PyObject * list,PyObject * item,Py_ssize_t lo,Py_ssize_t hi)120 internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi)
121 {
122 PyObject *litem;
123 Py_ssize_t mid;
124 int res;
125
126 if (lo < 0) {
127 PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
128 return -1;
129 }
130 if (hi == -1) {
131 hi = PySequence_Size(list);
132 if (hi < 0)
133 return -1;
134 }
135 while (lo < hi) {
136 /* The (size_t)cast ensures that the addition and subsequent division
137 are performed as unsigned operations, avoiding difficulties from
138 signed overflow. (See issue 13496.) */
139 mid = ((size_t)lo + hi) / 2;
140 litem = PySequence_GetItem(list, mid);
141 if (litem == NULL)
142 return -1;
143 res = PyObject_RichCompareBool(litem, item, Py_LT);
144 Py_DECREF(litem);
145 if (res < 0)
146 return -1;
147 if (res)
148 lo = mid + 1;
149 else
150 hi = mid;
151 }
152 return lo;
153 }
154
155
156 /*[clinic input]
157 _bisect.bisect_left -> Py_ssize_t
158
159 a: object
160 x: object
161 lo: Py_ssize_t = 0
162 hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
163
164 Return the index where to insert item x in list a, assuming a is sorted.
165
166 The return value i is such that all e in a[:i] have e < x, and all e in
167 a[i:] have e >= x. So if x already appears in the list, i points just
168 before the leftmost x already there.
169
170 Optional args lo (default 0) and hi (default len(a)) bound the
171 slice of a to be searched.
172 [clinic start generated code]*/
173
174 static Py_ssize_t
_bisect_bisect_left_impl(PyObject * module,PyObject * a,PyObject * x,Py_ssize_t lo,Py_ssize_t hi)175 _bisect_bisect_left_impl(PyObject *module, PyObject *a, PyObject *x,
176 Py_ssize_t lo, Py_ssize_t hi)
177 /*[clinic end generated code: output=af82168bc2856f24 input=2bd90f34afe5609f]*/
178 {
179 return internal_bisect_left(a, x, lo, hi);
180 }
181
182
183 /*[clinic input]
184 _bisect.insort_left
185
186 a: object
187 x: object
188 lo: Py_ssize_t = 0
189 hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
190
191 Insert item x in list a, and keep it sorted assuming a is sorted.
192
193 If x is already in a, insert it to the left of the leftmost x.
194
195 Optional args lo (default 0) and hi (default len(a)) bound the
196 slice of a to be searched.
197 [clinic start generated code]*/
198
199 static PyObject *
_bisect_insort_left_impl(PyObject * module,PyObject * a,PyObject * x,Py_ssize_t lo,Py_ssize_t hi)200 _bisect_insort_left_impl(PyObject *module, PyObject *a, PyObject *x,
201 Py_ssize_t lo, Py_ssize_t hi)
202 /*[clinic end generated code: output=9e8356c0844a182b input=bc4583308bce00cc]*/
203 {
204 PyObject *result;
205 Py_ssize_t index = internal_bisect_left(a, x, lo, hi);
206 if (index < 0)
207 return NULL;
208 if (PyList_CheckExact(a)) {
209 if (PyList_Insert(a, index, x) < 0)
210 return NULL;
211 } else {
212 result = _PyObject_CallMethodId(a, &PyId_insert, "nO", index, x);
213 if (result == NULL)
214 return NULL;
215 Py_DECREF(result);
216 }
217
218 Py_RETURN_NONE;
219 }
220
221 static PyMethodDef bisect_methods[] = {
222 _BISECT_BISECT_RIGHT_METHODDEF
223 _BISECT_INSORT_RIGHT_METHODDEF
224 _BISECT_BISECT_LEFT_METHODDEF
225 _BISECT_INSORT_LEFT_METHODDEF
226 {NULL, NULL} /* sentinel */
227 };
228
229 PyDoc_STRVAR(module_doc,
230 "Bisection algorithms.\n\
231 \n\
232 This module provides support for maintaining a list in sorted order without\n\
233 having to sort the list after each insertion. For long lists of items with\n\
234 expensive comparison operations, this can be an improvement over the more\n\
235 common approach.\n");
236
237
238 static struct PyModuleDef _bisectmodule = {
239 PyModuleDef_HEAD_INIT,
240 "_bisect",
241 module_doc,
242 -1,
243 bisect_methods,
244 NULL,
245 NULL,
246 NULL,
247 NULL
248 };
249
250 PyMODINIT_FUNC
PyInit__bisect(void)251 PyInit__bisect(void)
252 {
253 return PyModule_Create(&_bisectmodule);
254 }
255