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