1 files changed, 168 insertions, 0 deletions
diff --git a/boost/sort/common/rearrange.hpp b/boost/sort/common/rearrange.hpp
new file mode 100644
index 0000000000..5c65c4f2b7
--- /dev/null
+++ b/boost/sort/common/rearrange.hpp
@@ -0,0 +1,168 @@
+//----------------------------------------------------------------------------
+/// @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