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