# Original code by Kevin O'Connor, augmented by Tim Peters
# Translated to PyRex
__all__ = ['heappush', 'heappop', 'heapify', 'heapreplace']

cdef extern from "Python.h":
    int PyList_Check(object PyObj)
    int PyList_GET_SIZE(object PyList)
    int PyList_Append(object PyList, object val) except -1
    cdef int PyList_SET_ITEM(object PyList, int idx, object obj) except -1
    
    cdef void *PyList_GET_ITEM(object PyList, int idx) # except NULL
    cdef int PyList_SetSlice(object lst, int low, int high, void *items) except -1
    cdef void Py_INCREF(void *)
#    cdef object PySequence_GetItem(object PyList, int idx)
    ctypedef struct PyObject
    cdef int PyObject_RichCompareBool(o1, o2, int opid) except -1
    cdef int Py_LE

def heappush(heap, item):
    """Push item onto heap, maintaining the heap invariant."""
    assert PyList_Check(heap)
    PyList_Append(heap, item)
    _siftdown(heap, 0, PyList_GET_SIZE(heap)-1)

def heappop(sequence heap):
    """Pop the smallest item off the heap, maintaining the heap invariant."""
    cdef int length
    assert PyList_Check(heap)
    length = PyList_GET_SIZE(heap)
    assert length > 0
    lastelt = popListItem(heap, length)
    length = length - 1;
    if length > 0:
        returnitem = getListItem(heap,0)
        setListItem(heap, 0, lastelt)
        _siftup(heap, 0, length)
    else:
        returnitem = lastelt
    return returnitem

def heapreplace(heap, item):
    """Pop and return the current smallest value, and add the new item.

    This is more efficient than heappop() followed by heappush(), and can be
    more appropriate when using a fixed-size heap.  Note that the value
    returned may be larger than item!  That constrains reasonable uses of
    this routine.
    """
    assert PyList_Check(heap)
    returnitem = getListItem(heap,0) # raises appropriate IndexError if heap is empty
    setListItem(heap,0, item)
    _siftup(heap, 0, PyList_GET_SIZE(heap))
    return returnitem

def heapify(sequence heap):
    """Transform list into a heap, in-place, in O(len(heap)) time."""
    cdef int n, i 
    assert PyList_Check(heap)
    n = PyList_GET_SIZE(heap)
    # Transform bottom-up.  The largest index there's any point to looking at
    # is the largest with a child index in-range, so must have 2*i + 1 < n,
    # or i < (n-1)/2.  If n is even = 2*j, this is (2*j-1)/2 = j-1/2 so
    # j-1 is the largest, which is n//2 - 1.  If n is odd = 2*j+1, this is
    # (2*j+1-1)/2 = j so j-1 is the largest, and that's again n//2-1.
    for i from n/2 - 1 >= i > -1:
        _siftup(heap, i, n)

# 'heap' is a heap at all indices >= startpos, except possibly for pos.  pos
# is the index of a leaf with a possibly out-of-order value.  Restore the
# heap invariant.


cdef int _siftdown(sequence heap, int startpos, int pos) except -1:
    cdef int parentpos

    newitem = getListItem(heap,pos)
    # Follow the path to the root, moving parents down until finding a place
    # newitem fits.
    while pos > startpos:
        parentpos = (pos - 1) >> 1
        parent = getListItem(heap,parentpos)
        if PyObject_RichCompareBool(parent, newitem, Py_LE):
            break
        setListItem(heap,pos,parent)
        pos = parentpos
    setListItem(heap,pos,newitem)
    return 0

cdef int _siftup(sequence heap, int pos, int endpos) except -1:
    cdef int startpos, childpos, rightpos

    startpos = pos
    newitem = getListItem(heap,pos)
    # Bubble up the smaller child until hitting a leaf.
    childpos = 2*pos + 1    # leftmost child position
    while childpos < endpos:
        # Set childpos to index of smaller child.
        rightpos = childpos + 1
        if rightpos < endpos and \
		PyObject_RichCompareBool( getListItem(heap,rightpos), getListItem(heap,childpos), Py_LE):
            childpos = rightpos
        # Move the smaller child up.
        setListItem(heap,pos,getListItem(heap,childpos))
        pos = childpos
        childpos = 2*pos + 1
    # The leaf at pos is empty now.  Put newitem there, and and bubble it up
    # to its final resting place (by sifting its parents down).
    setListItem(heap,pos,newitem)
    _siftdown(heap, startpos, pos)

cdef int setListItem(object PyList, int idx, object obj) except -1:
    Py_INCREF(<PyObject *>obj)
    PyList_SET_ITEM(PyList, idx, obj)

cdef object getListItem(object PyList, int idx):
    return <object>PyList_GET_ITEM(PyList, idx)

from sys import getrefcount

cdef object popListItem(object lst, int length):
    cdef object lastelt
    lastelt = <object>PyList_GET_ITEM(lst, length-1)
    PyList_SetSlice(lst, length-1, length, NULL)
    return lastelt