1//----------------------------------------------------------------------------
2/// @file merge_block.hpp
3/// @brief This file constains the class merge_block, which is part of the
4/// block_indirect_sort algorithm
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_COMMON_MERGE_BLOCK_HPP
15#define __BOOST_SORT_COMMON_MERGE_BLOCK_HPP
16
17#include <ciso646>
18#include <boost/sort/common/range.hpp>
19#include <boost/sort/common/rearrange.hpp>
20#include <boost/sort/common/util/merge.hpp>
21#include <boost/sort/common/util/traits.hpp>
22
23namespace boost
24{
25namespace sort
26{
27namespace common
28{
29///---------------------------------------------------------------------------
30/// @struct merge_block
31/// @brief This contains all the information shared betwen the classes of the
32/// block indirect sort algorithm
33
34//----------------------------------------------------------------------------
35template<class Iter_t, class Compare, uint32_t Power2 = 10>
36struct merge_block
37{
38 //-------------------------------------------------------------------------
39 // D E F I N I T I O N S
40 //-------------------------------------------------------------------------
41 typedef util::value_iter<Iter_t> value_t;
42 typedef range<size_t> range_pos;
43 typedef range<Iter_t> range_it;
44 typedef range<value_t *> range_buf;
45 typedef typename std::vector<size_t>::iterator it_index;
46 typedef util::circular_buffer<value_t, Power2 + 1> circular_t;
47
48 //------------------------------------------------------------------------
49 // CONSTANTS
50 //------------------------------------------------------------------------
51 const size_t BLOCK_SIZE = (size_t) 1 << Power2;
52 const size_t LOG_BLOCK = Power2;
53
54 //------------------------------------------------------------------------
55 // V A R I A B L E S
56 //------------------------------------------------------------------------
57 // range with all the element to sort
58 range<Iter_t> global_range;
59
60 // index vector of block_pos elements
61 std::vector<size_t> index;
62
63 // Number of elements to sort
64 size_t nelem;
65
66 // Number of blocks to sort
67 size_t nblock;
68
69 // Number of elements in the last block (tail)
70 size_t ntail;
71
72 // object for to compare two elements
73 Compare cmp;
74
75 // range of elements of the last block (tail)
76 range_it range_tail;
77
78 // circular buffer
79 circular_t * ptr_circ;
80
81 // indicate if the circulr buffer is owned by the data structure
82 // or is received as parameter
83 bool owned;
84
85 //
86 //------------------------------------------------------------------------
87 // F U N C T I O N S
88 //------------------------------------------------------------------------
89 //
90 //------------------------------------------------------------------------
91 // function : merge_block
92 /// @brief constructor of the class
93 //
94 /// @param first : iterator to the first element of the range to sort
95 /// @param last : iterator after the last element to the range to sort
96 /// @param comp : object for to compare two elements pointed by Iter_t
97 /// iterators
98 //------------------------------------------------------------------------
99 merge_block (Iter_t first, Iter_t last, Compare comp,
100 circular_t *pcirc_buffer)
101 : global_range(first, last), cmp(comp), ptr_circ(pcirc_buffer),
102 owned(pcirc_buffer == nullptr)
103 {
104 assert((last - first) >= 0);
105 if (first == last) return; // nothing to do
106
107 nelem = size_t(last - first);
108 nblock = (nelem + BLOCK_SIZE - 1) / BLOCK_SIZE;
109 ntail = (nelem % BLOCK_SIZE);
110 index.reserve(n: nblock + 1);
111
112 for (size_t i = 0; i < nblock; ++i)
113 index.emplace_back(args&: i);
114
115 range_tail.first = first + ((nblock - 1) << LOG_BLOCK);
116 range_tail.last = last;
117 if (owned)
118 {
119 ptr_circ = new circular_t;
120 ptr_circ->initialize(*first);
121 };
122 }
123
124 merge_block(Iter_t first, Iter_t last, Compare comp)
125 : merge_block(first, last, comp, nullptr) { };
126
127 ~ merge_block()
128 {
129 if (ptr_circ != nullptr and owned)
130 {
131 delete ptr_circ;
132 ptr_circ = nullptr;
133 };
134 };
135 //-------------------------------------------------------------------------
136 // function : get_range
137 /// @brief obtain the range in the position pos
138 /// @param pos : position of the range
139 /// @return range required
140 //-------------------------------------------------------------------------
141 range_it get_range(size_t pos) const
142 {
143 Iter_t it1 = global_range.first + (pos << LOG_BLOCK);
144 Iter_t it2 = (pos == (nblock - 1)) ?
145 global_range.last : it1 + BLOCK_SIZE;
146 return range_it(it1, it2);
147 };
148 //-------------------------------------------------------------------------
149 // function : get_group_range
150 /// @brief obtain the range of the contiguous blocks beginning in the
151 // position pos
152 /// @param pos : position of the first range
153 /// @param nrange : number of ranges of the group
154 /// @return range required
155 //-------------------------------------------------------------------------
156 range_it get_group_range(size_t pos, size_t nrange) const
157 {
158 Iter_t it1 = global_range.first + (pos << LOG_BLOCK);
159
160 Iter_t it2 = ((pos + nrange) == nblock)?global_range.last: global_range.first + ((pos + nrange) << LOG_BLOCK);
161 //Iter_t it2 = global_range.first + ((pos + nrange) << LOG_BLOCK);
162 //if ((pos + nrange) == nblock) it2 = global_range.last;
163
164 return range_it(it1, it2);
165 };
166 //-------------------------------------------------------------------------
167 // function : is_tail
168 /// @brief indicate if a block is the tail
169 /// @param pos : position of the block
170 /// @return true : taiol false : not tail
171 //-------------------------------------------------------------------------
172 bool is_tail(size_t pos) const
173 {
174 return (pos == (nblock - 1) and ntail != 0);
175 };
176 //-------------------------------------------------------------------------
177 // function :
178 /// @brief
179 /// @param
180 /// @return
181 //-------------------------------------------------------------------------
182 void merge_range_pos(it_index itx_first, it_index itx_mid,
183 it_index itx_last);
184
185 //-------------------------------------------------------------------------
186 // function : move_range_pos_backward
187 /// @brief Move backward the elements of a range of blocks in a index
188 /// @param itx_first : iterator to the position of the first block
189 /// @param itx_last : itertor to the position of the last block
190 /// @param npos : number of positions to move. Must be less than BLOCK_SIZE
191 /// @return
192 //-------------------------------------------------------------------------
193 void move_range_pos_backward(it_index itx_first, it_index itx_last,
194 size_t npos);
195
196 //-------------------------------------------------------------------------
197 // function : rearrange_with_index
198 /// @brief rearrange the blocks with the relative positions of the index
199 /// @param
200 /// @param
201 /// @param
202 /// @return
203 //-------------------------------------------------------------------------
204 void rearrange_with_index(void);
205
206//---------------------------------------------------------------------------
207};// end struct merge_block
208//---------------------------------------------------------------------------
209//
210//############################################################################
211// ##
212// N O N I N L I N E F U N C T IO N S ##
213// ##
214//############################################################################
215//
216//-------------------------------------------------------------------------
217// function :
218/// @brief
219/// @param
220/// @return
221//-------------------------------------------------------------------------
222template<class Iter_t, class Compare, uint32_t Power2>
223void merge_block<Iter_t, Compare, Power2>
224::merge_range_pos(it_index itx_first, it_index itx_mid,it_index itx_last)
225{
226 assert((itx_last - itx_mid) >= 0 and (itx_mid - itx_first) >= 0);
227
228 size_t nelemA = (itx_mid - itx_first), nelemB = (itx_last - itx_mid);
229 if (nelemA == 0 or nelemB == 0) return;
230
231 //-------------------------------------------------------------------
232 // Create two index with the position of the blocks to merge
233 //-------------------------------------------------------------------
234 std::vector<size_t> indexA, indexB;
235 indexA.reserve(n: nelemA + 1);
236 indexB.reserve(n: nelemB);
237
238 indexA.insert(position: indexA.begin(), first: itx_first, last: itx_mid);
239 indexB.insert(position: indexB.begin(), first: itx_mid, last: itx_last);
240
241 it_index itx_out = itx_first;
242 it_index itxA = indexA.begin(), itxB = indexB.begin();
243 range_it rngA, rngB;
244 Iter_t itA = global_range.first, itB = global_range.first;
245 bool validA = false, validB = false;
246
247 while (itxA != indexA.end() and itxB != indexB.end())
248 { //----------------------------------------------------------------
249 // Load valid ranges from the itxA and ItxB positions
250 //----------------------------------------------------------------
251 if (not validA)
252 {
253 rngA = get_range(pos: *itxA);
254 itA = rngA.first;
255 validA = true;
256 };
257 if (not validB)
258 {
259 rngB = get_range(pos: *itxB);
260 itB = rngB.first;
261 validB = true;
262 };
263 //----------------------------------------------------------------
264 // If don't have merge betweeen the blocks, pass directly the
265 // position of the block to itx_out
266 //----------------------------------------------------------------
267 if (ptr_circ->size() == 0)
268 {
269 if (not cmp(*rngB.front(), *rngA.back()))
270 {
271 *(itx_out++) = *(itxA++);
272 validA = false;
273 continue;
274 };
275 if (cmp(*rngB.back(), *rngA.front()))
276 {
277 if (not is_tail(pos: *itxB))
278 *(itx_out++) = *itxB;
279 else ptr_circ->push_move_back(rngB.first, rngB.size());
280 ++itxB;
281 validB = false;
282 continue;
283 };
284 };
285 //----------------------------------------------------------------
286 // Normal merge
287 //----------------------------------------------------------------
288 bool side = util::merge_circular(itA, rngA.last, itB, rngB.last,
289 *ptr_circ, cmp, itA, itB);
290 if (side)
291 { // rngA is finished
292 ptr_circ->pop_move_front(rngA.first, rngA.size());
293 *(itx_out++) = *(itxA++);
294 validA = false;
295 }
296 else
297 { // rngB is finished
298 if (not is_tail(pos: *itxB))
299 {
300 ptr_circ->pop_move_front(rngB.first, rngB.size());
301 *(itx_out++) = *itxB;
302 };
303 ++itxB;
304 validB = false;
305 };
306 }; // end while
307
308 if (itxA == indexA.end())
309 { // the index A is finished
310 rngB = get_range(pos: *itxB);
311 ptr_circ->pop_move_front(rngB.first, ptr_circ->size());
312 while (itxB != indexB.end())
313 *(itx_out++) = *(itxB++);
314 }
315 else
316 { // The list B is finished
317 rngA = get_range(pos: *itxA);
318 if (ntail != 0 and indexB.back() == (nblock - 1)) // exist tail
319 { // add the tail block to indexA, and shift the element
320 indexA.push_back(x: indexB.back());
321 size_t numA = size_t(itA - rngA.first);
322 ptr_circ->pop_move_back(rngA.first, numA);
323 move_range_pos_backward(itx_first: itxA, itx_last: indexA.end(), npos: ntail);
324 };
325
326 ptr_circ->pop_move_front(rngA.first, ptr_circ->size());
327 while (itxA != indexA.end())
328 *(itx_out++) = *(itxA++);
329 };
330};
331
332//-------------------------------------------------------------------------
333// function : move_range_pos_backward
334/// @brief Move backward the elements of a range of blocks in a index
335/// @param itx_first : iterator to the position of the first block
336/// @param itx_last : itertor to the position of the last block
337/// @param npos : number of positions to move. Must be less than BLOCK_SIZE
338/// @return
339//-------------------------------------------------------------------------
340template<class Iter_t, class Compare, uint32_t Power2>
341void merge_block<Iter_t, Compare, Power2>
342::move_range_pos_backward(it_index itx_first, it_index itx_last, size_t npos)
343{
344 assert((itx_last - itx_first) >= 0 and npos <= BLOCK_SIZE);
345
346 //--------------------------------------------------------------------
347 // Processing the last block. Must be ready fore to accept npos
348 // elements from the upper block
349 //--------------------------------------------------------------------
350 range_it rng1 = get_range(pos: *(itx_last - 1));
351 assert(rng1.size() >= npos);
352 if (rng1.size() > npos)
353 {
354 size_t nmove = rng1.size() - npos;
355 util::move_backward(rng1.last, rng1.first, rng1.first + nmove);
356 };
357 //--------------------------------------------------------------------
358 // Movement of elements between blocks
359 //--------------------------------------------------------------------
360 for (it_index itx = itx_last - 1; itx != itx_first;)
361 {
362 --itx;
363 range_it rng2 = rng1;
364 rng1 = get_range(pos: *itx);
365 Iter_t it_mid1 = rng1.last - npos, it_mid2 = rng2.first + npos;
366 util::move_backward(it_mid2, it_mid1, rng1.last);
367 util::move_backward(rng1.last, rng1.first, it_mid1);
368 };
369};
370//-------------------------------------------------------------------------
371// function : rearrange_with_index
372/// @brief rearrange the blocks with the relative positions of the index
373/// @param
374/// @param
375/// @param
376/// @return
377//-------------------------------------------------------------------------
378template<class Iter_t, class Compare, uint32_t Power2>
379void merge_block<Iter_t, Compare, Power2>
380::rearrange_with_index(void)
381{ //--------------------------------------------------------------------
382 // Code
383 //--------------------------------------------------------------------
384 size_t pos_dest, pos_src, pos_ini;
385 size_t nelem = index.size();
386
387 ptr_circ->clear();
388 value_t * aux = ptr_circ->get_buffer();
389 range_buf rng_buf(aux, aux + ptr_circ->NMAX);
390
391 pos_ini = 0;
392 while (pos_ini < nelem)
393 {
394 while (pos_ini < nelem and index[pos_ini] == pos_ini)
395 ++pos_ini;
396 if (pos_ini == nelem) return;
397 pos_dest = pos_src = pos_ini;
398 rng_buf = move_forward(rng_buf, get_range(pos: pos_ini));
399 pos_src = index[pos_ini];
400
401 while (pos_src != pos_ini)
402 {
403 move_forward(get_range(pos: pos_dest), get_range(pos: pos_src));
404 index[pos_dest] = pos_dest;
405 pos_dest = pos_src;
406 pos_src = index[pos_src];
407 };
408 move_forward(get_range(pos: pos_dest), rng_buf);
409 index[pos_dest] = pos_dest;
410 ++pos_ini;
411 };
412};
413
414//****************************************************************************
415};// End namespace common
416};// End namespace sort
417};// End namespace boost
418//****************************************************************************
419#endif
420

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