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_SORT_HPP
13#define BOOST_MOVE_ADAPTIVE_SORT_HPP
14
15#include <boost/move/detail/config_begin.hpp>
16#include <boost/move/algo/detail/adaptive_sort_merge.hpp>
17
18namespace boost {
19namespace movelib {
20
21//! <b>Effects</b>: Sorts the elements in the range [first, last) in ascending order according
22//! to comparison functor "comp". The sort is stable (order of equal elements
23//! is guaranteed to be preserved). Performance is improved if additional raw storage is
24//! provided.
25//!
26//! <b>Requires</b>:
27//! - RandIt must meet the requirements of ValueSwappable and RandomAccessIterator.
28//! - The type of dereferenced RandIt must meet the requirements of MoveAssignable and MoveConstructible.
29//!
30//! <b>Parameters</b>:
31//! - first, last: the range of elements to sort
32//! - comp: comparison function object which returns true if the first argument is is ordered before the second.
33//! - uninitialized, uninitialized_len: raw storage starting on "uninitialized", able to hold "uninitialized_len"
34//! elements of type iterator_traits<RandIt>::value_type. Maximum performance is achieved when uninitialized_len
35//! is ceil(std::distance(first, last)/2).
36//!
37//! <b>Throws</b>: If comp throws or the move constructor, move assignment or swap of the type
38//! of dereferenced RandIt throws.
39//!
40//! <b>Complexity</b>: Always K x O(Nxlog(N)) comparisons and move assignments/constructors/swaps.
41//! Comparisons are close to minimum even with no additional memory. Constant factor for data movement is minimized
42//! when uninitialized_len is ceil(std::distance(first, last)/2). Pretty good enough performance is achieved when
43//! ceil(sqrt(std::distance(first, last)))*2.
44//!
45//! <b>Caution</b>: Experimental implementation, not production-ready.
46template<class RandIt, class RandRawIt, class Compare>
47void adaptive_sort( RandIt first, RandIt last, Compare comp
48 , RandRawIt uninitialized
49 , std::size_t uninitialized_len)
50{
51 typedef typename iterator_traits<RandIt>::size_type size_type;
52 typedef typename iterator_traits<RandIt>::value_type value_type;
53
54 ::boost::movelib::detail_adaptive::adaptive_xbuf<value_type, RandRawIt> xbuf(uninitialized, uninitialized_len);
55 ::boost::movelib::detail_adaptive::adaptive_sort_impl(first, size_type(last - first), comp, xbuf);
56}
57
58template<class RandIt, class Compare>
59void adaptive_sort( RandIt first, RandIt last, Compare comp)
60{
61 typedef typename iterator_traits<RandIt>::value_type value_type;
62 adaptive_sort(first, last, comp, (value_type*)0, 0u);
63}
64
65} //namespace movelib {
66} //namespace boost {
67
68#include <boost/move/detail/config_end.hpp>
69
70#endif //#define BOOST_MOVE_ADAPTIVE_SORT_HPP
71