1 //////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Ion Gaztanaga 2017-2018.
4 // Distributed under the Boost Software License, Version 1.0.
5 // (See accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7 //
8 // See http://www.boost.org/libs/move for documentation.
9 //
10 //////////////////////////////////////////////////////////////////////////////
11
12 //! \file
13
14 #ifndef BOOST_MOVE_DETAIL_HEAP_SORT_HPP
15 #define BOOST_MOVE_DETAIL_HEAP_SORT_HPP
16
17 #ifndef BOOST_CONFIG_HPP
18 # include <boost/config.hpp>
19 #endif
20 #
21 #if defined(BOOST_HAS_PRAGMA_ONCE)
22 # pragma once
23 #endif
24
25 #include <boost/move/detail/config_begin.hpp>
26 #include <boost/move/detail/workaround.hpp>
27 #include <boost/move/detail/iterator_traits.hpp>
28 #include <boost/move/algo/detail/is_sorted.hpp>
29 #include <boost/move/utility_core.hpp>
30
31 namespace boost { namespace movelib{
32
33 template <class RandomAccessIterator, class Compare>
34 class heap_sort_helper
35 {
36 typedef typename boost::movelib::iterator_traits<RandomAccessIterator>::size_type size_type;
37 typedef typename boost::movelib::iterator_traits<RandomAccessIterator>::value_type value_type;
38
adjust_heap(RandomAccessIterator first,size_type hole_index,size_type const len,value_type & value,Compare comp)39 static void adjust_heap(RandomAccessIterator first, size_type hole_index, size_type const len, value_type &value, Compare comp)
40 {
41 size_type const top_index = hole_index;
42 size_type second_child = 2 * (hole_index + 1);
43
44 while (second_child < len) {
45 if (comp(*(first + second_child), *(first + (second_child - 1))))
46 second_child--;
47 *(first + hole_index) = boost::move(*(first + second_child));
48 hole_index = second_child;
49 second_child = 2 * (second_child + 1);
50 }
51 if (second_child == len) {
52 *(first + hole_index) = boost::move(*(first + (second_child - 1)));
53 hole_index = second_child - 1;
54 }
55
56 { //push_heap-like ending
57 size_type parent = (hole_index - 1) / 2;
58 while (hole_index > top_index && comp(*(first + parent), value)) {
59 *(first + hole_index) = boost::move(*(first + parent));
60 hole_index = parent;
61 parent = (hole_index - 1) / 2;
62 }
63 *(first + hole_index) = boost::move(value);
64 }
65 }
66
make_heap(RandomAccessIterator first,RandomAccessIterator last,Compare comp)67 static void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
68 {
69 size_type const len = size_type(last - first);
70 if (len > 1) {
71 size_type parent = len/2u - 1u;
72
73 do {
74 value_type v(boost::move(*(first + parent)));
75 adjust_heap(first, parent, len, v, comp);
76 }while (parent--);
77 }
78 }
79
sort_heap(RandomAccessIterator first,RandomAccessIterator last,Compare comp)80 static void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
81 {
82 size_type len = size_type(last - first);
83 while (len > 1) {
84 //move biggest to the safe zone
85 --last;
86 value_type v(boost::move(*last));
87 *last = boost::move(*first);
88 adjust_heap(first, size_type(0), --len, v, comp);
89 }
90 }
91
92 public:
sort(RandomAccessIterator first,RandomAccessIterator last,Compare comp)93 static void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
94 {
95 make_heap(first, last, comp);
96 sort_heap(first, last, comp);
97 BOOST_ASSERT(boost::movelib::is_sorted(first, last, comp));
98 }
99 };
100
101 template <class RandomAccessIterator, class Compare>
heap_sort(RandomAccessIterator first,RandomAccessIterator last,Compare comp)102 BOOST_MOVE_FORCEINLINE void heap_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
103 {
104 heap_sort_helper<RandomAccessIterator, Compare>::sort(first, last, comp);
105 }
106
107 }} //namespace boost { namespace movelib{
108
109 #include <boost/move/detail/config_end.hpp>
110
111 #endif //#ifndef BOOST_MOVE_DETAIL_HEAP_SORT_HPP
112