//----------------------------------------------------------------------------
/// @file heap_sort.hpp
/// @brief Insertion Sort algorithm
///
/// @author Copyright (c) 2016 Francisco Jose Tapia (fjtapia@gmail.com )\n
///         Distributed under the Boost Software License, Version 1.0.\n
///         ( See accompanying file LICENSE_1_0.txt or copy at
///           http://www.boost.org/LICENSE_1_0.txt  )
/// @version 0.1
///
/// @remarks
//-----------------------------------------------------------------------------
#ifndef __BOOST_SORT_INTROSORT_DETAIL_HEAP_SORT_HPP
#define __BOOST_SORT_INTROSORT_DETAIL_HEAP_SORT_HPP

#include <cassert>
#include <cstdint>
#include <iterator>
#include <stdexcept>
#include <utility> // for std::swap
#include <boost/sort/common/util/traits.hpp>

namespace boost
{
namespace sort
{
namespace heap_detail
{
namespace bscu = boost::sort::common::util;
//
//---------------------------------------------------------------------------
//  struct : heap_sort
/// @brief : Heap sort algorithm
/// @remarks This algorithm is O(NLogN)
//---------------------------------------------------------------------------
template < class Iter_t, class Compare >
struct heap_sort
{
    typedef bscu::value_iter<Iter_t> value_t;

    //
    //------------------------------------------------------------------------
    //  function : sort3
    /// @brief Sort and signal the changes of three values
    /// @param val_0 : first value to compare
    /// @param val_1 : second value to compare
    /// @param val_2 : third value to compare
    /// @param [out] bool_0 : if true indicates val_0 had been changed
    /// @param [out] bool_1 : if true indicates val_1 had been changed
    /// @param [out] bool_2 : if true indicates val_2 had been changed
    /// @return if true , some value had changed
    /// @remarks
    //------------------------------------------------------------------------
    bool sort3 (value_t &val_0, value_t &val_1, value_t &val_2, bool &bool_0,
                bool &bool_1, bool &bool_2)
    {
        bool_0 = bool_1 = bool_2 = false;
        int value = 0;
        if (val_0 < val_1) value += 4;
        if (val_1 < val_2) value += 2;
        if (val_0 < val_2) value += 1;

        switch (value)
        {
            case 0: break;

            case 2:
                std::swap (val_1, val_2);
                bool_1 = bool_2 = true;
                break;

            case 3:
                if (not(val_0 > val_1)) {
                    std::swap (val_0, val_2);
                    bool_0 = bool_2 = true;
                }
                else
                {
                    auto aux = std::move (val_2);
                    val_2 = std::move (val_1);
                    val_1 = std::move (val_0);
                    val_0 = std::move (aux);
                    bool_0 = bool_1 = bool_2 = true;
                };
                break;

            case 4:
                std::swap (val_0, val_1);
                bool_0 = bool_1 = true;
                break;

            case 5:
                if (val_1 > val_2) {
                    auto aux = std::move (val_0);
                    val_0 = std::move (val_1);
                    val_1 = std::move (val_2);
                    val_2 = std::move (aux);
                    bool_0 = bool_1 = bool_2 = true;
                }
                else
                {
                    std::swap (val_0, val_2);
                    bool_0 = bool_2 = true;
                };
                break;

            case 7:
                std::swap (val_0, val_2);
                bool_0 = bool_2 = true;
                break;

            default: abort ( );
        };
        return (bool_0 or bool_1 or bool_2);
    };
    //
    //-----------------------------------------------------------------------
    //  function : make_heap
    /// @brief Make the heap for to extract the sorted elements
    /// @param first : iterator to the first element of the range
    /// @param nelem : number of lements of the range
    /// @param comp : object for to compare two elements
    /// @remarks This algorithm is O(NLogN)
    //------------------------------------------------------------------------
    void make_heap (Iter_t first, size_t nelem, Compare comp)
    {
        size_t pos_father, pos_son;
        Iter_t iter_father = first, iter_son = first;
        bool sw = false;

        for (size_t i = 1; i < nelem; ++i)
        {
            pos_father = i;
            iter_father = first + i;
            sw = false;
            do
            {
                iter_son = iter_father;
                pos_son = pos_father;
                pos_father = (pos_son - 1) >> 1;
                iter_father = first + pos_father;
                if ((sw = comp (*iter_father, *iter_son)))
                    std::swap (*iter_father, *iter_son);
            } while (sw and pos_father != 0);
        };
    };
    //
    //------------------------------------------------------------------------
    //  function : heap_sort
    /// @brief : Heap sort algorithm
    /// @param first: iterator to the first element of the range
    /// @param last : iterator to the next element of the last in the range
    /// @param comp : object for to do the comparison between the elements
    /// @remarks This algorithm is O(NLogN)
    //------------------------------------------------------------------------
    heap_sort (Iter_t first, Iter_t last, Compare comp)
    {
        assert ((last - first) >= 0);
        size_t nelem = last - first;
        if (nelem < 2) return;

        //--------------------------------------------------------------------
        // Creating the initial heap
        //--------------------------------------------------------------------
        make_heap (first, nelem, comp);

        //--------------------------------------------------------------------
        //  Sort the heap
        //--------------------------------------------------------------------
        size_t pos_father, pos_son;
        Iter_t iter_father = first, iter_son = first;

        bool sw = false;
        for (size_t i = 1; i < nelem; ++i)
        {
            std::swap (*first, *(first + (nelem - i)));
            pos_father = 0;
            pos_son = 1;
            iter_father = first;
            sw = true;
            while (sw and pos_son < (nelem - i))
            {
                // if the father have two sons must select the bigger
                iter_son = first + pos_son;
                if ((pos_son + 1) < (nelem - i) and
                    comp (*iter_son, *(iter_son + 1)))
                {
                    ++pos_son;
                    ++iter_son;
                };
                if ((sw = comp (*iter_father, *iter_son)))
                    std::swap (*iter_father, *iter_son);
                pos_father = pos_son;
                iter_father = iter_son;
                pos_son = (pos_father << 1) + 1;
            };
        };
    };
}; // End class heap_sort
}; // end namespace heap_sort

namespace bscu = boost::sort::common::util;

template < class Iter_t, typename Compare = bscu::compare_iter < Iter_t > >
void heap_sort (Iter_t first, Iter_t last, Compare comp = Compare())
{
	heap_detail::heap_sort<Iter_t, Compare> ( first, last, comp);
}
//
//****************************************************************************
}; //    End namespace sort
}; //    End namespace boost
//****************************************************************************
//
#endif