Mercurial > cpython-lru_cache-weakref

annotate Modules/_heapqmodule.c @ 79691:05c8928362ee

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merge __next__ method link fixes with 3.3.
author Ezio Melotti <ezio.melotti@gmail.com>
date Fri, 12 Oct 2012 13:46:37 +0300
parents 3c36849f0639
children 905b02749c26 6f0eb0e3820c
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
1 /* Drop in replacement for heapq.py
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
2
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
3 C implementation derived directly from heapq.py in Py2.3
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
4 which was written by Kevin O'Connor, augmented by Tim Peters,
64410
524b444a8095 Fix invalid bytes for UTF-8
Éric Araujo <merwok@netwok.org>
parents: 61466
diff changeset
5 annotated by François Pinard, and converted to C by Raymond Hettinger.
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
6
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
7 */
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
8
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
9 #include "Python.h"
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
10
47559
2925b568aacc Merged revisions 63562,63570,63728,63734,63784,63788,63802,63817,63827,63839,63887,63975,63998 via svnmerge from
Georg Brandl <georg@python.org>
parents: 45773
diff changeset
11 static int
36518
9f3f87e920a6 Use Py_ssize_t for counts and sizes.
Martin v. Löwis <martin@v.loewis.de>
parents: 36324
diff changeset
12 _siftdown(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos)
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
13 {
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
14 PyObject *newitem, *parent;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
15 int cmp;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
16 Py_ssize_t parentpos;
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
17
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
18 assert(PyList_Check(heap));
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
19 if (pos >= PyList_GET_SIZE(heap)) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
20 PyErr_SetString(PyExc_IndexError, "index out of range");
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
21 return -1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
22 }
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
23
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
24 newitem = PyList_GET_ITEM(heap, pos);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
25 Py_INCREF(newitem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
26 /* Follow the path to the root, moving parents down until finding
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
27 a place newitem fits. */
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
28 while (pos > startpos){
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
29 parentpos = (pos - 1) >> 1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
30 parent = PyList_GET_ITEM(heap, parentpos);
64454
3c36849f0639 Inline cmp_lt().
Raymond Hettinger <python@rcn.com>
parents: 64410
diff changeset
31 cmp = PyObject_RichCompareBool(newitem, parent, Py_LT);
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
32 if (cmp == -1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
33 Py_DECREF(newitem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
34 return -1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
35 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
36 if (cmp == 0)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
37 break;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
38 Py_INCREF(parent);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
39 Py_DECREF(PyList_GET_ITEM(heap, pos));
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
40 PyList_SET_ITEM(heap, pos, parent);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
41 pos = parentpos;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
42 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
43 Py_DECREF(PyList_GET_ITEM(heap, pos));
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
44 PyList_SET_ITEM(heap, pos, newitem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
45 return 0;
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
46 }
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
47
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
48 static int
36518
9f3f87e920a6 Use Py_ssize_t for counts and sizes.
Martin v. Löwis <martin@v.loewis.de>
parents: 36324
diff changeset
49 _siftup(PyListObject *heap, Py_ssize_t pos)
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
50 {
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
51 Py_ssize_t startpos, endpos, childpos, rightpos;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
52 int cmp;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
53 PyObject *newitem, *tmp;
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
54
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
55 assert(PyList_Check(heap));
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
56 endpos = PyList_GET_SIZE(heap);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
57 startpos = pos;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
58 if (pos >= endpos) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
59 PyErr_SetString(PyExc_IndexError, "index out of range");
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
60 return -1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
61 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
62 newitem = PyList_GET_ITEM(heap, pos);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
63 Py_INCREF(newitem);
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
64
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
65 /* Bubble up the smaller child until hitting a leaf. */
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
66 childpos = 2*pos + 1; /* leftmost child position */
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
67 while (childpos < endpos) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
68 /* Set childpos to index of smaller child. */
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
69 rightpos = childpos + 1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
70 if (rightpos < endpos) {
64454
3c36849f0639 Inline cmp_lt().
Raymond Hettinger <python@rcn.com>
parents: 64410
diff changeset
71 cmp = PyObject_RichCompareBool(
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
72 PyList_GET_ITEM(heap, childpos),
64454
3c36849f0639 Inline cmp_lt().
Raymond Hettinger <python@rcn.com>
parents: 64410
diff changeset
73 PyList_GET_ITEM(heap, rightpos),
3c36849f0639 Inline cmp_lt().
Raymond Hettinger <python@rcn.com>
parents: 64410
diff changeset
74 Py_LT);
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
75 if (cmp == -1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
76 Py_DECREF(newitem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
77 return -1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
78 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
79 if (cmp == 0)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
80 childpos = rightpos;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
81 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
82 /* Move the smaller child up. */
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
83 tmp = PyList_GET_ITEM(heap, childpos);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
84 Py_INCREF(tmp);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
85 Py_DECREF(PyList_GET_ITEM(heap, pos));
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
86 PyList_SET_ITEM(heap, pos, tmp);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
87 pos = childpos;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
88 childpos = 2*pos + 1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
89 }
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
90
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
91 /* The leaf at pos is empty now. Put newitem there, and and bubble
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
92 it up to its final resting place (by sifting its parents down). */
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
93 Py_DECREF(PyList_GET_ITEM(heap, pos));
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
94 PyList_SET_ITEM(heap, pos, newitem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
95 return _siftdown(heap, startpos, pos);
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
96 }
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
97
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
98 static PyObject *
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
99 heappush(PyObject *self, PyObject *args)
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
100 {
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
101 PyObject *heap, *item;
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
102
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
103 if (!PyArg_UnpackTuple(args, "heappush", 2, 2, &heap, &item))
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
104 return NULL;
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
105
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
106 if (!PyList_Check(heap)) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
107 PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
108 return NULL;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
109 }
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
110
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
111 if (PyList_Append(heap, item) == -1)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
112 return NULL;
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
113
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
114 if (_siftdown((PyListObject *)heap, 0, PyList_GET_SIZE(heap)-1) == -1)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
115 return NULL;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
116 Py_INCREF(Py_None);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
117 return Py_None;
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
118 }
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
119
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
120 PyDoc_STRVAR(heappush_doc,
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
121 "Push item onto heap, maintaining the heap invariant.");
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
122
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
123 static PyObject *
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
124 heappop(PyObject *self, PyObject *heap)
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
125 {
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
126 PyObject *lastelt, *returnitem;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
127 Py_ssize_t n;
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
128
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
129 if (!PyList_Check(heap)) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
130 PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
131 return NULL;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
132 }
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
133
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
134 /* # raises appropriate IndexError if heap is empty */
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
135 n = PyList_GET_SIZE(heap);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
136 if (n == 0) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
137 PyErr_SetString(PyExc_IndexError, "index out of range");
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
138 return NULL;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
139 }
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
140
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
141 lastelt = PyList_GET_ITEM(heap, n-1) ;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
142 Py_INCREF(lastelt);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
143 PyList_SetSlice(heap, n-1, n, NULL);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
144 n--;
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
145
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
146 if (!n)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
147 return lastelt;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
148 returnitem = PyList_GET_ITEM(heap, 0);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
149 PyList_SET_ITEM(heap, 0, lastelt);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
150 if (_siftup((PyListObject *)heap, 0) == -1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
151 Py_DECREF(returnitem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
152 return NULL;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
153 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
154 return returnitem;
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
155 }
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
156
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
157 PyDoc_STRVAR(heappop_doc,
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
158 "Pop the smallest item off the heap, maintaining the heap invariant.");
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
159
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
160 static PyObject *
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
161 heapreplace(PyObject *self, PyObject *args)
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
162 {
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
163 PyObject *heap, *item, *returnitem;
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
164
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
165 if (!PyArg_UnpackTuple(args, "heapreplace", 2, 2, &heap, &item))
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
166 return NULL;
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
167
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
168 if (!PyList_Check(heap)) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
169 PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
170 return NULL;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
171 }
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
172
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
173 if (PyList_GET_SIZE(heap) < 1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
174 PyErr_SetString(PyExc_IndexError, "index out of range");
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
175 return NULL;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
176 }
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
177
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
178 returnitem = PyList_GET_ITEM(heap, 0);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
179 Py_INCREF(item);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
180 PyList_SET_ITEM(heap, 0, item);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
181 if (_siftup((PyListObject *)heap, 0) == -1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
182 Py_DECREF(returnitem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
183 return NULL;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
184 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
185 return returnitem;
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
186 }
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
187
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
188 PyDoc_STRVAR(heapreplace_doc,
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
189 "Pop and return the current smallest value, and add the new item.\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
190 \n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
191 This is more efficient than heappop() followed by heappush(), and can be\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
192 more appropriate when using a fixed-size heap. Note that the value\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
193 returned may be larger than item! That constrains reasonable uses of\n\
33415
dc97f581f233 Fix erroneous docstring comment.
Raymond Hettinger <python@rcn.com>
parents: 32390
diff changeset
194 this routine unless written as part of a conditional replacement:\n\n\
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
195 if item > heap[0]:\n\
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
196 item = heapreplace(heap, item)\n");
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
197
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
198 static PyObject *
45773
832c820e9d14 Merged revisions 61239-61249,61252-61257,61260-61264,61269-61275,61278-61279,61285-61286,61288-61290,61298,61303-61305,61312-61314,61317,61329,61332,61344,61350-61351,61363-61376,61378-61379,61382-61383,61387-61388,61392,61395-61396,61402-61403 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 42757
diff changeset
199 heappushpop(PyObject *self, PyObject *args)
832c820e9d14 Merged revisions 61239-61249,61252-61257,61260-61264,61269-61275,61278-61279,61285-61286,61288-61290,61298,61303-61305,61312-61314,61317,61329,61332,61344,61350-61351,61363-61376,61378-61379,61382-61383,61387-61388,61392,61395-61396,61402-61403 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 42757
diff changeset
200 {
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
201 PyObject *heap, *item, *returnitem;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
202 int cmp;
45773
832c820e9d14 Merged revisions 61239-61249,61252-61257,61260-61264,61269-61275,61278-61279,61285-61286,61288-61290,61298,61303-61305,61312-61314,61317,61329,61332,61344,61350-61351,61363-61376,61378-61379,61382-61383,61387-61388,61392,61395-61396,61402-61403 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 42757
diff changeset
203
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
204 if (!PyArg_UnpackTuple(args, "heappushpop", 2, 2, &heap, &item))
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
205 return NULL;
45773
832c820e9d14 Merged revisions 61239-61249,61252-61257,61260-61264,61269-61275,61278-61279,61285-61286,61288-61290,61298,61303-61305,61312-61314,61317,61329,61332,61344,61350-61351,61363-61376,61378-61379,61382-61383,61387-61388,61392,61395-61396,61402-61403 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 42757
diff changeset
206
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
207 if (!PyList_Check(heap)) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
208 PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
209 return NULL;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
210 }
45773
832c820e9d14 Merged revisions 61239-61249,61252-61257,61260-61264,61269-61275,61278-61279,61285-61286,61288-61290,61298,61303-61305,61312-61314,61317,61329,61332,61344,61350-61351,61363-61376,61378-61379,61382-61383,61387-61388,61392,61395-61396,61402-61403 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 42757
diff changeset
211
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
212 if (PyList_GET_SIZE(heap) < 1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
213 Py_INCREF(item);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
214 return item;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
215 }
45773
832c820e9d14 Merged revisions 61239-61249,61252-61257,61260-61264,61269-61275,61278-61279,61285-61286,61288-61290,61298,61303-61305,61312-61314,61317,61329,61332,61344,61350-61351,61363-61376,61378-61379,61382-61383,61387-61388,61392,61395-61396,61402-61403 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 42757
diff changeset
216
64454
3c36849f0639 Inline cmp_lt().
Raymond Hettinger <python@rcn.com>
parents: 64410
diff changeset
217 cmp = PyObject_RichCompareBool(PyList_GET_ITEM(heap, 0), item, Py_LT);
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
218 if (cmp == -1)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
219 return NULL;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
220 if (cmp == 0) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
221 Py_INCREF(item);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
222 return item;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
223 }
45773
832c820e9d14 Merged revisions 61239-61249,61252-61257,61260-61264,61269-61275,61278-61279,61285-61286,61288-61290,61298,61303-61305,61312-61314,61317,61329,61332,61344,61350-61351,61363-61376,61378-61379,61382-61383,61387-61388,61392,61395-61396,61402-61403 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 42757
diff changeset
224
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
225 returnitem = PyList_GET_ITEM(heap, 0);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
226 Py_INCREF(item);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
227 PyList_SET_ITEM(heap, 0, item);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
228 if (_siftup((PyListObject *)heap, 0) == -1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
229 Py_DECREF(returnitem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
230 return NULL;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
231 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
232 return returnitem;
45773
832c820e9d14 Merged revisions 61239-61249,61252-61257,61260-61264,61269-61275,61278-61279,61285-61286,61288-61290,61298,61303-61305,61312-61314,61317,61329,61332,61344,61350-61351,61363-61376,61378-61379,61382-61383,61387-61388,61392,61395-61396,61402-61403 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 42757
diff changeset
233 }
832c820e9d14 Merged revisions 61239-61249,61252-61257,61260-61264,61269-61275,61278-61279,61285-61286,61288-61290,61298,61303-61305,61312-61314,61317,61329,61332,61344,61350-61351,61363-61376,61378-61379,61382-61383,61387-61388,61392,61395-61396,61402-61403 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 42757
diff changeset
234
832c820e9d14 Merged revisions 61239-61249,61252-61257,61260-61264,61269-61275,61278-61279,61285-61286,61288-61290,61298,61303-61305,61312-61314,61317,61329,61332,61344,61350-61351,61363-61376,61378-61379,61382-61383,61387-61388,61392,61395-61396,61402-61403 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 42757
diff changeset
235 PyDoc_STRVAR(heappushpop_doc,
832c820e9d14 Merged revisions 61239-61249,61252-61257,61260-61264,61269-61275,61278-61279,61285-61286,61288-61290,61298,61303-61305,61312-61314,61317,61329,61332,61344,61350-61351,61363-61376,61378-61379,61382-61383,61387-61388,61392,61395-61396,61402-61403 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 42757
diff changeset
236 "Push item on the heap, then pop and return the smallest item\n\
832c820e9d14 Merged revisions 61239-61249,61252-61257,61260-61264,61269-61275,61278-61279,61285-61286,61288-61290,61298,61303-61305,61312-61314,61317,61329,61332,61344,61350-61351,61363-61376,61378-61379,61382-61383,61387-61388,61392,61395-61396,61402-61403 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 42757
diff changeset
237 from the heap. The combined action runs more efficiently than\n\
832c820e9d14 Merged revisions 61239-61249,61252-61257,61260-61264,61269-61275,61278-61279,61285-61286,61288-61290,61298,61303-61305,61312-61314,61317,61329,61332,61344,61350-61351,61363-61376,61378-61379,61382-61383,61387-61388,61392,61395-61396,61402-61403 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 42757
diff changeset
238 heappush() followed by a separate call to heappop().");
832c820e9d14 Merged revisions 61239-61249,61252-61257,61260-61264,61269-61275,61278-61279,61285-61286,61288-61290,61298,61303-61305,61312-61314,61317,61329,61332,61344,61350-61351,61363-61376,61378-61379,61382-61383,61387-61388,61392,61395-61396,61402-61403 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 42757
diff changeset
239
832c820e9d14 Merged revisions 61239-61249,61252-61257,61260-61264,61269-61275,61278-61279,61285-61286,61288-61290,61298,61303-61305,61312-61314,61317,61329,61332,61344,61350-61351,61363-61376,61378-61379,61382-61383,61387-61388,61392,61395-61396,61402-61403 via svnmerge from
Christian Heimes <christian@cheimes.de>
parents: 42757
diff changeset
240 static PyObject *
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
241 heapify(PyObject *self, PyObject *heap)
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
242 {
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
243 Py_ssize_t i, n;
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
244
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
245 if (!PyList_Check(heap)) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
246 PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
247 return NULL;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
248 }
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
249
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
250 n = PyList_GET_SIZE(heap);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
251 /* Transform bottom-up. The largest index there's any point to
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
252 looking at is the largest with a child index in-range, so must
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
253 have 2*i + 1 < n, or i < (n-1)/2. If n is even = 2*j, this is
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
254 (2*j-1)/2 = j-1/2 so j-1 is the largest, which is n//2 - 1. If
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
255 n is odd = 2*j+1, this is (2*j+1-1)/2 = j so j-1 is the largest,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
256 and that's again n//2-1.
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
257 */
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
258 for (i=n/2-1 ; i>=0 ; i--)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
259 if(_siftup((PyListObject *)heap, i) == -1)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
260 return NULL;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
261 Py_INCREF(Py_None);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
262 return Py_None;
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
263 }
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
264
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
265 PyDoc_STRVAR(heapify_doc,
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
266 "Transform list into a heap, in-place, in O(len(heap)) time.");
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
267
32335
c7dcb09745d3 Install C version of heapq.nlargest().
Raymond Hettinger <python@rcn.com>
parents: 31948
diff changeset
268 static PyObject *
c7dcb09745d3 Install C version of heapq.nlargest().
Raymond Hettinger <python@rcn.com>
parents: 31948
diff changeset
269 nlargest(PyObject *self, PyObject *args)
c7dcb09745d3 Install C version of heapq.nlargest().
Raymond Hettinger <python@rcn.com>
parents: 31948
diff changeset
270 {
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
271 PyObject *heap=NULL, *elem, *iterable, *sol, *it, *oldelem;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
272 Py_ssize_t i, n;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
273 int cmp;
32335
c7dcb09745d3 Install C version of heapq.nlargest().
Raymond Hettinger <python@rcn.com>
parents: 31948
diff changeset
274
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
275 if (!PyArg_ParseTuple(args, "nO:nlargest", &n, &iterable))
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
276 return NULL;
32335
c7dcb09745d3 Install C version of heapq.nlargest().
Raymond Hettinger <python@rcn.com>
parents: 31948
diff changeset
277
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
278 it = PyObject_GetIter(iterable);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
279 if (it == NULL)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
280 return NULL;
32335
c7dcb09745d3 Install C version of heapq.nlargest().
Raymond Hettinger <python@rcn.com>
parents: 31948
diff changeset
281
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
282 heap = PyList_New(0);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
283 if (heap == NULL)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
284 goto fail;
32335
c7dcb09745d3 Install C version of heapq.nlargest().
Raymond Hettinger <python@rcn.com>
parents: 31948
diff changeset
285
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
286 for (i=0 ; i<n ; i++ ){
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
287 elem = PyIter_Next(it);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
288 if (elem == NULL) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
289 if (PyErr_Occurred())
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
290 goto fail;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
291 else
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
292 goto sortit;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
293 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
294 if (PyList_Append(heap, elem) == -1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
295 Py_DECREF(elem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
296 goto fail;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
297 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
298 Py_DECREF(elem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
299 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
300 if (PyList_GET_SIZE(heap) == 0)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
301 goto sortit;
32335
c7dcb09745d3 Install C version of heapq.nlargest().
Raymond Hettinger <python@rcn.com>
parents: 31948
diff changeset
302
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
303 for (i=n/2-1 ; i>=0 ; i--)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
304 if(_siftup((PyListObject *)heap, i) == -1)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
305 goto fail;
32335
c7dcb09745d3 Install C version of heapq.nlargest().
Raymond Hettinger <python@rcn.com>
parents: 31948
diff changeset
306
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
307 sol = PyList_GET_ITEM(heap, 0);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
308 while (1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
309 elem = PyIter_Next(it);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
310 if (elem == NULL) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
311 if (PyErr_Occurred())
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
312 goto fail;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
313 else
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
314 goto sortit;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
315 }
64454
3c36849f0639 Inline cmp_lt().
Raymond Hettinger <python@rcn.com>
parents: 64410
diff changeset
316 cmp = PyObject_RichCompareBool(sol, elem, Py_LT);
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
317 if (cmp == -1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
318 Py_DECREF(elem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
319 goto fail;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
320 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
321 if (cmp == 0) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
322 Py_DECREF(elem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
323 continue;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
324 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
325 oldelem = PyList_GET_ITEM(heap, 0);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
326 PyList_SET_ITEM(heap, 0, elem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
327 Py_DECREF(oldelem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
328 if (_siftup((PyListObject *)heap, 0) == -1)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
329 goto fail;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
330 sol = PyList_GET_ITEM(heap, 0);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
331 }
32335
c7dcb09745d3 Install C version of heapq.nlargest().
Raymond Hettinger <python@rcn.com>
parents: 31948
diff changeset
332 sortit:
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
333 if (PyList_Sort(heap) == -1)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
334 goto fail;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
335 if (PyList_Reverse(heap) == -1)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
336 goto fail;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
337 Py_DECREF(it);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
338 return heap;
32335
c7dcb09745d3 Install C version of heapq.nlargest().
Raymond Hettinger <python@rcn.com>
parents: 31948
diff changeset
339
c7dcb09745d3 Install C version of heapq.nlargest().
Raymond Hettinger <python@rcn.com>
parents: 31948
diff changeset
340 fail:
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
341 Py_DECREF(it);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
342 Py_XDECREF(heap);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
343 return NULL;
32335
c7dcb09745d3 Install C version of heapq.nlargest().
Raymond Hettinger <python@rcn.com>
parents: 31948
diff changeset
344 }
c7dcb09745d3 Install C version of heapq.nlargest().
Raymond Hettinger <python@rcn.com>
parents: 31948
diff changeset
345
c7dcb09745d3 Install C version of heapq.nlargest().
Raymond Hettinger <python@rcn.com>
parents: 31948
diff changeset
346 PyDoc_STRVAR(nlargest_doc,
c7dcb09745d3 Install C version of heapq.nlargest().
Raymond Hettinger <python@rcn.com>
parents: 31948
diff changeset
347 "Find the n largest elements in a dataset.\n\
c7dcb09745d3 Install C version of heapq.nlargest().
Raymond Hettinger <python@rcn.com>
parents: 31948
diff changeset
348 \n\
c7dcb09745d3 Install C version of heapq.nlargest().
Raymond Hettinger <python@rcn.com>
parents: 31948
diff changeset
349 Equivalent to: sorted(iterable, reverse=True)[:n]\n");
c7dcb09745d3 Install C version of heapq.nlargest().
Raymond Hettinger <python@rcn.com>
parents: 31948
diff changeset
350
32336
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
351 static int
36518
9f3f87e920a6 Use Py_ssize_t for counts and sizes.
Martin v. Löwis <martin@v.loewis.de>
parents: 36324
diff changeset
352 _siftdownmax(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos)
32336
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
353 {
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
354 PyObject *newitem, *parent;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
355 int cmp;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
356 Py_ssize_t parentpos;
32336
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
357
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
358 assert(PyList_Check(heap));
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
359 if (pos >= PyList_GET_SIZE(heap)) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
360 PyErr_SetString(PyExc_IndexError, "index out of range");
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
361 return -1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
362 }
32336
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
363
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
364 newitem = PyList_GET_ITEM(heap, pos);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
365 Py_INCREF(newitem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
366 /* Follow the path to the root, moving parents down until finding
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
367 a place newitem fits. */
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
368 while (pos > startpos){
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
369 parentpos = (pos - 1) >> 1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
370 parent = PyList_GET_ITEM(heap, parentpos);
64454
3c36849f0639 Inline cmp_lt().
Raymond Hettinger <python@rcn.com>
parents: 64410
diff changeset
371 cmp = PyObject_RichCompareBool(parent, newitem, Py_LT);
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
372 if (cmp == -1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
373 Py_DECREF(newitem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
374 return -1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
375 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
376 if (cmp == 0)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
377 break;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
378 Py_INCREF(parent);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
379 Py_DECREF(PyList_GET_ITEM(heap, pos));
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
380 PyList_SET_ITEM(heap, pos, parent);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
381 pos = parentpos;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
382 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
383 Py_DECREF(PyList_GET_ITEM(heap, pos));
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
384 PyList_SET_ITEM(heap, pos, newitem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
385 return 0;
32336
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
386 }
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
387
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
388 static int
36518
9f3f87e920a6 Use Py_ssize_t for counts and sizes.
Martin v. Löwis <martin@v.loewis.de>
parents: 36324
diff changeset
389 _siftupmax(PyListObject *heap, Py_ssize_t pos)
32336
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
390 {
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
391 Py_ssize_t startpos, endpos, childpos, rightpos;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
392 int cmp;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
393 PyObject *newitem, *tmp;
32336
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
394
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
395 assert(PyList_Check(heap));
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
396 endpos = PyList_GET_SIZE(heap);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
397 startpos = pos;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
398 if (pos >= endpos) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
399 PyErr_SetString(PyExc_IndexError, "index out of range");
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
400 return -1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
401 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
402 newitem = PyList_GET_ITEM(heap, pos);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
403 Py_INCREF(newitem);
32336
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
404
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
405 /* Bubble up the smaller child until hitting a leaf. */
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
406 childpos = 2*pos + 1; /* leftmost child position */
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
407 while (childpos < endpos) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
408 /* Set childpos to index of smaller child. */
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
409 rightpos = childpos + 1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
410 if (rightpos < endpos) {
64454
3c36849f0639 Inline cmp_lt().
Raymond Hettinger <python@rcn.com>
parents: 64410
diff changeset
411 cmp = PyObject_RichCompareBool(
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
412 PyList_GET_ITEM(heap, rightpos),
64454
3c36849f0639 Inline cmp_lt().
Raymond Hettinger <python@rcn.com>
parents: 64410
diff changeset
413 PyList_GET_ITEM(heap, childpos),
3c36849f0639 Inline cmp_lt().
Raymond Hettinger <python@rcn.com>
parents: 64410
diff changeset
414 Py_LT);
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
415 if (cmp == -1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
416 Py_DECREF(newitem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
417 return -1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
418 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
419 if (cmp == 0)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
420 childpos = rightpos;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
421 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
422 /* Move the smaller child up. */
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
423 tmp = PyList_GET_ITEM(heap, childpos);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
424 Py_INCREF(tmp);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
425 Py_DECREF(PyList_GET_ITEM(heap, pos));
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
426 PyList_SET_ITEM(heap, pos, tmp);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
427 pos = childpos;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
428 childpos = 2*pos + 1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
429 }
32336
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
430
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
431 /* The leaf at pos is empty now. Put newitem there, and and bubble
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
432 it up to its final resting place (by sifting its parents down). */
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
433 Py_DECREF(PyList_GET_ITEM(heap, pos));
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
434 PyList_SET_ITEM(heap, pos, newitem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
435 return _siftdownmax(heap, startpos, pos);
32336
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
436 }
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
437
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
438 static PyObject *
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
439 nsmallest(PyObject *self, PyObject *args)
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
440 {
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
441 PyObject *heap=NULL, *elem, *iterable, *los, *it, *oldelem;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
442 Py_ssize_t i, n;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
443 int cmp;
32336
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
444
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
445 if (!PyArg_ParseTuple(args, "nO:nsmallest", &n, &iterable))
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
446 return NULL;
32336
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
447
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
448 it = PyObject_GetIter(iterable);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
449 if (it == NULL)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
450 return NULL;
32336
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
451
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
452 heap = PyList_New(0);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
453 if (heap == NULL)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
454 goto fail;
32336
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
455
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
456 for (i=0 ; i<n ; i++ ){
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
457 elem = PyIter_Next(it);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
458 if (elem == NULL) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
459 if (PyErr_Occurred())
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
460 goto fail;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
461 else
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
462 goto sortit;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
463 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
464 if (PyList_Append(heap, elem) == -1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
465 Py_DECREF(elem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
466 goto fail;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
467 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
468 Py_DECREF(elem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
469 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
470 n = PyList_GET_SIZE(heap);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
471 if (n == 0)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
472 goto sortit;
32336
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
473
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
474 for (i=n/2-1 ; i>=0 ; i--)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
475 if(_siftupmax((PyListObject *)heap, i) == -1)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
476 goto fail;
32336
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
477
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
478 los = PyList_GET_ITEM(heap, 0);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
479 while (1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
480 elem = PyIter_Next(it);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
481 if (elem == NULL) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
482 if (PyErr_Occurred())
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
483 goto fail;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
484 else
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
485 goto sortit;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
486 }
64454
3c36849f0639 Inline cmp_lt().
Raymond Hettinger <python@rcn.com>
parents: 64410
diff changeset
487 cmp = PyObject_RichCompareBool(elem, los, Py_LT);
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
488 if (cmp == -1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
489 Py_DECREF(elem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
490 goto fail;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
491 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
492 if (cmp == 0) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
493 Py_DECREF(elem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
494 continue;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
495 }
32336
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
496
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
497 oldelem = PyList_GET_ITEM(heap, 0);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
498 PyList_SET_ITEM(heap, 0, elem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
499 Py_DECREF(oldelem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
500 if (_siftupmax((PyListObject *)heap, 0) == -1)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
501 goto fail;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
502 los = PyList_GET_ITEM(heap, 0);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
503 }
32336
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
504
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
505 sortit:
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
506 if (PyList_Sort(heap) == -1)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
507 goto fail;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
508 Py_DECREF(it);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
509 return heap;
32336
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
510
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
511 fail:
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
512 Py_DECREF(it);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
513 Py_XDECREF(heap);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
514 return NULL;
32336
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
515 }
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
516
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
517 PyDoc_STRVAR(nsmallest_doc,
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
518 "Find the n smallest elements in a dataset.\n\
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
519 \n\
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
520 Equivalent to: sorted(iterable)[:n]\n");
6e4fe5560d81 Install C version of heapq.nsmallest().
Raymond Hettinger <python@rcn.com>
parents: 32335
diff changeset
521
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
522 static PyMethodDef heapq_methods[] = {
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
523 {"heappush", (PyCFunction)heappush,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
524 METH_VARARGS, heappush_doc},
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
525 {"heappushpop", (PyCFunction)heappushpop,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
526 METH_VARARGS, heappushpop_doc},
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
527 {"heappop", (PyCFunction)heappop,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
528 METH_O, heappop_doc},
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
529 {"heapreplace", (PyCFunction)heapreplace,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
530 METH_VARARGS, heapreplace_doc},
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
531 {"heapify", (PyCFunction)heapify,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
532 METH_O, heapify_doc},
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
533 {"nlargest", (PyCFunction)nlargest,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
534 METH_VARARGS, nlargest_doc},
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
535 {"nsmallest", (PyCFunction)nsmallest,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
536 METH_VARARGS, nsmallest_doc},
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
537 {NULL, NULL} /* sentinel */
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
538 };
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
539
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
540 PyDoc_STRVAR(module_doc,
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
541 "Heap queue algorithm (a.k.a. priority queue).\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
542 \n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
543 Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
544 all k, counting elements from 0. For the sake of comparison,\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
545 non-existing elements are considered to be infinite. The interesting\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
546 property of a heap is that a[0] is always its smallest element.\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
547 \n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
548 Usage:\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
549 \n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
550 heap = [] # creates an empty heap\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
551 heappush(heap, item) # pushes a new item on the heap\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
552 item = heappop(heap) # pops the smallest item from the heap\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
553 item = heap[0] # smallest item on the heap without popping it\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
554 heapify(x) # transforms list into a heap, in-place, in linear time\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
555 item = heapreplace(heap, item) # pops and returns smallest item, and adds\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
556 # new item; the heap size is unchanged\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
557 \n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
558 Our API differs from textbook heap algorithms as follows:\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
559 \n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
560 - We use 0-based indexing. This makes the relationship between the\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
561 index for a node and the indexes for its children slightly less\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
562 obvious, but is more suitable since Python uses 0-based indexing.\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
563 \n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
564 - Our heappop() method returns the smallest item, not the largest.\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
565 \n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
566 These two make it possible to view the heap as a regular Python list\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
567 without surprises: heap[0] is the smallest item, and heap.sort()\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
568 maintains the heap invariant!\n");
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
569
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
570
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
571 PyDoc_STRVAR(__about__,
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
572 "Heap queues\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
573 \n\
42757
e744a20ed8a6 Use UTF-8 for a docstring that contains non-ASCII chars.
Neal Norwitz <nnorwitz@gmail.com>
parents: 36531
diff changeset
574 [explanation by Fran\xc3\xa7ois Pinard]\n\
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
575 \n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
576 Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
577 all k, counting elements from 0. For the sake of comparison,\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
578 non-existing elements are considered to be infinite. The interesting\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
579 property of a heap is that a[0] is always its smallest element.\n"
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
580 "\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
581 The strange invariant above is meant to be an efficient memory\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
582 representation for a tournament. The numbers below are `k', not a[k]:\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
583 \n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
584 0\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
585 \n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
586 1 2\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
587 \n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
588 3 4 5 6\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
589 \n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
590 7 8 9 10 11 12 13 14\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
591 \n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
592 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
593 \n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
594 \n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
595 In the tree above, each cell `k' is topping `2*k+1' and `2*k+2'. In\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
596 an usual binary tournament we see in sports, each cell is the winner\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
597 over the two cells it tops, and we can trace the winner down the tree\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
598 to see all opponents s/he had. However, in many computer applications\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
599 of such tournaments, we do not need to trace the history of a winner.\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
600 To be more memory efficient, when a winner is promoted, we try to\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
601 replace it by something else at a lower level, and the rule becomes\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
602 that a cell and the two cells it tops contain three different items,\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
603 but the top cell \"wins\" over the two topped cells.\n"
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
604 "\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
605 If this heap invariant is protected at all time, index 0 is clearly\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
606 the overall winner. The simplest algorithmic way to remove it and\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
607 find the \"next\" winner is to move some loser (let's say cell 30 in the\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
608 diagram above) into the 0 position, and then percolate this new 0 down\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
609 the tree, exchanging values, until the invariant is re-established.\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
610 This is clearly logarithmic on the total number of items in the tree.\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
611 By iterating over all items, you get an O(n ln n) sort.\n"
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
612 "\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
613 A nice feature of this sort is that you can efficiently insert new\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
614 items while the sort is going on, provided that the inserted items are\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
615 not \"better\" than the last 0'th element you extracted. This is\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
616 especially useful in simulation contexts, where the tree holds all\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
617 incoming events, and the \"win\" condition means the smallest scheduled\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
618 time. When an event schedule other events for execution, they are\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
619 scheduled into the future, so they can easily go into the heap. So, a\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
620 heap is a good structure for implementing schedulers (this is what I\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
621 used for my MIDI sequencer :-).\n"
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
622 "\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
623 Various structures for implementing schedulers have been extensively\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
624 studied, and heaps are good for this, as they are reasonably speedy,\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
625 the speed is almost constant, and the worst case is not much different\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
626 than the average case. However, there are other representations which\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
627 are more efficient overall, yet the worst cases might be terrible.\n"
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
628 "\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
629 Heaps are also very useful in big disk sorts. You most probably all\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
630 know that a big sort implies producing \"runs\" (which are pre-sorted\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
631 sequences, which size is usually related to the amount of CPU memory),\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
632 followed by a merging passes for these runs, which merging is often\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
633 very cleverly organised[1]. It is very important that the initial\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
634 sort produces the longest runs possible. Tournaments are a good way\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
635 to that. If, using all the memory available to hold a tournament, you\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
636 replace and percolate items that happen to fit the current run, you'll\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
637 produce runs which are twice the size of the memory for random input,\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
638 and much better for input fuzzily ordered.\n"
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
639 "\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
640 Moreover, if you output the 0'th item on disk and get an input which\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
641 may not fit in the current tournament (because the value \"wins\" over\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
642 the last output value), it cannot fit in the heap, so the size of the\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
643 heap decreases. The freed memory could be cleverly reused immediately\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
644 for progressively building a second heap, which grows at exactly the\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
645 same rate the first heap is melting. When the first heap completely\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
646 vanishes, you switch heaps and start a new run. Clever and quite\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
647 effective!\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
648 \n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
649 In a word, heaps are useful memory structures to know. I use them in\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
650 a few applications, and I think it is good to keep a `heap' module\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
651 around. :-)\n"
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
652 "\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
653 --------------------\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
654 [1] The disk balancing algorithms which are current, nowadays, are\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
655 more annoying than clever, and this is a consequence of the seeking\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
656 capabilities of the disks. On devices which cannot seek, like big\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
657 tape drives, the story was quite different, and one had to be very\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
658 clever to ensure (far in advance) that each tape movement will be the\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
659 most effective possible (that is, will best participate at\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
660 \"progressing\" the merge). Some tapes were even able to read\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
661 backwards, and this was also used to avoid the rewinding time.\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
662 Believe me, real good tape sorts were quite spectacular to watch!\n\
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
663 From all times, sorting has always been a Great Art! :-)\n");
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
664
47580
94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API.
Martin v. Löwis <martin@v.loewis.de>
parents: 47559
diff changeset
665
94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API.
Martin v. Löwis <martin@v.loewis.de>
parents: 47559
diff changeset
666 static struct PyModuleDef _heapqmodule = {
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
667 PyModuleDef_HEAD_INIT,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
668 "_heapq",
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
669 module_doc,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
670 -1,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
671 heapq_methods,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
672 NULL,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
673 NULL,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
674 NULL,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
675 NULL
47580
94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API.
Martin v. Löwis <martin@v.loewis.de>
parents: 47559
diff changeset
676 };
94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API.
Martin v. Löwis <martin@v.loewis.de>
parents: 47559
diff changeset
677
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
678 PyMODINIT_FUNC
47580
94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API.
Martin v. Löwis <martin@v.loewis.de>
parents: 47559
diff changeset
679 PyInit__heapq(void)
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
680 {
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
681 PyObject *m, *about;
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
682
61466
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
683 m = PyModule_Create(&_heapqmodule);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
684 if (m == NULL)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
685 return NULL;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
686 about = PyUnicode_DecodeUTF8(__about__, strlen(__about__), NULL);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
687 PyModule_AddObject(m, "__about__", about);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from
Antoine Pitrou <solipsis@pitrou.net>
parents: 48322
diff changeset
688 return m;
31948
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
689 }
f950ef309d75 Correct the file name of _heapq module.
Hye-Shik Chang <hyeshik@gmail.com>
parents:
diff changeset
690