+++ /dev/null
-/* Bisection algorithms. Drop in replacement for bisect.py\r
-\r
-Converted to C by Dmitry Vasiliev (dima at hlabs.spb.ru).\r
-*/\r
-\r
-#include "Python.h"\r
-\r
-static Py_ssize_t\r
-internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi)\r
-{\r
- PyObject *litem;\r
- Py_ssize_t mid, res;\r
-\r
- if (lo < 0) {\r
- PyErr_SetString(PyExc_ValueError, "lo must be non-negative");\r
- return -1;\r
- }\r
- if (hi == -1) {\r
- hi = PySequence_Size(list);\r
- if (hi < 0)\r
- return -1;\r
- }\r
- while (lo < hi) {\r
- /* The (size_t)cast ensures that the addition and subsequent division\r
- are performed as unsigned operations, avoiding difficulties from\r
- signed overflow. (See issue 13496.) */\r
- mid = ((size_t)lo + hi) / 2;\r
- litem = PySequence_GetItem(list, mid);\r
- if (litem == NULL)\r
- return -1;\r
- res = PyObject_RichCompareBool(item, litem, Py_LT);\r
- Py_DECREF(litem);\r
- if (res < 0)\r
- return -1;\r
- if (res)\r
- hi = mid;\r
- else\r
- lo = mid + 1;\r
- }\r
- return lo;\r
-}\r
-\r
-static PyObject *\r
-bisect_right(PyObject *self, PyObject *args, PyObject *kw)\r
-{\r
- PyObject *list, *item;\r
- Py_ssize_t lo = 0;\r
- Py_ssize_t hi = -1;\r
- Py_ssize_t index;\r
- static char *keywords[] = {"a", "x", "lo", "hi", NULL};\r
-\r
- if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:bisect_right",\r
- keywords, &list, &item, &lo, &hi))\r
- return NULL;\r
- index = internal_bisect_right(list, item, lo, hi);\r
- if (index < 0)\r
- return NULL;\r
- return PyInt_FromSsize_t(index);\r
-}\r
-\r
-PyDoc_STRVAR(bisect_right_doc,\r
-"bisect(a, x[, lo[, hi]]) -> index\n\\r
-bisect_right(a, x[, lo[, hi]]) -> index\n\\r
-\n\\r
-Return the index where to insert item x in list a, assuming a is sorted.\n\\r
-\n\\r
-The return value i is such that all e in a[:i] have e <= x, and all e in\n\\r
-a[i:] have e > x. So if x already appears in the list, i points just\n\\r
-beyond the rightmost x already there\n\\r
-\n\\r
-Optional args lo (default 0) and hi (default len(a)) bound the\n\\r
-slice of a to be searched.\n");\r
-\r
-static PyObject *\r
-insort_right(PyObject *self, PyObject *args, PyObject *kw)\r
-{\r
- PyObject *list, *item, *result;\r
- Py_ssize_t lo = 0;\r
- Py_ssize_t hi = -1;\r
- Py_ssize_t index;\r
- static char *keywords[] = {"a", "x", "lo", "hi", NULL};\r
-\r
- if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:insort_right",\r
- keywords, &list, &item, &lo, &hi))\r
- return NULL;\r
- index = internal_bisect_right(list, item, lo, hi);\r
- if (index < 0)\r
- return NULL;\r
- if (PyList_CheckExact(list)) {\r
- if (PyList_Insert(list, index, item) < 0)\r
- return NULL;\r
- } else {\r
- result = PyObject_CallMethod(list, "insert", "nO",\r
- index, item);\r
- if (result == NULL)\r
- return NULL;\r
- Py_DECREF(result);\r
- }\r
-\r
- Py_RETURN_NONE;\r
-}\r
-\r
-PyDoc_STRVAR(insort_right_doc,\r
-"insort(a, x[, lo[, hi]])\n\\r
-insort_right(a, x[, lo[, hi]])\n\\r
-\n\\r
-Insert item x in list a, and keep it sorted assuming a is sorted.\n\\r
-\n\\r
-If x is already in a, insert it to the right of the rightmost x.\n\\r
-\n\\r
-Optional args lo (default 0) and hi (default len(a)) bound the\n\\r
-slice of a to be searched.\n");\r
-\r
-static Py_ssize_t\r
-internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi)\r
-{\r
- PyObject *litem;\r
- Py_ssize_t mid, res;\r
-\r
- if (lo < 0) {\r
- PyErr_SetString(PyExc_ValueError, "lo must be non-negative");\r
- return -1;\r
- }\r
- if (hi == -1) {\r
- hi = PySequence_Size(list);\r
- if (hi < 0)\r
- return -1;\r
- }\r
- while (lo < hi) {\r
- /* The (size_t)cast ensures that the addition and subsequent division\r
- are performed as unsigned operations, avoiding difficulties from\r
- signed overflow. (See issue 13496.) */\r
- mid = ((size_t)lo + hi) / 2;\r
- litem = PySequence_GetItem(list, mid);\r
- if (litem == NULL)\r
- return -1;\r
- res = PyObject_RichCompareBool(litem, item, Py_LT);\r
- Py_DECREF(litem);\r
- if (res < 0)\r
- return -1;\r
- if (res)\r
- lo = mid + 1;\r
- else\r
- hi = mid;\r
- }\r
- return lo;\r
-}\r
-\r
-static PyObject *\r
-bisect_left(PyObject *self, PyObject *args, PyObject *kw)\r
-{\r
- PyObject *list, *item;\r
- Py_ssize_t lo = 0;\r
- Py_ssize_t hi = -1;\r
- Py_ssize_t index;\r
- static char *keywords[] = {"a", "x", "lo", "hi", NULL};\r
-\r
- if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:bisect_left",\r
- keywords, &list, &item, &lo, &hi))\r
- return NULL;\r
- index = internal_bisect_left(list, item, lo, hi);\r
- if (index < 0)\r
- return NULL;\r
- return PyInt_FromSsize_t(index);\r
-}\r
-\r
-PyDoc_STRVAR(bisect_left_doc,\r
-"bisect_left(a, x[, lo[, hi]]) -> index\n\\r
-\n\\r
-Return the index where to insert item x in list a, assuming a is sorted.\n\\r
-\n\\r
-The return value i is such that all e in a[:i] have e < x, and all e in\n\\r
-a[i:] have e >= x. So if x already appears in the list, i points just\n\\r
-before the leftmost x already there.\n\\r
-\n\\r
-Optional args lo (default 0) and hi (default len(a)) bound the\n\\r
-slice of a to be searched.\n");\r
-\r
-static PyObject *\r
-insort_left(PyObject *self, PyObject *args, PyObject *kw)\r
-{\r
- PyObject *list, *item, *result;\r
- Py_ssize_t lo = 0;\r
- Py_ssize_t hi = -1;\r
- Py_ssize_t index;\r
- static char *keywords[] = {"a", "x", "lo", "hi", NULL};\r
-\r
- if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:insort_left",\r
- keywords, &list, &item, &lo, &hi))\r
- return NULL;\r
- index = internal_bisect_left(list, item, lo, hi);\r
- if (index < 0)\r
- return NULL;\r
- if (PyList_CheckExact(list)) {\r
- if (PyList_Insert(list, index, item) < 0)\r
- return NULL;\r
- } else {\r
- result = PyObject_CallMethod(list, "insert", "nO",\r
- index, item);\r
- if (result == NULL)\r
- return NULL;\r
- Py_DECREF(result);\r
- }\r
-\r
- Py_RETURN_NONE;\r
-}\r
-\r
-PyDoc_STRVAR(insort_left_doc,\r
-"insort_left(a, x[, lo[, hi]])\n\\r
-\n\\r
-Insert item x in list a, and keep it sorted assuming a is sorted.\n\\r
-\n\\r
-If x is already in a, insert it to the left of the leftmost x.\n\\r
-\n\\r
-Optional args lo (default 0) and hi (default len(a)) bound the\n\\r
-slice of a to be searched.\n");\r
-\r
-static PyMethodDef bisect_methods[] = {\r
- {"bisect_right", (PyCFunction)bisect_right,\r
- METH_VARARGS|METH_KEYWORDS, bisect_right_doc},\r
- {"bisect", (PyCFunction)bisect_right,\r
- METH_VARARGS|METH_KEYWORDS, bisect_right_doc},\r
- {"insort_right", (PyCFunction)insort_right,\r
- METH_VARARGS|METH_KEYWORDS, insort_right_doc},\r
- {"insort", (PyCFunction)insort_right,\r
- METH_VARARGS|METH_KEYWORDS, insort_right_doc},\r
- {"bisect_left", (PyCFunction)bisect_left,\r
- METH_VARARGS|METH_KEYWORDS, bisect_left_doc},\r
- {"insort_left", (PyCFunction)insort_left,\r
- METH_VARARGS|METH_KEYWORDS, insort_left_doc},\r
- {NULL, NULL} /* sentinel */\r
-};\r
-\r
-PyDoc_STRVAR(module_doc,\r
-"Bisection algorithms.\n\\r
-\n\\r
-This module provides support for maintaining a list in sorted order without\n\\r
-having to sort the list after each insertion. For long lists of items with\n\\r
-expensive comparison operations, this can be an improvement over the more\n\\r
-common approach.\n");\r
-\r
-PyMODINIT_FUNC\r
-init_bisect(void)\r
-{\r
- Py_InitModule3("_bisect", bisect_methods, module_doc);\r
-}\r
projects / mirror_edk2.git / blobdiff