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 | |
Shantanu | 3a855b2 | 2020-05-17 20:38:35 -0700 | [diff] [blame] | 9 | /*[clinic input] |
| 10 | module _bisect |
| 11 | [clinic start generated code]*/ |
| 12 | /*[clinic end generated code: output=da39a3ee5e6b4b0d input=4d56a2b2033b462b]*/ |
| 13 | |
| 14 | #include "clinic/_bisectmodule.c.h" |
| 15 | |
Martin v. Löwis | e75fc14 | 2013-11-07 18:46:53 +0100 | [diff] [blame] | 16 | _Py_IDENTIFIER(insert); |
| 17 | |
Raymond Hettinger | de2e448 | 2018-10-08 08:02:41 -0700 | [diff] [blame] | 18 | static inline Py_ssize_t |
Raymond Hettinger | 871934d | 2020-10-19 22:04:01 -0700 | [diff] [blame] | 19 | internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi, |
| 20 | PyObject* key) |
Raymond Hettinger | 0c41027 | 2004-01-05 10:13:35 +0000 | [diff] [blame] | 21 | { |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 22 | PyObject *litem; |
Raymond Hettinger | b6f17f5 | 2016-02-14 01:41:35 -0800 | [diff] [blame] | 23 | Py_ssize_t mid; |
| 24 | int res; |
Raymond Hettinger | 0c41027 | 2004-01-05 10:13:35 +0000 | [diff] [blame] | 25 | |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 26 | if (lo < 0) { |
| 27 | PyErr_SetString(PyExc_ValueError, "lo must be non-negative"); |
| 28 | return -1; |
| 29 | } |
| 30 | if (hi == -1) { |
| 31 | hi = PySequence_Size(list); |
| 32 | if (hi < 0) |
| 33 | return -1; |
| 34 | } |
| 35 | while (lo < hi) { |
Mark Dickinson | a13b109 | 2012-04-15 16:30:35 +0100 | [diff] [blame] | 36 | /* The (size_t)cast ensures that the addition and subsequent division |
| 37 | are performed as unsigned operations, avoiding difficulties from |
| 38 | signed overflow. (See issue 13496.) */ |
| 39 | mid = ((size_t)lo + hi) / 2; |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 40 | litem = PySequence_GetItem(list, mid); |
| 41 | if (litem == NULL) |
| 42 | return -1; |
Raymond Hettinger | 871934d | 2020-10-19 22:04:01 -0700 | [diff] [blame] | 43 | if (key != Py_None) { |
| 44 | PyObject *newitem = PyObject_CallOneArg(key, litem); |
| 45 | if (newitem == NULL) { |
| 46 | Py_DECREF(litem); |
| 47 | return -1; |
| 48 | } |
| 49 | Py_SETREF(litem, newitem); |
| 50 | } |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 51 | res = PyObject_RichCompareBool(item, litem, Py_LT); |
| 52 | Py_DECREF(litem); |
| 53 | if (res < 0) |
| 54 | return -1; |
| 55 | if (res) |
| 56 | hi = mid; |
| 57 | else |
| 58 | lo = mid + 1; |
| 59 | } |
| 60 | return lo; |
Raymond Hettinger | 0c41027 | 2004-01-05 10:13:35 +0000 | [diff] [blame] | 61 | } |
| 62 | |
Shantanu | 3a855b2 | 2020-05-17 20:38:35 -0700 | [diff] [blame] | 63 | /*[clinic input] |
| 64 | _bisect.bisect_right -> Py_ssize_t |
Raymond Hettinger | 0c41027 | 2004-01-05 10:13:35 +0000 | [diff] [blame] | 65 | |
Shantanu | 3a855b2 | 2020-05-17 20:38:35 -0700 | [diff] [blame] | 66 | a: object |
| 67 | x: object |
| 68 | lo: Py_ssize_t = 0 |
| 69 | hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None |
Raymond Hettinger | 871934d | 2020-10-19 22:04:01 -0700 | [diff] [blame] | 70 | * |
| 71 | key: object = None |
Shantanu | 3a855b2 | 2020-05-17 20:38:35 -0700 | [diff] [blame] | 72 | |
| 73 | Return the index where to insert item x in list a, assuming a is sorted. |
| 74 | |
| 75 | The return value i is such that all e in a[:i] have e <= x, and all e in |
| 76 | a[i:] have e > x. So if x already appears in the list, i points just |
| 77 | beyond the rightmost x already there |
| 78 | |
| 79 | Optional args lo (default 0) and hi (default len(a)) bound the |
| 80 | slice of a to be searched. |
| 81 | [clinic start generated code]*/ |
| 82 | |
| 83 | static Py_ssize_t |
| 84 | _bisect_bisect_right_impl(PyObject *module, PyObject *a, PyObject *x, |
Raymond Hettinger | 871934d | 2020-10-19 22:04:01 -0700 | [diff] [blame] | 85 | Py_ssize_t lo, Py_ssize_t hi, PyObject *key) |
| 86 | /*[clinic end generated code: output=3a4bc09cc7c8a73d input=1313e9ca20c8bc3c]*/ |
Shantanu | 3a855b2 | 2020-05-17 20:38:35 -0700 | [diff] [blame] | 87 | { |
Raymond Hettinger | 871934d | 2020-10-19 22:04:01 -0700 | [diff] [blame] | 88 | return internal_bisect_right(a, x, lo, hi, key); |
Raymond Hettinger | 0c41027 | 2004-01-05 10:13:35 +0000 | [diff] [blame] | 89 | } |
| 90 | |
Shantanu | 3a855b2 | 2020-05-17 20:38:35 -0700 | [diff] [blame] | 91 | /*[clinic input] |
| 92 | _bisect.insort_right |
| 93 | |
| 94 | a: object |
| 95 | x: object |
| 96 | lo: Py_ssize_t = 0 |
| 97 | hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None |
Raymond Hettinger | 871934d | 2020-10-19 22:04:01 -0700 | [diff] [blame] | 98 | * |
| 99 | key: object = None |
Shantanu | 3a855b2 | 2020-05-17 20:38:35 -0700 | [diff] [blame] | 100 | |
| 101 | Insert item x in list a, and keep it sorted assuming a is sorted. |
| 102 | |
| 103 | If x is already in a, insert it to the right of the rightmost x. |
| 104 | |
| 105 | Optional args lo (default 0) and hi (default len(a)) bound the |
| 106 | slice of a to be searched. |
| 107 | [clinic start generated code]*/ |
Raymond Hettinger | 0c41027 | 2004-01-05 10:13:35 +0000 | [diff] [blame] | 108 | |
| 109 | static PyObject * |
Shantanu | 3a855b2 | 2020-05-17 20:38:35 -0700 | [diff] [blame] | 110 | _bisect_insort_right_impl(PyObject *module, PyObject *a, PyObject *x, |
Raymond Hettinger | 871934d | 2020-10-19 22:04:01 -0700 | [diff] [blame] | 111 | Py_ssize_t lo, Py_ssize_t hi, PyObject *key) |
| 112 | /*[clinic end generated code: output=ac3bf26d07aedda2 input=44e1708e26b7b802]*/ |
Raymond Hettinger | 0c41027 | 2004-01-05 10:13:35 +0000 | [diff] [blame] | 113 | { |
Raymond Hettinger | 871934d | 2020-10-19 22:04:01 -0700 | [diff] [blame] | 114 | PyObject *result, *key_x; |
| 115 | Py_ssize_t index; |
| 116 | |
| 117 | if (key == Py_None) { |
| 118 | index = internal_bisect_right(a, x, lo, hi, key); |
| 119 | } else { |
| 120 | key_x = PyObject_CallOneArg(key, x); |
| 121 | if (x == NULL) { |
| 122 | return NULL; |
| 123 | } |
| 124 | index = internal_bisect_right(a, key_x, lo, hi, key); |
| 125 | Py_DECREF(key_x); |
| 126 | } |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 127 | if (index < 0) |
| 128 | return NULL; |
Shantanu | 3a855b2 | 2020-05-17 20:38:35 -0700 | [diff] [blame] | 129 | if (PyList_CheckExact(a)) { |
| 130 | if (PyList_Insert(a, index, x) < 0) |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 131 | return NULL; |
Raymond Hettinger | de2e448 | 2018-10-08 08:02:41 -0700 | [diff] [blame] | 132 | } |
| 133 | else { |
Shantanu | 3a855b2 | 2020-05-17 20:38:35 -0700 | [diff] [blame] | 134 | result = _PyObject_CallMethodId(a, &PyId_insert, "nO", index, x); |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 135 | if (result == NULL) |
| 136 | return NULL; |
| 137 | Py_DECREF(result); |
| 138 | } |
Raymond Hettinger | 0c41027 | 2004-01-05 10:13:35 +0000 | [diff] [blame] | 139 | |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 140 | Py_RETURN_NONE; |
Raymond Hettinger | 0c41027 | 2004-01-05 10:13:35 +0000 | [diff] [blame] | 141 | } |
| 142 | |
Raymond Hettinger | de2e448 | 2018-10-08 08:02:41 -0700 | [diff] [blame] | 143 | static inline Py_ssize_t |
Raymond Hettinger | 871934d | 2020-10-19 22:04:01 -0700 | [diff] [blame] | 144 | internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi, |
| 145 | PyObject *key) |
Raymond Hettinger | 0c41027 | 2004-01-05 10:13:35 +0000 | [diff] [blame] | 146 | { |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 147 | PyObject *litem; |
Raymond Hettinger | b6f17f5 | 2016-02-14 01:41:35 -0800 | [diff] [blame] | 148 | Py_ssize_t mid; |
| 149 | int res; |
Raymond Hettinger | 0c41027 | 2004-01-05 10:13:35 +0000 | [diff] [blame] | 150 | |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 151 | if (lo < 0) { |
| 152 | PyErr_SetString(PyExc_ValueError, "lo must be non-negative"); |
| 153 | return -1; |
| 154 | } |
| 155 | if (hi == -1) { |
| 156 | hi = PySequence_Size(list); |
| 157 | if (hi < 0) |
| 158 | return -1; |
| 159 | } |
| 160 | while (lo < hi) { |
Mark Dickinson | a13b109 | 2012-04-15 16:30:35 +0100 | [diff] [blame] | 161 | /* The (size_t)cast ensures that the addition and subsequent division |
| 162 | are performed as unsigned operations, avoiding difficulties from |
| 163 | signed overflow. (See issue 13496.) */ |
| 164 | mid = ((size_t)lo + hi) / 2; |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 165 | litem = PySequence_GetItem(list, mid); |
| 166 | if (litem == NULL) |
| 167 | return -1; |
Raymond Hettinger | 871934d | 2020-10-19 22:04:01 -0700 | [diff] [blame] | 168 | if (key != Py_None) { |
| 169 | PyObject *newitem = PyObject_CallOneArg(key, litem); |
| 170 | if (newitem == NULL) { |
| 171 | Py_DECREF(litem); |
| 172 | return -1; |
| 173 | } |
| 174 | Py_SETREF(litem, newitem); |
| 175 | } |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 176 | res = PyObject_RichCompareBool(litem, item, Py_LT); |
| 177 | Py_DECREF(litem); |
| 178 | if (res < 0) |
| 179 | return -1; |
| 180 | if (res) |
| 181 | lo = mid + 1; |
| 182 | else |
| 183 | hi = mid; |
| 184 | } |
| 185 | return lo; |
Raymond Hettinger | 0c41027 | 2004-01-05 10:13:35 +0000 | [diff] [blame] | 186 | } |
| 187 | |
Raymond Hettinger | 0c41027 | 2004-01-05 10:13:35 +0000 | [diff] [blame] | 188 | |
Shantanu | 3a855b2 | 2020-05-17 20:38:35 -0700 | [diff] [blame] | 189 | /*[clinic input] |
| 190 | _bisect.bisect_left -> Py_ssize_t |
| 191 | |
| 192 | a: object |
| 193 | x: object |
| 194 | lo: Py_ssize_t = 0 |
| 195 | hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None |
Raymond Hettinger | 871934d | 2020-10-19 22:04:01 -0700 | [diff] [blame] | 196 | * |
| 197 | key: object = None |
Shantanu | 3a855b2 | 2020-05-17 20:38:35 -0700 | [diff] [blame] | 198 | |
| 199 | Return the index where to insert item x in list a, assuming a is sorted. |
| 200 | |
| 201 | The return value i is such that all e in a[:i] have e < x, and all e in |
| 202 | a[i:] have e >= x. So if x already appears in the list, i points just |
| 203 | before the leftmost x already there. |
| 204 | |
| 205 | Optional args lo (default 0) and hi (default len(a)) bound the |
| 206 | slice of a to be searched. |
| 207 | [clinic start generated code]*/ |
| 208 | |
| 209 | static Py_ssize_t |
| 210 | _bisect_bisect_left_impl(PyObject *module, PyObject *a, PyObject *x, |
Raymond Hettinger | 871934d | 2020-10-19 22:04:01 -0700 | [diff] [blame] | 211 | Py_ssize_t lo, Py_ssize_t hi, PyObject *key) |
| 212 | /*[clinic end generated code: output=70749d6e5cae9284 input=3cbeec690f2f6c6e]*/ |
Shantanu | 3a855b2 | 2020-05-17 20:38:35 -0700 | [diff] [blame] | 213 | { |
Raymond Hettinger | 871934d | 2020-10-19 22:04:01 -0700 | [diff] [blame] | 214 | return internal_bisect_left(a, x, lo, hi, key); |
Raymond Hettinger | 0c41027 | 2004-01-05 10:13:35 +0000 | [diff] [blame] | 215 | } |
| 216 | |
Shantanu | 3a855b2 | 2020-05-17 20:38:35 -0700 | [diff] [blame] | 217 | |
| 218 | /*[clinic input] |
| 219 | _bisect.insort_left |
| 220 | |
| 221 | a: object |
| 222 | x: object |
| 223 | lo: Py_ssize_t = 0 |
| 224 | hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None |
Raymond Hettinger | 871934d | 2020-10-19 22:04:01 -0700 | [diff] [blame] | 225 | * |
| 226 | key: object = None |
Shantanu | 3a855b2 | 2020-05-17 20:38:35 -0700 | [diff] [blame] | 227 | |
| 228 | Insert item x in list a, and keep it sorted assuming a is sorted. |
| 229 | |
| 230 | If x is already in a, insert it to the left of the leftmost x. |
| 231 | |
| 232 | Optional args lo (default 0) and hi (default len(a)) bound the |
| 233 | slice of a to be searched. |
| 234 | [clinic start generated code]*/ |
Raymond Hettinger | 0c41027 | 2004-01-05 10:13:35 +0000 | [diff] [blame] | 235 | |
| 236 | static PyObject * |
Shantanu | 3a855b2 | 2020-05-17 20:38:35 -0700 | [diff] [blame] | 237 | _bisect_insort_left_impl(PyObject *module, PyObject *a, PyObject *x, |
Raymond Hettinger | 871934d | 2020-10-19 22:04:01 -0700 | [diff] [blame] | 238 | Py_ssize_t lo, Py_ssize_t hi, PyObject *key) |
| 239 | /*[clinic end generated code: output=b1d33e5e7ffff11e input=3ab65d8784f585b1]*/ |
Raymond Hettinger | 0c41027 | 2004-01-05 10:13:35 +0000 | [diff] [blame] | 240 | { |
Raymond Hettinger | 871934d | 2020-10-19 22:04:01 -0700 | [diff] [blame] | 241 | PyObject *result, *key_x; |
| 242 | Py_ssize_t index; |
| 243 | |
| 244 | if (key == Py_None) { |
| 245 | index = internal_bisect_left(a, x, lo, hi, key); |
| 246 | } else { |
| 247 | key_x = PyObject_CallOneArg(key, x); |
| 248 | if (x == NULL) { |
| 249 | return NULL; |
| 250 | } |
| 251 | index = internal_bisect_left(a, key_x, lo, hi, key); |
| 252 | Py_DECREF(key_x); |
| 253 | } |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 254 | if (index < 0) |
| 255 | return NULL; |
Shantanu | 3a855b2 | 2020-05-17 20:38:35 -0700 | [diff] [blame] | 256 | if (PyList_CheckExact(a)) { |
| 257 | if (PyList_Insert(a, index, x) < 0) |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 258 | return NULL; |
| 259 | } else { |
Shantanu | 3a855b2 | 2020-05-17 20:38:35 -0700 | [diff] [blame] | 260 | result = _PyObject_CallMethodId(a, &PyId_insert, "nO", index, x); |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 261 | if (result == NULL) |
| 262 | return NULL; |
| 263 | Py_DECREF(result); |
| 264 | } |
Raymond Hettinger | 0c41027 | 2004-01-05 10:13:35 +0000 | [diff] [blame] | 265 | |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 266 | Py_RETURN_NONE; |
Raymond Hettinger | 0c41027 | 2004-01-05 10:13:35 +0000 | [diff] [blame] | 267 | } |
| 268 | |
Raymond Hettinger | 0c41027 | 2004-01-05 10:13:35 +0000 | [diff] [blame] | 269 | static PyMethodDef bisect_methods[] = { |
Shantanu | 3a855b2 | 2020-05-17 20:38:35 -0700 | [diff] [blame] | 270 | _BISECT_BISECT_RIGHT_METHODDEF |
| 271 | _BISECT_INSORT_RIGHT_METHODDEF |
| 272 | _BISECT_BISECT_LEFT_METHODDEF |
| 273 | _BISECT_INSORT_LEFT_METHODDEF |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 274 | {NULL, NULL} /* sentinel */ |
Raymond Hettinger | 0c41027 | 2004-01-05 10:13:35 +0000 | [diff] [blame] | 275 | }; |
| 276 | |
| 277 | PyDoc_STRVAR(module_doc, |
| 278 | "Bisection algorithms.\n\ |
| 279 | \n\ |
| 280 | This module provides support for maintaining a list in sorted order without\n\ |
| 281 | having to sort the list after each insertion. For long lists of items with\n\ |
| 282 | expensive comparison operations, this can be an improvement over the more\n\ |
| 283 | common approach.\n"); |
| 284 | |
Raymond Hettinger | 0c41027 | 2004-01-05 10:13:35 +0000 | [diff] [blame] | 285 | |
Martin v. Löwis | 1a21451 | 2008-06-11 05:26:20 +0000 | [diff] [blame] | 286 | static struct PyModuleDef _bisectmodule = { |
Antoine Pitrou | f95a1b3 | 2010-05-09 15:52:27 +0000 | [diff] [blame] | 287 | PyModuleDef_HEAD_INIT, |
Dong-hee Na | 2afd175 | 2020-09-26 19:56:26 +0900 | [diff] [blame] | 288 | .m_name = "_bisect", |
| 289 | .m_doc = module_doc, |
| 290 | .m_methods = bisect_methods, |
| 291 | .m_size = 0 |
Martin v. Löwis | 1a21451 | 2008-06-11 05:26:20 +0000 | [diff] [blame] | 292 | }; |
| 293 | |
| 294 | PyMODINIT_FUNC |
| 295 | PyInit__bisect(void) |
| 296 | { |
Dong-hee Na | 2afd175 | 2020-09-26 19:56:26 +0900 | [diff] [blame] | 297 | return PyModuleDef_Init(&_bisectmodule); |
Raymond Hettinger | 0c41027 | 2004-01-05 10:13:35 +0000 | [diff] [blame] | 298 | } |