//----------------------------------------------------------------------------
/// @file parallel_stable_sort.hpp
/// @brief This file contains the class parallel_stable_sort
///
/// @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_PARALLEL_DETAIL_PARALLEL_STABLE_SORT_HPP
#define __BOOST_SORT_PARALLEL_DETAIL_PARALLEL_STABLE_SORT_HPP

#include <boost/sort/sample_sort/sample_sort.hpp>
#include <boost/sort/common/util/traits.hpp>
#include <functional>
#include <future>
#include <iterator>
#include <memory>
#include <type_traits>
#include <vector>

namespace boost
{
namespace sort
{
namespace stable_detail
{

//---------------------------------------------------------------------------
//                    USING SENTENCES
//---------------------------------------------------------------------------
namespace bsc = boost::sort::common;
namespace bss = boost::sort::spin_detail;
using bsc::range;
using bsc::merge_half;
using boost::sort::sample_detail::sample_sort;
//
///---------------------------------------------------------------------------
/// @struct parallel_stable_sort
/// @brief This a structure for to implement a parallel stable sort, exception
///        safe
//----------------------------------------------------------------------------
template <class Iter_t, class Compare = compare_iter <Iter_t> >
struct parallel_stable_sort
{
    //-------------------------------------------------------------------------
    //                      DEFINITIONS
    //-------------------------------------------------------------------------
    typedef value_iter<Iter_t> value_t;

    //-------------------------------------------------------------------------
    //                     VARIABLES
    //-------------------------------------------------------------------------
    // Number of elements to sort
    size_t nelem;
    // Pointer to the auxiliary memory needed for the algorithm
    value_t *ptr;
    // Minimal number of elements for to be sorted in parallel mode
    const size_t nelem_min = 1 << 16;

    //------------------------------------------------------------------------
    //                F U N C T I O N S
    //------------------------------------------------------------------------
    parallel_stable_sort (Iter_t first, Iter_t last)
    : parallel_stable_sort (first, last, Compare(),
                            std::thread::hardware_concurrency()) { };

    parallel_stable_sort (Iter_t first, Iter_t last, Compare cmp)
    : parallel_stable_sort (first, last, cmp,
                            std::thread::hardware_concurrency()) { };

    parallel_stable_sort (Iter_t first, Iter_t last, uint32_t num_thread)
    : parallel_stable_sort (first, last, Compare(), num_thread) { };

    parallel_stable_sort (Iter_t first, Iter_t last, Compare cmp,
                          uint32_t num_thread);

    //
    //-----------------------------------------------------------------------------
    //  function : destroy_all
    /// @brief The utility is to destroy the temporary buffer used in the
    ///        sorting process
    //-----------------------------------------------------------------------------
    void destroy_all()
    {
        if (ptr != nullptr) std::return_temporary_buffer(ptr);
    };
    //
    //-----------------------------------------------------------------------------
    //  function :~parallel_stable_sort
    /// @brief destructor of the class. The utility is to destroy the temporary
    ///        buffer used in the sorting process
    //-----------------------------------------------------------------------------
    ~parallel_stable_sort() {destroy_all(); } ;
};
// end struct parallel_stable_sort

//
//############################################################################
//                                                                          ##
//                                                                          ##
//            N O N     I N L I N E      F U N C T I O N S                  ##
//                                                                          ##
//                                                                          ##
//############################################################################
//
//-----------------------------------------------------------------------------
//  function : parallel_stable_sort
/// @brief constructor of the class
///
/// @param first : iterator to the first element of the range to sort
/// @param last : iterator after the last element to the range to sort
/// @param comp : object for to compare two elements pointed by Iter_t
///                    iterators
/// @param nthread : Number of threads to use in the process. When this value
///                  is lower than 2, the sorting is done with 1 thread
//-----------------------------------------------------------------------------
template <class Iter_t, class Compare>
parallel_stable_sort <Iter_t, Compare>
::parallel_stable_sort (Iter_t first, Iter_t last, Compare comp,
                        uint32_t nthread) : nelem(0), ptr(nullptr)
{
    range<Iter_t> range_initial(first, last);
    assert(range_initial.valid());

    nelem = range_initial.size();
    size_t nptr = (nelem + 1) >> 1;

    if (nelem < nelem_min or nthread < 2)
    {
        bss::spinsort<Iter_t, Compare>
            (range_initial.first, range_initial.last, comp);
        return;
    };

    //------------------- check if sort --------------------------------------
    bool sw = true;
    for (Iter_t it1 = first, it2 = first + 1;
         it2 != last and (sw = not comp(*it2, *it1)); it1 = it2++);
    if (sw) return;

    //------------------- check if reverse sort ---------------------------
    sw = true;
    for (Iter_t it1 = first, it2 = first + 1;
         it2 != last and (sw = comp(*it2, *it1)); it1 = it2++);
    if (sw)
    {
        size_t nelem2 = nelem >> 1;
        Iter_t it1 = first, it2 = last - 1;
        for (size_t i = 0; i < nelem2; ++i)
            std::swap(*(it1++), *(it2--));
        return;
    };

    ptr = std::get_temporary_buffer<value_t>(nptr).first;
    if (ptr == nullptr) throw std::bad_alloc();

    //---------------------------------------------------------------------
    //     Parallel Process
    //---------------------------------------------------------------------
    range<Iter_t> range_first(range_initial.first, range_initial.first + nptr);

    range<Iter_t> range_second(range_initial.first + nptr, range_initial.last);

    range<value_t *> range_buffer(ptr, ptr + nptr);

    try
    {
        sample_sort<Iter_t, Compare>
            (range_initial.first, range_initial.first + nptr,
             comp, nthread, range_buffer);
    } catch (std::bad_alloc &)
    {
        destroy_all();
        throw std::bad_alloc();
    };

    try
    {
        sample_sort<Iter_t, Compare>
            (range_initial.first + nptr,
             range_initial.last, comp, nthread, range_buffer);
    } catch (std::bad_alloc &)
    {
        destroy_all();
        throw std::bad_alloc();
    };

    range_buffer = move_forward(range_buffer, range_first);
    range_initial = merge_half(range_initial, range_buffer, range_second, comp);
}; // end of constructor

//
//****************************************************************************
};//    End namespace stable_detail
//****************************************************************************
//

//---------------------------------------------------------------------------
//                    USING SENTENCES
//---------------------------------------------------------------------------
namespace bsc = boost::sort::common;
namespace bscu = bsc::util;
namespace bss = boost::sort::spin_detail;
using bsc::range;
using bsc::merge_half;
//
//############################################################################
//                                                                          ##
//                                                                          ##
//            P A R A L L E L _ S T A B L E _ S O R T                       ##
//                                                                          ##
//                                                                          ##
//############################################################################
//
//-----------------------------------------------------------------------------
//  function : parallel_stable_sort
/// @brief : parallel stable sort with 2 parameters
///
/// @param first : iterator to the first element of the range to sort
/// @param last : iterator after the last element to the range to sort
//-----------------------------------------------------------------------------
template<class Iter_t>
void parallel_stable_sort(Iter_t first, Iter_t last)
{
    typedef bscu::compare_iter<Iter_t> Compare;
    stable_detail::parallel_stable_sort<Iter_t, Compare>(first, last);
};
//
//-----------------------------------------------------------------------------
//  function : parallel_stable_sort
/// @brief parallel stable sort with 3 parameters. The third is the number 
///        of threads
///
/// @param first : iterator to the first element of the range to sort
/// @param last : iterator after the last element to the range to sort
/// @param nthread : Number of threads to use in the process. When this value
///                  is lower than 2, the sorting is done with 1 thread
//-----------------------------------------------------------------------------
template<class Iter_t>
void parallel_stable_sort(Iter_t first, Iter_t last, uint32_t nthread)
{
    typedef bscu::compare_iter<Iter_t> Compare;
    stable_detail::parallel_stable_sort<Iter_t, Compare>(first, last, nthread);
};
//
//-----------------------------------------------------------------------------
//  function : parallel_stable_sort
/// @brief : parallel stable sort with 3 parameters. The thisrd is the 
///          comparison object
///
/// @param first : iterator to the first element of the range to sort
/// @param last : iterator after the last element to the range to sort
/// @param comp : object for to compare two elements pointed by Iter_t
///               iterators
//-----------------------------------------------------------------------------
template <class Iter_t, class Compare,
          bscu::enable_if_not_integral<Compare> * = nullptr>
void parallel_stable_sort(Iter_t first, Iter_t last, Compare comp)
{
    stable_detail::parallel_stable_sort<Iter_t, Compare>(first, last, comp);
};

//
//-----------------------------------------------------------------------------
//  function : parallel_stable_sort
/// @brief : parallel stable sort with 3 parameters. 
///
/// @param first : iterator to the first element of the range to sort
/// @param last : iterator after the last element to the range to sort
/// @param comp : object for to compare two elements pointed by Iter_t
///               iterators
/// @param nthread : Number of threads to use in the process. When this value
///                  is lower than 2, the sorting is done with 1 thread
//-----------------------------------------------------------------------------
template<class Iter_t, class Compare>
void parallel_stable_sort (Iter_t first, Iter_t last, Compare comp,
                          uint32_t nthread)
{
    stable_detail::parallel_stable_sort<Iter_t, Compare>
                                                (first, last, comp, nthread);
}
//
//****************************************************************************
};//    End namespace sort
};//    End namespace boost
//****************************************************************************
//
#endif