blob: 8cda6429642822e91e6fecb610bc8b9c6ce26e21 [file] [log] [blame]
Raymond Hettinger0c410272004-01-05 10:13:35 +00001/* Bisection algorithms. Drop in replacement for bisect.py
2
3Converted to C by Dmitry Vasiliev (dima at hlabs.spb.ru).
4*/
5
6#include "Python.h"
7
Benjamin Petersond6313712008-07-31 16:23:04 +00008static Py_ssize_t
Martin v. Löwisad0a4622006-02-16 14:30:23 +00009internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi)
Raymond Hettinger0c410272004-01-05 10:13:35 +000010{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000011 PyObject *litem;
12 Py_ssize_t mid, res;
Raymond Hettinger0c410272004-01-05 10:13:35 +000013
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000014 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 mid = (lo + hi) / 2;
25 litem = PySequence_GetItem(list, mid);
26 if (litem == NULL)
27 return -1;
28 res = PyObject_RichCompareBool(item, litem, Py_LT);
29 Py_DECREF(litem);
30 if (res < 0)
31 return -1;
32 if (res)
33 hi = mid;
34 else
35 lo = mid + 1;
36 }
37 return lo;
Raymond Hettinger0c410272004-01-05 10:13:35 +000038}
39
40static PyObject *
Raymond Hettingercc9a9512005-10-05 11:39:12 +000041bisect_right(PyObject *self, PyObject *args, PyObject *kw)
Raymond Hettinger0c410272004-01-05 10:13:35 +000042{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000043 PyObject *list, *item;
44 Py_ssize_t lo = 0;
45 Py_ssize_t hi = -1;
46 Py_ssize_t index;
47 static char *keywords[] = {"a", "x", "lo", "hi", NULL};
Raymond Hettinger0c410272004-01-05 10:13:35 +000048
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000049 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:bisect_right",
50 keywords, &list, &item, &lo, &hi))
51 return NULL;
52 index = internal_bisect_right(list, item, lo, hi);
53 if (index < 0)
54 return NULL;
55 return PyLong_FromSsize_t(index);
Raymond Hettinger0c410272004-01-05 10:13:35 +000056}
57
58PyDoc_STRVAR(bisect_right_doc,
Raymond Hettingercc9a9512005-10-05 11:39:12 +000059"bisect_right(a, x[, lo[, hi]]) -> index\n\
Raymond Hettinger0c410272004-01-05 10:13:35 +000060\n\
61Return the index where to insert item x in list a, assuming a is sorted.\n\
62\n\
63The return value i is such that all e in a[:i] have e <= x, and all e in\n\
64a[i:] have e > x. So if x already appears in the list, i points just\n\
65beyond the rightmost x already there\n\
66\n\
67Optional args lo (default 0) and hi (default len(a)) bound the\n\
68slice of a to be searched.\n");
69
70static PyObject *
Raymond Hettingercc9a9512005-10-05 11:39:12 +000071insort_right(PyObject *self, PyObject *args, PyObject *kw)
Raymond Hettinger0c410272004-01-05 10:13:35 +000072{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000073 PyObject *list, *item, *result;
74 Py_ssize_t lo = 0;
75 Py_ssize_t hi = -1;
76 Py_ssize_t index;
77 static char *keywords[] = {"a", "x", "lo", "hi", NULL};
Raymond Hettinger0c410272004-01-05 10:13:35 +000078
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000079 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:insort_right",
80 keywords, &list, &item, &lo, &hi))
81 return NULL;
82 index = internal_bisect_right(list, item, lo, hi);
83 if (index < 0)
84 return NULL;
85 if (PyList_CheckExact(list)) {
86 if (PyList_Insert(list, index, item) < 0)
87 return NULL;
88 } else {
Martin v. Löwisbd928fe2011-10-14 10:20:37 +020089 _Py_IDENTIFIER(insert);
Martin v. Löwisafe55bb2011-10-09 10:38:36 +020090
91 result = _PyObject_CallMethodId(list, &PyId_insert, "nO", index, item);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000092 if (result == NULL)
93 return NULL;
94 Py_DECREF(result);
95 }
Raymond Hettinger0c410272004-01-05 10:13:35 +000096
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000097 Py_RETURN_NONE;
Raymond Hettinger0c410272004-01-05 10:13:35 +000098}
99
100PyDoc_STRVAR(insort_right_doc,
Raymond Hettingercc9a9512005-10-05 11:39:12 +0000101"insort_right(a, x[, lo[, hi]])\n\
Raymond Hettinger0c410272004-01-05 10:13:35 +0000102\n\
103Insert item x in list a, and keep it sorted assuming a is sorted.\n\
104\n\
105If x is already in a, insert it to the right of the rightmost x.\n\
106\n\
107Optional args lo (default 0) and hi (default len(a)) bound the\n\
108slice of a to be searched.\n");
109
Benjamin Petersond6313712008-07-31 16:23:04 +0000110static Py_ssize_t
111internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi)
Raymond Hettinger0c410272004-01-05 10:13:35 +0000112{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000113 PyObject *litem;
114 Py_ssize_t mid, res;
Raymond Hettinger0c410272004-01-05 10:13:35 +0000115
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000116 if (lo < 0) {
117 PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
118 return -1;
119 }
120 if (hi == -1) {
121 hi = PySequence_Size(list);
122 if (hi < 0)
123 return -1;
124 }
125 while (lo < hi) {
126 mid = (lo + hi) / 2;
127 litem = PySequence_GetItem(list, mid);
128 if (litem == NULL)
129 return -1;
130 res = PyObject_RichCompareBool(litem, item, Py_LT);
131 Py_DECREF(litem);
132 if (res < 0)
133 return -1;
134 if (res)
135 lo = mid + 1;
136 else
137 hi = mid;
138 }
139 return lo;
Raymond Hettinger0c410272004-01-05 10:13:35 +0000140}
141
142static PyObject *
Raymond Hettingercc9a9512005-10-05 11:39:12 +0000143bisect_left(PyObject *self, PyObject *args, PyObject *kw)
Raymond Hettinger0c410272004-01-05 10:13:35 +0000144{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000145 PyObject *list, *item;
146 Py_ssize_t lo = 0;
147 Py_ssize_t hi = -1;
148 Py_ssize_t index;
149 static char *keywords[] = {"a", "x", "lo", "hi", NULL};
Raymond Hettinger0c410272004-01-05 10:13:35 +0000150
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000151 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:bisect_left",
152 keywords, &list, &item, &lo, &hi))
153 return NULL;
154 index = internal_bisect_left(list, item, lo, hi);
155 if (index < 0)
156 return NULL;
157 return PyLong_FromSsize_t(index);
Raymond Hettinger0c410272004-01-05 10:13:35 +0000158}
159
160PyDoc_STRVAR(bisect_left_doc,
Raymond Hettingercc9a9512005-10-05 11:39:12 +0000161"bisect_left(a, x[, lo[, hi]]) -> index\n\
Raymond Hettinger0c410272004-01-05 10:13:35 +0000162\n\
163Return the index where to insert item x in list a, assuming a is sorted.\n\
164\n\
165The return value i is such that all e in a[:i] have e < x, and all e in\n\
166a[i:] have e >= x. So if x already appears in the list, i points just\n\
167before the leftmost x already there.\n\
168\n\
169Optional args lo (default 0) and hi (default len(a)) bound the\n\
170slice of a to be searched.\n");
171
172static PyObject *
Raymond Hettingercc9a9512005-10-05 11:39:12 +0000173insort_left(PyObject *self, PyObject *args, PyObject *kw)
Raymond Hettinger0c410272004-01-05 10:13:35 +0000174{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000175 PyObject *list, *item, *result;
176 Py_ssize_t lo = 0;
177 Py_ssize_t hi = -1;
178 Py_ssize_t index;
179 static char *keywords[] = {"a", "x", "lo", "hi", NULL};
Raymond Hettinger0c410272004-01-05 10:13:35 +0000180
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000181 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:insort_left",
182 keywords, &list, &item, &lo, &hi))
183 return NULL;
184 index = internal_bisect_left(list, item, lo, hi);
185 if (index < 0)
186 return NULL;
187 if (PyList_CheckExact(list)) {
188 if (PyList_Insert(list, index, item) < 0)
189 return NULL;
190 } else {
Martin v. Löwisbd928fe2011-10-14 10:20:37 +0200191 _Py_IDENTIFIER(insert);
Martin v. Löwisafe55bb2011-10-09 10:38:36 +0200192
193 result = _PyObject_CallMethodId(list, &PyId_insert, "iO", index, item);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000194 if (result == NULL)
195 return NULL;
196 Py_DECREF(result);
197 }
Raymond Hettinger0c410272004-01-05 10:13:35 +0000198
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000199 Py_RETURN_NONE;
Raymond Hettinger0c410272004-01-05 10:13:35 +0000200}
201
202PyDoc_STRVAR(insort_left_doc,
Raymond Hettingercc9a9512005-10-05 11:39:12 +0000203"insort_left(a, x[, lo[, hi]])\n\
Raymond Hettinger0c410272004-01-05 10:13:35 +0000204\n\
205Insert item x in list a, and keep it sorted assuming a is sorted.\n\
206\n\
207If x is already in a, insert it to the left of the leftmost x.\n\
208\n\
209Optional args lo (default 0) and hi (default len(a)) bound the\n\
210slice of a to be searched.\n");
211
212PyDoc_STRVAR(bisect_doc, "Alias for bisect_right().\n");
213PyDoc_STRVAR(insort_doc, "Alias for insort_right().\n");
214
215static PyMethodDef bisect_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000216 {"bisect_right", (PyCFunction)bisect_right,
217 METH_VARARGS|METH_KEYWORDS, bisect_right_doc},
218 {"bisect", (PyCFunction)bisect_right,
219 METH_VARARGS|METH_KEYWORDS, bisect_doc},
220 {"insort_right", (PyCFunction)insort_right,
221 METH_VARARGS|METH_KEYWORDS, insort_right_doc},
222 {"insort", (PyCFunction)insort_right,
223 METH_VARARGS|METH_KEYWORDS, insort_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 */
Raymond Hettinger0c410272004-01-05 10:13:35 +0000229};
230
231PyDoc_STRVAR(module_doc,
232"Bisection algorithms.\n\
233\n\
234This module provides support for maintaining a list in sorted order without\n\
235having to sort the list after each insertion. For long lists of items with\n\
236expensive comparison operations, this can be an improvement over the more\n\
237common approach.\n");
238
Raymond Hettinger0c410272004-01-05 10:13:35 +0000239
Martin v. Löwis1a214512008-06-11 05:26:20 +0000240static struct PyModuleDef _bisectmodule = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000241 PyModuleDef_HEAD_INIT,
242 "_bisect",
243 module_doc,
244 -1,
245 bisect_methods,
246 NULL,
247 NULL,
248 NULL,
249 NULL
Martin v. Löwis1a214512008-06-11 05:26:20 +0000250};
251
252PyMODINIT_FUNC
253PyInit__bisect(void)
254{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000255 return PyModule_Create(&_bisectmodule);
Raymond Hettinger0c410272004-01-05 10:13:35 +0000256}