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