Modules/_bisectmodule.c

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