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,PyObject * key)19 internal_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
73 Return the index where to insert item x in list a, assuming a is sorted.
74
75 The return value i is such that all e in a[:i] have e <= x, and all e in
76 a[i:] have e > x. So if x already appears in the list, a.insert(i, x) will
77 insert just after the rightmost x already there.
78
79 Optional args lo (default 0) and hi (default len(a)) bound the
80 slice of a to be searched.
81 [clinic start generated code]*/
82
83 static Py_ssize_t
_bisect_bisect_right_impl(PyObject * module,PyObject * a,PyObject * x,Py_ssize_t lo,Py_ssize_t hi,PyObject * key)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
101 Insert item x in list a, and keep it sorted assuming a is sorted.
102
103 If x is already in a, insert it to the right of the rightmost x.
104
105 Optional args lo (default 0) and hi (default len(a)) bound the
106 slice of a to be searched.
107 [clinic start generated code]*/
108
109 static PyObject *
_bisect_insort_right_impl(PyObject * module,PyObject * a,PyObject * x,Py_ssize_t lo,Py_ssize_t hi,PyObject * key)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 (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
143 static inline Py_ssize_t
internal_bisect_left(PyObject * list,PyObject * item,Py_ssize_t lo,Py_ssize_t hi,PyObject * key)144 internal_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
199 Return the index where to insert item x in list a, assuming a is sorted.
200
201 The return value i is such that all e in a[:i] have e < x, and all e in
202 a[i:] have e >= x. So if x already appears in the list, a.insert(i, x) will
203 insert just before the leftmost x already there.
204
205 Optional args lo (default 0) and hi (default len(a)) bound the
206 slice of a to be searched.
207 [clinic start generated code]*/
208
209 static Py_ssize_t
_bisect_bisect_left_impl(PyObject * module,PyObject * a,PyObject * x,Py_ssize_t lo,Py_ssize_t hi,PyObject * key)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
228 Insert item x in list a, and keep it sorted assuming a is sorted.
229
230 If x is already in a, insert it to the left of the leftmost x.
231
232 Optional args lo (default 0) and hi (default len(a)) bound the
233 slice of a to be searched.
234 [clinic start generated code]*/
235
236 static PyObject *
_bisect_insort_left_impl(PyObject * module,PyObject * a,PyObject * x,Py_ssize_t lo,Py_ssize_t hi,PyObject * key)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 (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
269 static 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
277 PyDoc_STRVAR(module_doc,
278 "Bisection algorithms.\n\
279 \n\
280 This module provides support for maintaining a list in sorted order without\n\
281 having to sort the list after each insertion. For long lists of items with\n\
282 expensive comparison operations, this can be an improvement over the more\n\
283 common approach.\n");
284
285
286 static 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
294 PyMODINIT_FUNC
PyInit__bisect(void)295 PyInit__bisect(void)
296 {
297 return PyModuleDef_Init(&_bisectmodule);
298 }
299