blob: fe2e1102ed729aa0288fa10949c1e6c969bad2e7 [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{
11 PyObject *litem;
Martin v. Löwisad0a4622006-02-16 14:30:23 +000012 Py_ssize_t mid, res;
Raymond Hettinger0c410272004-01-05 10:13:35 +000013
Georg Brandl2ee470f2008-07-16 12:55:28 +000014 if (lo < 0) {
15 PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
16 return -1;
17 }
Raymond Hettinger0c410272004-01-05 10:13:35 +000018 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;
38}
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{
43 PyObject *list, *item;
Benjamin Petersond6313712008-07-31 16:23:04 +000044 Py_ssize_t lo = 0;
45 Py_ssize_t hi = -1;
46 Py_ssize_t index;
Martin v. Löwis02cbf4a2006-02-27 17:20:04 +000047 static char *keywords[] = {"a", "x", "lo", "hi", NULL};
Raymond Hettinger0c410272004-01-05 10:13:35 +000048
Benjamin Petersond6313712008-07-31 16:23:04 +000049 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:bisect_right",
Raymond Hettingercc9a9512005-10-05 11:39:12 +000050 keywords, &list, &item, &lo, &hi))
Raymond Hettinger0c410272004-01-05 10:13:35 +000051 return NULL;
52 index = internal_bisect_right(list, item, lo, hi);
53 if (index < 0)
54 return NULL;
Benjamin Petersond6313712008-07-31 16:23:04 +000055 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{
Michael W. Hudsonc9f510a2004-08-02 13:24:54 +000073 PyObject *list, *item, *result;
Benjamin Petersond6313712008-07-31 16:23:04 +000074 Py_ssize_t lo = 0;
75 Py_ssize_t hi = -1;
76 Py_ssize_t index;
Martin v. Löwis02cbf4a2006-02-27 17:20:04 +000077 static char *keywords[] = {"a", "x", "lo", "hi", NULL};
Raymond Hettinger0c410272004-01-05 10:13:35 +000078
Benjamin Petersond6313712008-07-31 16:23:04 +000079 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:insort_right",
Raymond Hettingercc9a9512005-10-05 11:39:12 +000080 keywords, &list, &item, &lo, &hi))
Raymond Hettinger0c410272004-01-05 10:13:35 +000081 return NULL;
82 index = internal_bisect_right(list, item, lo, hi);
83 if (index < 0)
84 return NULL;
Benjamin Petersonf10a79a2008-10-11 00:49:57 +000085 if (PyList_CheckExact(list)) {
Raymond Hettinger0c410272004-01-05 10:13:35 +000086 if (PyList_Insert(list, index, item) < 0)
87 return NULL;
88 } else {
Benjamin Petersond6313712008-07-31 16:23:04 +000089 result = PyObject_CallMethod(list, "insert", "nO",
Michael W. Hudsonc9f510a2004-08-02 13:24:54 +000090 index, item);
91 if (result == NULL)
Raymond Hettinger0c410272004-01-05 10:13:35 +000092 return NULL;
Michael W. Hudsonc9f510a2004-08-02 13:24:54 +000093 Py_DECREF(result);
Raymond Hettinger0c410272004-01-05 10:13:35 +000094 }
95
96 Py_RETURN_NONE;
97}
98
99PyDoc_STRVAR(insort_right_doc,
Raymond Hettingercc9a9512005-10-05 11:39:12 +0000100"insort_right(a, x[, lo[, hi]])\n\
Raymond Hettinger0c410272004-01-05 10:13:35 +0000101\n\
102Insert item x in list a, and keep it sorted assuming a is sorted.\n\
103\n\
104If x is already in a, insert it to the right of the rightmost x.\n\
105\n\
106Optional args lo (default 0) and hi (default len(a)) bound the\n\
107slice of a to be searched.\n");
108
Benjamin Petersond6313712008-07-31 16:23:04 +0000109static Py_ssize_t
110internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi)
Raymond Hettinger0c410272004-01-05 10:13:35 +0000111{
112 PyObject *litem;
Benjamin Petersond6313712008-07-31 16:23:04 +0000113 Py_ssize_t mid, res;
Raymond Hettinger0c410272004-01-05 10:13:35 +0000114
Georg Brandl2ee470f2008-07-16 12:55:28 +0000115 if (lo < 0) {
116 PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
117 return -1;
118 }
Raymond Hettinger0c410272004-01-05 10:13:35 +0000119 if (hi == -1) {
120 hi = PySequence_Size(list);
121 if (hi < 0)
122 return -1;
123 }
124 while (lo < hi) {
125 mid = (lo + hi) / 2;
126 litem = PySequence_GetItem(list, mid);
127 if (litem == NULL)
128 return -1;
129 res = PyObject_RichCompareBool(litem, item, Py_LT);
130 Py_DECREF(litem);
131 if (res < 0)
132 return -1;
133 if (res)
134 lo = mid + 1;
135 else
136 hi = mid;
137 }
138 return lo;
139}
140
141static PyObject *
Raymond Hettingercc9a9512005-10-05 11:39:12 +0000142bisect_left(PyObject *self, PyObject *args, PyObject *kw)
Raymond Hettinger0c410272004-01-05 10:13:35 +0000143{
144 PyObject *list, *item;
Benjamin Petersond6313712008-07-31 16:23:04 +0000145 Py_ssize_t lo = 0;
146 Py_ssize_t hi = -1;
147 Py_ssize_t index;
Martin v. Löwis02cbf4a2006-02-27 17:20:04 +0000148 static char *keywords[] = {"a", "x", "lo", "hi", NULL};
Raymond Hettinger0c410272004-01-05 10:13:35 +0000149
Benjamin Petersond6313712008-07-31 16:23:04 +0000150 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:bisect_left",
Raymond Hettingercc9a9512005-10-05 11:39:12 +0000151 keywords, &list, &item, &lo, &hi))
Raymond Hettinger0c410272004-01-05 10:13:35 +0000152 return NULL;
153 index = internal_bisect_left(list, item, lo, hi);
154 if (index < 0)
155 return NULL;
Benjamin Petersond6313712008-07-31 16:23:04 +0000156 return PyLong_FromSsize_t(index);
Raymond Hettinger0c410272004-01-05 10:13:35 +0000157}
158
159PyDoc_STRVAR(bisect_left_doc,
Raymond Hettingercc9a9512005-10-05 11:39:12 +0000160"bisect_left(a, x[, lo[, hi]]) -> index\n\
Raymond Hettinger0c410272004-01-05 10:13:35 +0000161\n\
162Return the index where to insert item x in list a, assuming a is sorted.\n\
163\n\
164The return value i is such that all e in a[:i] have e < x, and all e in\n\
165a[i:] have e >= x. So if x already appears in the list, i points just\n\
166before the leftmost x already there.\n\
167\n\
168Optional args lo (default 0) and hi (default len(a)) bound the\n\
169slice of a to be searched.\n");
170
171static PyObject *
Raymond Hettingercc9a9512005-10-05 11:39:12 +0000172insort_left(PyObject *self, PyObject *args, PyObject *kw)
Raymond Hettinger0c410272004-01-05 10:13:35 +0000173{
Michael W. Hudsonc9f510a2004-08-02 13:24:54 +0000174 PyObject *list, *item, *result;
Benjamin Petersond6313712008-07-31 16:23:04 +0000175 Py_ssize_t lo = 0;
176 Py_ssize_t hi = -1;
177 Py_ssize_t index;
Martin v. Löwis02cbf4a2006-02-27 17:20:04 +0000178 static char *keywords[] = {"a", "x", "lo", "hi", NULL};
Raymond Hettinger0c410272004-01-05 10:13:35 +0000179
Benjamin Petersond6313712008-07-31 16:23:04 +0000180 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:insort_left",
Raymond Hettingercc9a9512005-10-05 11:39:12 +0000181 keywords, &list, &item, &lo, &hi))
Raymond Hettinger0c410272004-01-05 10:13:35 +0000182 return NULL;
183 index = internal_bisect_left(list, item, lo, hi);
184 if (index < 0)
185 return NULL;
Benjamin Petersonf10a79a2008-10-11 00:49:57 +0000186 if (PyList_CheckExact(list)) {
Raymond Hettinger0c410272004-01-05 10:13:35 +0000187 if (PyList_Insert(list, index, item) < 0)
188 return NULL;
189 } else {
Michael W. Hudsonc9f510a2004-08-02 13:24:54 +0000190 result = PyObject_CallMethod(list, "insert", "iO",
191 index, item);
192 if (result == NULL)
Raymond Hettinger0c410272004-01-05 10:13:35 +0000193 return NULL;
Michael W. Hudsonc9f510a2004-08-02 13:24:54 +0000194 Py_DECREF(result);
Raymond Hettinger0c410272004-01-05 10:13:35 +0000195 }
196
197 Py_RETURN_NONE;
198}
199
200PyDoc_STRVAR(insort_left_doc,
Raymond Hettingercc9a9512005-10-05 11:39:12 +0000201"insort_left(a, x[, lo[, hi]])\n\
Raymond Hettinger0c410272004-01-05 10:13:35 +0000202\n\
203Insert item x in list a, and keep it sorted assuming a is sorted.\n\
204\n\
205If x is already in a, insert it to the left of the leftmost x.\n\
206\n\
207Optional args lo (default 0) and hi (default len(a)) bound the\n\
208slice of a to be searched.\n");
209
210PyDoc_STRVAR(bisect_doc, "Alias for bisect_right().\n");
211PyDoc_STRVAR(insort_doc, "Alias for insort_right().\n");
212
213static PyMethodDef bisect_methods[] = {
214 {"bisect_right", (PyCFunction)bisect_right,
Raymond Hettingercc9a9512005-10-05 11:39:12 +0000215 METH_VARARGS|METH_KEYWORDS, bisect_right_doc},
Raymond Hettinger0c410272004-01-05 10:13:35 +0000216 {"bisect", (PyCFunction)bisect_right,
Raymond Hettingercc9a9512005-10-05 11:39:12 +0000217 METH_VARARGS|METH_KEYWORDS, bisect_doc},
Raymond Hettinger0c410272004-01-05 10:13:35 +0000218 {"insort_right", (PyCFunction)insort_right,
Raymond Hettingercc9a9512005-10-05 11:39:12 +0000219 METH_VARARGS|METH_KEYWORDS, insort_right_doc},
Raymond Hettinger0c410272004-01-05 10:13:35 +0000220 {"insort", (PyCFunction)insort_right,
Raymond Hettingercc9a9512005-10-05 11:39:12 +0000221 METH_VARARGS|METH_KEYWORDS, insort_doc},
Raymond Hettinger0c410272004-01-05 10:13:35 +0000222 {"bisect_left", (PyCFunction)bisect_left,
Raymond Hettingercc9a9512005-10-05 11:39:12 +0000223 METH_VARARGS|METH_KEYWORDS, bisect_left_doc},
Raymond Hettinger0c410272004-01-05 10:13:35 +0000224 {"insort_left", (PyCFunction)insort_left,
Raymond Hettingercc9a9512005-10-05 11:39:12 +0000225 METH_VARARGS|METH_KEYWORDS, insort_left_doc},
Raymond Hettinger0c410272004-01-05 10:13:35 +0000226 {NULL, NULL} /* sentinel */
227};
228
229PyDoc_STRVAR(module_doc,
230"Bisection algorithms.\n\
231\n\
232This module provides support for maintaining a list in sorted order without\n\
233having to sort the list after each insertion. For long lists of items with\n\
234expensive comparison operations, this can be an improvement over the more\n\
235common approach.\n");
236
Raymond Hettinger0c410272004-01-05 10:13:35 +0000237
Martin v. Löwis1a214512008-06-11 05:26:20 +0000238static struct PyModuleDef _bisectmodule = {
239 PyModuleDef_HEAD_INIT,
240 "_bisect",
241 module_doc,
242 -1,
243 bisect_methods,
244 NULL,
245 NULL,
246 NULL,
247 NULL
248};
249
250PyMODINIT_FUNC
251PyInit__bisect(void)
252{
253 return PyModule_Create(&_bisectmodule);
Raymond Hettinger0c410272004-01-05 10:13:35 +0000254}