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 #include "Python.h"
      7 
      8 static Py_ssize_t
      9 internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi)
     10 {
     11     PyObject *litem;
     12     Py_ssize_t mid, res;
     13 
     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) {
     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;
     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;
     41 }
     42 
     43 static PyObject *
     44 bisect_right(PyObject *self, PyObject *args, PyObject *kw)
     45 {
     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};
     51 
     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 PyInt_FromSsize_t(index);
     59 }
     60 
     61 PyDoc_STRVAR(bisect_right_doc,
     62 "bisect(a, x[, lo[, hi]]) -> index\n\
     63 bisect_right(a, x[, lo[, hi]]) -> index\n\
     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 *
     75 insort_right(PyObject *self, PyObject *args, PyObject *kw)
     76 {
     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};
     82 
     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 {
     93         result = PyObject_CallMethod(list, "insert", "nO",
     94                                      index, item);
     95         if (result == NULL)
     96             return NULL;
     97         Py_DECREF(result);
     98     }
     99 
    100     Py_RETURN_NONE;
    101 }
    102 
    103 PyDoc_STRVAR(insort_right_doc,
    104 "insort(a, x[, lo[, hi]])\n\
    105 insort_right(a, x[, lo[, hi]])\n\
    106 \n\
    107 Insert item x in list a, and keep it sorted assuming a is sorted.\n\
    108 \n\
    109 If x is already in a, insert it to the right of the rightmost x.\n\
    110 \n\
    111 Optional args lo (default 0) and hi (default len(a)) bound the\n\
    112 slice of a to be searched.\n");
    113 
    114 static Py_ssize_t
    115 internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi)
    116 {
    117     PyObject *litem;
    118     Py_ssize_t mid, res;
    119 
    120     if (lo < 0) {
    121         PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
    122         return -1;
    123     }
    124     if (hi == -1) {
    125         hi = PySequence_Size(list);
    126         if (hi < 0)
    127             return -1;
    128     }
    129     while (lo < hi) {
    130         /* The (size_t)cast ensures that the addition and subsequent division
    131            are performed as unsigned operations, avoiding difficulties from
    132            signed overflow.  (See issue 13496.) */
    133         mid = ((size_t)lo + hi) / 2;
    134         litem = PySequence_GetItem(list, mid);
    135         if (litem == NULL)
    136             return -1;
    137         res = PyObject_RichCompareBool(litem, item, Py_LT);
    138         Py_DECREF(litem);
    139         if (res < 0)
    140             return -1;
    141         if (res)
    142             lo = mid + 1;
    143         else
    144             hi = mid;
    145     }
    146     return lo;
    147 }
    148 
    149 static PyObject *
    150 bisect_left(PyObject *self, PyObject *args, PyObject *kw)
    151 {
    152     PyObject *list, *item;
    153     Py_ssize_t lo = 0;
    154     Py_ssize_t hi = -1;
    155     Py_ssize_t index;
    156     static char *keywords[] = {"a", "x", "lo", "hi", NULL};
    157 
    158     if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:bisect_left",
    159         keywords, &list, &item, &lo, &hi))
    160         return NULL;
    161     index = internal_bisect_left(list, item, lo, hi);
    162     if (index < 0)
    163         return NULL;
    164     return PyInt_FromSsize_t(index);
    165 }
    166 
    167 PyDoc_STRVAR(bisect_left_doc,
    168 "bisect_left(a, x[, lo[, hi]]) -> index\n\
    169 \n\
    170 Return the index where to insert item x in list a, assuming a is sorted.\n\
    171 \n\
    172 The return value i is such that all e in a[:i] have e < x, and all e in\n\
    173 a[i:] have e >= x.  So if x already appears in the list, i points just\n\
    174 before the leftmost x already there.\n\
    175 \n\
    176 Optional args lo (default 0) and hi (default len(a)) bound the\n\
    177 slice of a to be searched.\n");
    178 
    179 static PyObject *
    180 insort_left(PyObject *self, PyObject *args, PyObject *kw)
    181 {
    182     PyObject *list, *item, *result;
    183     Py_ssize_t lo = 0;
    184     Py_ssize_t hi = -1;
    185     Py_ssize_t index;
    186     static char *keywords[] = {"a", "x", "lo", "hi", NULL};
    187 
    188     if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:insort_left",
    189         keywords, &list, &item, &lo, &hi))
    190         return NULL;
    191     index = internal_bisect_left(list, item, lo, hi);
    192     if (index < 0)
    193         return NULL;
    194     if (PyList_CheckExact(list)) {
    195         if (PyList_Insert(list, index, item) < 0)
    196             return NULL;
    197     } else {
    198         result = PyObject_CallMethod(list, "insert", "nO",
    199                                      index, item);
    200         if (result == NULL)
    201             return NULL;
    202         Py_DECREF(result);
    203     }
    204 
    205     Py_RETURN_NONE;
    206 }
    207 
    208 PyDoc_STRVAR(insort_left_doc,
    209 "insort_left(a, x[, lo[, hi]])\n\
    210 \n\
    211 Insert item x in list a, and keep it sorted assuming a is sorted.\n\
    212 \n\
    213 If x is already in a, insert it to the left of the leftmost x.\n\
    214 \n\
    215 Optional args lo (default 0) and hi (default len(a)) bound the\n\
    216 slice of a to be searched.\n");
    217 
    218 static PyMethodDef bisect_methods[] = {
    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_right_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_right_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 */
    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 
    242 PyMODINIT_FUNC
    243 init_bisect(void)
    244 {
    245     Py_InitModule3("_bisect", bisect_methods, module_doc);
    246 }
    247