ceph/src/boost/libs/move/include/boost/move/algo/adaptive_merge.hpp

   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