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 <ciso646>
17#include <functional>
18#include <iterator>
19#include <type_traits>
20#include <vector>
21#include <cassert>
22#include <boost/sort/common/util/traits.hpp>
23
24
25namespace boost
26{
27namespace sort
28{
29namespace common
30{
31
32template<class Iter_data>
33struct filter_iterator
34{
35 //-----------------------------------------------------------------------
36 // Variables
37 //-----------------------------------------------------------------------
38 Iter_data origin;
39
40 //-----------------------------------------------------------------------
41 // Functions
42 //-----------------------------------------------------------------------
43 filter_iterator(Iter_data global_first): origin(global_first) { };
44 size_t operator ()(Iter_data itx) const
45 {
46 return size_t(itx - origin);
47 }
48};
49
50struct filter_pos
51{
52 size_t operator ()(size_t pos) const { return pos; };
53};
54
55//
56//-----------------------------------------------------------------------------
57// function : rearrange
58/// @brief This function transform a logical sort of the elements in the index
59/// of iterators in a physical sort.
60//
61/// @param global_first : iterator to the first element of the data
62/// @param [in] index : vector of the iterators
63//-----------------------------------------------------------------------------
64template<class Iter_data, class Iter_index, class Filter_pos>
65void rearrange(Iter_data global_first, Iter_index itx_first,
66 Iter_index itx_last, Filter_pos pos)
67{
68 //-----------------------------------------------------------------------
69 // Metaprogramming
70 //-----------------------------------------------------------------------
71 typedef util::value_iter<Iter_data> value_data;
72 typedef util::value_iter<Iter_index> value_index;
73
74 //-------------------------------------------------------------------------
75 // Code
76 //-------------------------------------------------------------------------
77 assert((itx_last - itx_first) >= 0);
78 size_t pos_dest, pos_src, pos_ini;
79 size_t nelem = size_t(itx_last - itx_first);
80 Iter_data data = global_first;
81 Iter_index index = itx_first;
82
83 pos_ini = 0;
84 while (pos_ini < nelem)
85 {
86 while (pos_ini < nelem and pos(index[pos_ini]) == pos_ini)
87 ++pos_ini;
88 if (pos_ini == nelem) return;
89 pos_dest = pos_src = pos_ini;
90 value_data aux = std::move(data[pos_ini]);
91 value_index itx_src = std::move(index[pos_ini]);
92
93 while ((pos_src = pos(itx_src)) != pos_ini)
94 {
95 using std::swap;
96 data[pos_dest] = std::move(data[pos_src]);
97 swap(itx_src, index[pos_src]);
98 pos_dest = pos_src;
99 };
100
101 data[pos_dest] = std::move(aux);
102 index[pos_ini] = std::move(itx_src);
103 ++pos_ini;
104 };
105};
106
107/*
108 //
109 //-----------------------------------------------------------------------------
110 // function : rearrange_pos
111 /// @brief This function transform a logical sort of the elements in the index
112 /// of iterators in a physical sort.
113 //
114 /// @param global_first : iterator to the first element of the data
115 /// @param [in] index : vector of the iterators
116 //-----------------------------------------------------------------------------
117 template < class Iter_t, class Number >
118 void rearrange_pos (Iter_t global_first, std::vector< Number> &index)
119 {
120 //-------------------------------------------------------------------------
121 // METAPROGRAMMING AND DEFINITIONS
122 //-------------------------------------------------------------------------
123 static_assert ( std::is_integral<Number>::value, "Incompatible Types");
124 typedef iter_value< Iter_t > value_t;
125
126 //-------------------------------------------------------------------------
127 // CODE
128 //-------------------------------------------------------------------------
129 size_t pos_dest = 0;
130 size_t pos_src = 0;
131 size_t pos_ini = 0;
132 size_t nelem = index.size ( );
133 Iter_t it_dest (global_first), it_src(global_first);
134
135 while (pos_ini < nelem)
136 {
137 while (pos_ini < nelem and
138 index[pos_ini] == pos_ini)
139 {
140 ++pos_ini;
141 };
142
143 if (pos_ini == nelem) return;
144 pos_dest = pos_src = pos_ini;
145 it_dest = global_first + pos_dest;
146 value_t Aux = std::move (*it_dest);
147
148 while ((pos_src = index[pos_dest]) != pos_ini)
149 {
150 index[pos_dest] = it_dest - global_first;
151 it_src = global_first + pos_src;
152 *it_dest = std::move (*it_src);
153 it_dest = it_src;
154 pos_dest = pos_src;
155 };
156
157 *it_dest = std::move (Aux);
158 index[pos_dest] = it_dest - global_first;
159 ++pos_ini;
160 };
161 };
162 */
163//
164//****************************************************************************
165};// End namespace common
166};// End namespace sort
167};// End namespace boost
168//****************************************************************************
169//
170#endif
171

source code of boost/libs/sort/include/boost/sort/common/rearrange.hpp