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