1 //////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Ion Gaztanaga 2015-2016.
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_MERGE_SORT_HPP
15 #define BOOST_MOVE_DETAIL_MERGE_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
28 #include <boost/move/utility_core.hpp>
29 #include <boost/move/algo/move.hpp>
30 #include <boost/move/algo/detail/merge.hpp>
31 #include <boost/move/detail/iterator_traits.hpp>
32 #include <boost/move/adl_move_swap.hpp>
33 #include <boost/move/detail/destruct_n.hpp>
34 #include <boost/move/algo/detail/insertion_sort.hpp>
35 #include <cassert>
36
37 namespace boost {
38 namespace movelib {
39
40 // @cond
41
42 static const unsigned MergeSortInsertionSortThreshold = 16;
43
44 template <class RandIt, class Compare>
inplace_stable_sort(RandIt first,RandIt last,Compare comp)45 void inplace_stable_sort(RandIt first, RandIt last, Compare comp)
46 {
47 typedef typename iterator_traits<RandIt>::size_type size_type;
48 if (size_type(last - first) <= size_type(MergeSortInsertionSortThreshold)) {
49 insertion_sort(first, last, comp);
50 return;
51 }
52 RandIt middle = first + (last - first) / 2;
53 inplace_stable_sort(first, middle, comp);
54 inplace_stable_sort(middle, last, comp);
55 merge_bufferless_ONlogN_recursive
56 (first, middle, last, size_type(middle - first), size_type(last - middle), comp);
57 }
58
59 // @endcond
60
61 template<class RandIt, class RandIt2, class Compare>
merge_sort_copy(RandIt first,RandIt last,RandIt2 dest,Compare comp)62 void merge_sort_copy( RandIt first, RandIt last
63 , RandIt2 dest, Compare comp)
64 {
65 typedef typename iterator_traits<RandIt>::size_type size_type;
66
67 size_type const count = size_type(last - first);
68 if(count <= MergeSortInsertionSortThreshold){
69 insertion_sort_copy(first, last, dest, comp);
70 }
71 else{
72 size_type const half = count/2;
73 merge_sort_copy(first + half, last , dest+half , comp);
74 merge_sort_copy(first , first + half, first + half, comp);
75 merge_with_right_placed
76 ( first + half, first + half + half
77 , dest, dest+half, dest + count
78 , comp);
79 }
80 }
81
82 template<class RandIt, class RandItRaw, class Compare>
merge_sort_uninitialized_copy(RandIt first,RandIt last,RandItRaw uninitialized,Compare comp)83 void merge_sort_uninitialized_copy( RandIt first, RandIt last
84 , RandItRaw uninitialized
85 , Compare comp)
86 {
87 typedef typename iterator_traits<RandIt>::size_type size_type;
88 typedef typename iterator_traits<RandIt>::value_type value_type;
89
90 size_type const count = size_type(last - first);
91 if(count <= MergeSortInsertionSortThreshold){
92 insertion_sort_uninitialized_copy(first, last, uninitialized, comp);
93 }
94 else{
95 size_type const half = count/2;
96 merge_sort_uninitialized_copy(first + half, last, uninitialized + half, comp);
97 destruct_n<value_type, RandItRaw> d(uninitialized+half);
98 d.incr(count-half);
99 merge_sort_copy(first, first + half, first + half, comp);
100 uninitialized_merge_with_right_placed
101 ( first + half, first + half + half
102 , uninitialized, uninitialized+half, uninitialized+count
103 , comp);
104 d.release();
105 }
106 }
107
108 template<class RandIt, class RandItRaw, class Compare>
merge_sort(RandIt first,RandIt last,Compare comp,RandItRaw uninitialized)109 void merge_sort( RandIt first, RandIt last, Compare comp
110 , RandItRaw uninitialized)
111 {
112 typedef typename iterator_traits<RandIt>::size_type size_type;
113 typedef typename iterator_traits<RandIt>::value_type value_type;
114
115 size_type const count = size_type(last - first);
116 if(count <= MergeSortInsertionSortThreshold){
117 insertion_sort(first, last, comp);
118 }
119 else{
120 size_type const half = count/2;
121 size_type const rest = count - half;
122 RandIt const half_it = first + half;
123 RandIt const rest_it = first + rest;
124
125 merge_sort_uninitialized_copy(half_it, last, uninitialized, comp);
126 destruct_n<value_type, RandItRaw> d(uninitialized);
127 d.incr(rest);
128 merge_sort_copy(first, half_it, rest_it, comp);
129 merge_with_right_placed
130 ( uninitialized, uninitialized + rest
131 , first, rest_it, last, antistable<Compare>(comp));
132 }
133 }
134
135 ///@cond
136
137 template<class RandIt, class RandItRaw, class Compare>
merge_sort_with_constructed_buffer(RandIt first,RandIt last,Compare comp,RandItRaw buffer)138 void merge_sort_with_constructed_buffer( RandIt first, RandIt last, Compare comp, RandItRaw buffer)
139 {
140 typedef typename iterator_traits<RandIt>::size_type size_type;
141
142 size_type const count = size_type(last - first);
143 if(count <= MergeSortInsertionSortThreshold){
144 insertion_sort(first, last, comp);
145 }
146 else{
147 size_type const half = count/2;
148 size_type const rest = count - half;
149 RandIt const half_it = first + half;
150 RandIt const rest_it = first + rest;
151
152 merge_sort_copy(half_it, last, buffer, comp);
153 merge_sort_copy(first, half_it, rest_it, comp);
154 merge_with_right_placed
155 (buffer, buffer + rest
156 , first, rest_it, last, antistable<Compare>(comp));
157 }
158 }
159
160 template<typename RandIt, typename Pointer,
161 typename Distance, typename Compare>
stable_sort_ONlogN_recursive(RandIt first,RandIt last,Pointer buffer,Distance buffer_size,Compare comp)162 void stable_sort_ONlogN_recursive(RandIt first, RandIt last, Pointer buffer, Distance buffer_size, Compare comp)
163 {
164 typedef typename iterator_traits<RandIt>::size_type size_type;
165 if (size_type(last - first) <= size_type(MergeSortInsertionSortThreshold)) {
166 insertion_sort(first, last, comp);
167 }
168 else {
169 const size_type len = (last - first) / 2;
170 const RandIt middle = first + len;
171 if (len > ((buffer_size+1)/2)){
172 stable_sort_ONlogN_recursive(first, middle, buffer, buffer_size, comp);
173 stable_sort_ONlogN_recursive(middle, last, buffer, buffer_size, comp);
174 }
175 else{
176 merge_sort_with_constructed_buffer(first, middle, comp, buffer);
177 merge_sort_with_constructed_buffer(middle, last, comp, buffer);
178 }
179 merge_adaptive_ONlogN_recursive(first, middle, last,
180 size_type(middle - first),
181 size_type(last - middle),
182 buffer, buffer_size,
183 comp);
184 }
185 }
186
187 template<typename BidirectionalIterator, typename Compare, typename RandRawIt>
stable_sort_adaptive_ONlogN2(BidirectionalIterator first,BidirectionalIterator last,Compare comp,RandRawIt uninitialized,std::size_t uninitialized_len)188 void stable_sort_adaptive_ONlogN2(BidirectionalIterator first,
189 BidirectionalIterator last,
190 Compare comp,
191 RandRawIt uninitialized,
192 std::size_t uninitialized_len)
193 {
194 typedef typename iterator_traits<BidirectionalIterator>::value_type value_type;
195
196 ::boost::movelib::adaptive_xbuf<value_type, RandRawIt> xbuf(uninitialized, uninitialized_len);
197 xbuf.initialize_until(uninitialized_len, *first);
198 stable_sort_ONlogN_recursive(first, last, uninitialized, uninitialized_len, comp);
199 }
200
201 ///@endcond
202
203 }} //namespace boost { namespace movelib{
204
205 #include <boost/move/detail/config_end.hpp>
206
207 #endif //#ifndef BOOST_MOVE_DETAIL_MERGE_SORT_HPP
208