1/* Bisection algorithms. Drop in replacement for bisect.py
2
3Converted 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]
10module _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
18static inline Py_ssize_t
19internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi,
20 PyObject* key)
21{
22 PyObject *litem;
23 Py_ssize_t mid;
24 int res;
25
26 if (lo < 0) {
27 PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
28 return -1;
29 }
30 if (hi == -1) {
31 hi = PySequence_Size(list);
32 if (hi < 0)
33 return -1;
34 }
35 while (lo < hi) {
36 /* The (size_t)cast ensures that the addition and subsequent division
37 are performed as unsigned operations, avoiding difficulties from
38 signed overflow. (See issue 13496.) */
39 mid = ((size_t)lo + hi) / 2;
40 litem = PySequence_GetItem(list, mid);
41 if (litem == NULL)
42 return -1;
43 if (key != Py_None) {
44 PyObject *newitem = PyObject_CallOneArg(key, litem);
45 if (newitem == NULL) {
46 Py_DECREF(litem);
47 return -1;
48 }
49 Py_SETREF(litem, newitem);
50 }
51 res = PyObject_RichCompareBool(item, litem, Py_LT);
52 Py_DECREF(litem);
53 if (res < 0)
54 return -1;
55 if (res)
56 hi = mid;
57 else
58 lo = mid + 1;
59 }
60 return lo;
61}
62
63/*[clinic input]
64_bisect.bisect_right -> Py_ssize_t
65
66 a: object
67 x: object
68 lo: Py_ssize_t = 0
69 hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
70 *
71 key: object = None
72
73Return the index where to insert item x in list a, assuming a is sorted.
74
75The return value i is such that all e in a[:i] have e <= x, and all e in
76a[i:] have e > x. So if x already appears in the list, a.insert(i, x) will
77insert just after the rightmost x already there.
78
79Optional args lo (default 0) and hi (default len(a)) bound the
80slice of a to be searched.
81[clinic start generated code]*/
82
83static Py_ssize_t
84_bisect_bisect_right_impl(PyObject *module, PyObject *a, PyObject *x,
85 Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
86/*[clinic end generated code: output=3a4bc09cc7c8a73d input=40fcc5afa06ae593]*/
87{
88 return internal_bisect_right(a, x, lo, hi, key);
89}
90
91/*[clinic input]
92_bisect.insort_right
93
94 a: object
95 x: object
96 lo: Py_ssize_t = 0
97 hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
98 *
99 key: object = None
100
101Insert item x in list a, and keep it sorted assuming a is sorted.
102
103If x is already in a, insert it to the right of the rightmost x.
104
105Optional args lo (default 0) and hi (default len(a)) bound the
106slice of a to be searched.
107[clinic start generated code]*/
108
109static PyObject *
110_bisect_insort_right_impl(PyObject *module, PyObject *a, PyObject *x,
111 Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
112/*[clinic end generated code: output=ac3bf26d07aedda2 input=44e1708e26b7b802]*/
113{
114 PyObject *result, *key_x;
115 Py_ssize_t index;
116
117 if (key == Py_None) {
118 index = internal_bisect_right(a, x, lo, hi, key);
119 } else {
120 key_x = PyObject_CallOneArg(key, x);
121 if (key_x == NULL) {
122 return NULL;
123 }
124 index = internal_bisect_right(a, key_x, lo, hi, key);
125 Py_DECREF(key_x);
126 }
127 if (index < 0)
128 return NULL;
129 if (PyList_CheckExact(a)) {
130 if (PyList_Insert(a, index, x) < 0)
131 return NULL;
132 }
133 else {
134 result = _PyObject_CallMethodId(a, &PyId_insert, "nO", index, x);
135 if (result == NULL)
136 return NULL;
137 Py_DECREF(result);
138 }
139
140 Py_RETURN_NONE;
141}
142
143static inline Py_ssize_t
144internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi,
145 PyObject *key)
146{
147 PyObject *litem;
148 Py_ssize_t mid;
149 int res;
150
151 if (lo < 0) {
152 PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
153 return -1;
154 }
155 if (hi == -1) {
156 hi = PySequence_Size(list);
157 if (hi < 0)
158 return -1;
159 }
160 while (lo < hi) {
161 /* The (size_t)cast ensures that the addition and subsequent division
162 are performed as unsigned operations, avoiding difficulties from
163 signed overflow. (See issue 13496.) */
164 mid = ((size_t)lo + hi) / 2;
165 litem = PySequence_GetItem(list, mid);
166 if (litem == NULL)
167 return -1;
168 if (key != Py_None) {
169 PyObject *newitem = PyObject_CallOneArg(key, litem);
170 if (newitem == NULL) {
171 Py_DECREF(litem);
172 return -1;
173 }
174 Py_SETREF(litem, newitem);
175 }
176 res = PyObject_RichCompareBool(litem, item, Py_LT);
177 Py_DECREF(litem);
178 if (res < 0)
179 return -1;
180 if (res)
181 lo = mid + 1;
182 else
183 hi = mid;
184 }
185 return lo;
186}
187
188
189/*[clinic input]
190_bisect.bisect_left -> Py_ssize_t
191
192 a: object
193 x: object
194 lo: Py_ssize_t = 0
195 hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
196 *
197 key: object = None
198
199Return the index where to insert item x in list a, assuming a is sorted.
200
201The return value i is such that all e in a[:i] have e < x, and all e in
202a[i:] have e >= x. So if x already appears in the list, a.insert(i, x) will
203insert just before the leftmost x already there.
204
205Optional args lo (default 0) and hi (default len(a)) bound the
206slice of a to be searched.
207[clinic start generated code]*/
208
209static Py_ssize_t
210_bisect_bisect_left_impl(PyObject *module, PyObject *a, PyObject *x,
211 Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
212/*[clinic end generated code: output=70749d6e5cae9284 input=90dd35b50ceb05e3]*/
213{
214 return internal_bisect_left(a, x, lo, hi, key);
215}
216
217
218/*[clinic input]
219_bisect.insort_left
220
221 a: object
222 x: object
223 lo: Py_ssize_t = 0
224 hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
225 *
226 key: object = None
227
228Insert item x in list a, and keep it sorted assuming a is sorted.
229
230If x is already in a, insert it to the left of the leftmost x.
231
232Optional args lo (default 0) and hi (default len(a)) bound the
233slice of a to be searched.
234[clinic start generated code]*/
235
236static PyObject *
237_bisect_insort_left_impl(PyObject *module, PyObject *a, PyObject *x,
238 Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
239/*[clinic end generated code: output=b1d33e5e7ffff11e input=3ab65d8784f585b1]*/
240{
241 PyObject *result, *key_x;
242 Py_ssize_t index;
243
244 if (key == Py_None) {
245 index = internal_bisect_left(a, x, lo, hi, key);
246 } else {
247 key_x = PyObject_CallOneArg(key, x);
248 if (key_x == NULL) {
249 return NULL;
250 }
251 index = internal_bisect_left(a, key_x, lo, hi, key);
252 Py_DECREF(key_x);
253 }
254 if (index < 0)
255 return NULL;
256 if (PyList_CheckExact(a)) {
257 if (PyList_Insert(a, index, x) < 0)
258 return NULL;
259 } else {
260 result = _PyObject_CallMethodId(a, &PyId_insert, "nO", index, x);
261 if (result == NULL)
262 return NULL;
263 Py_DECREF(result);
264 }
265
266 Py_RETURN_NONE;
267}
268
269static PyMethodDef bisect_methods[] = {
270 _BISECT_BISECT_RIGHT_METHODDEF
271 _BISECT_INSORT_RIGHT_METHODDEF
272 _BISECT_BISECT_LEFT_METHODDEF
273 _BISECT_INSORT_LEFT_METHODDEF
274 {NULL, NULL} /* sentinel */
275};
276
277PyDoc_STRVAR(module_doc,
278"Bisection algorithms.\n\
279\n\
280This module provides support for maintaining a list in sorted order without\n\
281having to sort the list after each insertion. For long lists of items with\n\
282expensive comparison operations, this can be an improvement over the more\n\
283common approach.\n");
284
285
286static struct PyModuleDef _bisectmodule = {
287 PyModuleDef_HEAD_INIT,
288 .m_name = "_bisect",
289 .m_doc = module_doc,
290 .m_methods = bisect_methods,
291 .m_size = 0
292};
293
294PyMODINIT_FUNC
295PyInit__bisect(void)
296{
297 return PyModuleDef_Init(&_bisectmodule);
298}
299