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