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
23 namespace boost
24 {
25 namespace sort
26 {
27 namespace 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 //---------------------------------------------------------------------------
37 template<class Iter_t, class Compare = util::compare_iter<Iter_t> >
38 struct 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 //-----------------------------------------------------------------------
less_ptr_no_nullboost::sort::common::less_ptr_no_null48 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 //-----------------------------------------------------------------------
operator ( )boost::sort::common::less_ptr_no_null59 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 //-----------------------------------------------------------------------------
74 template<class Iter_t>
create_index(Iter_t first,Iter_t last,std::vector<Iter_t> & index)75 static void 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 //-----------------------------------------------------------------------------
92 template<class Iter_t>
sort_index(Iter_t global_first,std::vector<Iter_t> & index)93 static void 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
132 template<class func, class Iter_t, class Compare = compare_iter<Iter_t> >
indirect_sort(func method,Iter_t first,Iter_t last,Compare comp)133 static void 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