1/* Bisection algorithms. Drop in replacement for bisect.py
2
3Converted 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]
10module _bisect
11[clinic start generated code]*/
12/*[clinic end generated code: output=da39a3ee5e6b4b0d input=4d56a2b2033b462b]*/
13
14#include "clinic/_bisectmodule.c.h"
15
16typedef struct {
17    PyObject *str_insert;
18} bisect_state;
19
20static inline bisect_state*
21get_bisect_state(PyObject *module)
22{
23    void *state = PyModule_GetState(module);
24    assert(state != NULL);
25    return (bisect_state *)state;
26}
27
28static inline Py_ssize_t
29internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi,
30                      PyObject* key)
31{
32    PyObject *litem;
33    Py_ssize_t mid;
34    int res;
35
36    if (lo < 0) {
37        PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
38        return -1;
39    }
40    if (hi == -1) {
41        hi = PySequence_Size(list);
42        if (hi < 0)
43            return -1;
44    }
45    while (lo < hi) {
46        /* The (size_t)cast ensures that the addition and subsequent division
47           are performed as unsigned operations, avoiding difficulties from
48           signed overflow.  (See issue 13496.) */
49        mid = ((size_t)lo + hi) / 2;
50        litem = PySequence_GetItem(list, mid);
51        if (litem == NULL)
52            return -1;
53        if (key != Py_None) {
54            PyObject *newitem = PyObject_CallOneArg(key, litem);
55            if (newitem == NULL) {
56                Py_DECREF(litem);
57                return -1;
58            }
59            Py_SETREF(litem, newitem);
60        }
61        res = PyObject_RichCompareBool(item, litem, Py_LT);
62        Py_DECREF(litem);
63        if (res < 0)
64            return -1;
65        if (res)
66            hi = mid;
67        else
68            lo = mid + 1;
69    }
70    return lo;
71}
72
73/*[clinic input]
74_bisect.bisect_right -> Py_ssize_t
75
76    a: object
77    x: object
78    lo: Py_ssize_t = 0
79    hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
80    *
81    key: object = None
82
83Return the index where to insert item x in list a, assuming a is sorted.
84
85The return value i is such that all e in a[:i] have e <= x, and all e in
86a[i:] have e > x.  So if x already appears in the list, a.insert(i, x) will
87insert just after the rightmost x already there.
88
89Optional args lo (default 0) and hi (default len(a)) bound the
90slice of a to be searched.
91[clinic start generated code]*/
92
93static Py_ssize_t
94_bisect_bisect_right_impl(PyObject *module, PyObject *a, PyObject *x,
95                          Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
96/*[clinic end generated code: output=3a4bc09cc7c8a73d input=40fcc5afa06ae593]*/
97{
98    return internal_bisect_right(a, x, lo, hi, key);
99}
100
101/*[clinic input]
102_bisect.insort_right
103
104    a: object
105    x: object
106    lo: Py_ssize_t = 0
107    hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
108    *
109    key: object = None
110
111Insert item x in list a, and keep it sorted assuming a is sorted.
112
113If x is already in a, insert it to the right of the rightmost x.
114
115Optional args lo (default 0) and hi (default len(a)) bound the
116slice of a to be searched.
117[clinic start generated code]*/
118
119static PyObject *
120_bisect_insort_right_impl(PyObject *module, PyObject *a, PyObject *x,
121                          Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
122/*[clinic end generated code: output=ac3bf26d07aedda2 input=44e1708e26b7b802]*/
123{
124    PyObject *result, *key_x;
125    Py_ssize_t index;
126
127    if (key == Py_None) {
128        index = internal_bisect_right(a, x, lo, hi, key);
129    } else {
130        key_x = PyObject_CallOneArg(key, x);
131        if (key_x == NULL) {
132            return NULL;
133        }
134        index = internal_bisect_right(a, key_x, lo, hi, key);
135        Py_DECREF(key_x);
136    }
137    if (index < 0)
138        return NULL;
139    if (PyList_CheckExact(a)) {
140        if (PyList_Insert(a, index, x) < 0)
141            return NULL;
142    }
143    else {
144        bisect_state *state = get_bisect_state(module);
145        result = _PyObject_CallMethod(a, state->str_insert, "nO", index, x);
146        if (result == NULL)
147            return NULL;
148        Py_DECREF(result);
149    }
150
151    Py_RETURN_NONE;
152}
153
154static inline Py_ssize_t
155internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi,
156                     PyObject *key)
157{
158    PyObject *litem;
159    Py_ssize_t mid;
160    int res;
161
162    if (lo < 0) {
163        PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
164        return -1;
165    }
166    if (hi == -1) {
167        hi = PySequence_Size(list);
168        if (hi < 0)
169            return -1;
170    }
171    while (lo < hi) {
172        /* The (size_t)cast ensures that the addition and subsequent division
173           are performed as unsigned operations, avoiding difficulties from
174           signed overflow.  (See issue 13496.) */
175        mid = ((size_t)lo + hi) / 2;
176        litem = PySequence_GetItem(list, mid);
177        if (litem == NULL)
178            return -1;
179        if (key != Py_None) {
180            PyObject *newitem = PyObject_CallOneArg(key, litem);
181            if (newitem == NULL) {
182                Py_DECREF(litem);
183                return -1;
184            }
185            Py_SETREF(litem, newitem);
186        }
187        res = PyObject_RichCompareBool(litem, item, Py_LT);
188        Py_DECREF(litem);
189        if (res < 0)
190            return -1;
191        if (res)
192            lo = mid + 1;
193        else
194            hi = mid;
195    }
196    return lo;
197}
198
199
200/*[clinic input]
201_bisect.bisect_left -> Py_ssize_t
202
203    a: object
204    x: object
205    lo: Py_ssize_t = 0
206    hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
207    *
208    key: object = None
209
210Return the index where to insert item x in list a, assuming a is sorted.
211
212The return value i is such that all e in a[:i] have e < x, and all e in
213a[i:] have e >= x.  So if x already appears in the list, a.insert(i, x) will
214insert just before the leftmost x already there.
215
216Optional args lo (default 0) and hi (default len(a)) bound the
217slice of a to be searched.
218[clinic start generated code]*/
219
220static Py_ssize_t
221_bisect_bisect_left_impl(PyObject *module, PyObject *a, PyObject *x,
222                         Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
223/*[clinic end generated code: output=70749d6e5cae9284 input=90dd35b50ceb05e3]*/
224{
225    return internal_bisect_left(a, x, lo, hi, key);
226}
227
228
229/*[clinic input]
230_bisect.insort_left
231
232    a: object
233    x: object
234    lo: Py_ssize_t = 0
235    hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
236    *
237    key: object = None
238
239Insert item x in list a, and keep it sorted assuming a is sorted.
240
241If x is already in a, insert it to the left of the leftmost x.
242
243Optional args lo (default 0) and hi (default len(a)) bound the
244slice of a to be searched.
245[clinic start generated code]*/
246
247static PyObject *
248_bisect_insort_left_impl(PyObject *module, PyObject *a, PyObject *x,
249                         Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
250/*[clinic end generated code: output=b1d33e5e7ffff11e input=3ab65d8784f585b1]*/
251{
252    PyObject *result, *key_x;
253    Py_ssize_t index;
254
255    if (key == Py_None) {
256        index = internal_bisect_left(a, x, lo, hi, key);
257    } else {
258        key_x = PyObject_CallOneArg(key, x);
259        if (key_x == NULL) {
260            return NULL;
261        }
262        index = internal_bisect_left(a, key_x, lo, hi, key);
263        Py_DECREF(key_x);
264    }
265    if (index < 0)
266        return NULL;
267    if (PyList_CheckExact(a)) {
268        if (PyList_Insert(a, index, x) < 0)
269            return NULL;
270    } else {
271        bisect_state *state = get_bisect_state(module);
272        result = _PyObject_CallMethod(a, state->str_insert, "nO", index, x);
273        if (result == NULL)
274            return NULL;
275        Py_DECREF(result);
276    }
277
278    Py_RETURN_NONE;
279}
280
281static PyMethodDef bisect_methods[] = {
282    _BISECT_BISECT_RIGHT_METHODDEF
283    _BISECT_INSORT_RIGHT_METHODDEF
284    _BISECT_BISECT_LEFT_METHODDEF
285    _BISECT_INSORT_LEFT_METHODDEF
286    {NULL, NULL} /* sentinel */
287};
288
289PyDoc_STRVAR(module_doc,
290"Bisection algorithms.\n\
291\n\
292This module provides support for maintaining a list in sorted order without\n\
293having to sort the list after each insertion. For long lists of items with\n\
294expensive comparison operations, this can be an improvement over the more\n\
295common approach.\n");
296
297static int
298bisect_clear(PyObject *module)
299{
300    bisect_state *state = get_bisect_state(module);
301    Py_CLEAR(state->str_insert);
302    return 0;
303}
304
305static void
306bisect_free(void *module)
307{
308    bisect_clear((PyObject *)module);
309}
310
311static int
312bisect_modexec(PyObject *m)
313{
314    bisect_state *state = get_bisect_state(m);
315    state->str_insert = PyUnicode_InternFromString("insert");
316    if (state->str_insert == NULL) {
317        return -1;
318    }
319    return 0;
320}
321
322static PyModuleDef_Slot bisect_slots[] = {
323    {Py_mod_exec, bisect_modexec},
324    {0, NULL}
325};
326
327static struct PyModuleDef _bisectmodule = {
328    PyModuleDef_HEAD_INIT,
329    .m_name = "_bisect",
330    .m_size = sizeof(bisect_state),
331    .m_doc = module_doc,
332    .m_methods = bisect_methods,
333    .m_slots = bisect_slots,
334    .m_clear = bisect_clear,
335    .m_free = bisect_free,
336};
337
338PyMODINIT_FUNC
339PyInit__bisect(void)
340{
341    return PyModuleDef_Init(&_bisectmodule);
342}
343