Mercurial > cpython-lru_cache-weakref

annotate Modules/_bisectmodule.c @ 31965:ef34dec004cd legacy-trunk

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Stacks based on lists work better and read more clearly when they grow and shrink on the right.
author Raymond Hettinger <python@rcn.com>
date Tue, 04 May 2004 08:21:52 +0000
parents ed20259a1ea5
children daec2d311def
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 {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
68 PyObject *list, *item;
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 {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
83 if (PyObject_CallMethod(list, "insert", "iO", index, item)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
84 == NULL)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
85 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
86 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
87
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
88 Py_RETURN_NONE;
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
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
91 PyDoc_STRVAR(insort_right_doc,
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
92 "insort_right(list, item[, lo[, hi]])\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
93 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
94 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
95 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
96 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
97 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
98 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
99 slice of a to be searched.\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
100
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
101 static int
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
102 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
103 {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
104 PyObject *litem;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
105 int mid, res;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
106
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
107 if (hi == -1) {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
108 hi = PySequence_Size(list);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
109 if (hi < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
110 return -1;
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 while (lo < hi) {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
113 mid = (lo + hi) / 2;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
114 litem = PySequence_GetItem(list, mid);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
115 if (litem == NULL)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
116 return -1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
117 res = PyObject_RichCompareBool(litem, item, Py_LT);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
118 Py_DECREF(litem);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
119 if (res < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
120 return -1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
121 if (res)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
122 lo = mid + 1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
123 else
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
124 hi = mid;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
125 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
126 return lo;
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
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
129 static PyObject *
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
130 bisect_left(PyObject *self, PyObject *args)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
131 {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
132 PyObject *list, *item;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
133 int lo = 0;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
134 int hi = -1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
135 int index;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
136
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
137 if (!PyArg_ParseTuple(args, "OO|ii:bisect_left",
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
138 &list, &item, &lo, &hi))
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
139 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
140 index = internal_bisect_left(list, item, lo, hi);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
141 if (index < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
142 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
143 return PyInt_FromLong(index);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
144 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
145
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
146 PyDoc_STRVAR(bisect_left_doc,
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
147 "bisect_left(list, item[, lo[, hi]]) -> index\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
148 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
149 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
150 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
151 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
152 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
153 before the leftmost x already there.\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
154 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
155 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
156 slice of a to be searched.\n");
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 static PyObject *
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
159 insort_left(PyObject *self, PyObject *args)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
160 {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
161 PyObject *list, *item;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
162 int lo = 0;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
163 int hi = -1;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
164 int index;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
165
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
166 if (!PyArg_ParseTuple(args, "OO|ii:insort_left",
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
167 &list, &item, &lo, &hi))
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
168 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
169 index = internal_bisect_left(list, item, lo, hi);
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
170 if (index < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
171 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
172 if (PyList_Check(list)) {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
173 if (PyList_Insert(list, index, item) < 0)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
174 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
175 } else {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
176 if (PyObject_CallMethod(list, "insert", "iO", index, item)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
177 == NULL)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
178 return NULL;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
179 }
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
180
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
181 Py_RETURN_NONE;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
182 }
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 PyDoc_STRVAR(insort_left_doc,
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
185 "insort_left(list, item[, lo[, hi]])\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
186 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
187 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
188 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
189 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
190 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
191 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
192 slice of a to be searched.\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
193
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
194 PyDoc_STRVAR(bisect_doc, "Alias for bisect_right().\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
195 PyDoc_STRVAR(insort_doc, "Alias for insort_right().\n");
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 static PyMethodDef bisect_methods[] = {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
198 {"bisect_right", (PyCFunction)bisect_right,
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
199 METH_VARARGS, bisect_right_doc},
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
200 {"bisect", (PyCFunction)bisect_right,
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
201 METH_VARARGS, bisect_doc},
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
202 {"insort_right", (PyCFunction)insort_right,
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
203 METH_VARARGS, insort_right_doc},
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
204 {"insort", (PyCFunction)insort_right,
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
205 METH_VARARGS, insort_doc},
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
206 {"bisect_left", (PyCFunction)bisect_left,
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
207 METH_VARARGS, bisect_left_doc},
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
208 {"insort_left", (PyCFunction)insort_left,
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
209 METH_VARARGS, insort_left_doc},
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
210 {NULL, NULL} /* sentinel */
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
211 };
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 PyDoc_STRVAR(module_doc,
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
214 "Bisection algorithms.\n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
215 \n\
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
216 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
217 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
218 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
219 common approach.\n");
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
220
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
221 PyMODINIT_FUNC
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
222 init_bisect(void)
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
223 {
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
224 PyObject *m;
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
225
ed20259a1ea5 SF Patch #864863: Bisect C implementation
Raymond Hettinger <python@rcn.com>
parents:
diff changeset
226 m = Py_InitModule3("_bisect", bisect_methods, module_doc);
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