AppPkg/Applications/Python/Python-2.7.10: Initial Checkin part 2/5.

[mirror_edk2.git] / AppPkg / Applications / Python / Python-2.7.10 / Modules / _heapqmodule.c

/* Drop in replacement for heapq.py\r
\r
C implementation derived directly from heapq.py in Py2.3\r
which was written by Kevin O'Connor, augmented by Tim Peters,\r
annotated by François Pinard, and converted to C by Raymond Hettinger.\r
\r
*/\r
\r
#include "Python.h"\r
\r
/* Older implementations of heapq used Py_LE for comparisons.  Now, it uses\r
   Py_LT so it will match min(), sorted(), and bisect().  Unfortunately, some\r
   client code (Twisted for example) relied on Py_LE, so this little function\r
   restores compatibility by trying both.\r
*/\r
static int\r
cmp_lt(PyObject *x, PyObject *y)\r
{\r
    int cmp;\r
    static PyObject *lt = NULL;\r
\r
    if (lt == NULL) {\r
        lt = PyString_FromString("__lt__");\r
        if (lt == NULL)\r
            return -1;\r
    }\r
    if (PyObject_HasAttr(x, lt))\r
        return PyObject_RichCompareBool(x, y, Py_LT);\r
    cmp = PyObject_RichCompareBool(y, x, Py_LE);\r
    if (cmp != -1)\r
        cmp = 1 - cmp;\r
    return cmp;\r
}\r
\r
static int\r
_siftdown(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos)\r
{\r
    PyObject *newitem, *parent;\r
    Py_ssize_t parentpos, size;\r
    int cmp;\r
\r
    assert(PyList_Check(heap));\r
    size = PyList_GET_SIZE(heap);\r
    if (pos >= size) {\r
        PyErr_SetString(PyExc_IndexError, "index out of range");\r
        return -1;\r
    }\r
\r
    /* Follow the path to the root, moving parents down until finding\r
       a place newitem fits. */\r
    newitem = PyList_GET_ITEM(heap, pos);\r
    while (pos > startpos) {\r
        parentpos = (pos - 1) >> 1;\r
        parent = PyList_GET_ITEM(heap, parentpos);\r
        cmp = cmp_lt(newitem, parent);\r
        if (cmp == -1)\r
            return -1;\r
        if (size != PyList_GET_SIZE(heap)) {\r
            PyErr_SetString(PyExc_RuntimeError,\r
                            "list changed size during iteration");\r
            return -1;\r
        }\r
        if (cmp == 0)\r
            break;\r
        parent = PyList_GET_ITEM(heap, parentpos);\r
        newitem = PyList_GET_ITEM(heap, pos);\r
        PyList_SET_ITEM(heap, parentpos, newitem);\r
        PyList_SET_ITEM(heap, pos, parent);\r
        pos = parentpos;\r
    }\r
    return 0;\r
}\r
\r
static int\r
_siftup(PyListObject *heap, Py_ssize_t pos)\r
{\r
    Py_ssize_t startpos, endpos, childpos, rightpos, limit;\r
    PyObject *tmp1, *tmp2;\r
    int cmp;\r
\r
    assert(PyList_Check(heap));\r
    endpos = PyList_GET_SIZE(heap);\r
    startpos = pos;\r
    if (pos >= endpos) {\r
        PyErr_SetString(PyExc_IndexError, "index out of range");\r
        return -1;\r
    }\r
\r
    /* Bubble up the smaller child until hitting a leaf. */\r
    limit = endpos / 2;          /* smallest pos that has no child */\r
    while (pos < limit) {\r
        /* Set childpos to index of smaller child.   */\r
        childpos = 2*pos + 1;    /* leftmost child position  */\r
        rightpos = childpos + 1;\r
        if (rightpos < endpos) {\r
            cmp = cmp_lt(\r
                PyList_GET_ITEM(heap, childpos),\r
                PyList_GET_ITEM(heap, rightpos));\r
            if (cmp == -1)\r
                return -1;\r
            if (cmp == 0)\r
                childpos = rightpos;\r
            if (endpos != PyList_GET_SIZE(heap)) {\r
                PyErr_SetString(PyExc_RuntimeError,\r
                                "list changed size during iteration");\r
                return -1;\r
            }\r
        }\r
        /* Move the smaller child up. */\r
        tmp1 = PyList_GET_ITEM(heap, childpos);\r
        tmp2 = PyList_GET_ITEM(heap, pos);\r
        PyList_SET_ITEM(heap, childpos, tmp2);\r
        PyList_SET_ITEM(heap, pos, tmp1);\r
        pos = childpos;\r
    }\r
    /* Bubble it up to its final resting place (by sifting its parents down). */\r
    return _siftdown(heap, startpos, pos);\r
}\r
\r
static PyObject *\r
heappush(PyObject *self, PyObject *args)\r
{\r
    PyObject *heap, *item;\r
\r
    if (!PyArg_UnpackTuple(args, "heappush", 2, 2, &heap, &item))\r
        return NULL;\r
\r
    if (!PyList_Check(heap)) {\r
        PyErr_SetString(PyExc_TypeError, "heap argument must be a list");\r
        return NULL;\r
    }\r
\r
    if (PyList_Append(heap, item) == -1)\r
        return NULL;\r
\r
    if (_siftdown((PyListObject *)heap, 0, PyList_GET_SIZE(heap)-1) == -1)\r
        return NULL;\r
    Py_INCREF(Py_None);\r
    return Py_None;\r
}\r
\r
PyDoc_STRVAR(heappush_doc,\r
"heappush(heap, item) -> None. Push item onto heap, maintaining the heap invariant.");\r
\r
static PyObject *\r
heappop(PyObject *self, PyObject *heap)\r
{\r
    PyObject *lastelt, *returnitem;\r
    Py_ssize_t n;\r
\r
    if (!PyList_Check(heap)) {\r
        PyErr_SetString(PyExc_TypeError, "heap argument must be a list");\r
        return NULL;\r
    }\r
\r
    /* # raises appropriate IndexError if heap is empty */\r
    n = PyList_GET_SIZE(heap);\r
    if (n == 0) {\r
        PyErr_SetString(PyExc_IndexError, "index out of range");\r
        return NULL;\r
    }\r
\r
    lastelt = PyList_GET_ITEM(heap, n-1) ;\r
    Py_INCREF(lastelt);\r
    PyList_SetSlice(heap, n-1, n, NULL);\r
    n--;\r
\r
    if (!n)\r
        return lastelt;\r
    returnitem = PyList_GET_ITEM(heap, 0);\r
    PyList_SET_ITEM(heap, 0, lastelt);\r
    if (_siftup((PyListObject *)heap, 0) == -1) {\r
        Py_DECREF(returnitem);\r
        return NULL;\r
    }\r
    return returnitem;\r
}\r
\r
PyDoc_STRVAR(heappop_doc,\r
"Pop the smallest item off the heap, maintaining the heap invariant.");\r
\r
static PyObject *\r
heapreplace(PyObject *self, PyObject *args)\r
{\r
    PyObject *heap, *item, *returnitem;\r
\r
    if (!PyArg_UnpackTuple(args, "heapreplace", 2, 2, &heap, &item))\r
        return NULL;\r
\r
    if (!PyList_Check(heap)) {\r
        PyErr_SetString(PyExc_TypeError, "heap argument must be a list");\r
        return NULL;\r
    }\r
\r
    if (PyList_GET_SIZE(heap) < 1) {\r
        PyErr_SetString(PyExc_IndexError, "index out of range");\r
        return NULL;\r
    }\r
\r
    returnitem = PyList_GET_ITEM(heap, 0);\r
    Py_INCREF(item);\r
    PyList_SET_ITEM(heap, 0, item);\r
    if (_siftup((PyListObject *)heap, 0) == -1) {\r
        Py_DECREF(returnitem);\r
        return NULL;\r
    }\r
    return returnitem;\r
}\r
\r
PyDoc_STRVAR(heapreplace_doc,\r
"heapreplace(heap, item) -> value. Pop and return the current smallest value, and add the new item.\n\\r
\n\\r
This is more efficient than heappop() followed by heappush(), and can be\n\\r
more appropriate when using a fixed-size heap.  Note that the value\n\\r
returned may be larger than item!  That constrains reasonable uses of\n\\r
this routine unless written as part of a conditional replacement:\n\n\\r
    if item > heap[0]:\n\\r
        item = heapreplace(heap, item)\n");\r
\r
static PyObject *\r
heappushpop(PyObject *self, PyObject *args)\r
{\r
    PyObject *heap, *item, *returnitem;\r
    int cmp;\r
\r
    if (!PyArg_UnpackTuple(args, "heappushpop", 2, 2, &heap, &item))\r
        return NULL;\r
\r
    if (!PyList_Check(heap)) {\r
        PyErr_SetString(PyExc_TypeError, "heap argument must be a list");\r
        return NULL;\r
    }\r
\r
    if (PyList_GET_SIZE(heap) < 1) {\r
        Py_INCREF(item);\r
        return item;\r
    }\r
\r
    cmp = cmp_lt(PyList_GET_ITEM(heap, 0), item);\r
    if (cmp == -1)\r
        return NULL;\r
    if (cmp == 0) {\r
        Py_INCREF(item);\r
        return item;\r
    }\r
\r
    returnitem = PyList_GET_ITEM(heap, 0);\r
    Py_INCREF(item);\r
    PyList_SET_ITEM(heap, 0, item);\r
    if (_siftup((PyListObject *)heap, 0) == -1) {\r
        Py_DECREF(returnitem);\r
        return NULL;\r
    }\r
    return returnitem;\r
}\r
\r
PyDoc_STRVAR(heappushpop_doc,\r
"heappushpop(heap, item) -> value. Push item on the heap, then pop and return the smallest item\n\\r
from the heap. The combined action runs more efficiently than\n\\r
heappush() followed by a separate call to heappop().");\r
\r
static PyObject *\r
heapify(PyObject *self, PyObject *heap)\r
{\r
    Py_ssize_t i, n;\r
\r
    if (!PyList_Check(heap)) {\r
        PyErr_SetString(PyExc_TypeError, "heap argument must be a list");\r
        return NULL;\r
    }\r
\r
    n = PyList_GET_SIZE(heap);\r
    /* Transform bottom-up.  The largest index there's any point to\r
       looking at is the largest with a child index in-range, so must\r
       have 2*i + 1 < n, or i < (n-1)/2.  If n is even = 2*j, this is\r
       (2*j-1)/2 = j-1/2 so j-1 is the largest, which is n//2 - 1.  If\r
       n is odd = 2*j+1, this is (2*j+1-1)/2 = j so j-1 is the largest,\r
       and that's again n//2-1.\r
    */\r
    for (i=n/2-1 ; i>=0 ; i--)\r
        if(_siftup((PyListObject *)heap, i) == -1)\r
            return NULL;\r
    Py_INCREF(Py_None);\r
    return Py_None;\r
}\r
\r
PyDoc_STRVAR(heapify_doc,\r
"Transform list into a heap, in-place, in O(len(heap)) time.");\r
\r
static PyObject *\r
nlargest(PyObject *self, PyObject *args)\r
{\r
    PyObject *heap=NULL, *elem, *iterable, *sol, *it, *oldelem;\r
    Py_ssize_t i, n;\r
    int cmp;\r
\r
    if (!PyArg_ParseTuple(args, "nO:nlargest", &n, &iterable))\r
        return NULL;\r
\r
    it = PyObject_GetIter(iterable);\r
    if (it == NULL)\r
        return NULL;\r
\r
    heap = PyList_New(0);\r
    if (heap == NULL)\r
        goto fail;\r
\r
    for (i=0 ; i<n ; i++ ){\r
        elem = PyIter_Next(it);\r
        if (elem == NULL) {\r
            if (PyErr_Occurred())\r
                goto fail;\r
            else\r
                goto sortit;\r
        }\r
        if (PyList_Append(heap, elem) == -1) {\r
            Py_DECREF(elem);\r
            goto fail;\r
        }\r
        Py_DECREF(elem);\r
    }\r
    if (PyList_GET_SIZE(heap) == 0)\r
        goto sortit;\r
\r
    for (i=n/2-1 ; i>=0 ; i--)\r
        if(_siftup((PyListObject *)heap, i) == -1)\r
            goto fail;\r
\r
    sol = PyList_GET_ITEM(heap, 0);\r
    while (1) {\r
        elem = PyIter_Next(it);\r
        if (elem == NULL) {\r
            if (PyErr_Occurred())\r
                goto fail;\r
            else\r
                goto sortit;\r
        }\r
        cmp = cmp_lt(sol, elem);\r
        if (cmp == -1) {\r
            Py_DECREF(elem);\r
            goto fail;\r
        }\r
        if (cmp == 0) {\r
            Py_DECREF(elem);\r
            continue;\r
        }\r
        oldelem = PyList_GET_ITEM(heap, 0);\r
        PyList_SET_ITEM(heap, 0, elem);\r
        Py_DECREF(oldelem);\r
        if (_siftup((PyListObject *)heap, 0) == -1)\r
            goto fail;\r
        sol = PyList_GET_ITEM(heap, 0);\r
    }\r
sortit:\r
    if (PyList_Sort(heap) == -1)\r
        goto fail;\r
    if (PyList_Reverse(heap) == -1)\r
        goto fail;\r
    Py_DECREF(it);\r
    return heap;\r
\r
fail:\r
    Py_DECREF(it);\r
    Py_XDECREF(heap);\r
    return NULL;\r
}\r
\r
PyDoc_STRVAR(nlargest_doc,\r
"Find the n largest elements in a dataset.\n\\r
\n\\r
Equivalent to:  sorted(iterable, reverse=True)[:n]\n");\r
\r
static int\r
_siftdownmax(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos)\r
{\r
    PyObject *newitem, *parent;\r
    int cmp;\r
    Py_ssize_t parentpos;\r
\r
    assert(PyList_Check(heap));\r
    if (pos >= PyList_GET_SIZE(heap)) {\r
        PyErr_SetString(PyExc_IndexError, "index out of range");\r
        return -1;\r
    }\r
\r
    newitem = PyList_GET_ITEM(heap, pos);\r
    Py_INCREF(newitem);\r
    /* Follow the path to the root, moving parents down until finding\r
       a place newitem fits. */\r
    while (pos > startpos){\r
        parentpos = (pos - 1) >> 1;\r
        parent = PyList_GET_ITEM(heap, parentpos);\r
        cmp = cmp_lt(parent, newitem);\r
        if (cmp == -1) {\r
            Py_DECREF(newitem);\r
            return -1;\r
        }\r
        if (cmp == 0)\r
            break;\r
        Py_INCREF(parent);\r
        Py_DECREF(PyList_GET_ITEM(heap, pos));\r
        PyList_SET_ITEM(heap, pos, parent);\r
        pos = parentpos;\r
    }\r
    Py_DECREF(PyList_GET_ITEM(heap, pos));\r
    PyList_SET_ITEM(heap, pos, newitem);\r
    return 0;\r
}\r
\r
static int\r
_siftupmax(PyListObject *heap, Py_ssize_t pos)\r
{\r
    Py_ssize_t startpos, endpos, childpos, rightpos, limit;\r
    int cmp;\r
    PyObject *newitem, *tmp;\r
\r
    assert(PyList_Check(heap));\r
    endpos = PyList_GET_SIZE(heap);\r
    startpos = pos;\r
    if (pos >= endpos) {\r
        PyErr_SetString(PyExc_IndexError, "index out of range");\r
        return -1;\r
    }\r
    newitem = PyList_GET_ITEM(heap, pos);\r
    Py_INCREF(newitem);\r
\r
    /* Bubble up the smaller child until hitting a leaf. */\r
    limit = endpos / 2;          /* smallest pos that has no child */\r
    while (pos < limit) {\r
        /* Set childpos to index of smaller child.   */\r
        childpos = 2*pos + 1;    /* leftmost child position  */\r
        rightpos = childpos + 1;\r
        if (rightpos < endpos) {\r
            cmp = cmp_lt(\r
                PyList_GET_ITEM(heap, rightpos),\r
                PyList_GET_ITEM(heap, childpos));\r
            if (cmp == -1) {\r
                Py_DECREF(newitem);\r
                return -1;\r
            }\r
            if (cmp == 0)\r
                childpos = rightpos;\r
        }\r
        /* Move the smaller child up. */\r
        tmp = PyList_GET_ITEM(heap, childpos);\r
        Py_INCREF(tmp);\r
        Py_DECREF(PyList_GET_ITEM(heap, pos));\r
        PyList_SET_ITEM(heap, pos, tmp);\r
        pos = childpos;\r
    }\r
\r
    /* The leaf at pos is empty now.  Put newitem there, and bubble\r
       it up to its final resting place (by sifting its parents down). */\r
    Py_DECREF(PyList_GET_ITEM(heap, pos));\r
    PyList_SET_ITEM(heap, pos, newitem);\r
    return _siftdownmax(heap, startpos, pos);\r
}\r
\r
static PyObject *\r
nsmallest(PyObject *self, PyObject *args)\r
{\r
    PyObject *heap=NULL, *elem, *iterable, *los, *it, *oldelem;\r
    Py_ssize_t i, n;\r
    int cmp;\r
\r
    if (!PyArg_ParseTuple(args, "nO:nsmallest", &n, &iterable))\r
        return NULL;\r
\r
    it = PyObject_GetIter(iterable);\r
    if (it == NULL)\r
        return NULL;\r
\r
    heap = PyList_New(0);\r
    if (heap == NULL)\r
        goto fail;\r
\r
    for (i=0 ; i<n ; i++ ){\r
        elem = PyIter_Next(it);\r
        if (elem == NULL) {\r
            if (PyErr_Occurred())\r
                goto fail;\r
            else\r
                goto sortit;\r
        }\r
        if (PyList_Append(heap, elem) == -1) {\r
            Py_DECREF(elem);\r
            goto fail;\r
        }\r
        Py_DECREF(elem);\r
    }\r
    n = PyList_GET_SIZE(heap);\r
    if (n == 0)\r
        goto sortit;\r
\r
    for (i=n/2-1 ; i>=0 ; i--)\r
        if(_siftupmax((PyListObject *)heap, i) == -1)\r
            goto fail;\r
\r
    los = PyList_GET_ITEM(heap, 0);\r
    while (1) {\r
        elem = PyIter_Next(it);\r
        if (elem == NULL) {\r
            if (PyErr_Occurred())\r
                goto fail;\r
            else\r
                goto sortit;\r
        }\r
        cmp = cmp_lt(elem, los);\r
        if (cmp == -1) {\r
            Py_DECREF(elem);\r
            goto fail;\r
        }\r
        if (cmp == 0) {\r
            Py_DECREF(elem);\r
            continue;\r
        }\r
\r
        oldelem = PyList_GET_ITEM(heap, 0);\r
        PyList_SET_ITEM(heap, 0, elem);\r
        Py_DECREF(oldelem);\r
        if (_siftupmax((PyListObject *)heap, 0) == -1)\r
            goto fail;\r
        los = PyList_GET_ITEM(heap, 0);\r
    }\r
\r
sortit:\r
    if (PyList_Sort(heap) == -1)\r
        goto fail;\r
    Py_DECREF(it);\r
    return heap;\r
\r
fail:\r
    Py_DECREF(it);\r
    Py_XDECREF(heap);\r
    return NULL;\r
}\r
\r
PyDoc_STRVAR(nsmallest_doc,\r
"Find the n smallest elements in a dataset.\n\\r
\n\\r
Equivalent to:  sorted(iterable)[:n]\n");\r
\r
static PyMethodDef heapq_methods[] = {\r
    {"heappush",        (PyCFunction)heappush,\r
        METH_VARARGS,           heappush_doc},\r
    {"heappushpop",     (PyCFunction)heappushpop,\r
        METH_VARARGS,           heappushpop_doc},\r
    {"heappop",         (PyCFunction)heappop,\r
        METH_O,                 heappop_doc},\r
    {"heapreplace",     (PyCFunction)heapreplace,\r
        METH_VARARGS,           heapreplace_doc},\r
    {"heapify",         (PyCFunction)heapify,\r
        METH_O,                 heapify_doc},\r
    {"nlargest",        (PyCFunction)nlargest,\r
        METH_VARARGS,           nlargest_doc},\r
    {"nsmallest",       (PyCFunction)nsmallest,\r
        METH_VARARGS,           nsmallest_doc},\r
    {NULL,              NULL}           /* sentinel */\r
};\r
\r
PyDoc_STRVAR(module_doc,\r
"Heap queue algorithm (a.k.a. priority queue).\n\\r
\n\\r
Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for\n\\r
all k, counting elements from 0.  For the sake of comparison,\n\\r
non-existing elements are considered to be infinite.  The interesting\n\\r
property of a heap is that a[0] is always its smallest element.\n\\r
\n\\r
Usage:\n\\r
\n\\r
heap = []            # creates an empty heap\n\\r
heappush(heap, item) # pushes a new item on the heap\n\\r
item = heappop(heap) # pops the smallest item from the heap\n\\r
item = heap[0]       # smallest item on the heap without popping it\n\\r
heapify(x)           # transforms list into a heap, in-place, in linear time\n\\r
item = heapreplace(heap, item) # pops and returns smallest item, and adds\n\\r
                               # new item; the heap size is unchanged\n\\r
\n\\r
Our API differs from textbook heap algorithms as follows:\n\\r
\n\\r
- We use 0-based indexing.  This makes the relationship between the\n\\r
  index for a node and the indexes for its children slightly less\n\\r
  obvious, but is more suitable since Python uses 0-based indexing.\n\\r
\n\\r
- Our heappop() method returns the smallest item, not the largest.\n\\r
\n\\r
These two make it possible to view the heap as a regular Python list\n\\r
without surprises: heap[0] is the smallest item, and heap.sort()\n\\r
maintains the heap invariant!\n");\r
\r
\r
PyDoc_STRVAR(__about__,\r
"Heap queues\n\\r
\n\\r