1//----------------------------------------------------------------------------
2/// @file indirect.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_PARALLEL_COMMON_INDIRECT_HPP
14#define __BOOST_SORT_PARALLEL_COMMON_INDIRECT_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
23namespace boost
24{
25namespace sort
26{
27namespace common
28{
29
30//
31//---------------------------------------------------------------------------
32/// @struct less_ptr_no_null
33///
34/// @remarks this is the comparison object for pointers. Compare the objects
35/// pointed by the iterators
36//---------------------------------------------------------------------------
37template<class Iter_t, class Compare = util::compare_iter<Iter_t> >
38struct less_ptr_no_null
39{
40 //----------------------------- Variables -----------------------
41 Compare comp; // comparison object of the elements pointed by Iter_t
42
43 //------------------------------------------------------------------------
44 // function : less_ptr_no_null
45 /// @brief constructor from a Compare object
46 /// @param C1 : comparison object
47 //-----------------------------------------------------------------------
48 less_ptr_no_null(Compare C1 = Compare()): comp(C1) { };
49
50 //------------------------------------------------------------------------
51 // function : operator ( )
52 /// @brief Make the comparison of the objects pointed by T1 and T2, using
53 // the internal comp
54 //
55 /// @param T1 : first iterator
56 /// @param T2 : second iterator
57 /// @return bool result of the comparison
58 //-----------------------------------------------------------------------
59 bool operator( )(Iter_t T1, Iter_t T2) const
60 {
61 return comp(*T1, *T2);
62 };
63};
64//
65//-----------------------------------------------------------------------------
66// function : create_index
67/// @brief From a vector of objects, create a vector of iterators to
68/// the objects
69///
70/// @param first : iterator to the first element of the range
71/// @param last : iterator to the element after the last of the range
72/// @param index : vector where store the iterators
73//-----------------------------------------------------------------------------
74template<class Iter_t>
75void create_index(Iter_t first, Iter_t last, std::vector<Iter_t> &index)
76{
77 auto nelem = last - first;
78 assert(nelem >= 0);
79 index.clear();
80 index.reserve(nelem);
81 for (; first != last; ++first) index.push_back(first);
82};
83//
84//-----------------------------------------------------------------------------
85// function : sort_index
86/// @brief This function transform a logical sort of the elements in the index
87/// in a physical sort
88//
89/// @param global_first : iterator to the first element of the data
90/// @param [in] index : vector of the iterators
91//-----------------------------------------------------------------------------
92template<class Iter_t>
93void sort_index(Iter_t global_first, std::vector<Iter_t> &index)
94{
95 typedef util::value_iter<Iter_t> value_t;
96
97 size_t pos_dest = 0;
98 size_t pos_src = 0;
99 size_t pos_in_vector = 0;
100 size_t nelem = index.size();
101 Iter_t it_dest, it_src;
102
103 while (pos_in_vector < nelem)
104 {
105 while (pos_in_vector < nelem and
106 (size_t(index[pos_in_vector] - global_first)) == pos_in_vector)
107 {
108 ++pos_in_vector;
109 };
110
111 if (pos_in_vector == nelem) return;
112 pos_dest = pos_src = pos_in_vector;
113 it_dest = global_first + pos_dest;
114 value_t Aux = std::move(*it_dest);
115
116 while ((pos_src = (size_t(index[pos_dest] - global_first)))
117 != pos_in_vector)
118 {
119 index[pos_dest] = it_dest;
120 it_src = global_first + pos_src;
121 *it_dest = std::move(*it_src);
122 it_dest = it_src;
123 pos_dest = pos_src;
124 };
125
126 *it_dest = std::move(Aux);
127 index[pos_dest] = it_dest;
128 ++pos_in_vector;
129 };
130};
131
132template<class func, class Iter_t, class Compare = util::compare_iter<Iter_t> >
133void indirect_sort(func method, Iter_t first, Iter_t last, Compare comp)
134{
135 auto nelem = (last - first);
136 assert(nelem >= 0);
137 if (nelem < 2) return;
138 std::vector<Iter_t> index;
139 index.reserve((size_t) nelem);
140 create_index(first, last, index);
141 less_ptr_no_null<Iter_t, Compare> index_comp(comp);
142 method(index.begin(), index.end(), index_comp);
143 sort_index(first, index);
144};
145
146//
147//****************************************************************************
148};// End namespace common
149};// End namespace sort
150};// End namespace boost
151//****************************************************************************
152//
153#endif
154

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