summaryrefslogtreecommitdiff
path: root/boost/sort/common/rearrange.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/sort/common/rearrange.hpp')
-rw-r--r--boost/sort/common/rearrange.hpp168
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