Mercurial > cpython-lru_cache-weakref

annotate Modules/_bisectmodule.c @ 34161:ca2ca1aeb080 2.4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Check in missing png version of pyfav.gif.
author Johannes Gijsbers <jlg@dds.nl>
date Mon, 13 Dec 2004 13:11:42 +0000
parents daec2d311def
children 3572249c1e77
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
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
8 static int
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
9 internal_bisect_right(PyObject *list, PyObject *item, int lo, int hi)
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;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
12 int mid, res;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
13
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
14 if (hi == -1) {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
15 hi = PySequence_Size(list);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
16 if (hi < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
17 return -1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
18 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
19 while (lo < hi) {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
20 mid = (lo + hi) / 2;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
21 litem = PySequence_GetItem(list, mid);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
22 if (litem == NULL)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
23 return -1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
24 res = PyObject_RichCompareBool(item, litem, Py_LT);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
25 Py_DECREF(litem);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
26 if (res < 0)
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 if (res)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
29 hi = mid;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
30 else
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
31 lo = mid + 1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
32 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
33 return lo;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
34 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
35
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
36 static PyObject *
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
37 bisect_right(PyObject *self, PyObject *args)
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 PyObject *list, *item;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
40 int lo = 0;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
41 int hi = -1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
42 int index;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
43
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
44 if (!PyArg_ParseTuple(args, "OO|ii:bisect_right",
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
45 &list, &item, &lo, &hi))
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
46 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
47 index = internal_bisect_right(list, item, lo, hi);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
48 if (index < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
49 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
50 return PyInt_FromLong(index);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
51 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
52
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
53 PyDoc_STRVAR(bisect_right_doc,
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
54 "bisect_right(list, item[, lo[, hi]]) -> index\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
55 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
56 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
57 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
58 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
59 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
60 beyond the rightmost x already there\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
61 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
62 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
63 slice of a to be searched.\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
64
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
65 static PyObject *
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
66 insort_right(PyObject *self, PyObject *args)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
67 {
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
68 PyObject *list, *item, *result;
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
69 int lo = 0;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
70 int hi = -1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
71 int index;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
72
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
73 if (!PyArg_ParseTuple(args, "OO|ii:insort_right",
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
74 &list, &item, &lo, &hi))
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
75 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
76 index = internal_bisect_right(list, item, lo, hi);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
77 if (index < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
78 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
79 if (PyList_Check(list)) {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
80 if (PyList_Insert(list, index, item) < 0)
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 } 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
83 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
84 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
85 if (result == NULL)
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
86 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
87 Py_DECREF(result);
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
88 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
89
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
90 Py_RETURN_NONE;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
91 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
92
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
93 PyDoc_STRVAR(insort_right_doc,
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
94 "insort_right(list, item[, lo[, hi]])\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
95 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
96 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
97 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
98 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
99 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
100 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
101 slice of a to be searched.\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
102
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
103 static int
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
104 internal_bisect_left(PyObject *list, PyObject *item, int lo, int hi)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
105 {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
106 PyObject *litem;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
107 int mid, res;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
108
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
109 if (hi == -1) {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
110 hi = PySequence_Size(list);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
111 if (hi < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
112 return -1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
113 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
114 while (lo < hi) {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
115 mid = (lo + hi) / 2;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
116 litem = PySequence_GetItem(list, mid);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
117 if (litem == NULL)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
118 return -1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
119 res = PyObject_RichCompareBool(litem, item, Py_LT);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
120 Py_DECREF(litem);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
121 if (res < 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 if (res)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
124 lo = mid + 1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
125 else
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
126 hi = mid;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
127 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
128 return lo;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
129 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
130
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
131 static PyObject *
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
132 bisect_left(PyObject *self, PyObject *args)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
133 {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
134 PyObject *list, *item;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
135 int lo = 0;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
136 int hi = -1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
137 int index;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
138
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
139 if (!PyArg_ParseTuple(args, "OO|ii:bisect_left",
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
140 &list, &item, &lo, &hi))
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
141 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
142 index = internal_bisect_left(list, item, lo, hi);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
143 if (index < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
144 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
145 return PyInt_FromLong(index);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
146 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
147
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
148 PyDoc_STRVAR(bisect_left_doc,
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
149 "bisect_left(list, item[, lo[, hi]]) -> index\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
150 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
151 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
152 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
153 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
154 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
155 before the leftmost x already there.\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
156 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
157 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
158 slice of a to be searched.\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
159
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
160 static PyObject *
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
161 insort_left(PyObject *self, PyObject *args)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
162 {
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
163 PyObject *list, *item, *result;
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
164 int lo = 0;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
165 int hi = -1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
166 int index;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
167
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
168 if (!PyArg_ParseTuple(args, "OO|ii:insort_left",
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
169 &list, &item, &lo, &hi))
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
170 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
171 index = internal_bisect_left(list, item, lo, hi);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
172 if (index < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
173 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
174 if (PyList_Check(list)) {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
175 if (PyList_Insert(list, index, item) < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
176 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
177 } 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
178 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
179 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
180 if (result == NULL)
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
181 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
182 Py_DECREF(result);
31353
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
183 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
184
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
185 Py_RETURN_NONE;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
186 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
187
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
188 PyDoc_STRVAR(insort_left_doc,
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
189 "insort_left(list, item[, lo[, hi]])\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
190 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
191 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
192 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
193 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
194 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
195 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
196 slice of a to be searched.\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
197
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
198 PyDoc_STRVAR(bisect_doc, "Alias for bisect_right().\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
199 PyDoc_STRVAR(insort_doc, "Alias for insort_right().\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
200
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
201 static PyMethodDef bisect_methods[] = {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
202 {"bisect_right", (PyCFunction)bisect_right,
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
203 METH_VARARGS, bisect_right_doc},
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
204 {"bisect", (PyCFunction)bisect_right,
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
205 METH_VARARGS, bisect_doc},
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
206 {"insort_right", (PyCFunction)insort_right,
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
207 METH_VARARGS, insort_right_doc},
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
208 {"insort", (PyCFunction)insort_right,
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
209 METH_VARARGS, insort_doc},
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
210 {"bisect_left", (PyCFunction)bisect_left,
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
211 METH_VARARGS, bisect_left_doc},
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
212 {"insort_left", (PyCFunction)insort_left,
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
213 METH_VARARGS, insort_left_doc},
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
214 {NULL, NULL} /* sentinel */
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
215 };
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
216
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
217 PyDoc_STRVAR(module_doc,
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
218 "Bisection algorithms.\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
219 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
220 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
221 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
222 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
223 common approach.\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
224
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
225 PyMODINIT_FUNC
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
226 init_bisect(void)
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 PyObject *m;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
229
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
230 m = Py_InitModule3("_bisect", bisect_methods, module_doc);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
231 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
232