/**
 * 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>

/**
 * @brief Compute the parent's index of a given child.
 *
 * @param i is the index of the child in the heap.
 * @return size_t
 */
inline size_t parent(size_t i)
{
    assert(i > 0);
    return (i - 1) / 2;
}

/**
 * @brief Compute the left child's index of a given parent.
 *
 * @param i is the index of the parent in the heap.
 * @return the index of the left child.
 */
inline size_t left(size_t i)
{
    return 2 * i + 1;
}

/**
 * @brief Compute the right child's index of a given parent.
 *
 * @param i is the index of the parent in the heap.
 * @return the index of the right child.
 */
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 && comp_((*values_)[i], (*values_)[parent(i)])) {
        std::swap((*values_)[i], (*values_)[parent(i)]);
        i = parent(i);
    }
}

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

template <class T>
bool Heap<T>::is_a_heap(size_t root) const
{
    if (root >= last_item_) return 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 true;
}

template <class T>
void Heap<T>::heapify()
{
    if (last_item_ > 1) {
        for (int i = static_cast<int>(parent(last_item_ - 1)); i >= 0; --i) {
            shift_down(static_cast<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_)[last_item_] = new_it;
    } else {
        values_->push_back(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)
{
    Heap<T> heap(values, comp);
    while (heap.size() > 0) {
        heap.remove();
    }
#ifndef NDEBUG
    for (size_t i = 1; i < values.size(); ++i)
        assert(comp(values[i], values[i - 1]));
#endif
}