//----------------------------------------------------------------------------
/// @file indirect.hpp
/// @brief Indirect 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_PARALLEL_COMMON_INDIRECT_HPP
#define __BOOST_SORT_PARALLEL_COMMON_INDIRECT_HPP

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

namespace boost
{
namespace sort
{
namespace common
{

//
//---------------------------------------------------------------------------
/// @struct less_ptr_no_null
///
/// @remarks this is the comparison object for pointers. Compare the objects
///          pointed by the iterators
//---------------------------------------------------------------------------
template<class Iter_t, class Compare = util::compare_iter<Iter_t> >
struct less_ptr_no_null
{
    //----------------------------- Variables -----------------------
    Compare comp; // comparison object of the elements pointed by Iter_t

    //------------------------------------------------------------------------
    //  function : less_ptr_no_null
    /// @brief constructor from a Compare object
    /// @param C1 : comparison object
    //-----------------------------------------------------------------------
    less_ptr_no_null(Compare C1 = Compare()): comp(C1) { };

    //------------------------------------------------------------------------
    //  function : operator ( )
    /// @brief Make the comparison of the objects pointed by T1 and T2, using
    //         the internal comp
    //
    /// @param  T1 : first iterator
    /// @param  T2 : second iterator
    /// @return bool result of the comparison
    //-----------------------------------------------------------------------
    bool operator( )(Iter_t T1, Iter_t T2) const
    {
        return comp(*T1, *T2);
    };
};
//
//-----------------------------------------------------------------------------
//  function : create_index
/// @brief From a vector of objects, create a vector of iterators to
///        the objects
///
/// @param first : iterator to the first element of the range
/// @param last : iterator to the element after the last of the range
/// @param index : vector where store the iterators
//-----------------------------------------------------------------------------
template<class Iter_t>
void create_index(Iter_t first, Iter_t last, std::vector<Iter_t> &index)
{
    auto nelem = last - first;
    assert(nelem >= 0);
    index.clear();
    index.reserve(nelem);
    for (; first != last; ++first) index.push_back(first);
};
//
//-----------------------------------------------------------------------------
//  function : sort_index
/// @brief This function transform a logical sort of the elements in the index
///        in a physical sort
//
/// @param global_first : iterator to the first element of the data
/// @param [in] index : vector of the iterators
//-----------------------------------------------------------------------------
template<class Iter_t>
void sort_index(Iter_t global_first, std::vector<Iter_t> &index)
{
    typedef util::value_iter<Iter_t> value_t;

    size_t pos_dest = 0;
    size_t pos_src = 0;
    size_t pos_in_vector = 0;
    size_t nelem = index.size();
    Iter_t it_dest, it_src;

    while (pos_in_vector < nelem)
    {
        while (pos_in_vector < nelem and
               (size_t(index[pos_in_vector] - global_first)) == pos_in_vector)
        {
            ++pos_in_vector;
        };

        if (pos_in_vector == nelem) return;
        pos_dest = pos_src = pos_in_vector;
        it_dest = global_first + pos_dest;
        value_t Aux = std::move(*it_dest);

        while ((pos_src = (size_t(index[pos_dest] - global_first)))
               != pos_in_vector)
        {
            index[pos_dest] = it_dest;
            it_src = global_first + pos_src;
            *it_dest = std::move(*it_src);
            it_dest = it_src;
            pos_dest = pos_src;
        };

        *it_dest = std::move(Aux);
        index[pos_dest] = it_dest;
        ++pos_in_vector;
    };
};

template<class func, class Iter_t, class Compare = util::compare_iter<Iter_t> >
void indirect_sort(func method, Iter_t first, Iter_t last, Compare comp)
{
    auto nelem = (last - first);
    assert(nelem >= 0);
    if (nelem < 2) return;
    std::vector<Iter_t> index;
    index.reserve((size_t) nelem);
    create_index(first, last, index);
    less_ptr_no_null<Iter_t, Compare> index_comp(comp);
    method(index.begin(), index.end(), index_comp);
    sort_index(first, index);
};

//
//****************************************************************************
};//    End namespace common
};//    End namespace sort
};//    End namespace boost
//****************************************************************************
//
#endif