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