]>
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 | #ifndef BOOST_MOVE_ADAPTIVE_MERGE_HPP | |
13 | #define BOOST_MOVE_ADAPTIVE_MERGE_HPP | |
14 | ||
15 | #include <boost/move/detail/config_begin.hpp> | |
16 | #include <boost/move/algo/detail/adaptive_sort_merge.hpp> | |
17 | ||
18 | namespace boost { | |
19 | namespace movelib { | |
20 | ||
21 | //! <b>Effects</b>: Merges two consecutive sorted ranges [first, middle) and [middle, last) | |
22 | //! into one sorted range [first, last) according to the given comparison function comp. | |
23 | //! The algorithm is stable (if there are equivalent elements in the original two ranges, | |
24 | //! the elements from the first range (preserving their original order) precede the elements | |
25 | //! from the second range (preserving their original order). | |
26 | //! | |
27 | //! <b>Requires</b>: | |
28 | //! - RandIt must meet the requirements of ValueSwappable and RandomAccessIterator. | |
29 | //! - The type of dereferenced RandIt must meet the requirements of MoveAssignable and MoveConstructible. | |
30 | //! | |
31 | //! <b>Parameters</b>: | |
32 | //! - first: the beginning of the first sorted range. | |
33 | //! - middle: the end of the first sorted range and the beginning of the second | |
34 | //! - last: the end of the second sorted range | |
35 | //! - comp: comparison function object which returns true if the first argument is is ordered before the second. | |
36 | //! - uninitialized, uninitialized_len: raw storage starting on "uninitialized", able to hold "uninitialized_len" | |
37 | //! elements of type iterator_traits<RandIt>::value_type. Maximum performance is achieved when uninitialized_len | |
38 | //! is min(std::distance(first, middle), std::distance(middle, last)). | |
39 | //! | |
40 | //! <b>Throws</b>: If comp throws or the move constructor, move assignment or swap of the type | |
41 | //! of dereferenced RandIt throws. | |
42 | //! | |
43 | //! <b>Complexity</b>: Always K x O(N) comparisons and move assignments/constructors/swaps. | |
44 | //! Constant factor for comparisons and data movement is minimized when uninitialized_len | |
45 | //! is min(std::distance(first, middle), std::distance(middle, last)). | |
46 | //! Pretty good enough performance is achieved when uninitialized_len is | |
47 | //! ceil(sqrt(std::distance(first, last)))*2. | |
48 | //! | |
49 | //! <b>Caution</b>: Experimental implementation, not production-ready. | |
50 | template<class RandIt, class Compare> | |
51 | void adaptive_merge( RandIt first, RandIt middle, RandIt last, Compare comp | |
52 | , typename iterator_traits<RandIt>::value_type* uninitialized = 0 | |
53 | , std::size_t uninitialized_len = 0) | |
54 | { | |
55 | typedef typename iterator_traits<RandIt>::size_type size_type; | |
56 | typedef typename iterator_traits<RandIt>::value_type value_type; | |
57 | ||
58 | ::boost::movelib::detail_adaptive::adaptive_xbuf<value_type> xbuf(uninitialized, uninitialized_len); | |
59 | ::boost::movelib::detail_adaptive::adaptive_merge_impl(first, size_type(middle - first), size_type(last - middle), comp, xbuf); | |
60 | } | |
61 | ||
62 | } //namespace movelib { | |
63 | } //namespace boost { | |
64 | ||
65 | #include <boost/move/detail/config_end.hpp> | |
66 | ||
67 | #endif //#define BOOST_MOVE_ADAPTIVE_MERGE_HPP |