1//----------------------------------------------------------------------------
2/// @file flat_stable_sort.hpp
3/// @brief Flat stable sort algorithm
4///
5/// @author Copyright (c) 2017 Francisco José 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_FLAT_STABLE_SORT_HPP
14#define __BOOST_SORT_FLAT_STABLE_SORT_HPP
15
16#include <ciso646>
17#include <cstdlib>
18#include <functional>
19#include <iterator>
20#include <memory>
21#include <type_traits>
22#include <vector>
23
24#include <boost/sort/insert_sort/insert_sort.hpp>
25#include <boost/sort/common/util/insert.hpp>
26#include <boost/sort/common/merge_block.hpp>
27#include <boost/sort/common/sort_basic.hpp>
28#include <boost/sort/common/range.hpp>
29#include <boost/sort/common/util/traits.hpp>
30#include <boost/sort/common/indirect.hpp>
31
32
33
34namespace boost
35{
36namespace sort
37{
38namespace flat_internal
39{
40namespace bsc = boost::sort::common;
41namespace bscu = boost::sort::common::util;
42//---------------------------------------------------------------------------
43/// @struct flat_stable_sort
44/// @brief This class implement s stable sort algorithm with 1 thread, with
45/// an auxiliary memory of N/2 elements
46//----------------------------------------------------------------------------
47template <class Iter_t, typename Compare = bscu::compare_iter<Iter_t>,
48 uint32_t Power2 = 10>
49class flat_stable_sort: public bsc::merge_block<Iter_t, Compare, Power2>
50{
51 //------------------------------------------------------------------------
52 // DEFINITIONS AND CONSTANTS
53 //------------------------------------------------------------------------
54 typedef bsc::merge_block<Iter_t, Compare, Power2> merge_block_t;
55
56 //-------------------------------------------------------------------------
57 // D E F I N I T I O N S
58 //-------------------------------------------------------------------------
59 typedef typename merge_block_t::value_t value_t;
60 typedef typename merge_block_t::range_pos range_pos;
61 typedef typename merge_block_t::range_it range_it;
62 typedef typename merge_block_t::range_buf range_buf;
63 typedef typename merge_block_t::it_index it_index;
64 typedef typename merge_block_t::circular_t circular_t;
65
66 //------------------------------------------------------------------------
67 // CONSTANTS
68 //------------------------------------------------------------------------
69 using merge_block_t::BLOCK_SIZE;
70 using merge_block_t::LOG_BLOCK;
71
72 using merge_block_t::index;
73 using merge_block_t::cmp;
74 using merge_block_t::ptr_circ;
75
76 using merge_block_t::get_range;
77 using merge_block_t::get_group_range;
78 using merge_block_t::merge_range_pos;
79 using merge_block_t::move_range_pos_backward;
80 using merge_block_t::rearrange_with_index;
81
82public:
83 //------------------------------------------------------------------------
84 // PUBLIC FUNCTIONS
85 //-------------------------------------------------------------------------
86 flat_stable_sort(Iter_t first, Iter_t last, Compare comp,
87 circular_t *ptr_circ)
88 : merge_block_t(first, last, comp, ptr_circ)
89 {
90 auto nelem = last - first;
91 assert (nelem >= 0);
92 if (nelem < 2) return;
93 divide(itx_first: index.begin(), itx_last: index.end());
94 rearrange_with_index();
95 };
96
97 flat_stable_sort(Iter_t first, Iter_t last, Compare comp = Compare())
98 : flat_stable_sort(first, last, comp, nullptr) { };
99
100 void divide(it_index itx_first, it_index itx_last);
101
102 void sort_small(it_index itx_first, it_index itx_last);
103
104 bool is_sorted_forward(it_index itx_first, it_index itx_last);
105
106 bool is_sorted_backward(it_index itx_first, it_index itx_last);
107};
108//----------------------------------------------------------------------------
109// End of class flat_stable_sort
110//----------------------------------------------------------------------------
111//
112//------------------------------------------------------------------------
113// function :
114/// @brief :
115/// @param Pos :
116/// @return
117//------------------------------------------------------------------------
118template <class Iter_t, typename Compare, uint32_t Power2>
119void flat_stable_sort <Iter_t, Compare, Power2>
120::divide(it_index itx_first, it_index itx_last)
121{
122 size_t nblock = size_t(itx_last - itx_first);
123 if (nblock < 5)
124 { sort_small(itx_first, itx_last);
125 return;
126 };
127 if ( nblock > 7)
128 { if (is_sorted_forward(itx_first, itx_last)) return;
129 if (is_sorted_backward(itx_first, itx_last)) return;
130 };
131 size_t nblock1 = (nblock + 1) >> 1;
132 divide(itx_first, itx_last: itx_first + nblock1);
133 divide(itx_first: itx_first + nblock1, itx_last);
134 merge_range_pos(itx_first, itx_first + nblock1, itx_last);
135};
136//
137//------------------------------------------------------------------------
138// function : sort_small
139/// @brief :
140/// @param
141/// @param
142/// @param
143//------------------------------------------------------------------------
144template <class Iter_t, typename Compare, uint32_t Power2>
145void flat_stable_sort <Iter_t, Compare, Power2>
146::sort_small(it_index itx_first, it_index itx_last)
147{
148 size_t nblock = size_t(itx_last - itx_first);
149 assert(nblock > 0 and nblock < 5);
150 value_t *paux = ptr_circ->get_buffer();
151 range_it rng_data = get_group_range(*itx_first, nblock);
152
153 if (nblock < 3)
154 {
155 range_buf rng_aux(paux, paux + rng_data.size());
156 range_sort_data(rng_data, rng_aux, cmp);
157 return;
158 };
159
160 //--------------------------------------------------------------------
161 // division of range_data in two ranges for be sorted and merged
162 //--------------------------------------------------------------------
163 size_t nblock1 = (nblock + 1) >> 1;
164 range_it rng_data1 = get_group_range(*itx_first, nblock1);
165 range_it rng_data2(rng_data1.last, rng_data.last);
166 range_buf rng_aux1(paux, paux + rng_data1.size());
167 range_buf rng_aux2(paux, paux + rng_data2.size());
168
169 range_sort_data(rng_data2, rng_aux2, cmp);
170 range_sort_buffer(rng_data1, rng_aux1, cmp);
171 merge_half(rng_data, rng_aux1, rng_data2, cmp);
172};
173//
174//------------------------------------------------------------------------
175// function : is_sorted_forward
176/// @brief : return if the data are ordered,
177/// @param itx_first : iterator to the first block in the index
178/// @param itx_last : iterator to the last block in the index
179/// @return : true : the data are ordered false : not ordered
180//------------------------------------------------------------------------
181template <class Iter_t, typename Compare, uint32_t Power2>
182bool flat_stable_sort <Iter_t, Compare, Power2>
183::is_sorted_forward(it_index itx_first, it_index itx_last)
184{
185 size_t nblock = size_t(itx_last - itx_first);
186 range_it rng = get_group_range(*itx_first, nblock);
187 size_t nelem = rng.size();
188 size_t min_process = (std::max)(BLOCK_SIZE, (nelem >> 3));
189
190 size_t nsorted1 = bsc::number_stable_sorted_forward (rng.first, rng.last,
191 min_process, cmp);
192 if (nsorted1 == nelem) return true;
193 if (nsorted1 == 0) return false;
194
195 size_t nsorted2 = nelem - nsorted1;
196 Iter_t itaux = rng.first + nsorted1;
197 if (nsorted2 <= (BLOCK_SIZE << 1))
198 {
199 flat_stable_sort(itaux, rng.last, cmp, ptr_circ);
200 bscu::insert_sorted(rng.first, itaux, rng.last, cmp,
201 ptr_circ->get_buffer());
202 }
203 else
204 { // Adjust the size of the sorted data to a number of blocks
205 size_t mask = ~(BLOCK_SIZE - 1);
206 size_t nsorted1_adjust = nsorted1 & mask;
207 flat_stable_sort(rng.first + nsorted1_adjust, rng.last, cmp,
208 ptr_circ);
209 size_t nblock1 = nsorted1_adjust >> Power2;
210 merge_range_pos(itx_first, itx_first + nblock1, itx_last);
211 };
212 return true;
213};
214//
215//------------------------------------------------------------------------
216// function : is_sorted_backward
217/// @brief : return if the data are ordered,
218/// @param itx_first : iterator to the first block in the index
219/// @param itx_last : iterator to the last block in the index
220/// @return : true : the data are ordered false : not ordered
221//------------------------------------------------------------------------
222template <class Iter_t, typename Compare, uint32_t Power2>
223bool flat_stable_sort <Iter_t, Compare, Power2>
224::is_sorted_backward(it_index itx_first, it_index itx_last)
225{
226 size_t nblock = size_t(itx_last - itx_first);
227 range_it rng = get_group_range(*itx_first, nblock);
228
229 size_t nelem = rng.size();
230 size_t min_process = (std::max)(BLOCK_SIZE, (nelem >> 3));
231
232 size_t nsorted2 = bsc::number_stable_sorted_backward(rng.first, rng.last,
233 min_process, cmp);
234 if (nsorted2 == nelem) return true;
235 if (nsorted2 == 0 ) return false;
236 Iter_t itaux = rng.last - nsorted2;
237 size_t nsorted1 = nelem - nsorted2;
238
239 if (nsorted1 <= (BLOCK_SIZE << 1))
240 {
241 flat_stable_sort(rng.first, itaux, cmp, ptr_circ);
242 bscu::insert_sorted_backward(rng.first, itaux, rng.last, cmp,
243 ptr_circ->get_buffer());
244 }
245 else
246 { // Adjust the size of nsorted2 for to be a number of blocks
247 size_t nblock1 = (nsorted1 + BLOCK_SIZE - 1) >> Power2;
248 size_t nsorted1_adjust = (nblock1 << Power2);
249 flat_stable_sort(rng.first, rng.first + nsorted1_adjust, cmp,
250 ptr_circ);
251 merge_range_pos(itx_first, itx_first + nblock1, itx_last);
252 };
253 return true;
254};
255//****************************************************************************
256};// End namespace flat_internal
257//****************************************************************************
258//
259namespace bscu = boost::sort::common::util;
260namespace flat = boost::sort::flat_internal;
261//
262///---------------------------------------------------------------------------
263// function flat_stable_sort
264/// @brief This class is select the block size in the block_indirect_sort
265/// algorithm depending of the type and size of the data to sort
266///
267//----------------------------------------------------------------------------
268template <class Iter_t, class Compare = bscu::compare_iter<Iter_t>,
269 bscu::enable_if_string<value_iter<Iter_t> > * = nullptr>
270inline void flat_stable_sort (Iter_t first, Iter_t last,
271 Compare cmp = Compare())
272{
273 flat::flat_stable_sort<Iter_t, Compare, 6> (first, last, cmp);
274};
275
276template<size_t Size>
277struct block_size_fss
278{
279 static constexpr const uint32_t BitsSize =
280 (Size == 0) ? 0 : (Size > 128) ? 7 : bscu::tmsb[Size - 1];
281 static constexpr const uint32_t sz[10] =
282 { 10, 10, 10, 9, 8, 7, 6, 6 };
283 static constexpr const uint32_t data = sz[BitsSize];
284};
285
286//
287///---------------------------------------------------------------------------
288// function flat_stable_sort
289/// @brief This class is select the block size in the flat_stable_sort
290/// algorithm depending of the type and size of the data to sort
291///
292//----------------------------------------------------------------------------
293template <class Iter_t, class Compare = bscu::compare_iter<Iter_t>,
294 bscu::enable_if_not_string<value_iter<Iter_t> >* = nullptr>
295inline void flat_stable_sort (Iter_t first, Iter_t last,
296 Compare cmp = Compare())
297{
298 flat::flat_stable_sort<Iter_t, Compare,
299 block_size_fss<sizeof(value_iter<Iter_t> )>::data>
300 (first, last, cmp);
301};
302
303template<class Iter_t, class Compare = compare_iter<Iter_t> >
304inline void indirect_flat_stable_sort (Iter_t first, Iter_t last,
305 Compare comp = Compare())
306{
307 typedef typename std::vector<Iter_t>::iterator itx_iter;
308 typedef common::less_ptr_no_null <Iter_t, Compare> itx_comp;
309 common::indirect_sort ( flat_stable_sort<itx_iter, itx_comp>,
310 first, last, comp);
311};
312
313//****************************************************************************
314};// End namespace sort
315};// End namepspace boost
316//****************************************************************************
317//
318#endif
319

source code of boost/libs/sort/include/boost/sort/flat_stable_sort/flat_stable_sort.hpp