ยปCore Development>Code coverage>Modules/_bisectmodule.c

Python code coverage for Modules/_bisectmodule.c

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