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