]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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_ALGO_BUFFERLESS_MERGE_SORT_HPP | |
15 | #define BOOST_MOVE_ALGO_BUFFERLESS_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/adl_move_swap.hpp> | |
30 | ||
31 | #include <boost/move/algo/move.hpp> | |
32 | #include <boost/move/algo/detail/merge.hpp> | |
33 | ||
34 | #include <boost/move/detail/iterator_traits.hpp> | |
35 | #include <boost/move/algo/detail/insertion_sort.hpp> | |
36 | #include <cassert> | |
37 | ||
38 | namespace boost { | |
39 | namespace movelib { | |
40 | // @cond | |
41 | namespace detail_bufferless_mergesort { | |
42 | ||
43 | static const std::size_t UnbufferedMergeSortInsertionSortThreshold = 16; | |
44 | ||
45 | //A in-placed version based on: | |
46 | //Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola. | |
47 | //``Practical in-place mergesort''. Nordic Journal of Computing, 1996. | |
48 | ||
49 | template<class RandIt, class Compare> | |
50 | void bufferless_merge_sort(RandIt first, RandIt last, Compare comp); | |
51 | ||
52 | template<class RandIt, class Compare> | |
53 | void swap_sort(RandIt const first, RandIt const last, RandIt const buffer_first, RandIt const buffer_last, Compare comp, bool buffer_at_right) | |
54 | { | |
55 | typedef typename iterator_traits<RandIt>::size_type size_type; | |
56 | if (size_type(last - first) > UnbufferedMergeSortInsertionSortThreshold) { | |
57 | RandIt m = first + (last - first) / 2; | |
58 | bufferless_merge_sort(first, m, comp); | |
59 | bufferless_merge_sort(m, last, comp); | |
60 | if(buffer_at_right){ | |
61 | //Use antistable to minimize movements (if equal, move first half elements | |
62 | //to maximize the chance last half elements are already in place. | |
63 | boost::movelib::swap_merge_right(first, m, last, buffer_last, boost::movelib::antistable<Compare>(comp)); | |
64 | } | |
65 | else{ | |
66 | boost::movelib::swap_merge_left(buffer_first, first, m, last, comp); | |
67 | } | |
68 | } | |
69 | else | |
70 | boost::movelib::insertion_sort_swap(first, last, buffer_first, comp); | |
71 | } | |
72 | ||
73 | template<class RandIt, class Compare> | |
74 | void bufferless_merge_sort(RandIt const first, RandIt const last, Compare comp) | |
75 | { | |
76 | typedef typename iterator_traits<RandIt>::size_type size_type; | |
77 | size_type len = size_type(last - first); | |
78 | if (len > size_type(UnbufferedMergeSortInsertionSortThreshold)) { | |
79 | len /= 2; | |
80 | RandIt h = last - len; //ceil(half) | |
81 | RandIt f = h - len; //ceil(first) | |
82 | swap_sort(f, h, h, last, comp, true); //[h, last) contains sorted elements | |
83 | ||
84 | //Divide unsorted first half in two | |
85 | len = size_type(h - first); | |
86 | while (len > size_type(UnbufferedMergeSortInsertionSortThreshold)) { | |
87 | len /= 2; | |
88 | RandIt n = h; //new end | |
89 | h = n - len; //ceil(half') | |
90 | f = h - len; //ceil(first') | |
91 | swap_sort(h, n, f, h, comp, false); // the first half of the previous working area [f, h) | |
92 | //contains sorted elements: working area in the middle [h, n) | |
93 | //Now merge small (left) sorted with big (right) sorted (buffer is between them) | |
94 | swap_merge_with_right_placed(f, h, h, n, last, comp); | |
95 | } | |
96 | ||
97 | boost::movelib::insertion_sort(first, h, comp); | |
98 | boost::movelib::merge_bufferless(first, h, last, comp); | |
99 | } | |
100 | else{ | |
101 | boost::movelib::insertion_sort(first, last, comp); | |
102 | } | |
103 | } | |
104 | ||
105 | } //namespace detail_bufferless_mergesort { | |
106 | ||
107 | // @endcond | |
108 | ||
109 | //Unstable bufferless merge sort | |
110 | template<class RandIt, class Compare> | |
111 | void bufferless_merge_sort(RandIt first, RandIt last, Compare comp) | |
112 | { | |
113 | detail_bufferless_mergesort::bufferless_merge_sort(first, last, comp); | |
114 | } | |
115 | ||
116 | }} //namespace boost::movelib | |
117 | ||
118 | #include <boost/move/detail/config_end.hpp> | |
119 | ||
120 | #endif //#ifndef BOOST_MOVE_ALGO_BUFFERLESS_MERGE_SORT_HPP |