]>
Commit | Line | Data |
---|---|---|
11fdf7f2 TL |
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> | |
1e59de90 | 26 | |
11fdf7f2 TL |
27 | #include <boost/move/detail/workaround.hpp> |
28 | #include <boost/move/detail/iterator_traits.hpp> | |
29 | #include <boost/move/algo/detail/is_sorted.hpp> | |
30 | #include <boost/move/utility_core.hpp> | |
31 | ||
1e59de90 TL |
32 | #if defined(BOOST_CLANG) || (defined(BOOST_GCC) && (BOOST_GCC >= 40600)) |
33 | #pragma GCC diagnostic push | |
34 | #pragma GCC diagnostic ignored "-Wsign-conversion" | |
35 | #endif | |
36 | ||
11fdf7f2 TL |
37 | namespace boost { namespace movelib{ |
38 | ||
39 | template <class RandomAccessIterator, class Compare> | |
40 | class heap_sort_helper | |
41 | { | |
1e59de90 | 42 | typedef typename boost::movelib::iter_size<RandomAccessIterator>::type size_type; |
11fdf7f2 TL |
43 | typedef typename boost::movelib::iterator_traits<RandomAccessIterator>::value_type value_type; |
44 | ||
45 | static void adjust_heap(RandomAccessIterator first, size_type hole_index, size_type const len, value_type &value, Compare comp) | |
46 | { | |
47 | size_type const top_index = hole_index; | |
1e59de90 | 48 | size_type second_child = size_type(2u*(hole_index + 1u)); |
11fdf7f2 TL |
49 | |
50 | while (second_child < len) { | |
1e59de90 | 51 | if (comp(*(first + second_child), *(first + size_type(second_child - 1u)))) |
11fdf7f2 TL |
52 | second_child--; |
53 | *(first + hole_index) = boost::move(*(first + second_child)); | |
54 | hole_index = second_child; | |
1e59de90 | 55 | second_child = size_type(2u * (second_child + 1u)); |
11fdf7f2 TL |
56 | } |
57 | if (second_child == len) { | |
1e59de90 TL |
58 | *(first + hole_index) = boost::move(*(first + size_type(second_child - 1u))); |
59 | hole_index = size_type(second_child - 1); | |
11fdf7f2 TL |
60 | } |
61 | ||
62 | { //push_heap-like ending | |
1e59de90 | 63 | size_type parent = size_type((hole_index - 1u) / 2u); |
11fdf7f2 TL |
64 | while (hole_index > top_index && comp(*(first + parent), value)) { |
65 | *(first + hole_index) = boost::move(*(first + parent)); | |
66 | hole_index = parent; | |
1e59de90 | 67 | parent = size_type((hole_index - 1u) / 2u); |
11fdf7f2 TL |
68 | } |
69 | *(first + hole_index) = boost::move(value); | |
70 | } | |
71 | } | |
72 | ||
73 | static void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp) | |
74 | { | |
75 | size_type const len = size_type(last - first); | |
76 | if (len > 1) { | |
1e59de90 | 77 | size_type parent = size_type(len/2u - 1u); |
11fdf7f2 TL |
78 | |
79 | do { | |
80 | value_type v(boost::move(*(first + parent))); | |
81 | adjust_heap(first, parent, len, v, comp); | |
82 | }while (parent--); | |
83 | } | |
84 | } | |
85 | ||
86 | static void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp) | |
87 | { | |
88 | size_type len = size_type(last - first); | |
89 | while (len > 1) { | |
90 | //move biggest to the safe zone | |
91 | --last; | |
92 | value_type v(boost::move(*last)); | |
93 | *last = boost::move(*first); | |
94 | adjust_heap(first, size_type(0), --len, v, comp); | |
95 | } | |
96 | } | |
97 | ||
98 | public: | |
99 | static void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp) | |
100 | { | |
101 | make_heap(first, last, comp); | |
102 | sort_heap(first, last, comp); | |
103 | BOOST_ASSERT(boost::movelib::is_sorted(first, last, comp)); | |
104 | } | |
105 | }; | |
106 | ||
107 | template <class RandomAccessIterator, class Compare> | |
108 | BOOST_MOVE_FORCEINLINE void heap_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp) | |
109 | { | |
110 | heap_sort_helper<RandomAccessIterator, Compare>::sort(first, last, comp); | |
111 | } | |
112 | ||
113 | }} //namespace boost { namespace movelib{ | |
114 | ||
1e59de90 TL |
115 | #if defined(BOOST_CLANG) || (defined(BOOST_GCC) && (BOOST_GCC >= 40600)) |
116 | #pragma GCC diagnostic pop | |
117 | #endif | |
118 | ||
11fdf7f2 TL |
119 | #include <boost/move/detail/config_end.hpp> |
120 | ||
121 | #endif //#ifndef BOOST_MOVE_DETAIL_HEAP_SORT_HPP |