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