# tag: cpp

from libcpp cimport bool
from libcpp.algorithm cimport make_heap, sort_heap, sort, partial_sort
from libcpp.vector cimport vector


# XXX should use std::greater, but I don't know how to wrap that.
cdef inline bool greater(int x, int y):
    return x > y


def heapsort(l, bool reverse=False):
    """
    >>> heapsort([3, 5, 1, 0, 2, 4])
    [0, 1, 2, 3, 4, 5]
    >>> heapsort([3, 5, 1, 0, 2, 4], reverse=True)
    [5, 4, 3, 2, 1, 0]
    """
    cdef vector[int] v = l

    if reverse:
        make_heap(v.begin(), v.end(), greater)
        sort_heap(v.begin(), v.end(), greater)
    else:
        make_heap(v.begin(), v.end())
        sort_heap(v.begin(), v.end())

    return v


def partialsort(l, int k, reverse=False):
    """
    >>> partialsort([4, 2, 3, 1, 5], k=2)[:2]
    [1, 2]
    >>> partialsort([4, 2, 3, 1, 5], k=2, reverse=True)[:2]
    [5, 4]
    """
    cdef vector[int] v = l
    if reverse:
        partial_sort(v.begin(), v.begin() + k, v.end(), greater)
    else:
        partial_sort(v.begin(), v.begin() + k, v.end())
    return v


def stdsort(l, reverse=False):
    """
    >>> stdsort([3, 2, 1, 4, 5])
    [1, 2, 3, 4, 5]
    >>> stdsort([3, 2, 1, 4, 5], reverse=True)
    [5, 4, 3, 2, 1]
    """
    cdef vector[int] v = l
    if reverse:
        sort(v.begin(), v.end(), greater)
    else:
        sort(v.begin(), v.end())
    return v