cpython-lru_cache-weakref: Modules/

annotate Modules/_heapqmodule.c @ 87690:66c1c9f32567 default tip

Add use_weakref option to functools.lru_cache The use_weakref option makes lru_cache create weak references to the function arguments when creating the cache key, which prevents them from staying in the memory forever even after all other references to them are gone. This is a proof of concept for http://bugs.python.org/issue19859

author	Radomir Dopieralski <devel@sheep.art.pl>
date	Tue, 03 Dec 2013 16:02:48 +0100
parents	563b27bef79f
children

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 {
82479 905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	14 PyObject newitem, parent, *olditem;
61466 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;
82479 905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	17 Py_ssize_t size;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	18
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	19 assert(PyList_Check(heap));
82479 905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	20 size = PyList_GET_SIZE(heap);
905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	21 if (pos >= size) {
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	22 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	23 return -1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	24 }
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	25
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	26 newitem = PyList_GET_ITEM(heap, pos);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	27 Py_INCREF(newitem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	28 /* 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	29 a place newitem fits. */
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	30 while (pos > startpos){
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	31 parentpos = (pos - 1) >> 1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	32 parent = PyList_GET_ITEM(heap, parentpos);
64454 3c36849f0639 Inline cmp_lt(). Raymond Hettinger <python@rcn.com> parents: 64410 diff changeset	33 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	34 if (cmp == -1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	35 Py_DECREF(newitem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	36 return -1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	37 }
82479 905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	38 if (size != PyList_GET_SIZE(heap)) {
905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	39 Py_DECREF(newitem);
905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	40 PyErr_SetString(PyExc_RuntimeError,
905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	41 "list changed size during iteration");
905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	42 return -1;
905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	43 }
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	44 if (cmp == 0)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	45 break;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	46 Py_INCREF(parent);
82479 905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	47 olditem = PyList_GET_ITEM(heap, pos);
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	48 PyList_SET_ITEM(heap, pos, parent);
82479 905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	49 Py_DECREF(olditem);
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	50 pos = parentpos;
82479 905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	51 if (size != PyList_GET_SIZE(heap)) {
905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	52 PyErr_SetString(PyExc_RuntimeError,
905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	53 "list changed size during iteration");
905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	54 return -1;
905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	55 }
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	56 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	57 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	58 PyList_SET_ITEM(heap, pos, newitem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	59 return 0;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	60 }
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	61
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	62 static int
36518 9f3f87e920a6 Use Py_ssize_t for counts and sizes. Martin v. Löwis <martin@v.loewis.de> parents: 36324 diff changeset	63 _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	64 {
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	65 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	66 int cmp;
82479 905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	67 PyObject newitem, tmp, *olditem;
905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	68 Py_ssize_t size;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	69
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	70 assert(PyList_Check(heap));
82479 905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	71 size = PyList_GET_SIZE(heap);
905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	72 endpos = size;
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	73 startpos = pos;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	74 if (pos >= endpos) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	75 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	76 return -1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	77 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	78 newitem = PyList_GET_ITEM(heap, pos);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	79 Py_INCREF(newitem);
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	80
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	81 /* 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	82 childpos = 2pos + 1; / leftmost child position */
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	83 while (childpos < endpos) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	84 /* 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	85 rightpos = childpos + 1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	86 if (rightpos < endpos) {
64454 3c36849f0639 Inline cmp_lt(). Raymond Hettinger <python@rcn.com> parents: 64410 diff changeset	87 cmp = PyObject_RichCompareBool(
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	88 PyList_GET_ITEM(heap, childpos),
64454 3c36849f0639 Inline cmp_lt(). Raymond Hettinger <python@rcn.com> parents: 64410 diff changeset	89 PyList_GET_ITEM(heap, rightpos),
3c36849f0639 Inline cmp_lt(). Raymond Hettinger <python@rcn.com> parents: 64410 diff changeset	90 Py_LT);
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	91 if (cmp == -1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	92 Py_DECREF(newitem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	93 return -1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	94 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	95 if (cmp == 0)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	96 childpos = rightpos;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	97 }
82479 905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	98 if (size != PyList_GET_SIZE(heap)) {
905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	99 Py_DECREF(newitem);
905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	100 PyErr_SetString(PyExc_RuntimeError,
905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	101 "list changed size during iteration");
905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	102 return -1;
905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	103 }
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	104 /* Move the smaller child up. */
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	105 tmp = PyList_GET_ITEM(heap, childpos);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	106 Py_INCREF(tmp);
82479 905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	107 olditem = PyList_GET_ITEM(heap, pos);
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	108 PyList_SET_ITEM(heap, pos, tmp);
82479 905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	109 Py_DECREF(olditem);
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	110 pos = childpos;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	111 childpos = 2*pos + 1;
82479 905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	112 if (size != PyList_GET_SIZE(heap)) {
905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	113 PyErr_SetString(PyExc_RuntimeError,
905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	114 "list changed size during iteration");
905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	115 return -1;
905b02749c26 Issue #17278: Fix a crash in heapq.heappush() and heapq.heappop() when the list is being resized concurrently. Antoine Pitrou <solipsis@pitrou.net> parents: 64454 diff changeset	116 }
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	117 }
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	118
82614 e9ba9f21a828 Issue #17047: remove doubled words found in 2.7 to 3.4 Modules/, Terry Jan Reedy <tjreedy@udel.edu>* parents: 82479 diff changeset	119 /* The leaf at pos is empty now. Put newitem there, and bubble
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	120 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	121 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	122 PyList_SET_ITEM(heap, pos, newitem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	123 return _siftdown(heap, startpos, pos);
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	124 }
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	125
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	126 static PyObject *
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	127 heappush(PyObject self, PyObject args)
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 PyObject heap, item;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	130
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	131 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	132 return NULL;
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 if (!PyList_Check(heap)) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	135 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	136 return NULL;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	137 }
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	138
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	139 if (PyList_Append(heap, item) == -1)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	140 return NULL;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	141
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	142 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	143 return NULL;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	144 Py_INCREF(Py_None);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	145 return Py_None;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	146 }
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	147
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	148 PyDoc_STRVAR(heappush_doc,
81583 6f0eb0e3820c Show the function signature in the docstring Raymond Hettinger <python@rcn.com> parents: 64454 diff changeset	149 "heappush(heap, item) -> None. Push item onto heap, maintaining the heap invariant.");
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	150
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	151 static PyObject *
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	152 heappop(PyObject self, PyObject heap)
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	153 {
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	154 PyObject lastelt, returnitem;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	155 Py_ssize_t n;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	156
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	157 if (!PyList_Check(heap)) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	158 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	159 return NULL;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	160 }
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	161
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	162 /* # 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	163 n = PyList_GET_SIZE(heap);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	164 if (n == 0) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	165 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	166 return NULL;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	167 }
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	168
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	169 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	170 Py_INCREF(lastelt);
84691 563b27bef79f Issue #18408: Fix heapq.heappop(), handle PyList_SetSlice() failure Victor Stinner <victor.stinner@gmail.com> parents: 82615 diff changeset	171 if (PyList_SetSlice(heap, n-1, n, NULL) < 0) {
563b27bef79f Issue #18408: Fix heapq.heappop(), handle PyList_SetSlice() failure Victor Stinner <victor.stinner@gmail.com> parents: 82615 diff changeset	172 Py_DECREF(lastelt);
563b27bef79f Issue #18408: Fix heapq.heappop(), handle PyList_SetSlice() failure Victor Stinner <victor.stinner@gmail.com> parents: 82615 diff changeset	173 return NULL;
563b27bef79f Issue #18408: Fix heapq.heappop(), handle PyList_SetSlice() failure Victor Stinner <victor.stinner@gmail.com> parents: 82615 diff changeset	174 }
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	175 n--;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	176
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	177 if (!n)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	178 return lastelt;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	179 returnitem = PyList_GET_ITEM(heap, 0);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	180 PyList_SET_ITEM(heap, 0, lastelt);
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(heappop_doc,
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	189 "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	190
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	191 static PyObject *
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	192 heapreplace(PyObject self, PyObject args)
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	193 {
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	194 PyObject heap, item, *returnitem;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	195
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	196 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	197 return NULL;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	198
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	199 if (!PyList_Check(heap)) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	200 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	201 return NULL;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	202 }
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	203
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	204 if (PyList_GET_SIZE(heap) < 1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	205 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	206 return NULL;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	207 }
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	208
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	209 returnitem = PyList_GET_ITEM(heap, 0);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	210 Py_INCREF(item);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	211 PyList_SET_ITEM(heap, 0, item);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	212 if (_siftup((PyListObject *)heap, 0) == -1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	213 Py_DECREF(returnitem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	214 return NULL;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	215 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	216 return returnitem;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	217 }
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	218
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	219 PyDoc_STRVAR(heapreplace_doc,
81583 6f0eb0e3820c Show the function signature in the docstring Raymond Hettinger <python@rcn.com> parents: 64454 diff changeset	220 "heapreplace(heap, item) -> value. Pop and return the current smallest value, and add the new item.\n\
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	221 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	222 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	223 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	224 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	225 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	226 if item > heap[0]:\n\
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	227 item = heapreplace(heap, item)\n");
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	228
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	229 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	230 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	231 {
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	232 PyObject heap, item, *returnitem;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	233 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	234
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	235 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	236 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	237
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	238 if (!PyList_Check(heap)) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	239 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	240 return NULL;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	241 }
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	242
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	243 if (PyList_GET_SIZE(heap) < 1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	244 Py_INCREF(item);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	245 return item;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	246 }
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	247
64454 3c36849f0639 Inline cmp_lt(). Raymond Hettinger <python@rcn.com> parents: 64410 diff changeset	248 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	249 if (cmp == -1)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	250 return NULL;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	251 if (cmp == 0) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	252 Py_INCREF(item);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	253 return item;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	254 }
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	255
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	256 returnitem = PyList_GET_ITEM(heap, 0);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	257 Py_INCREF(item);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	258 PyList_SET_ITEM(heap, 0, item);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	259 if (_siftup((PyListObject *)heap, 0) == -1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	260 Py_DECREF(returnitem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	261 return NULL;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	262 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	263 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	264 }
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	265
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	266 PyDoc_STRVAR(heappushpop_doc,
81583 6f0eb0e3820c Show the function signature in the docstring Raymond Hettinger <python@rcn.com> parents: 64454 diff changeset	267 "heappushpop(heap, item) -> value. Push item on the heap, then pop and return the smallest item\n\
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	268 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	269 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	270
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	271 static PyObject *
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	272 heapify(PyObject self, PyObject heap)
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	273 {
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	274 Py_ssize_t i, n;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	275
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	276 if (!PyList_Check(heap)) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	277 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	278 return NULL;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	279 }
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	280
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	281 n = PyList_GET_SIZE(heap);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	282 /* 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	283 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	284 have 2i + 1 < n, or i < (n-1)/2. If n is even = 2j, this is
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	285 (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	286 n is odd = 2j+1, this is (2j+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	287 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	288 */
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	289 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	290 if(_siftup((PyListObject *)heap, i) == -1)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	291 return NULL;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	292 Py_INCREF(Py_None);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	293 return Py_None;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	294 }
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	295
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	296 PyDoc_STRVAR(heapify_doc,
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	297 "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	298
32335 c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	299 static PyObject *
c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	300 nlargest(PyObject self, PyObject args)
c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	301 {
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	302 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	303 Py_ssize_t i, n;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	304 int cmp;
32335 c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	305
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	306 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	307 return NULL;
32335 c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	308
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	309 it = PyObject_GetIter(iterable);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	310 if (it == NULL)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	311 return NULL;
32335 c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	312
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	313 heap = PyList_New(0);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	314 if (heap == NULL)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	315 goto fail;
32335 c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	316
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	317 for (i=0 ; i<n ; i++ ){
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	318 elem = PyIter_Next(it);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	319 if (elem == NULL) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	320 if (PyErr_Occurred())
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	321 goto fail;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	322 else
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	323 goto sortit;
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 if (PyList_Append(heap, elem) == -1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	326 Py_DECREF(elem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	327 goto fail;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	328 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	329 Py_DECREF(elem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	330 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	331 if (PyList_GET_SIZE(heap) == 0)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	332 goto sortit;
32335 c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	333
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	334 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	335 if(_siftup((PyListObject *)heap, i) == -1)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	336 goto fail;
32335 c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	337
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	338 sol = PyList_GET_ITEM(heap, 0);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	339 while (1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	340 elem = PyIter_Next(it);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	341 if (elem == NULL) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	342 if (PyErr_Occurred())
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	343 goto fail;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	344 else
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	345 goto sortit;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	346 }
64454 3c36849f0639 Inline cmp_lt(). Raymond Hettinger <python@rcn.com> parents: 64410 diff changeset	347 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	348 if (cmp == -1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	349 Py_DECREF(elem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	350 goto fail;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	351 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	352 if (cmp == 0) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	353 Py_DECREF(elem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	354 continue;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	355 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	356 oldelem = PyList_GET_ITEM(heap, 0);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	357 PyList_SET_ITEM(heap, 0, elem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	358 Py_DECREF(oldelem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	359 if (_siftup((PyListObject *)heap, 0) == -1)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	360 goto fail;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	361 sol = PyList_GET_ITEM(heap, 0);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	362 }
32335 c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	363 sortit:
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	364 if (PyList_Sort(heap) == -1)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	365 goto fail;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	366 if (PyList_Reverse(heap) == -1)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	367 goto fail;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	368 Py_DECREF(it);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	369 return heap;
32335 c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	370
c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	371 fail:
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	372 Py_DECREF(it);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	373 Py_XDECREF(heap);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	374 return NULL;
32335 c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	375 }
c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	376
c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	377 PyDoc_STRVAR(nlargest_doc,
c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	378 "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	379 \n\
c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	380 Equivalent to: sorted(iterable, reverse=True)[:n]\n");
c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	381
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	382 static int
36518 9f3f87e920a6 Use Py_ssize_t for counts and sizes. Martin v. Löwis <martin@v.loewis.de> parents: 36324 diff changeset	383 _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	384 {
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	385 PyObject newitem, parent;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	386 int cmp;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	387 Py_ssize_t parentpos;
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	388
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	389 assert(PyList_Check(heap));
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	390 if (pos >= PyList_GET_SIZE(heap)) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	391 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	392 return -1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	393 }
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 newitem = PyList_GET_ITEM(heap, pos);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	396 Py_INCREF(newitem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	397 /* 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	398 a place newitem fits. */
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	399 while (pos > startpos){
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	400 parentpos = (pos - 1) >> 1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	401 parent = PyList_GET_ITEM(heap, parentpos);
64454 3c36849f0639 Inline cmp_lt(). Raymond Hettinger <python@rcn.com> parents: 64410 diff changeset	402 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	403 if (cmp == -1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	404 Py_DECREF(newitem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	405 return -1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	406 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	407 if (cmp == 0)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	408 break;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	409 Py_INCREF(parent);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	410 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	411 PyList_SET_ITEM(heap, pos, parent);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	412 pos = parentpos;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	413 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	414 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	415 PyList_SET_ITEM(heap, pos, newitem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	416 return 0;
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	417 }
6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	418
6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	419 static int
36518 9f3f87e920a6 Use Py_ssize_t for counts and sizes. Martin v. Löwis <martin@v.loewis.de> parents: 36324 diff changeset	420 _siftupmax(PyListObject *heap, Py_ssize_t pos)
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	421 {
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	422 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	423 int cmp;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	424 PyObject newitem, tmp;
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	425
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	426 assert(PyList_Check(heap));
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	427 endpos = PyList_GET_SIZE(heap);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	428 startpos = pos;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	429 if (pos >= endpos) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	430 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	431 return -1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	432 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	433 newitem = PyList_GET_ITEM(heap, pos);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	434 Py_INCREF(newitem);
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	435
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	436 /* 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	437 childpos = 2pos + 1; / leftmost child position */
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	438 while (childpos < endpos) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	439 /* 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	440 rightpos = childpos + 1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	441 if (rightpos < endpos) {
64454 3c36849f0639 Inline cmp_lt(). Raymond Hettinger <python@rcn.com> parents: 64410 diff changeset	442 cmp = PyObject_RichCompareBool(
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	443 PyList_GET_ITEM(heap, rightpos),
64454 3c36849f0639 Inline cmp_lt(). Raymond Hettinger <python@rcn.com> parents: 64410 diff changeset	444 PyList_GET_ITEM(heap, childpos),
3c36849f0639 Inline cmp_lt(). Raymond Hettinger <python@rcn.com> parents: 64410 diff changeset	445 Py_LT);
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	446 if (cmp == -1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	447 Py_DECREF(newitem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	448 return -1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	449 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	450 if (cmp == 0)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	451 childpos = rightpos;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	452 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	453 /* Move the smaller child up. */
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	454 tmp = PyList_GET_ITEM(heap, childpos);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	455 Py_INCREF(tmp);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	456 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	457 PyList_SET_ITEM(heap, pos, tmp);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	458 pos = childpos;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	459 childpos = 2*pos + 1;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	460 }
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	461
82614 e9ba9f21a828 Issue #17047: remove doubled words found in 2.7 to 3.4 Modules/, Terry Jan Reedy <tjreedy@udel.edu>* parents: 82479 diff changeset	462 /* The leaf at pos is empty now. Put newitem there, and bubble
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	463 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	464 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	465 PyList_SET_ITEM(heap, pos, newitem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	466 return _siftdownmax(heap, startpos, pos);
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	467 }
6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	468
6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	469 static PyObject *
6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	470 nsmallest(PyObject self, PyObject args)
6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	471 {
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	472 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	473 Py_ssize_t i, n;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	474 int cmp;
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	475
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	476 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	477 return NULL;
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	478
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	479 it = PyObject_GetIter(iterable);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	480 if (it == NULL)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	481 return NULL;
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	482
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	483 heap = PyList_New(0);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	484 if (heap == NULL)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	485 goto fail;
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	486
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	487 for (i=0 ; i<n ; i++ ){
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	488 elem = PyIter_Next(it);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	489 if (elem == NULL) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	490 if (PyErr_Occurred())
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	491 goto fail;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	492 else
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	493 goto sortit;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	494 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	495 if (PyList_Append(heap, elem) == -1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	496 Py_DECREF(elem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	497 goto fail;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	498 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	499 Py_DECREF(elem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	500 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	501 n = PyList_GET_SIZE(heap);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	502 if (n == 0)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	503 goto sortit;
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	504
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	505 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	506 if(_siftupmax((PyListObject *)heap, i) == -1)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	507 goto fail;
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	508
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	509 los = PyList_GET_ITEM(heap, 0);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	510 while (1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	511 elem = PyIter_Next(it);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	512 if (elem == NULL) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	513 if (PyErr_Occurred())
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	514 goto fail;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	515 else
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	516 goto sortit;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	517 }
64454 3c36849f0639 Inline cmp_lt(). Raymond Hettinger <python@rcn.com> parents: 64410 diff changeset	518 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	519 if (cmp == -1) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	520 Py_DECREF(elem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	521 goto fail;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	522 }
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	523 if (cmp == 0) {
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	524 Py_DECREF(elem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	525 continue;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	526 }
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	527
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	528 oldelem = PyList_GET_ITEM(heap, 0);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	529 PyList_SET_ITEM(heap, 0, elem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	530 Py_DECREF(oldelem);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	531 if (_siftupmax((PyListObject *)heap, 0) == -1)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	532 goto fail;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	533 los = PyList_GET_ITEM(heap, 0);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	534 }
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	535
6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	536 sortit:
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	537 if (PyList_Sort(heap) == -1)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	538 goto fail;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	539 Py_DECREF(it);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	540 return heap;
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	541
6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	542 fail:
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	543 Py_DECREF(it);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	544 Py_XDECREF(heap);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	545 return NULL;
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	546 }
6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	547
6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	548 PyDoc_STRVAR(nsmallest_doc,
6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	549 "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	550 \n\
6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	551 Equivalent to: sorted(iterable)[:n]\n");
6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	552
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	553 static PyMethodDef heapq_methods[] = {
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	554 {"heappush", (PyCFunction)heappush,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	555 METH_VARARGS, heappush_doc},
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	556 {"heappushpop", (PyCFunction)heappushpop,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	557 METH_VARARGS, heappushpop_doc},
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	558 {"heappop", (PyCFunction)heappop,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	559 METH_O, heappop_doc},
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	560 {"heapreplace", (PyCFunction)heapreplace,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	561 METH_VARARGS, heapreplace_doc},
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	562 {"heapify", (PyCFunction)heapify,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	563 METH_O, heapify_doc},
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	564 {"nlargest", (PyCFunction)nlargest,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	565 METH_VARARGS, nlargest_doc},
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	566 {"nsmallest", (PyCFunction)nsmallest,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	567 METH_VARARGS, nsmallest_doc},
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	568 {NULL, NULL} /* sentinel */
31948 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(module_doc,
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	572 "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	573 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	574 Heaps are arrays for which a[k] <= a[2k+1] and a[k] <= a[2k+2] for\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	575 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	576 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	577 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	578 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	579 Usage:\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 heap = [] # creates an empty heap\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	582 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	583 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	584 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	585 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	586 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	587 # 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	588 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	589 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	590 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	591 - 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	592 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	593 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	594 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	595 - 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	596 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	597 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	598 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	599 maintains the heap invariant!\n");
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	600
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	601
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	602 PyDoc_STRVAR(__about__,
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	603 "Heap queues\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	604 \n\
42757 e744a20ed8a6 Use UTF-8 for a docstring that contains non-ASCII chars. Neal Norwitz <nnorwitz@gmail.com> parents: 36531 diff changeset	605 [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	606 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	607 Heaps are arrays for which a[k] <= a[2k+1] and a[k] <= a[2k+2] for\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	608 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	609 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	610 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	611 "\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	612 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	613 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	614 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	615 0\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	616 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	617 1 2\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	618 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	619 3 4 5 6\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	620 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	621 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	622 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	623 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	624 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	625 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	626 In the tree above, each cell `k' is topping `2k+1' and `2k+2'. In\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	627 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	628 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	629 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	630 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	631 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	632 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	633 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	634 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	635 "\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	636 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	637 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	638 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	639 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	640 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	641 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	642 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	643 "\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	644 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	645 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	646 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	647 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	648 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	649 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	650 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	651 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	652 used for my MIDI sequencer :-).\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 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	655 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	656 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	657 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	658 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	659 "\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	660 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	661 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	662 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	663 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	664 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	665 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	666 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	667 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	668 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	669 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	670 "\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	671 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	672 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	673 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	674 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	675 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	676 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	677 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	678 effective!\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	679 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	680 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	681 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	682 around. :-)\n"
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	683 "\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	684 --------------------\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	685 [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	686 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	687 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	688 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	689 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	690 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	691 \"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	692 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	693 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	694 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	695
47580 94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API. Martin v. Löwis <martin@v.loewis.de> parents: 47559 diff changeset	696
94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API. Martin v. Löwis <martin@v.loewis.de> parents: 47559 diff changeset	697 static struct PyModuleDef _heapqmodule = {
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	698 PyModuleDef_HEAD_INIT,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	699 "_heapq",
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	700 module_doc,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	701 -1,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	702 heapq_methods,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	703 NULL,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	704 NULL,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	705 NULL,
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	706 NULL
47580 94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API. Martin v. Löwis <martin@v.loewis.de> parents: 47559 diff changeset	707 };
94f64f11fdd0 Implement PEP 3121: new module initialization and finalization API. Martin v. Löwis <martin@v.loewis.de> parents: 47559 diff changeset	708
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	709 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	710 PyInit__heapq(void)
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	711 {
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	712 PyObject m, about;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	713
61466 cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	714 m = PyModule_Create(&_heapqmodule);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	715 if (m == NULL)
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	716 return NULL;
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	717 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	718 PyModule_AddObject(m, "__about__", about);
cab14be0ada1 Recorded merge of revisions 81029 via svnmerge from Antoine Pitrou <solipsis@pitrou.net> parents: 48322 diff changeset	719 return m;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	720 }
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	721

Mercurial > cpython-lru_cache-weakref

annotate Modules/_heapqmodule.c @ 87690:66c1c9f32567 default tip