//----------------------------------------------------------------------------
/// @file rearrange.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_COMMON_REARRANGE_HPP
#define __BOOST_SORT_COMMON_REARRANGE_HPP

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

namespace boost
{
namespace sort
{
namespace common
{

template<class Iter_data>
struct filter_iterator
{
    //-----------------------------------------------------------------------
    //                   Variables
    //-----------------------------------------------------------------------
    Iter_data origin;

    //-----------------------------------------------------------------------
    //                   Functions
    //-----------------------------------------------------------------------
    filter_iterator(Iter_data global_first): origin(global_first) { };
    size_t operator ()(Iter_data itx) const
    {
        return size_t(itx - origin);
    }
};

struct filter_pos
{
    size_t operator ()(size_t pos) const {  return pos; };
};

//
//-----------------------------------------------------------------------------
//  function : rearrange
/// @brief This function transform a logical sort of the elements in the index  
///        of iterators 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_data, class Iter_index, class Filter_pos>
void rearrange(Iter_data global_first, Iter_index itx_first,
               Iter_index itx_last, Filter_pos pos)
{
    //-----------------------------------------------------------------------
    //                    Metaprogramming
    //-----------------------------------------------------------------------
    typedef util::value_iter<Iter_data>     value_data;
    typedef util::value_iter<Iter_index>    value_index;

    //-------------------------------------------------------------------------
    //                     Code
    //-------------------------------------------------------------------------	
    assert((itx_last - itx_first) >= 0);
    size_t pos_dest, pos_src, pos_ini;
    size_t nelem = size_t(itx_last - itx_first);
    Iter_data data = global_first;
    Iter_index index = itx_first;

    pos_ini = 0;
    while (pos_ini < nelem)
    {
        while (pos_ini < nelem and pos(index[pos_ini]) == pos_ini)
            ++pos_ini;
        if (pos_ini == nelem) return;
        pos_dest = pos_src = pos_ini;
        value_data aux = std::move(data[pos_ini]);
        value_index itx_src = std::move(index[pos_ini]);

        while ((pos_src = pos(itx_src)) != pos_ini)
        {
            data[pos_dest] = std::move(data[pos_src]);
            std::swap(itx_src, index[pos_src]);
            pos_dest = pos_src;
        };

        data[pos_dest] = std::move(aux);
        index[pos_ini] = std::move(itx_src);
        ++pos_ini;
    };
};

/*
 //
 //-----------------------------------------------------------------------------
 //  function : rearrange_pos
 /// @brief This function transform a logical sort of the elements in the index  
 ///        of iterators 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, class Number >
 void rearrange_pos (Iter_t global_first, std::vector< Number> &index)
 {	
 //-------------------------------------------------------------------------
 //          METAPROGRAMMING AND DEFINITIONS
 //-------------------------------------------------------------------------
 static_assert ( std::is_integral<Number>::value, "Incompatible Types");
 typedef iter_value< Iter_t > value_t;

 //-------------------------------------------------------------------------
 //                     CODE
 //-------------------------------------------------------------------------
 size_t pos_dest = 0;
 size_t pos_src = 0;
 size_t pos_ini = 0;
 size_t nelem = index.size ( );
 Iter_t it_dest (global_first), it_src(global_first);

 while (pos_ini < nelem)
 {
 while (pos_ini < nelem and
 index[pos_ini] == pos_ini)
 {
 ++pos_ini;
 };

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

 while ((pos_src = index[pos_dest]) != pos_ini)
 {
 index[pos_dest] = it_dest - global_first;
 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 - global_first;
 ++pos_ini;
 };
 };
 */
//
//****************************************************************************
};//    End namespace common
};//    End namespace sort
};//    End namespace boost
//****************************************************************************
//
#endif