1//----------------------------------------------------------------------------
2/// @file spinsort.hpp
3/// @brief Spin Sort algorithm
4///
5/// @author Copyright (c) 2016 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_PARALLEL_ALGORITHM_SPIN_SORT_HPP
14#define __BOOST_SORT_PARALLEL_ALGORITHM_SPIN_SORT_HPP
15
16
17#include <ciso646>
18#include <cstdlib>
19#include <functional>
20#include <iterator>
21#include <memory>
22#include <type_traits>
23#include <vector>
24#include <cstddef>
25#include <boost/sort/insert_sort/insert_sort.hpp>
26#include <boost/sort/common/util/traits.hpp>
27#include <boost/sort/common/util/algorithm.hpp>
28#include <boost/sort/common/range.hpp>
29#include <boost/sort/common/indirect.hpp>
30
31
32namespace boost
33{
34namespace sort
35{
36namespace spin_detail
37{
38
39//----------------------------------------------------------------------------
40// USING SENTENCES
41//----------------------------------------------------------------------------
42namespace bsc = boost::sort::common;
43using bsc::range;
44using bsc::util::nbits64;
45using bsc::util::compare_iter;
46using bsc::util::value_iter;
47using boost::sort::insert_sort;
48
49//
50//############################################################################
51// ##
52// D E F I N I T I O N S O F F U N C T I O N S ##
53// ##
54//############################################################################
55//
56template <class Iter1_t, class Iter2_t, typename Compare>
57static void insert_partial_sort (Iter1_t first, Iter1_t mid,
58 Iter1_t last, Compare comp,
59 const range<Iter2_t> &rng_aux);
60
61template<class Iter1_t, class Iter2_t, class Compare>
62static bool check_stable_sort (const range<Iter1_t> &rng_data,
63 const range<Iter2_t> &rng_aux, Compare comp);
64
65template<class Iter1_t, class Iter2_t, class Compare>
66static void range_sort (const range<Iter1_t> &range1,
67 const range<Iter2_t> &range2, Compare comp,
68 uint32_t level);
69
70template<class Iter1_t, class Iter2_t, class Compare>
71static void sort_range_sort (const range<Iter1_t> &rng_data,
72 const range<Iter2_t> &rng_aux, Compare comp);
73
74//
75//-----------------------------------------------------------------------------
76// function : insert_partial_sort
77/// @brief : Insertion sort of elements sorted
78/// @param first: iterator to the first element of the range
79/// @param mid : last pointer of the sorted data, and first pointer to the
80/// elements to insert
81/// @param last : iterator to the next element of the last in the range
82/// @param comp :
83/// @comments : the two ranges are sorted
84//-----------------------------------------------------------------------------
85template<class Iter1_t, class Iter2_t, typename Compare>
86static void insert_partial_sort (Iter1_t first, Iter1_t mid, Iter1_t last,
87 Compare comp, const range <Iter2_t> &rng_aux)
88{
89 //------------------------------------------------------------------------
90 // metaprogram
91 //------------------------------------------------------------------------
92 typedef value_iter<Iter1_t> value_t;
93 typedef value_iter<Iter2_t> value2_t;
94 static_assert (std::is_same<value_t, value2_t>::value,
95 "Incompatible iterators\n");
96
97 //--------------------------------------------------------------------
98 // program
99 //--------------------------------------------------------------------
100 assert(size_t(last - mid) <= rng_aux.size());
101
102 if (mid == last) return;
103 //insertionsort ( mid, last, comp);
104 if (first == mid) return;
105
106 //------------------------------------------------------------------------
107 // creation of the vector of elements to insert and their position in the
108 // sorted part
109 // the data are inserted in rng_aux
110 //-----------------------------------------------------------------------
111 std::vector<Iter1_t> viter;
112 Iter2_t beta = rng_aux.first, data = rng_aux.first;
113
114 for (Iter1_t alpha = mid; alpha != last; ++alpha)
115 *(beta++) = std::move(*alpha);
116
117 size_t ndata = last - mid;
118
119 Iter1_t linf = first, lsup = mid;
120 for (uint32_t i = 0; i < ndata; ++i)
121 {
122 Iter1_t it1 = std::upper_bound(linf, lsup, *(data + i), comp);
123 viter.push_back(it1);
124 linf = it1;
125 };
126
127 // moving the elements
128 viter.push_back(mid);
129 for (uint32_t i = viter.size() - 1; i != 0; --i)
130 {
131 Iter1_t src = viter[i], limit = viter[i - 1];
132 Iter1_t dest = src + (i);
133 while (src != limit) *(--dest) = std::move(*(--src));
134 *(viter[i - 1] + (i - 1)) = std::move(*(data + (i - 1)));
135 };
136}
137;
138//-----------------------------------------------------------------------------
139// function : check_stable_sort
140/// @brief check if the elements between first and last are osted or reverse
141/// sorted. If the number of elements not sorted is small, insert in
142/// the sorted part
143/// @param range_input : range with the elements to sort
144/// @param range_buffer : range with the elements sorted
145/// @param comp : object for to compare two elements
146/// @param level : when is 1, sort with the insertionsort algorithm
147/// if not make a recursive call splitting the ranges
148//
149/// @comments : if the number of levels is odd, the data are in the first
150/// parameter of range_sort, and the results appear in the second parameter
151/// If the number of levels is even, the data are in the second
152/// parameter of range_sort, and the results are in the same parameter
153//-----------------------------------------------------------------------------
154template<class Iter1_t, class Iter2_t, class Compare>
155static bool check_stable_sort(const range<Iter1_t> &rng_data,
156 const range<Iter2_t> &rng_aux, Compare comp)
157{
158 //------------------------------------------------------------------------
159 // metaprogramming
160 //------------------------------------------------------------------------
161 typedef value_iter<Iter1_t> value_t;
162 typedef value_iter<Iter2_t> value2_t;
163 static_assert (std::is_same<value_t, value2_t>::value,
164 "Incompatible iterators\n");
165
166 //------------------------------------------------------------------------
167 // program
168 //------------------------------------------------------------------------
169 // the maximun number of elements not ordered, for to be inserted in the
170 // sorted part
171 //const ptrdiff_t min_insert_partial_sort = 32 ;
172 const size_t ndata = rng_data.size();
173 if (ndata < 32)
174 {
175 insert_sort(rng_data.first, rng_data.last, comp);
176 return true;
177 };
178 const size_t min_insert_partial_sort =
179 ((ndata >> 3) < 33) ? 32 : (ndata >> 3);
180 if (ndata < 2) return true;
181
182 // check if sorted
183 bool sw = true;
184 Iter1_t it2 = rng_data.first + 1;
185 for (Iter1_t it1 = rng_data.first;
186 it2 != rng_data.last and (sw = not comp(*it2, *it1)); it1 =
187 it2++)
188 ;
189 if (sw) return true;
190
191 // insert the elements between it1 and last
192 if (size_t(rng_data.last - it2) < min_insert_partial_sort)
193 {
194 sort_range_sort(range<Iter1_t>(it2, rng_data.last), rng_aux, comp);
195 insert_partial_sort(rng_data.first, it2, rng_data.last, comp, rng_aux);
196 return true;
197 };
198
199 // check if reverse sorted
200 if ((it2 != (rng_data.first + 1))) return false;
201 sw = true;
202 for (Iter1_t it1 = rng_data.first;
203 it2 != rng_data.last and (sw = comp(*it2, *it1)); it1 =
204 it2++)
205 ;
206 if (size_t(rng_data.last - it2) >= min_insert_partial_sort) return false;
207
208 // reverse the elements between first and it1
209 size_t nreverse = it2 - rng_data.first;
210 Iter1_t alpha(rng_data.first), beta(it2 - 1), mid(
211 rng_data.first + (nreverse >> 1));
212 while (alpha != mid) {
213 using std::swap;
214 swap(*(alpha++), *(beta--));
215 }
216
217 // insert the elements between it1 and last
218 if (it2 != rng_data.last)
219 {
220 sort_range_sort(range<Iter1_t>(it2, rng_data.last), rng_aux, comp);
221 insert_partial_sort(rng_data.first, it2, rng_data.last, comp, rng_aux);
222 };
223 return true;
224}
225;
226//-----------------------------------------------------------------------------
227// function : range_sort
228/// @brief this function divide r_input in two parts, sort it,and merge moving
229/// the elements to range_buf
230/// @param range_input : range with the elements to sort
231/// @param range_buffer : range with the elements sorted
232/// @param comp : object for to compare two elements
233/// @param level : when is 1, sort with the insertionsort algorithm
234/// if not make a recursive call splitting the ranges
235//
236/// @comments : if the number of levels is odd, the data are in the first
237/// parameter of range_sort, and the results appear in the second parameter
238/// If the number of levels is even, the data are in the second
239/// parameter of range_sort, and the results are in the same parameter
240/// The two ranges must have the same size
241//-----------------------------------------------------------------------------
242template<class Iter1_t, class Iter2_t, class Compare>
243static void range_sort(const range<Iter1_t> &range1,
244 const range<Iter2_t> &range2, Compare comp,
245 uint32_t level)
246{
247 //-----------------------------------------------------------------------
248 // metaprogram
249 //-----------------------------------------------------------------------
250 typedef value_iter<Iter1_t> value_t;
251 typedef value_iter<Iter2_t> value2_t;
252 static_assert (std::is_same<value_t, value2_t>::value,
253 "Incompatible iterators\n");
254
255 //-----------------------------------------------------------------------
256 // program
257 //-----------------------------------------------------------------------
258 typedef range<Iter1_t> range_it1;
259 typedef range<Iter2_t> range_it2;
260 assert(range1.size() == range2.size() and level != 0);
261
262 //------------------- check if sort --------------------------------------
263 if (range1.size() > 1024)
264 {
265 if ((level & 1) == 0)
266 {
267 if (check_stable_sort(range2, range1, comp)) return;
268 }
269 else
270 {
271 if (check_stable_sort(range1, range2, comp))
272 {
273 move_forward(range2, range1);
274 return;
275 };
276 };
277 };
278
279 //------------------- normal process -----------------------------------
280 size_t nelem1 = (range1.size() + 1) >> 1;
281 range_it1 range_input1(range1.first, range1.first + nelem1),
282 range_input2(range1.first + nelem1, range1.last);
283
284 if (level < 2)
285 {
286 insert_sort(range_input1.first, range_input1.last, comp);
287 insert_sort(range_input2.first, range_input2.last, comp);
288 }
289 else
290 {
291 range_sort (range_it2(range2.first, range2.first + nelem1),
292 range_input1, comp, level - 1);
293
294 range_sort (range_it2(range2.first + nelem1, range2.last),
295 range_input2, comp, level - 1);
296 };
297
298 merge(range2, range_input1, range_input2, comp);
299}
300;
301//-----------------------------------------------------------------------------
302// function : sort_range_sort
303/// @brief this sort elements using the range_sort function and receiving a
304/// buffer of initialized memory
305/// @param rng_data : range with the elements to sort
306/// @param rng_aux : range of at least the same memory than rng_data used as
307/// auxiliary memory in the sorting
308/// @param comp : object for to compare two elements
309//-----------------------------------------------------------------------------
310template<class Iter1_t, class Iter2_t, class Compare>
311static void sort_range_sort(const range<Iter1_t> &rng_data,
312 const range<Iter2_t> &rng_aux, Compare comp)
313{
314 //-----------------------------------------------------------------------
315 // metaprogram
316 //-----------------------------------------------------------------------
317 typedef value_iter<Iter1_t> value_t;
318 typedef value_iter<Iter2_t> value2_t;
319 static_assert (std::is_same<value_t, value2_t>::value,
320 "Incompatible iterators\n");
321
322 //------------------------------------------------------------------------
323 // program
324 //------------------------------------------------------------------------
325 // minimal number of element before to jump to insertionsort
326 static const uint32_t sort_min = 32;
327 if (rng_data.size() <= sort_min)
328 {
329 insert_sort(rng_data.first, rng_data.last, comp);
330 return;
331 };
332
333#ifdef __BS_DEBUG
334 assert (rng_aux.size () >= rng_data.size ());
335#endif
336
337 range<Iter2_t> rng_buffer(rng_aux.first, rng_aux.first + rng_data.size());
338 uint32_t nlevel =
339 nbits64(((rng_data.size() + sort_min - 1) / sort_min) - 1);
340 //assert (nlevel != 0);
341
342 if ((nlevel & 1) == 0)
343 {
344 range_sort(rng_buffer, rng_data, comp, nlevel);
345 }
346 else
347 {
348 range_sort(rng_data, rng_buffer, comp, nlevel);
349 move_forward(rng_data, rng_buffer);
350 };
351}
352;
353//
354//############################################################################
355// ##
356// S T R U C T ##
357// ##
358// S P I N _ S O R T ##
359// ##
360//############################################################################
361//---------------------------------------------------------------------------
362/// @struct spin_sort
363/// @brief This class implement s stable sort algorithm with 1 thread, with
364/// an auxiliary memory of N/2 elements
365//----------------------------------------------------------------------------
366template<class Iter_t, typename Compare = compare_iter<Iter_t>>
367class spinsort
368{
369 //------------------------------------------------------------------------
370 // DEFINITIONS AND CONSTANTS
371 //------------------------------------------------------------------------
372 typedef value_iter<Iter_t> value_t;
373 typedef range<Iter_t> range_it;
374 typedef range<value_t *> range_buf;
375 // When the number of elements to sort is smaller than Sort_min, are sorted
376 // by the insertion sort algorithm
377 static const uint32_t Sort_min = 36;
378
379 //------------------------------------------------------------------------
380 // VARIABLES
381 //------------------------------------------------------------------------
382 // Pointer to the auxiliary memory
383 value_t *ptr;
384
385 // Number of elements in the auxiliary memory
386 size_t nptr;
387
388 // construct indicate if the auxiliary memory in initialized, and owner
389 // indicate if the auxiliary memory had been created inside the object or
390 // had
391 // been received as a parameter
392 bool construct = false, owner = false;
393
394 //------------------------------------------------------------------------
395 // PRIVATE FUNCTIONS
396 //-------------------------------------------------------------------------
397 spinsort (Iter_t first, Iter_t last, Compare comp, value_t *paux,
398 size_t naux);
399
400public:
401 //------------------------------------------------------------------------
402 // PUBLIC FUNCTIONS
403 //-------------------------------------------------------------------------
404 spinsort(Iter_t first, Iter_t last, Compare comp = Compare())
405 : spinsort(first, last, comp, nullptr, 0) { };
406
407 spinsort(Iter_t first, Iter_t last, Compare comp, range_buf range_aux)
408 : spinsort(first, last, comp, range_aux.first, range_aux.size()) { };
409 //
410 //-----------------------------------------------------------------------
411 // function :~spinsort
412 /// @brief destructor of the struct. Destroy the elements if construct is
413 /// true,
414 /// and return the memory if owner is true
415 //-----------------------------------------------------------------------
416 ~spinsort(void)
417 {
418 if (construct)
419 {
420 destroy(range<value_t *>(ptr, ptr + nptr));
421 construct = false;
422 };
423 if (owner and ptr != nullptr) std::free (ptr: ptr);
424 };
425};
426//----------------------------------------------------------------------------
427// End of class spinsort
428//----------------------------------------------------------------------------
429//
430//-------------------------------------------------------------------------
431// function : spinsort
432/// @brief constructor of the struct
433//
434/// @param first : iterator to the first element of the range to sort
435/// @param last : iterator after the last element to the range to sort
436/// @param comp : object for to compare two elements pointed by Iter_t
437/// iterators
438/// @param paux : pointer to the auxiliary memory provided. If nullptr, the
439/// memory is created inside the class
440/// @param naux : number of elements pointed by paux
441//------------------------------------------------------------------------
442template <class Iter_t, typename Compare>
443spinsort <Iter_t, Compare>
444::spinsort (Iter_t first, Iter_t last, Compare comp, value_t *paux, size_t naux)
445: ptr(paux), nptr(naux), construct(false), owner(false)
446{
447 range<Iter_t> range_input(first, last);
448 assert(range_input.valid());
449
450 size_t nelem = range_input.size();
451 owner = construct = false;
452
453 nptr = (nelem + 1) >> 1;
454 size_t nelem_1 = nptr;
455 size_t nelem_2 = nelem - nelem_1;
456
457 if (nelem <= (Sort_min << 1))
458 {
459 insert_sort(range_input.first, range_input.last, comp);
460 return;
461 };
462
463 //------------------- check if sort ---------------------------------
464 bool sw = true;
465 for (Iter_t it1 = first, it2 = first + 1; it2 != last
466 and (sw = not comp(*it2, *it1)); it1 = it2++) ;
467 if (sw) return;
468
469 //------------------- check if reverse sort -------------------------
470 sw = true;
471 for (Iter_t it1 = first, it2 = first + 1;
472 it2 != last and (sw = comp(*it2, *it1)); it1 = it2++);
473 if (sw)
474 {
475 using std::swap;
476 size_t nelem2 = nelem >> 1;
477 Iter_t it1 = first, it2 = last - 1;
478 for (size_t i = 0; i < nelem2; ++i)
479 swap(*(it1++), *(it2--));
480 return;
481 };
482
483 if (ptr == nullptr)
484 {
485 ptr = reinterpret_cast <value_t*>
486 (std::malloc (size: nptr * sizeof(value_t)));
487
488 if (ptr == nullptr) throw std::bad_alloc();
489 owner = true;
490 };
491 range_buf range_aux(ptr, (ptr + nptr));
492
493 //---------------------------------------------------------------------
494 // Process
495 //---------------------------------------------------------------------
496 uint32_t nlevel = nbits64(num: ((nelem + Sort_min - 1) / Sort_min) - 1) - 1;
497 assert(nlevel != 0);
498
499 if ((nlevel & 1) == 1)
500 {
501 //----------------------------------------------------------------
502 // if the number of levels is odd, the data are in the first
503 // parameter of range_sort, and the results appear in the second
504 // parameter
505 //----------------------------------------------------------------
506 range_it range_1(first, first + nelem_2), range_2(first + nelem_2,
507 last);
508 range_aux = move_construct(range_aux, range_2);
509 construct = true;
510
511 range_sort(range_aux, range_2, comp, nlevel);
512 range_buf rng_bx(range_aux.first, range_aux.first + nelem_2);
513
514 range_sort(range_1, rng_bx, comp, nlevel);
515 merge_half(range_input, rng_bx, range_2, comp);
516 }
517 else
518 {
519 //----------------------------------------------------------------
520 // If the number of levels is even, the data are in the second
521 // parameter of range_sort, and the results are in the same
522 // parameter
523 //----------------------------------------------------------------
524 range_it range_1(first, first + nelem_1), range_2(first + nelem_1,
525 last);
526 range_aux = move_construct(range_aux, range_1);
527 construct = true;
528
529 range_sort(range_1, range_aux, comp, nlevel);
530
531 range_1.last = range_1.first + range_2.size();
532 range_sort(range_1, range_2, comp, nlevel);
533 merge_half(range_input, range_aux, range_2, comp);
534 };
535};
536
537//****************************************************************************
538};// End namepspace spin_detail
539//****************************************************************************
540//
541namespace bsc = boost::sort::common;
542//-----------------------------------------------------------------------------
543// function : spinsort
544/// @brief this function implement a single thread stable sort
545///
546/// @param first : iterator to the first element of the range to sort
547/// @param last : iterator after the last element to the range to sort
548/// @param comp : object for to compare two elements pointed by Iter_t
549/// iterators
550//-----------------------------------------------------------------------------
551template <class Iter_t, class Compare = compare_iter<Iter_t>>
552inline void spinsort (Iter_t first, Iter_t last, Compare comp = Compare())
553{
554 spin_detail::spinsort <Iter_t, Compare> (first, last, comp);
555};
556
557template <class Iter_t, class Compare = compare_iter<Iter_t>>
558inline void indirect_spinsort (Iter_t first, Iter_t last,
559 Compare comp = Compare())
560{
561 typedef typename std::vector<Iter_t>::iterator itx_iter;
562 typedef common::less_ptr_no_null <Iter_t, Compare> itx_comp;
563 common::indirect_sort (spinsort<itx_iter, itx_comp>, first, last, comp);
564};
565
566//****************************************************************************
567};// End namespace sort
568};// End namepspace boost
569//****************************************************************************
570//
571#endif
572

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