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

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