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 |
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 |
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 * |
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 (key_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 |
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 |
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 * |
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 (key_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 |
295 | PyInit__bisect(void) |
296 | { |
297 | return PyModuleDef_Init(&_bisectmodule); |
298 | } |
299 | |