ceph/src/boost/libs/move/include/boost/move/algo/detail/merge_sort.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 //! \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>
  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>
  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 Compare>
  83 void merge_sort_uninitialized_copy( RandIt first, RandIt last
  84                                  , typename iterator_traits<RandIt>::value_type* 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> 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 Compare>
 109 void merge_sort( RandIt first, RandIt last, Compare comp
 110                , typename iterator_traits<RandIt>::value_type* 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> 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 }} //namespace boost {  namespace movelib{
 136
 137 #include <boost/move/detail/config_end.hpp>
 138
 139 #endif //#ifndef BOOST_MOVE_DETAIL_MERGE_SORT_HPP