1 /*[clinic input]
2 preserve
3 [clinic start generated code]*/
4
5 #if defined(Py_BUILD_CORE) && !defined(Py_BUILD_CORE_MODULE)
6 # include "pycore_gc.h" // PyGC_Head
7 # include "pycore_runtime.h" // _Py_ID()
8 #endif
9
10
11 PyDoc_STRVAR(_bisect_bisect_right__doc__,
12 "bisect_right($module, /, a, x, lo=0, hi=None, *, key=None)\n"
13 "--\n"
14 "\n"
15 "Return the index where to insert item x in list a, assuming a is sorted.\n"
16 "\n"
17 "The return value i is such that all e in a[:i] have e <= x, and all e in\n"
18 "a[i:] have e > x. So if x already appears in the list, a.insert(i, x) will\n"
19 "insert just after the rightmost x already there.\n"
20 "\n"
21 "Optional args lo (default 0) and hi (default len(a)) bound the\n"
22 "slice of a to be searched.\n"
23 "\n"
24 "A custom key function can be supplied to customize the sort order.");
25
26 #define _BISECT_BISECT_RIGHT_METHODDEF \
27 {"bisect_right", _PyCFunction_CAST(_bisect_bisect_right), METH_FASTCALL|METH_KEYWORDS, _bisect_bisect_right__doc__},
28
29 static Py_ssize_t
30 _bisect_bisect_right_impl(PyObject *module, PyObject *a, PyObject *x,
31 Py_ssize_t lo, Py_ssize_t hi, PyObject *key);
32
33 static PyObject *
34 _bisect_bisect_right(PyObject *module, PyObject *const *args, Py_ssize_t nargs, PyObject *kwnames)
35 {
36 PyObject *return_value = NULL;
37 #if defined(Py_BUILD_CORE) && !defined(Py_BUILD_CORE_MODULE)
38
39 #define NUM_KEYWORDS 5
40 static struct {
41 PyGC_Head _this_is_not_used;
42 PyObject_VAR_HEAD
43 PyObject *ob_item[NUM_KEYWORDS];
44 } _kwtuple = {
45 .ob_base = PyVarObject_HEAD_INIT(&PyTuple_Type, NUM_KEYWORDS)
46 .ob_item = { &_Py_ID(a), &_Py_ID(x), &_Py_ID(lo), &_Py_ID(hi), &_Py_ID(key), },
47 };
48 #undef NUM_KEYWORDS
49 #define KWTUPLE (&_kwtuple.ob_base.ob_base)
50
51 #else // !Py_BUILD_CORE
52 # define KWTUPLE NULL
53 #endif // !Py_BUILD_CORE
54
55 static const char * const _keywords[] = {"a", "x", "lo", "hi", "key", NULL};
56 static _PyArg_Parser _parser = {
57 .keywords = _keywords,
58 .fname = "bisect_right",
59 .kwtuple = KWTUPLE,
60 };
61 #undef KWTUPLE
62 PyObject *argsbuf[5];
63 Py_ssize_t noptargs = nargs + (kwnames ? PyTuple_GET_SIZE(kwnames) : 0) - 2;
64 PyObject *a;
65 PyObject *x;
66 Py_ssize_t lo = 0;
67 Py_ssize_t hi = -1;
68 PyObject *key = Py_None;
69 Py_ssize_t _return_value;
70
71 args = _PyArg_UnpackKeywords(args, nargs, NULL, kwnames, &_parser, 2, 4, 0, argsbuf);
72 if (!args) {
73 goto exit;
74 }
75 a = args[0];
76 x = args[1];
77 if (!noptargs) {
78 goto skip_optional_pos;
79 }
80 if (args[2]) {
81 {
82 Py_ssize_t ival = -1;
83 PyObject *iobj = _PyNumber_Index(args[2]);
84 if (iobj != NULL) {
85 ival = PyLong_AsSsize_t(iobj);
86 Py_DECREF(iobj);
87 }
88 if (ival == -1 && PyErr_Occurred()) {
89 goto exit;
90 }
91 lo = ival;
92 }
93 if (!--noptargs) {
94 goto skip_optional_pos;
95 }
96 }
97 if (args[3]) {
98 if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
99 goto exit;
100 }
101 if (!--noptargs) {
102 goto skip_optional_pos;
103 }
104 }
105 skip_optional_pos:
106 if (!noptargs) {
107 goto skip_optional_kwonly;
108 }
109 key = args[4];
110 skip_optional_kwonly:
111 _return_value = _bisect_bisect_right_impl(module, a, x, lo, hi, key);
112 if ((_return_value == -1) && PyErr_Occurred()) {
113 goto exit;
114 }
115 return_value = PyLong_FromSsize_t(_return_value);
116
117 exit:
118 return return_value;
119 }
120
121 PyDoc_STRVAR(_bisect_insort_right__doc__,
122 "insort_right($module, /, a, x, lo=0, hi=None, *, key=None)\n"
123 "--\n"
124 "\n"
125 "Insert item x in list a, and keep it sorted assuming a is sorted.\n"
126 "\n"
127 "If x is already in a, insert it to the right of the rightmost x.\n"
128 "\n"
129 "Optional args lo (default 0) and hi (default len(a)) bound the\n"
130 "slice of a to be searched.\n"
131 "\n"
132 "A custom key function can be supplied to customize the sort order.");
133
134 #define _BISECT_INSORT_RIGHT_METHODDEF \
135 {"insort_right", _PyCFunction_CAST(_bisect_insort_right), METH_FASTCALL|METH_KEYWORDS, _bisect_insort_right__doc__},
136
137 static PyObject *
138 _bisect_insort_right_impl(PyObject *module, PyObject *a, PyObject *x,
139 Py_ssize_t lo, Py_ssize_t hi, PyObject *key);
140
141 static PyObject *
142 _bisect_insort_right(PyObject *module, PyObject *const *args, Py_ssize_t nargs, PyObject *kwnames)
143 {
144 PyObject *return_value = NULL;
145 #if defined(Py_BUILD_CORE) && !defined(Py_BUILD_CORE_MODULE)
146
147 #define NUM_KEYWORDS 5
148 static struct {
149 PyGC_Head _this_is_not_used;
150 PyObject_VAR_HEAD
151 PyObject *ob_item[NUM_KEYWORDS];
152 } _kwtuple = {
153 .ob_base = PyVarObject_HEAD_INIT(&PyTuple_Type, NUM_KEYWORDS)
154 .ob_item = { &_Py_ID(a), &_Py_ID(x), &_Py_ID(lo), &_Py_ID(hi), &_Py_ID(key), },
155 };
156 #undef NUM_KEYWORDS
157 #define KWTUPLE (&_kwtuple.ob_base.ob_base)
158
159 #else // !Py_BUILD_CORE
160 # define KWTUPLE NULL
161 #endif // !Py_BUILD_CORE
162
163 static const char * const _keywords[] = {"a", "x", "lo", "hi", "key", NULL};
164 static _PyArg_Parser _parser = {
165 .keywords = _keywords,
166 .fname = "insort_right",
167 .kwtuple = KWTUPLE,
168 };
169 #undef KWTUPLE
170 PyObject *argsbuf[5];
171 Py_ssize_t noptargs = nargs + (kwnames ? PyTuple_GET_SIZE(kwnames) : 0) - 2;
172 PyObject *a;
173 PyObject *x;
174 Py_ssize_t lo = 0;
175 Py_ssize_t hi = -1;
176 PyObject *key = Py_None;
177
178 args = _PyArg_UnpackKeywords(args, nargs, NULL, kwnames, &_parser, 2, 4, 0, argsbuf);
179 if (!args) {
180 goto exit;
181 }
182 a = args[0];
183 x = args[1];
184 if (!noptargs) {
185 goto skip_optional_pos;
186 }
187 if (args[2]) {
188 {
189 Py_ssize_t ival = -1;
190 PyObject *iobj = _PyNumber_Index(args[2]);
191 if (iobj != NULL) {
192 ival = PyLong_AsSsize_t(iobj);
193 Py_DECREF(iobj);
194 }
195 if (ival == -1 && PyErr_Occurred()) {
196 goto exit;
197 }
198 lo = ival;
199 }
200 if (!--noptargs) {
201 goto skip_optional_pos;
202 }
203 }
204 if (args[3]) {
205 if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
206 goto exit;
207 }
208 if (!--noptargs) {
209 goto skip_optional_pos;
210 }
211 }
212 skip_optional_pos:
213 if (!noptargs) {
214 goto skip_optional_kwonly;
215 }
216 key = args[4];
217 skip_optional_kwonly:
218 return_value = _bisect_insort_right_impl(module, a, x, lo, hi, key);
219
220 exit:
221 return return_value;
222 }
223
224 PyDoc_STRVAR(_bisect_bisect_left__doc__,
225 "bisect_left($module, /, a, x, lo=0, hi=None, *, key=None)\n"
226 "--\n"
227 "\n"
228 "Return the index where to insert item x in list a, assuming a is sorted.\n"
229 "\n"
230 "The return value i is such that all e in a[:i] have e < x, and all e in\n"
231 "a[i:] have e >= x. So if x already appears in the list, a.insert(i, x) will\n"
232 "insert just before the leftmost x already there.\n"
233 "\n"
234 "Optional args lo (default 0) and hi (default len(a)) bound the\n"
235 "slice of a to be searched.\n"
236 "\n"
237 "A custom key function can be supplied to customize the sort order.");
238
239 #define _BISECT_BISECT_LEFT_METHODDEF \
240 {"bisect_left", _PyCFunction_CAST(_bisect_bisect_left), METH_FASTCALL|METH_KEYWORDS, _bisect_bisect_left__doc__},
241
242 static Py_ssize_t
243 _bisect_bisect_left_impl(PyObject *module, PyObject *a, PyObject *x,
244 Py_ssize_t lo, Py_ssize_t hi, PyObject *key);
245
246 static PyObject *
247 _bisect_bisect_left(PyObject *module, PyObject *const *args, Py_ssize_t nargs, PyObject *kwnames)
248 {
249 PyObject *return_value = NULL;
250 #if defined(Py_BUILD_CORE) && !defined(Py_BUILD_CORE_MODULE)
251
252 #define NUM_KEYWORDS 5
253 static struct {
254 PyGC_Head _this_is_not_used;
255 PyObject_VAR_HEAD
256 PyObject *ob_item[NUM_KEYWORDS];
257 } _kwtuple = {
258 .ob_base = PyVarObject_HEAD_INIT(&PyTuple_Type, NUM_KEYWORDS)
259 .ob_item = { &_Py_ID(a), &_Py_ID(x), &_Py_ID(lo), &_Py_ID(hi), &_Py_ID(key), },
260 };
261 #undef NUM_KEYWORDS
262 #define KWTUPLE (&_kwtuple.ob_base.ob_base)
263
264 #else // !Py_BUILD_CORE
265 # define KWTUPLE NULL
266 #endif // !Py_BUILD_CORE
267
268 static const char * const _keywords[] = {"a", "x", "lo", "hi", "key", NULL};
269 static _PyArg_Parser _parser = {
270 .keywords = _keywords,
271 .fname = "bisect_left",
272 .kwtuple = KWTUPLE,
273 };
274 #undef KWTUPLE
275 PyObject *argsbuf[5];
276 Py_ssize_t noptargs = nargs + (kwnames ? PyTuple_GET_SIZE(kwnames) : 0) - 2;
277 PyObject *a;
278 PyObject *x;
279 Py_ssize_t lo = 0;
280 Py_ssize_t hi = -1;
281 PyObject *key = Py_None;
282 Py_ssize_t _return_value;
283
284 args = _PyArg_UnpackKeywords(args, nargs, NULL, kwnames, &_parser, 2, 4, 0, argsbuf);
285 if (!args) {
286 goto exit;
287 }
288 a = args[0];
289 x = args[1];
290 if (!noptargs) {
291 goto skip_optional_pos;
292 }
293 if (args[2]) {
294 {
295 Py_ssize_t ival = -1;
296 PyObject *iobj = _PyNumber_Index(args[2]);
297 if (iobj != NULL) {
298 ival = PyLong_AsSsize_t(iobj);
299 Py_DECREF(iobj);
300 }
301 if (ival == -1 && PyErr_Occurred()) {
302 goto exit;
303 }
304 lo = ival;
305 }
306 if (!--noptargs) {
307 goto skip_optional_pos;
308 }
309 }
310 if (args[3]) {
311 if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
312 goto exit;
313 }
314 if (!--noptargs) {
315 goto skip_optional_pos;
316 }
317 }
318 skip_optional_pos:
319 if (!noptargs) {
320 goto skip_optional_kwonly;
321 }
322 key = args[4];
323 skip_optional_kwonly:
324 _return_value = _bisect_bisect_left_impl(module, a, x, lo, hi, key);
325 if ((_return_value == -1) && PyErr_Occurred()) {
326 goto exit;
327 }
328 return_value = PyLong_FromSsize_t(_return_value);
329
330 exit:
331 return return_value;
332 }
333
334 PyDoc_STRVAR(_bisect_insort_left__doc__,
335 "insort_left($module, /, a, x, lo=0, hi=None, *, key=None)\n"
336 "--\n"
337 "\n"
338 "Insert item x in list a, and keep it sorted assuming a is sorted.\n"
339 "\n"
340 "If x is already in a, insert it to the left of the leftmost x.\n"
341 "\n"
342 "Optional args lo (default 0) and hi (default len(a)) bound the\n"
343 "slice of a to be searched.\n"
344 "\n"
345 "A custom key function can be supplied to customize the sort order.");
346
347 #define _BISECT_INSORT_LEFT_METHODDEF \
348 {"insort_left", _PyCFunction_CAST(_bisect_insort_left), METH_FASTCALL|METH_KEYWORDS, _bisect_insort_left__doc__},
349
350 static PyObject *
351 _bisect_insort_left_impl(PyObject *module, PyObject *a, PyObject *x,
352 Py_ssize_t lo, Py_ssize_t hi, PyObject *key);
353
354 static PyObject *
355 _bisect_insort_left(PyObject *module, PyObject *const *args, Py_ssize_t nargs, PyObject *kwnames)
356 {
357 PyObject *return_value = NULL;
358 #if defined(Py_BUILD_CORE) && !defined(Py_BUILD_CORE_MODULE)
359
360 #define NUM_KEYWORDS 5
361 static struct {
362 PyGC_Head _this_is_not_used;
363 PyObject_VAR_HEAD
364 PyObject *ob_item[NUM_KEYWORDS];
365 } _kwtuple = {
366 .ob_base = PyVarObject_HEAD_INIT(&PyTuple_Type, NUM_KEYWORDS)
367 .ob_item = { &_Py_ID(a), &_Py_ID(x), &_Py_ID(lo), &_Py_ID(hi), &_Py_ID(key), },
368 };
369 #undef NUM_KEYWORDS
370 #define KWTUPLE (&_kwtuple.ob_base.ob_base)
371
372 #else // !Py_BUILD_CORE
373 # define KWTUPLE NULL
374 #endif // !Py_BUILD_CORE
375
376 static const char * const _keywords[] = {"a", "x", "lo", "hi", "key", NULL};
377 static _PyArg_Parser _parser = {
378 .keywords = _keywords,
379 .fname = "insort_left",
380 .kwtuple = KWTUPLE,
381 };
382 #undef KWTUPLE
383 PyObject *argsbuf[5];
384 Py_ssize_t noptargs = nargs + (kwnames ? PyTuple_GET_SIZE(kwnames) : 0) - 2;
385 PyObject *a;
386 PyObject *x;
387 Py_ssize_t lo = 0;
388 Py_ssize_t hi = -1;
389 PyObject *key = Py_None;
390
391 args = _PyArg_UnpackKeywords(args, nargs, NULL, kwnames, &_parser, 2, 4, 0, argsbuf);
392 if (!args) {
393 goto exit;
394 }
395 a = args[0];
396 x = args[1];
397 if (!noptargs) {
398 goto skip_optional_pos;
399 }
400 if (args[2]) {
401 {
402 Py_ssize_t ival = -1;
403 PyObject *iobj = _PyNumber_Index(args[2]);
404 if (iobj != NULL) {
405 ival = PyLong_AsSsize_t(iobj);
406 Py_DECREF(iobj);
407 }
408 if (ival == -1 && PyErr_Occurred()) {
409 goto exit;
410 }
411 lo = ival;
412 }
413 if (!--noptargs) {
414 goto skip_optional_pos;
415 }
416 }
417 if (args[3]) {
418 if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
419 goto exit;
420 }
421 if (!--noptargs) {
422 goto skip_optional_pos;
423 }
424 }
425 skip_optional_pos:
426 if (!noptargs) {
427 goto skip_optional_kwonly;
428 }
429 key = args[4];
430 skip_optional_kwonly:
431 return_value = _bisect_insort_left_impl(module, a, x, lo, hi, key);
432
433 exit:
434 return return_value;
435 }
436 /*[clinic end generated code: output=5a7fa64bf9b262f3 input=a9049054013a1b77]*/