1 //----------------------------------------------------------------------------
2 /// @file merge_vector.hpp
3 /// @brief In this file have the functions for to do a stable merge of
4 // ranges, in a vector
5 ///
6 /// @author Copyright (c) 2016 Francisco Jose Tapia (fjtapia@gmail.com )\n
7 /// Distributed under the Boost Software License, Version 1.0.\n
8 /// ( See accompanying file LICENSE_1_0.txt or copy at
9 /// http://www.boost.org/LICENSE_1_0.txt )
10 /// @version 0.1
11 ///
12 /// @remarks
13 //-----------------------------------------------------------------------------
14 #ifndef __BOOST_SORT_PARALLEL_DETAIL_UTIL_MERGE_VECTOR_HPP
15 #define __BOOST_SORT_PARALLEL_DETAIL_UTIL_MERGE_VECTOR_HPP
16
17 #include <boost/sort/common/merge_four.hpp>
18 #include <functional>
19 #include <iterator>
20 #include <memory>
21 #include <type_traits>
22 #include <vector>
23
24 namespace boost
25 {
26 namespace sort
27 {
28 namespace common
29 {
30
31 //############################################################################
32 // ##
33 // F U S I O N O F ##
34 // ##
35 // A V E C T O R O F R A N G E S ##
36 // ##
37 //############################################################################
38
39 //
40 //-----------------------------------------------------------------------------
41 // function : merge_level4
42 /// @brief merge the ranges in the vector v_input with the full_merge4 function.
43 /// The v_output vector is used as auxiliary memory in the internal
44 /// process. The final results is in the dest range.
45 /// All the ranges of v_output are inside the range dest
46 /// @param dest : range where move the elements merged
47 /// @param v_input : vector of ranges to merge
48 /// @param v_output : vector of ranges obtained
49 /// @param comp : comparison object
50 /// @return range with all the elements moved
51 //-----------------------------------------------------------------------------
52 template<class Iter1_t, class Iter2_t, class Compare>
merge_level4(range<Iter1_t> dest,std::vector<range<Iter2_t>> & v_input,std::vector<range<Iter1_t>> & v_output,Compare comp)53 void merge_level4(range<Iter1_t> dest, std::vector<range<Iter2_t> > &v_input,
54 std::vector<range<Iter1_t> > &v_output, Compare comp)
55 {
56 typedef range<Iter1_t> range1_t;
57 typedef util::value_iter<Iter1_t> type1;
58 typedef util::value_iter<Iter2_t> type2;
59 static_assert (std::is_same< type1, type2 >::value,
60 "Incompatible iterators\n");
61
62 v_output.clear();
63 if (v_input.size() == 0) return;
64 if (v_input.size() == 1)
65 {
66 v_output.emplace_back(move_forward(dest, v_input[0]));
67 return;
68 };
69
70 uint32_t nrange = v_input.size();
71 uint32_t pos_ini = 0;
72 while (pos_ini < v_input.size())
73 {
74 uint32_t nmerge = (nrange + 3) >> 2;
75 uint32_t nelem = (nrange + nmerge - 1) / nmerge;
76 range1_t rz = full_merge4(dest, &v_input[pos_ini], nelem, comp);
77 v_output.emplace_back(rz);
78 dest.first = rz.last;
79 pos_ini += nelem;
80 nrange -= nelem;
81 };
82 return;
83 };
84 //
85 //-----------------------------------------------------------------------------
86 // function : uninit_merge_level4
87 /// @brief merge the ranges moving the objects and constructing them in
88 /// uninitialized memory, in the vector v_input
89 /// using full_merge4. The v_output vector is used as auxiliary memory
90 /// in the internal process. The final results is in the dest range.
91 /// All the ranges of v_output are inside the range dest
92 ///
93 /// @param dest : range where move the elements merged
94 /// @param v_input : vector of ranges to merge
95 /// @param v_output : vector of ranges obtained
96 /// @param comp : comparison object
97 /// @return range with all the elements moved and constructed
98 //-----------------------------------------------------------------------------
99 template<class Value_t, class Iter_t, class Compare>
uninit_merge_level4(range<Value_t * > dest,std::vector<range<Iter_t>> & v_input,std::vector<range<Value_t * >> & v_output,Compare comp)100 void uninit_merge_level4(range<Value_t *> dest,
101 std::vector<range<Iter_t> > &v_input,
102 std::vector<range<Value_t *> > &v_output, Compare comp)
103 {
104 typedef range<Value_t *> range1_t;
105 typedef util::value_iter<Iter_t> type1;
106 static_assert (std::is_same< type1, Value_t >::value,
107 "Incompatible iterators\n");
108
109 v_output.clear();
110 if (v_input.size() == 0) return;
111 if (v_input.size() == 1)
112 {
113 v_output.emplace_back(move_construct(dest, v_input[0]));
114 return;
115 };
116
117 uint32_t nrange = v_input.size();
118 uint32_t pos_ini = 0;
119 while (pos_ini < v_input.size())
120 {
121 uint32_t nmerge = (nrange + 3) >> 2;
122 uint32_t nelem = (nrange + nmerge - 1) / nmerge;
123 range1_t rz = uninit_full_merge4(dest, &v_input[pos_ini], nelem, comp);
124 v_output.emplace_back(rz);
125 dest.first = rz.last;
126 pos_ini += nelem;
127 nrange -= nelem;
128 };
129 return;
130 };
131 //
132 //-----------------------------------------------------------------------------
133 // function : merge_vector4
134 /// @brief merge the ranges in the vector v_input using the merge_level4
135 /// function. The v_output vector is used as auxiliary memory in the
136 /// internal process
137 /// The final results is in the range_output range.
138 /// All the ranges of v_output are inside the range range_output
139 /// All the ranges of v_input are inside the range range_input
140 /// @param range_input : range including all the ranges of v_input
141 /// @param ange_output : range including all the elements of v_output
142 /// @param v_input : vector of ranges to merge
143 /// @param v_output : vector of ranges obtained
144 /// @param comp : comparison object
145 /// @return range with all the elements moved
146 //-----------------------------------------------------------------------------
147 template<class Iter1_t, class Iter2_t, class Compare>
merge_vector4(range<Iter1_t> range_input,range<Iter2_t> range_output,std::vector<range<Iter1_t>> & v_input,std::vector<range<Iter2_t>> & v_output,Compare comp)148 range<Iter2_t> merge_vector4(range<Iter1_t> range_input,
149 range<Iter2_t> range_output,
150 std::vector<range<Iter1_t> > &v_input,
151 std::vector<range<Iter2_t> > &v_output,
152 Compare comp)
153 {
154 typedef range<Iter2_t> range2_t;
155 typedef util::value_iter<Iter1_t> type1;
156 typedef util::value_iter<Iter2_t> type2;
157 static_assert (std::is_same< type1, type2 >::value,
158 "Incompatible iterators\n");
159
160 v_output.clear();
161 if (v_input.size() == 0)
162 {
163 return range2_t(range_output.first, range_output.first);
164 };
165 if (v_input.size() == 1)
166 {
167 return move_forward(range_output, v_input[0]);
168 };
169 bool sw = false;
170 uint32_t nrange = v_input.size();
171
172 while (nrange > 1)
173 {
174 if (sw)
175 {
176 merge_level4(range_input, v_output, v_input, comp);
177 sw = false;
178 nrange = v_input.size();
179 }
180 else
181 {
182 merge_level4(range_output, v_input, v_output, comp);
183 sw = true;
184 nrange = v_output.size();
185 };
186 };
187 return (sw) ? v_output[0] : move_forward(range_output, v_input[0]);
188 };
189
190 //****************************************************************************
191 };// End namespace common
192 };// End namespace sort
193 };// End namespace boost
194 //****************************************************************************
195 //
196 #endif
197