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