/**
 * CopyRight F. J. Madrid-Cuevas <fjmadrid@uco.es>
 *
 * Sólo se permite el uso de este código en la docencia de las asignaturas sobre
 * Estructuras de Datos de la Universidad de Córdoba.
 *
 * Está prohibido su uso para cualquier otro objetivo.
 */

#pragma once
#include <exception>
#include <cassert>
#include <algorithm>
#include <heap.hpp>

inline size_t parent(size_t i)
{
    assert(i > 0);
    return (i - 1) / 2;
}

inline size_t left(size_t i)
{
    return 2 * i + 1;
}

inline size_t right(size_t i)
{
    return 2 * i + 2;
}

template <class T>
void Heap<T>::shift_up(size_t i)
{
    while (i > 0)
    {
        size_t p = parent(i);
        if (comp_((*values_)[i], (*values_)[p]))
        {
            std::swap((*values_)[i], (*values_)[p]);
            i = p;
        }
        else
            break;
    }
}

template <class T>
void Heap<T>::shift_down(size_t i)
{
    while (true)
    {
        size_t best = i;
        size_t l = left(i);
        size_t r = right(i);
        if (l < last_item_ && comp_((*values_)[l], (*values_)[best]))
            best = l;
        if (r < last_item_ && comp_((*values_)[r], (*values_)[best]))
            best = r;
        if (best == i)
            break;
        std::swap((*values_)[i], (*values_)[best]);
        i = best;
    }
}

template <class T>
bool Heap<T>::is_a_heap(size_t root) const
{
    bool ret_val = true;
    size_t l = left(root);
    size_t r = right(root);
    if (l < last_item_)
    {
        if (!comp_((*values_)[root], (*values_)[l]))
            return false;
        if (!is_a_heap(l))
            return false;
    }
    if (r < last_item_)
    {
        if (!comp_((*values_)[root], (*values_)[r]))
            return false;
        if (!is_a_heap(r))
            return false;
    }
    return ret_val;
}

template <class T>
void Heap<T>::heapify()
{
    if (last_item_ == 0)
        return;
    for (int i = (int)(last_item_ / 2) - 1; i >= 0; --i)
        shift_down((size_t)i);
    assert(is_a_heap());
}

template <class T>
Heap<T>::Heap(std::vector<T> &values, Comp const &comp) : values_(&values), comp_(comp)
{
    last_item_ = values.size();
    heapify();
    assert(is_a_heap());
    assert(size() == values.size());
}

template <class T>
bool Heap<T>::is_empty() const
{
    return last_item_ == 0;
}

template <class T>
size_t Heap<T>::size() const
{
    return last_item_;
}

template <class T>
T const &Heap<T>::item() const
{
    assert(!is_empty());
    return (*values_)[0];
}

template <class T>
void Heap<T>::insert(T const &new_it)
{
#ifndef NDEBUG
    size_t old_size = size();
#endif
    if (last_item_ == values_->size())
        values_->push_back(new_it);
    else
        (*values_)[last_item_] = new_it;
    ++last_item_;
    shift_up(last_item_ - 1);
    assert(is_a_heap());
    assert(size() == old_size + 1);
}

template <class T>
void Heap<T>::remove()
{
#ifndef NDEBUG
    size_t old_size = size();
#endif
    assert(!is_empty());
    std::swap((*values_)[0], (*values_)[last_item_ - 1]);
    --last_item_;
    if (last_item_ > 0)
        shift_down(0);
    assert(is_a_heap());
    assert(size() == old_size - 1);
}

template <class T>
void heapsort(std::vector<T> &values, std::function<bool(T const &a, T const &b)> const &comp)
{
    size_t n = values.size();
    if (n <= 1)
        return;

    auto shift_down = [&](size_t i, size_t sz)
    {
        while (true)
        {
            size_t best = i;
            size_t l = left(i);
            size_t r = right(i);
            if (l < sz && comp(values[l], values[best]))
                best = l;
            if (r < sz && comp(values[r], values[best]))
                best = r;
            if (best == i)
                break;
            std::swap(values[i], values[best]);
            i = best;
        }
    };

    for (int i = (int)(n / 2) - 1; i >= 0; --i)
        shift_down((size_t)i, n);

    for (size_t i = n - 1; i > 0; --i)
    {
        std::swap(values[0], values[i]);
        shift_down(0, i);
    }

#ifndef NDEBUG
    for (size_t i = 1; i < values.size(); ++i)
        assert(comp(values[i], values[i - 1]));
#endif
}