1 //----------------------------------------------------------------------------
2 /// @file rearrange.hpp
3 /// @brief Indirect algorithm
4 ///
5 /// @author Copyright (c) 2016 Francisco Jose Tapia (fjtapia@gmail.com )\n
6 /// Distributed under the Boost Software License, Version 1.0.\n
7 /// ( See accompanying file LICENSE_1_0.txt or copy at
8 /// http://www.boost.org/LICENSE_1_0.txt )
9 /// @version 0.1
10 ///
11 /// @remarks
12 //-----------------------------------------------------------------------------
13 #ifndef __BOOST_SORT_COMMON_REARRANGE_HPP
14 #define __BOOST_SORT_COMMON_REARRANGE_HPP
15
16 //#include <boost/sort/common/atomic.hpp>
17 #include <boost/sort/common/util/traits.hpp>
18 #include <functional>
19 #include <iterator>
20 #include <type_traits>
21 #include <vector>
22 #include <cassert>
23
24 namespace boost
25 {
26 namespace sort
27 {
28 namespace common
29 {
30
31 template<class Iter_data>
32 struct filter_iterator
33 {
34 //-----------------------------------------------------------------------
35 // Variables
36 //-----------------------------------------------------------------------
37 Iter_data origin;
38
39 //-----------------------------------------------------------------------
40 // Functions
41 //-----------------------------------------------------------------------
filter_iteratorboost::sort::common::filter_iterator42 filter_iterator(Iter_data global_first): origin(global_first) { };
operator ()boost::sort::common::filter_iterator43 size_t operator ()(Iter_data itx) const
44 {
45 return size_t(itx - origin);
46 }
47 };
48
49 struct filter_pos
50 {
operator ()boost::sort::common::filter_pos51 size_t operator ()(size_t pos) const { return pos; };
52 };
53
54 //
55 //-----------------------------------------------------------------------------
56 // function : rearrange
57 /// @brief This function transform a logical sort of the elements in the index
58 /// of iterators in a physical sort.
59 //
60 /// @param global_first : iterator to the first element of the data
61 /// @param [in] index : vector of the iterators
62 //-----------------------------------------------------------------------------
63 template<class Iter_data, class Iter_index, class Filter_pos>
rearrange(Iter_data global_first,Iter_index itx_first,Iter_index itx_last,Filter_pos pos)64 void rearrange(Iter_data global_first, Iter_index itx_first,
65 Iter_index itx_last, Filter_pos pos)
66 {
67 //-----------------------------------------------------------------------
68 // Metaprogramming
69 //-----------------------------------------------------------------------
70 typedef util::value_iter<Iter_data> value_data;
71 typedef util::value_iter<Iter_index> value_index;
72
73 //-------------------------------------------------------------------------
74 // Code
75 //-------------------------------------------------------------------------
76 assert((itx_last - itx_first) >= 0);
77 size_t pos_dest, pos_src, pos_ini;
78 size_t nelem = size_t(itx_last - itx_first);
79 Iter_data data = global_first;
80 Iter_index index = itx_first;
81
82 pos_ini = 0;
83 while (pos_ini < nelem)
84 {
85 while (pos_ini < nelem and pos(index[pos_ini]) == pos_ini)
86 ++pos_ini;
87 if (pos_ini == nelem) return;
88 pos_dest = pos_src = pos_ini;
89 value_data aux = std::move(data[pos_ini]);
90 value_index itx_src = std::move(index[pos_ini]);
91
92 while ((pos_src = pos(itx_src)) != pos_ini)
93 {
94 data[pos_dest] = std::move(data[pos_src]);
95 std::swap(itx_src, index[pos_src]);
96 pos_dest = pos_src;
97 };
98
99 data[pos_dest] = std::move(aux);
100 index[pos_ini] = std::move(itx_src);
101 ++pos_ini;
102 };
103 };
104
105 /*
106 //
107 //-----------------------------------------------------------------------------
108 // function : rearrange_pos
109 /// @brief This function transform a logical sort of the elements in the index
110 /// of iterators in a physical sort.
111 //
112 /// @param global_first : iterator to the first element of the data
113 /// @param [in] index : vector of the iterators
114 //-----------------------------------------------------------------------------
115 template < class Iter_t, class Number >
116 void rearrange_pos (Iter_t global_first, std::vector< Number> &index)
117 {
118 //-------------------------------------------------------------------------
119 // METAPROGRAMMING AND DEFINITIONS
120 //-------------------------------------------------------------------------
121 static_assert ( std::is_integral<Number>::value, "Incompatible Types");
122 typedef iter_value< Iter_t > value_t;
123
124 //-------------------------------------------------------------------------
125 // CODE
126 //-------------------------------------------------------------------------
127 size_t pos_dest = 0;
128 size_t pos_src = 0;
129 size_t pos_ini = 0;
130 size_t nelem = index.size ( );
131 Iter_t it_dest (global_first), it_src(global_first);
132
133 while (pos_ini < nelem)
134 {
135 while (pos_ini < nelem and
136 index[pos_ini] == pos_ini)
137 {
138 ++pos_ini;
139 };
140
141 if (pos_ini == nelem) return;
142 pos_dest = pos_src = pos_ini;
143 it_dest = global_first + pos_dest;
144 value_t Aux = std::move (*it_dest);
145
146 while ((pos_src = index[pos_dest]) != pos_ini)
147 {
148 index[pos_dest] = it_dest - global_first;
149 it_src = global_first + pos_src;
150 *it_dest = std::move (*it_src);
151 it_dest = it_src;
152 pos_dest = pos_src;
153 };
154
155 *it_dest = std::move (Aux);
156 index[pos_dest] = it_dest - global_first;
157 ++pos_ini;
158 };
159 };
160 */
161 //
162 //****************************************************************************
163 };// End namespace common
164 };// End namespace sort
165 };// End namespace boost
166 //****************************************************************************
167 //
168 #endif
169