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