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