cpython-lru_cache-weakref: Modules/

annotate Modules/_heapqmodule.c @ 80661:94de77bd0b4b 2.7

Issue #16194: document imp.load_dynamic problems when read several extension modules from the same binary object file.

author	Andrew Svetlov <andrew.svetlov@gmail.com>
date	Thu, 29 Nov 2012 19:51:28 +0200
parents	ee5350f1d0c2
children	0b6cef575090

rev	line source
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 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,
64412 895aeb4595c2 Merged revisions 84472 via svnmerge from Éric Araujo <merwok@netwok.org> parents: 61463 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
47502 c89434cb914d Issue 3501: Make heapq support both __le__ and __lt__. Raymond Hettinger <python@rcn.com> parents: 47402 diff changeset	11 /* Older implementations of heapq used Py_LE for comparisons. Now, it uses
c89434cb914d Issue 3501: Make heapq support both __le__ and __lt__. Raymond Hettinger <python@rcn.com> parents: 47402 diff changeset	12 Py_LT so it will match min(), sorted(), and bisect(). Unfortunately, some
c89434cb914d Issue 3501: Make heapq support both __le__ and __lt__. Raymond Hettinger <python@rcn.com> parents: 47402 diff changeset	13 client code (Twisted for example) relied on Py_LE, so this little function
68503 ee5350f1d0c2 #11515: fix several typos. Patch by Piotr Kasprzyk. Ezio Melotti <ezio.melotti@gmail.com> parents: 64412 diff changeset	14 restores compatibility by trying both.
47502 c89434cb914d Issue 3501: Make heapq support both __le__ and __lt__. Raymond Hettinger <python@rcn.com> parents: 47402 diff changeset	15 */
c89434cb914d Issue 3501: Make heapq support both __le__ and __lt__. Raymond Hettinger <python@rcn.com> parents: 47402 diff changeset	16 static int
c89434cb914d Issue 3501: Make heapq support both __le__ and __lt__. Raymond Hettinger <python@rcn.com> parents: 47402 diff changeset	17 cmp_lt(PyObject x, PyObject y)
c89434cb914d Issue 3501: Make heapq support both __le__ and __lt__. Raymond Hettinger <python@rcn.com> parents: 47402 diff changeset	18 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	19 int cmp;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	20 static PyObject *lt = NULL;
47589 cb8494ce1337 Issue 3051: Let heapq work with either __lt__ or __le__. Raymond Hettinger <python@rcn.com> parents: 47527 diff changeset	21
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	22 if (lt == NULL) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	23 lt = PyString_FromString("__lt__");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	24 if (lt == NULL)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	25 return -1;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	26 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	27 if (PyObject_HasAttr(x, lt))
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	28 return PyObject_RichCompareBool(x, y, Py_LT);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	29 cmp = PyObject_RichCompareBool(y, x, Py_LE);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	30 if (cmp != -1)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	31 cmp = 1 - cmp;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	32 return cmp;
47502 c89434cb914d Issue 3501: Make heapq support both __le__ and __lt__. Raymond Hettinger <python@rcn.com> parents: 47402 diff changeset	33 }
c89434cb914d Issue 3501: Make heapq support both __le__ and __lt__. Raymond Hettinger <python@rcn.com> parents: 47402 diff changeset	34
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	35 static int
36518 9f3f87e920a6 Use Py_ssize_t for counts and sizes. Martin v. Löwis <martin@v.loewis.de> parents: 36324 diff changeset	36 _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	37 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	38 PyObject newitem, parent;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	39 int cmp;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	40 Py_ssize_t parentpos;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	41
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	42 assert(PyList_Check(heap));
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	43 if (pos >= PyList_GET_SIZE(heap)) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	44 PyErr_SetString(PyExc_IndexError, "index out of range");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	45 return -1;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	46 }
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	47
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	48 newitem = PyList_GET_ITEM(heap, pos);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	49 Py_INCREF(newitem);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	50 /* Follow the path to the root, moving parents down until finding
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	51 a place newitem fits. */
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	52 while (pos > startpos){
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	53 parentpos = (pos - 1) >> 1;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	54 parent = PyList_GET_ITEM(heap, parentpos);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	55 cmp = cmp_lt(newitem, parent);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	56 if (cmp == -1) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	57 Py_DECREF(newitem);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	58 return -1;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	59 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	60 if (cmp == 0)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	61 break;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	62 Py_INCREF(parent);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	63 Py_DECREF(PyList_GET_ITEM(heap, pos));
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	64 PyList_SET_ITEM(heap, pos, parent);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	65 pos = parentpos;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	66 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	67 Py_DECREF(PyList_GET_ITEM(heap, pos));
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	68 PyList_SET_ITEM(heap, pos, newitem);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	69 return 0;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	70 }
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	71
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	72 static int
36518 9f3f87e920a6 Use Py_ssize_t for counts and sizes. Martin v. Löwis <martin@v.loewis.de> parents: 36324 diff changeset	73 _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	74 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	75 Py_ssize_t startpos, endpos, childpos, rightpos;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	76 int cmp;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	77 PyObject newitem, tmp;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	78
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	79 assert(PyList_Check(heap));
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	80 endpos = PyList_GET_SIZE(heap);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	81 startpos = pos;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	82 if (pos >= endpos) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	83 PyErr_SetString(PyExc_IndexError, "index out of range");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	84 return -1;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	85 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	86 newitem = PyList_GET_ITEM(heap, pos);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	87 Py_INCREF(newitem);
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	88
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	89 /* Bubble up the smaller child until hitting a leaf. */
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	90 childpos = 2pos + 1; / leftmost child position */
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	91 while (childpos < endpos) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	92 /* Set childpos to index of smaller child. */
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	93 rightpos = childpos + 1;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	94 if (rightpos < endpos) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	95 cmp = cmp_lt(
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	96 PyList_GET_ITEM(heap, childpos),
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	97 PyList_GET_ITEM(heap, rightpos));
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	98 if (cmp == -1) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	99 Py_DECREF(newitem);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	100 return -1;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	101 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	102 if (cmp == 0)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	103 childpos = rightpos;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	104 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	105 /* Move the smaller child up. */
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	106 tmp = PyList_GET_ITEM(heap, childpos);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	107 Py_INCREF(tmp);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	108 Py_DECREF(PyList_GET_ITEM(heap, pos));
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	109 PyList_SET_ITEM(heap, pos, tmp);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	110 pos = childpos;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	111 childpos = 2*pos + 1;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	112 }
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	113
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	114 /* The leaf at pos is empty now. Put newitem there, and and bubble
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	115 it up to its final resting place (by sifting its parents down). */
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	116 Py_DECREF(PyList_GET_ITEM(heap, pos));
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	117 PyList_SET_ITEM(heap, pos, newitem);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	118 return _siftdown(heap, startpos, pos);
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	119 }
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	120
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	121 static PyObject *
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	122 heappush(PyObject self, PyObject args)
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	123 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	124 PyObject heap, item;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	125
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	126 if (!PyArg_UnpackTuple(args, "heappush", 2, 2, &heap, &item))
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	127 return NULL;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	128
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	129 if (!PyList_Check(heap)) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	130 PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	131 return NULL;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	132 }
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	133
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	134 if (PyList_Append(heap, item) == -1)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	135 return NULL;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	136
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	137 if (_siftdown((PyListObject *)heap, 0, PyList_GET_SIZE(heap)-1) == -1)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	138 return NULL;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	139 Py_INCREF(Py_None);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	140 return Py_None;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	141 }
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	142
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	143 PyDoc_STRVAR(heappush_doc,
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	144 "Push item onto heap, maintaining the heap invariant.");
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	145
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	146 static PyObject *
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	147 heappop(PyObject self, PyObject heap)
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	148 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	149 PyObject lastelt, returnitem;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	150 Py_ssize_t n;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	151
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	152 if (!PyList_Check(heap)) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	153 PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	154 return NULL;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	155 }
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	156
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	157 /* # raises appropriate IndexError if heap is empty */
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	158 n = PyList_GET_SIZE(heap);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	159 if (n == 0) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	160 PyErr_SetString(PyExc_IndexError, "index out of range");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	161 return NULL;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	162 }
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	163
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	164 lastelt = PyList_GET_ITEM(heap, n-1) ;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	165 Py_INCREF(lastelt);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	166 PyList_SetSlice(heap, n-1, n, NULL);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	167 n--;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	168
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	169 if (!n)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	170 return lastelt;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	171 returnitem = PyList_GET_ITEM(heap, 0);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	172 PyList_SET_ITEM(heap, 0, lastelt);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	173 if (_siftup((PyListObject *)heap, 0) == -1) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	174 Py_DECREF(returnitem);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	175 return NULL;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	176 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	177 return returnitem;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	178 }
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	179
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	180 PyDoc_STRVAR(heappop_doc,
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	181 "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	182
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	183 static PyObject *
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	184 heapreplace(PyObject self, PyObject args)
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	185 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	186 PyObject heap, item, *returnitem;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	187
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	188 if (!PyArg_UnpackTuple(args, "heapreplace", 2, 2, &heap, &item))
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	189 return NULL;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	190
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	191 if (!PyList_Check(heap)) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	192 PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	193 return NULL;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	194 }
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	195
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	196 if (PyList_GET_SIZE(heap) < 1) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	197 PyErr_SetString(PyExc_IndexError, "index out of range");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	198 return NULL;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	199 }
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	200
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	201 returnitem = PyList_GET_ITEM(heap, 0);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	202 Py_INCREF(item);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	203 PyList_SET_ITEM(heap, 0, item);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	204 if (_siftup((PyListObject *)heap, 0) == -1) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	205 Py_DECREF(returnitem);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	206 return NULL;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	207 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	208 return returnitem;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	209 }
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	210
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	211 PyDoc_STRVAR(heapreplace_doc,
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	212 "Pop and return the current smallest value, and add the new item.\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	213 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	214 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	215 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	216 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	217 this routine unless written as part of a conditional replacement:\n\n\
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	218 if item > heap[0]:\n\
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	219 item = heapreplace(heap, item)\n");
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	220
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	221 static PyObject *
45747 cbb9e2f4b202 Issue 2274: Add heapq.heappushpop(). Raymond Hettinger <python@rcn.com> parents: 36531 diff changeset	222 heappushpop(PyObject self, PyObject args)
cbb9e2f4b202 Issue 2274: Add heapq.heappushpop(). Raymond Hettinger <python@rcn.com> parents: 36531 diff changeset	223 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	224 PyObject heap, item, *returnitem;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	225 int cmp;
45747 cbb9e2f4b202 Issue 2274: Add heapq.heappushpop(). Raymond Hettinger <python@rcn.com> parents: 36531 diff changeset	226
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	227 if (!PyArg_UnpackTuple(args, "heappushpop", 2, 2, &heap, &item))
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	228 return NULL;
45747 cbb9e2f4b202 Issue 2274: Add heapq.heappushpop(). Raymond Hettinger <python@rcn.com> parents: 36531 diff changeset	229
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	230 if (!PyList_Check(heap)) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	231 PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	232 return NULL;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	233 }
45747 cbb9e2f4b202 Issue 2274: Add heapq.heappushpop(). Raymond Hettinger <python@rcn.com> parents: 36531 diff changeset	234
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	235 if (PyList_GET_SIZE(heap) < 1) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	236 Py_INCREF(item);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	237 return item;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	238 }
45747 cbb9e2f4b202 Issue 2274: Add heapq.heappushpop(). Raymond Hettinger <python@rcn.com> parents: 36531 diff changeset	239
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	240 cmp = cmp_lt(PyList_GET_ITEM(heap, 0), item);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	241 if (cmp == -1)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	242 return NULL;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	243 if (cmp == 0) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	244 Py_INCREF(item);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	245 return item;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	246 }
45747 cbb9e2f4b202 Issue 2274: Add heapq.heappushpop(). Raymond Hettinger <python@rcn.com> parents: 36531 diff changeset	247
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	248 returnitem = PyList_GET_ITEM(heap, 0);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	249 Py_INCREF(item);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	250 PyList_SET_ITEM(heap, 0, item);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	251 if (_siftup((PyListObject *)heap, 0) == -1) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	252 Py_DECREF(returnitem);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	253 return NULL;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	254 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	255 return returnitem;
45747 cbb9e2f4b202 Issue 2274: Add heapq.heappushpop(). Raymond Hettinger <python@rcn.com> parents: 36531 diff changeset	256 }
cbb9e2f4b202 Issue 2274: Add heapq.heappushpop(). Raymond Hettinger <python@rcn.com> parents: 36531 diff changeset	257
cbb9e2f4b202 Issue 2274: Add heapq.heappushpop(). Raymond Hettinger <python@rcn.com> parents: 36531 diff changeset	258 PyDoc_STRVAR(heappushpop_doc,
cbb9e2f4b202 Issue 2274: Add heapq.heappushpop(). Raymond Hettinger <python@rcn.com> parents: 36531 diff changeset	259 "Push item on the heap, then pop and return the smallest item\n\
cbb9e2f4b202 Issue 2274: Add heapq.heappushpop(). Raymond Hettinger <python@rcn.com> parents: 36531 diff changeset	260 from the heap. The combined action runs more efficiently than\n\
cbb9e2f4b202 Issue 2274: Add heapq.heappushpop(). Raymond Hettinger <python@rcn.com> parents: 36531 diff changeset	261 heappush() followed by a separate call to heappop().");
cbb9e2f4b202 Issue 2274: Add heapq.heappushpop(). Raymond Hettinger <python@rcn.com> parents: 36531 diff changeset	262
cbb9e2f4b202 Issue 2274: Add heapq.heappushpop(). Raymond Hettinger <python@rcn.com> parents: 36531 diff changeset	263 static PyObject *
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	264 heapify(PyObject self, PyObject heap)
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	265 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	266 Py_ssize_t i, n;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	267
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	268 if (!PyList_Check(heap)) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	269 PyErr_SetString(PyExc_TypeError, "heap argument must be a list");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	270 return NULL;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	271 }
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	272
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	273 n = PyList_GET_SIZE(heap);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	274 /* Transform bottom-up. The largest index there's any point to
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	275 looking at is the largest with a child index in-range, so must
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	276 have 2i + 1 < n, or i < (n-1)/2. If n is even = 2j, this is
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	277 (2*j-1)/2 = j-1/2 so j-1 is the largest, which is n//2 - 1. If
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	278 n is odd = 2j+1, this is (2j+1-1)/2 = j so j-1 is the largest,
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	279 and that's again n//2-1.
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	280 */
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	281 for (i=n/2-1 ; i>=0 ; i--)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	282 if(_siftup((PyListObject *)heap, i) == -1)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	283 return NULL;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	284 Py_INCREF(Py_None);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	285 return Py_None;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	286 }
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	287
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	288 PyDoc_STRVAR(heapify_doc,
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	289 "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	290
32335 c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	291 static PyObject *
c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	292 nlargest(PyObject self, PyObject args)
c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	293 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	294 PyObject heap=NULL, elem, iterable, sol, it, oldelem;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	295 Py_ssize_t i, n;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	296 int cmp;
32335 c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	297
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	298 if (!PyArg_ParseTuple(args, "nO:nlargest", &n, &iterable))
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	299 return NULL;
32335 c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	300
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	301 it = PyObject_GetIter(iterable);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	302 if (it == NULL)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	303 return NULL;
32335 c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	304
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	305 heap = PyList_New(0);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	306 if (heap == NULL)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	307 goto fail;
32335 c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	308
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	309 for (i=0 ; i<n ; i++ ){
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	310 elem = PyIter_Next(it);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	311 if (elem == NULL) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	312 if (PyErr_Occurred())
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	313 goto fail;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	314 else
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	315 goto sortit;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	316 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	317 if (PyList_Append(heap, elem) == -1) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	318 Py_DECREF(elem);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	319 goto fail;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	320 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	321 Py_DECREF(elem);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	322 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	323 if (PyList_GET_SIZE(heap) == 0)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	324 goto sortit;
32335 c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	325
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	326 for (i=n/2-1 ; i>=0 ; i--)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	327 if(_siftup((PyListObject *)heap, i) == -1)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	328 goto fail;
32335 c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	329
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	330 sol = PyList_GET_ITEM(heap, 0);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	331 while (1) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	332 elem = PyIter_Next(it);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	333 if (elem == NULL) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	334 if (PyErr_Occurred())
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	335 goto fail;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	336 else
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	337 goto sortit;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	338 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	339 cmp = cmp_lt(sol, elem);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	340 if (cmp == -1) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	341 Py_DECREF(elem);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	342 goto fail;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	343 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	344 if (cmp == 0) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	345 Py_DECREF(elem);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	346 continue;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	347 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	348 oldelem = PyList_GET_ITEM(heap, 0);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	349 PyList_SET_ITEM(heap, 0, elem);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	350 Py_DECREF(oldelem);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	351 if (_siftup((PyListObject *)heap, 0) == -1)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	352 goto fail;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	353 sol = PyList_GET_ITEM(heap, 0);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	354 }
32335 c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	355 sortit:
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	356 if (PyList_Sort(heap) == -1)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	357 goto fail;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	358 if (PyList_Reverse(heap) == -1)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	359 goto fail;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	360 Py_DECREF(it);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	361 return heap;
32335 c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	362
c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	363 fail:
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	364 Py_DECREF(it);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	365 Py_XDECREF(heap);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	366 return NULL;
32335 c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	367 }
c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	368
c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	369 PyDoc_STRVAR(nlargest_doc,
c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	370 "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	371 \n\
c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	372 Equivalent to: sorted(iterable, reverse=True)[:n]\n");
c7dcb09745d3 Install C version of heapq.nlargest(). Raymond Hettinger <python@rcn.com> parents: 31948 diff changeset	373
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	374 static int
36518 9f3f87e920a6 Use Py_ssize_t for counts and sizes. Martin v. Löwis <martin@v.loewis.de> parents: 36324 diff changeset	375 _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	376 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	377 PyObject newitem, parent;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	378 int cmp;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	379 Py_ssize_t parentpos;
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	380
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	381 assert(PyList_Check(heap));
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	382 if (pos >= PyList_GET_SIZE(heap)) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	383 PyErr_SetString(PyExc_IndexError, "index out of range");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	384 return -1;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	385 }
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	386
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	387 newitem = PyList_GET_ITEM(heap, pos);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	388 Py_INCREF(newitem);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	389 /* Follow the path to the root, moving parents down until finding
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	390 a place newitem fits. */
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	391 while (pos > startpos){
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	392 parentpos = (pos - 1) >> 1;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	393 parent = PyList_GET_ITEM(heap, parentpos);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	394 cmp = cmp_lt(parent, newitem);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	395 if (cmp == -1) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	396 Py_DECREF(newitem);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	397 return -1;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	398 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	399 if (cmp == 0)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	400 break;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	401 Py_INCREF(parent);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	402 Py_DECREF(PyList_GET_ITEM(heap, pos));
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	403 PyList_SET_ITEM(heap, pos, parent);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	404 pos = parentpos;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	405 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	406 Py_DECREF(PyList_GET_ITEM(heap, pos));
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	407 PyList_SET_ITEM(heap, pos, newitem);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	408 return 0;
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	409 }
6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	410
6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	411 static int
36518 9f3f87e920a6 Use Py_ssize_t for counts and sizes. Martin v. Löwis <martin@v.loewis.de> parents: 36324 diff changeset	412 _siftupmax(PyListObject *heap, Py_ssize_t pos)
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	413 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	414 Py_ssize_t startpos, endpos, childpos, rightpos;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	415 int cmp;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	416 PyObject newitem, tmp;
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	417
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	418 assert(PyList_Check(heap));
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	419 endpos = PyList_GET_SIZE(heap);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	420 startpos = pos;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	421 if (pos >= endpos) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	422 PyErr_SetString(PyExc_IndexError, "index out of range");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	423 return -1;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	424 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	425 newitem = PyList_GET_ITEM(heap, pos);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	426 Py_INCREF(newitem);
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	427
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	428 /* Bubble up the smaller child until hitting a leaf. */
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	429 childpos = 2pos + 1; / leftmost child position */
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	430 while (childpos < endpos) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	431 /* Set childpos to index of smaller child. */
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	432 rightpos = childpos + 1;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	433 if (rightpos < endpos) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	434 cmp = cmp_lt(
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	435 PyList_GET_ITEM(heap, rightpos),
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	436 PyList_GET_ITEM(heap, childpos));
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	437 if (cmp == -1) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	438 Py_DECREF(newitem);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	439 return -1;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	440 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	441 if (cmp == 0)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	442 childpos = rightpos;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	443 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	444 /* Move the smaller child up. */
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	445 tmp = PyList_GET_ITEM(heap, childpos);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	446 Py_INCREF(tmp);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	447 Py_DECREF(PyList_GET_ITEM(heap, pos));
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	448 PyList_SET_ITEM(heap, pos, tmp);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	449 pos = childpos;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	450 childpos = 2*pos + 1;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	451 }
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	452
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	453 /* The leaf at pos is empty now. Put newitem there, and and bubble
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	454 it up to its final resting place (by sifting its parents down). */
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	455 Py_DECREF(PyList_GET_ITEM(heap, pos));
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	456 PyList_SET_ITEM(heap, pos, newitem);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	457 return _siftdownmax(heap, startpos, pos);
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	458 }
6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	459
6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	460 static PyObject *
6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	461 nsmallest(PyObject self, PyObject args)
6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	462 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	463 PyObject heap=NULL, elem, iterable, los, it, oldelem;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	464 Py_ssize_t i, n;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	465 int cmp;
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	466
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	467 if (!PyArg_ParseTuple(args, "nO:nsmallest", &n, &iterable))
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	468 return NULL;
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	469
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	470 it = PyObject_GetIter(iterable);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	471 if (it == NULL)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	472 return NULL;
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	473
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	474 heap = PyList_New(0);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	475 if (heap == NULL)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	476 goto fail;
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	477
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	478 for (i=0 ; i<n ; i++ ){
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	479 elem = PyIter_Next(it);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	480 if (elem == NULL) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	481 if (PyErr_Occurred())
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	482 goto fail;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	483 else
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	484 goto sortit;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	485 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	486 if (PyList_Append(heap, elem) == -1) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	487 Py_DECREF(elem);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	488 goto fail;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	489 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	490 Py_DECREF(elem);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	491 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	492 n = PyList_GET_SIZE(heap);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	493 if (n == 0)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	494 goto sortit;
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	495
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	496 for (i=n/2-1 ; i>=0 ; i--)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	497 if(_siftupmax((PyListObject *)heap, i) == -1)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	498 goto fail;
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	499
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	500 los = PyList_GET_ITEM(heap, 0);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	501 while (1) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	502 elem = PyIter_Next(it);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	503 if (elem == NULL) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	504 if (PyErr_Occurred())
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	505 goto fail;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	506 else
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	507 goto sortit;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	508 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	509 cmp = cmp_lt(elem, los);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	510 if (cmp == -1) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	511 Py_DECREF(elem);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	512 goto fail;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	513 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	514 if (cmp == 0) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	515 Py_DECREF(elem);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	516 continue;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	517 }
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	518
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	519 oldelem = PyList_GET_ITEM(heap, 0);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	520 PyList_SET_ITEM(heap, 0, elem);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	521 Py_DECREF(oldelem);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	522 if (_siftupmax((PyListObject *)heap, 0) == -1)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	523 goto fail;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	524 los = PyList_GET_ITEM(heap, 0);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	525 }
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	526
6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	527 sortit:
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	528 if (PyList_Sort(heap) == -1)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	529 goto fail;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	530 Py_DECREF(it);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	531 return heap;
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	532
6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	533 fail:
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	534 Py_DECREF(it);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	535 Py_XDECREF(heap);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	536 return NULL;
32336 6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	537 }
6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	538
6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	539 PyDoc_STRVAR(nsmallest_doc,
6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	540 "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	541 \n\
6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	542 Equivalent to: sorted(iterable)[:n]\n");
6e4fe5560d81 Install C version of heapq.nsmallest(). Raymond Hettinger <python@rcn.com> parents: 32335 diff changeset	543
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	544 static PyMethodDef heapq_methods[] = {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	545 {"heappush", (PyCFunction)heappush,
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	546 METH_VARARGS, heappush_doc},
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	547 {"heappushpop", (PyCFunction)heappushpop,
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	548 METH_VARARGS, heappushpop_doc},
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	549 {"heappop", (PyCFunction)heappop,
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	550 METH_O, heappop_doc},
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	551 {"heapreplace", (PyCFunction)heapreplace,
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	552 METH_VARARGS, heapreplace_doc},
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	553 {"heapify", (PyCFunction)heapify,
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	554 METH_O, heapify_doc},
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	555 {"nlargest", (PyCFunction)nlargest,
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	556 METH_VARARGS, nlargest_doc},
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	557 {"nsmallest", (PyCFunction)nsmallest,
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	558 METH_VARARGS, nsmallest_doc},
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	559 {NULL, NULL} /* sentinel */
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	560 };
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	561
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	562 PyDoc_STRVAR(module_doc,
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	563 "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	564 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	565 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	566 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	567 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	568 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	569 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	570 Usage:\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	571 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	572 heap = [] # creates an empty heap\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	573 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	574 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	575 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	576 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	577 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	578 # 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	579 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	580 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	581 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	582 - 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	583 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	584 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	585 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	586 - 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	587 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	588 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	589 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	590 maintains the heap invariant!\n");
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	591
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	592
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	593 PyDoc_STRVAR(__about__,
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	594 "Heap queues\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	595 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	596 [explanation by Fran�ois Pinard]\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	597 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	598 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	599 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	600 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	601 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	602 "\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	603 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	604 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	605 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	606 0\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	607 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	608 1 2\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	609 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	610 3 4 5 6\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 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	613 \n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	614 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	615 \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 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	618 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	619 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	620 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	621 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	622 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	623 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	624 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	625 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	626 "\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	627 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	628 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	629 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	630 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	631 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	632 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	633 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	634 "\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	635 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	636 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	637 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	638 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	639 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	640 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	641 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	642 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	643 used for my MIDI sequencer :-).\n"
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	644 "\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	645 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	646 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	647 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	648 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	649 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	650 "\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	651 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	652 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	653 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	654 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	655 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	656 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	657 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	658 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	659 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	660 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	661 "\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	662 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	663 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	664 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	665 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	666 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	667 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	668 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	669 effective!\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 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	672 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	673 around. :-)\n"
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	674 "\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	675 --------------------\n\
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	676 [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	677 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	678 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	679 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	680 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	681 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	682 \"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	683 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	684 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	685 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	686
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	687 PyMODINIT_FUNC
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	688 init_heapq(void)
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	689 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	690 PyObject *m;
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	691
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	692 m = Py_InitModule3("_heapq", heapq_methods, module_doc);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	693 if (m == NULL)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	694 return;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 47591 diff changeset	695 PyModule_AddObject(m, "__about__", PyString_FromString(__about__));
31948 f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	696 }
f950ef309d75 Correct the file name of _heapq module. Hye-Shik Chang <hyeshik@gmail.com> parents: diff changeset	697

Mercurial > cpython-lru_cache-weakref

annotate Modules/_heapqmodule.c @ 80661:94de77bd0b4b 2.7