Mercurial > cpython-lru_cache-weakref

annotate Modules/_bisectmodule.c @ 57303:4aa4c19dfaed legacy-trunk

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
#1757126: fix typo with the cyrillic_asian alias
author Philip Jenvey <pjenvey@underboss.org>
date Tue, 17 Nov 2009 02:42:26 +0000
parents 82ccc7e77ec5
children e38335d4df91 982eec9a8c28
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
1 /* Bisection algorithms. Drop in replacement for bisect.py
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
2
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
3 Converted to C by Dmitry Vasiliev (dima at hlabs.spb.ru).
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
4 */
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
5
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
6 #include "Python.h"
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
7
48064
07b89653145e Finish conversion from int to Py_ssize_t.
Raymond Hettinger <python@rcn.com>
parents: 47919
diff changeset
8 static Py_ssize_t
36518
9f3f87e920a6 Use Py_ssize_t for counts and sizes.
Martin v. Löwis <martin@v.loewis.de>
parents: 35999
diff changeset
9 internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi)
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
10 {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
11 PyObject *litem;
36518
9f3f87e920a6 Use Py_ssize_t for counts and sizes.
Martin v. Löwis <martin@v.loewis.de>
parents: 35999
diff changeset
12 Py_ssize_t mid, res;
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
13
47919
8e7383cbe56e Issue 3301: Bisect functions behaved badly when lo was negative.
Raymond Hettinger <python@rcn.com>
parents: 36684
diff changeset
14 if (lo < 0) {
8e7383cbe56e Issue 3301: Bisect functions behaved badly when lo was negative.
Raymond Hettinger <python@rcn.com>
parents: 36684
diff changeset
15 PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
8e7383cbe56e Issue 3301: Bisect functions behaved badly when lo was negative.
Raymond Hettinger <python@rcn.com>
parents: 36684
diff changeset
16 return -1;
8e7383cbe56e Issue 3301: Bisect functions behaved badly when lo was negative.
Raymond Hettinger <python@rcn.com>
parents: 36684
diff changeset
17 }
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
18 if (hi == -1) {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
19 hi = PySequence_Size(list);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
20 if (hi < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
21 return -1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
22 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
23 while (lo < hi) {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
24 mid = (lo + hi) / 2;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
25 litem = PySequence_GetItem(list, mid);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
26 if (litem == NULL)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
27 return -1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
28 res = PyObject_RichCompareBool(item, litem, Py_LT);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
29 Py_DECREF(litem);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
30 if (res < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
31 return -1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
32 if (res)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
33 hi = mid;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
34 else
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
35 lo = mid + 1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
36 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
37 return lo;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
38 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
39
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
40 static PyObject *
35699
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 32898
diff changeset
41 bisect_right(PyObject *self, PyObject *args, PyObject *kw)
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
42 {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
43 PyObject *list, *item;
48064
07b89653145e Finish conversion from int to Py_ssize_t.
Raymond Hettinger <python@rcn.com>
parents: 47919
diff changeset
44 Py_ssize_t lo = 0;
07b89653145e Finish conversion from int to Py_ssize_t.
Raymond Hettinger <python@rcn.com>
parents: 47919
diff changeset
45 Py_ssize_t hi = -1;
07b89653145e Finish conversion from int to Py_ssize_t.
Raymond Hettinger <python@rcn.com>
parents: 47919
diff changeset
46 Py_ssize_t index;
36684
0bebeb393045 More unconsting.
Martin v. Löwis <martin@v.loewis.de>
parents: 36518
diff changeset
47 static char *keywords[] = {"a", "x", "lo", "hi", NULL};
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
48
48064
07b89653145e Finish conversion from int to Py_ssize_t.
Raymond Hettinger <python@rcn.com>
parents: 47919
diff changeset
49 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:bisect_right",
35699
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 32898
diff changeset
50 keywords, &list, &item, &lo, &hi))
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
51 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
52 index = internal_bisect_right(list, item, lo, hi);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
53 if (index < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
54 return NULL;
48064
07b89653145e Finish conversion from int to Py_ssize_t.
Raymond Hettinger <python@rcn.com>
parents: 47919
diff changeset
55 return PyInt_FromSsize_t(index);
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
56 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
57
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
58 PyDoc_STRVAR(bisect_right_doc,
35699
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 32898
diff changeset
59 "bisect_right(a, x[, lo[, hi]]) -> index\n\
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
60 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
61 Return the index where to insert item x in list a, assuming a is sorted.\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
62 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
63 The return value i is such that all e in a[:i] have e <= x, and all e in\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
64 a[i:] have e > x. So if x already appears in the list, i points just\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
65 beyond the rightmost x already there\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
66 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
67 Optional args lo (default 0) and hi (default len(a)) bound the\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
68 slice of a to be searched.\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
69
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
70 static PyObject *
35699
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 32898
diff changeset
71 insort_right(PyObject *self, PyObject *args, PyObject *kw)
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
72 {
32898
daec2d311def Any call to insort_{left,right} with a non-list leaked a reference to None
Michael W. Hudson <mwh@python.net>
parents: 31353
diff changeset
73 PyObject *list, *item, *result;
48064
07b89653145e Finish conversion from int to Py_ssize_t.
Raymond Hettinger <python@rcn.com>
parents: 47919
diff changeset
74 Py_ssize_t lo = 0;
07b89653145e Finish conversion from int to Py_ssize_t.
Raymond Hettinger <python@rcn.com>
parents: 47919
diff changeset
75 Py_ssize_t hi = -1;
07b89653145e Finish conversion from int to Py_ssize_t.
Raymond Hettinger <python@rcn.com>
parents: 47919
diff changeset
76 Py_ssize_t index;
36684
0bebeb393045 More unconsting.
Martin v. Löwis <martin@v.loewis.de>
parents: 36518
diff changeset
77 static char *keywords[] = {"a", "x", "lo", "hi", NULL};
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
78
48064
07b89653145e Finish conversion from int to Py_ssize_t.
Raymond Hettinger <python@rcn.com>
parents: 47919
diff changeset
79 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:insort_right",
35699
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 32898
diff changeset
80 keywords, &list, &item, &lo, &hi))
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
81 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
82 index = internal_bisect_right(list, item, lo, hi);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
83 if (index < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
84 return NULL;
49677
82ccc7e77ec5 Merged revisions 66801,66803-66804,66813,66854-66856,66866,66870-66872,66874,66887,66903,66905,66911,66913,66927,66932,66938,66942,66962,66964,66973-66974,66977,66992,66998-66999,67002,67005,67007,67028,67040-67041,67044,67070,67089,67091,67101,67117-67119,67123-67124 via svnmerge from
Georg Brandl <georg@python.org>
parents: 48064
diff changeset
85 if (PyList_CheckExact(list)) {
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
86 if (PyList_Insert(list, index, item) < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
87 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
88 } else {
48064
07b89653145e Finish conversion from int to Py_ssize_t.
Raymond Hettinger <python@rcn.com>
parents: 47919
diff changeset
89 result = PyObject_CallMethod(list, "insert", "nO",
32898
daec2d311def Any call to insort_{left,right} with a non-list leaked a reference to None
Michael W. Hudson <mwh@python.net>
parents: 31353
diff changeset
90 index, item);
daec2d311def Any call to insort_{left,right} with a non-list leaked a reference to None
Michael W. Hudson <mwh@python.net>
parents: 31353
diff changeset
91 if (result == NULL)
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
92 return NULL;
32898
daec2d311def Any call to insort_{left,right} with a non-list leaked a reference to None
Michael W. Hudson <mwh@python.net>
parents: 31353
diff changeset
93 Py_DECREF(result);
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
94 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
95
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
96 Py_RETURN_NONE;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
97 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
98
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
99 PyDoc_STRVAR(insort_right_doc,
35699
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 32898
diff changeset
100 "insort_right(a, x[, lo[, hi]])\n\
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
101 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
102 Insert item x in list a, and keep it sorted assuming a is sorted.\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
103 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
104 If x is already in a, insert it to the right of the rightmost x.\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
105 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
106 Optional args lo (default 0) and hi (default len(a)) bound the\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
107 slice of a to be searched.\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
108
48064
07b89653145e Finish conversion from int to Py_ssize_t.
Raymond Hettinger <python@rcn.com>
parents: 47919
diff changeset
109 static Py_ssize_t
07b89653145e Finish conversion from int to Py_ssize_t.
Raymond Hettinger <python@rcn.com>
parents: 47919
diff changeset
110 internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi)
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
111 {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
112 PyObject *litem;
48064
07b89653145e Finish conversion from int to Py_ssize_t.
Raymond Hettinger <python@rcn.com>
parents: 47919
diff changeset
113 Py_ssize_t mid, res;
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
114
47919
8e7383cbe56e Issue 3301: Bisect functions behaved badly when lo was negative.
Raymond Hettinger <python@rcn.com>
parents: 36684
diff changeset
115 if (lo < 0) {
8e7383cbe56e Issue 3301: Bisect functions behaved badly when lo was negative.
Raymond Hettinger <python@rcn.com>
parents: 36684
diff changeset
116 PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
8e7383cbe56e Issue 3301: Bisect functions behaved badly when lo was negative.
Raymond Hettinger <python@rcn.com>
parents: 36684
diff changeset
117 return -1;
8e7383cbe56e Issue 3301: Bisect functions behaved badly when lo was negative.
Raymond Hettinger <python@rcn.com>
parents: 36684
diff changeset
118 }
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
119 if (hi == -1) {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
120 hi = PySequence_Size(list);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
121 if (hi < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
122 return -1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
123 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
124 while (lo < hi) {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
125 mid = (lo + hi) / 2;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
126 litem = PySequence_GetItem(list, mid);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
127 if (litem == NULL)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
128 return -1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
129 res = PyObject_RichCompareBool(litem, item, Py_LT);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
130 Py_DECREF(litem);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
131 if (res < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
132 return -1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
133 if (res)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
134 lo = mid + 1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
135 else
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
136 hi = mid;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
137 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
138 return lo;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
139 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
140
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
141 static PyObject *
35699
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 32898
diff changeset
142 bisect_left(PyObject *self, PyObject *args, PyObject *kw)
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
143 {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
144 PyObject *list, *item;
48064
07b89653145e Finish conversion from int to Py_ssize_t.
Raymond Hettinger <python@rcn.com>
parents: 47919
diff changeset
145 Py_ssize_t lo = 0;
07b89653145e Finish conversion from int to Py_ssize_t.
Raymond Hettinger <python@rcn.com>
parents: 47919
diff changeset
146 Py_ssize_t hi = -1;
07b89653145e Finish conversion from int to Py_ssize_t.
Raymond Hettinger <python@rcn.com>
parents: 47919
diff changeset
147 Py_ssize_t index;
36684
0bebeb393045 More unconsting.
Martin v. Löwis <martin@v.loewis.de>
parents: 36518
diff changeset
148 static char *keywords[] = {"a", "x", "lo", "hi", NULL};
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
149
48064
07b89653145e Finish conversion from int to Py_ssize_t.
Raymond Hettinger <python@rcn.com>
parents: 47919
diff changeset
150 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:bisect_left",
35699
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 32898
diff changeset
151 keywords, &list, &item, &lo, &hi))
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
152 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
153 index = internal_bisect_left(list, item, lo, hi);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
154 if (index < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
155 return NULL;
48064
07b89653145e Finish conversion from int to Py_ssize_t.
Raymond Hettinger <python@rcn.com>
parents: 47919
diff changeset
156 return PyInt_FromSsize_t(index);
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
157 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
158
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
159 PyDoc_STRVAR(bisect_left_doc,
35699
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 32898
diff changeset
160 "bisect_left(a, x[, lo[, hi]]) -> index\n\
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
161 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
162 Return the index where to insert item x in list a, assuming a is sorted.\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
163 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
164 The return value i is such that all e in a[:i] have e < x, and all e in\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
165 a[i:] have e >= x. So if x already appears in the list, i points just\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
166 before the leftmost x already there.\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
167 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
168 Optional args lo (default 0) and hi (default len(a)) bound the\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
169 slice of a to be searched.\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
170
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
171 static PyObject *
35699
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 32898
diff changeset
172 insort_left(PyObject *self, PyObject *args, PyObject *kw)
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
173 {
32898
daec2d311def Any call to insort_{left,right} with a non-list leaked a reference to None
Michael W. Hudson <mwh@python.net>
parents: 31353
diff changeset
174 PyObject *list, *item, *result;
48064
07b89653145e Finish conversion from int to Py_ssize_t.
Raymond Hettinger <python@rcn.com>
parents: 47919
diff changeset
175 Py_ssize_t lo = 0;
07b89653145e Finish conversion from int to Py_ssize_t.
Raymond Hettinger <python@rcn.com>
parents: 47919
diff changeset
176 Py_ssize_t hi = -1;
07b89653145e Finish conversion from int to Py_ssize_t.
Raymond Hettinger <python@rcn.com>
parents: 47919
diff changeset
177 Py_ssize_t index;
36684
0bebeb393045 More unconsting.
Martin v. Löwis <martin@v.loewis.de>
parents: 36518
diff changeset
178 static char *keywords[] = {"a", "x", "lo", "hi", NULL};
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
179
48064
07b89653145e Finish conversion from int to Py_ssize_t.
Raymond Hettinger <python@rcn.com>
parents: 47919
diff changeset
180 if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn:insort_left",
35699
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 32898
diff changeset
181 keywords, &list, &item, &lo, &hi))
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
182 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
183 index = internal_bisect_left(list, item, lo, hi);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
184 if (index < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
185 return NULL;
49677
82ccc7e77ec5 Merged revisions 66801,66803-66804,66813,66854-66856,66866,66870-66872,66874,66887,66903,66905,66911,66913,66927,66932,66938,66942,66962,66964,66973-66974,66977,66992,66998-66999,67002,67005,67007,67028,67040-67041,67044,67070,67089,67091,67101,67117-67119,67123-67124 via svnmerge from
Georg Brandl <georg@python.org>
parents: 48064
diff changeset
186 if (PyList_CheckExact(list)) {
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
187 if (PyList_Insert(list, index, item) < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
188 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
189 } else {
32898
daec2d311def Any call to insort_{left,right} with a non-list leaked a reference to None
Michael W. Hudson <mwh@python.net>
parents: 31353
diff changeset
190 result = PyObject_CallMethod(list, "insert", "iO",
daec2d311def Any call to insort_{left,right} with a non-list leaked a reference to None
Michael W. Hudson <mwh@python.net>
parents: 31353
diff changeset
191 index, item);
daec2d311def Any call to insort_{left,right} with a non-list leaked a reference to None
Michael W. Hudson <mwh@python.net>
parents: 31353
diff changeset
192 if (result == NULL)
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
193 return NULL;
32898
daec2d311def Any call to insort_{left,right} with a non-list leaked a reference to None
Michael W. Hudson <mwh@python.net>
parents: 31353
diff changeset
194 Py_DECREF(result);
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
195 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
196
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
197 Py_RETURN_NONE;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
198 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
199
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
200 PyDoc_STRVAR(insort_left_doc,
35699
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 32898
diff changeset
201 "insort_left(a, x[, lo[, hi]])\n\
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
202 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
203 Insert item x in list a, and keep it sorted assuming a is sorted.\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
204 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
205 If x is already in a, insert it to the left of the leftmost x.\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
206 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
207 Optional args lo (default 0) and hi (default len(a)) bound the\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
208 slice of a to be searched.\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
209
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
210 PyDoc_STRVAR(bisect_doc, "Alias for bisect_right().\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
211 PyDoc_STRVAR(insort_doc, "Alias for insort_right().\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
212
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
213 static PyMethodDef bisect_methods[] = {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
214 {"bisect_right", (PyCFunction)bisect_right,
35699
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 32898
diff changeset
215 METH_VARARGS|METH_KEYWORDS, bisect_right_doc},
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
216 {"bisect", (PyCFunction)bisect_right,
35699
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 32898
diff changeset
217 METH_VARARGS|METH_KEYWORDS, bisect_doc},
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
218 {"insort_right", (PyCFunction)insort_right,
35699
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 32898
diff changeset
219 METH_VARARGS|METH_KEYWORDS, insort_right_doc},
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
220 {"insort", (PyCFunction)insort_right,
35699
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 32898
diff changeset
221 METH_VARARGS|METH_KEYWORDS, insort_doc},
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
222 {"bisect_left", (PyCFunction)bisect_left,
35699
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 32898
diff changeset
223 METH_VARARGS|METH_KEYWORDS, bisect_left_doc},
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
224 {"insort_left", (PyCFunction)insort_left,
35699
3572249c1e77 SF #1313496: bisect C replacement doesn't accept named args
Raymond Hettinger <python@rcn.com>
parents: 32898
diff changeset
225 METH_VARARGS|METH_KEYWORDS, insort_left_doc},
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
226 {NULL, NULL} /* sentinel */
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
227 };
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
228
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
229 PyDoc_STRVAR(module_doc,
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
230 "Bisection algorithms.\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
231 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
232 This module provides support for maintaining a list in sorted order without\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
233 having to sort the list after each insertion. For long lists of items with\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
234 expensive comparison operations, this can be an improvement over the more\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
235 common approach.\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
236
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
237 PyMODINIT_FUNC
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
238 init_bisect(void)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
239 {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
240 PyObject *m;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
241
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
242 m = Py_InitModule3("_bisect", bisect_methods, module_doc);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
243 }