ceph/src/boost/boost/move/algo/detail/insertion_sort.hpp

   1 //////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga 2014-2014.
   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_INSERT_SORT_HPP
  15 #define BOOST_MOVE_DETAIL_INSERT_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/utility_core.hpp>
  26 #include <boost/move/algo/move.hpp>
  27 #include <boost/move/detail/iterator_traits.hpp>
  28 #include <boost/move/adl_move_swap.hpp>
  29 #include <boost/move/utility_core.hpp>
  30 #include <boost/move/detail/placement_new.hpp>
  31 #include <boost/move/detail/destruct_n.hpp>
  32 #include <boost/move/algo/detail/basic_op.hpp>
  33 #include <boost/move/detail/placement_new.hpp>
  34 #include <boost/move/detail/iterator_to_raw_pointer.hpp>
  35
  36 namespace boost {  namespace movelib{
  37
  38 // @cond
  39
  40 template <class Compare, class ForwardIterator, class BirdirectionalIterator, class Op>
  41 void insertion_sort_op(ForwardIterator first1, ForwardIterator last1, BirdirectionalIterator first2, Compare comp, Op op)
  42 {
  43    if (first1 != last1){
  44       BirdirectionalIterator last2 = first2;
  45       op(first1, last2);
  46       for (++last2; ++first1 != last1; ++last2){
  47          BirdirectionalIterator j2 = last2;
  48          BirdirectionalIterator i2 = j2;
  49          if (comp(*first1, *--i2)){
  50             op(i2, j2);
  51             for (--j2; i2 != first2 && comp(*first1, *--i2); --j2) {
  52                op(i2, j2);
  53             }
  54          }
  55          op(first1, j2);
  56       }
  57    }
  58 }
  59
  60 template <class Compare, class ForwardIterator, class BirdirectionalIterator>
  61 void insertion_sort_swap(ForwardIterator first1, ForwardIterator last1, BirdirectionalIterator first2, Compare comp)
  62 {
  63    insertion_sort_op(first1, last1, first2, comp, swap_op());
  64 }
  65
  66
  67 template <class Compare, class ForwardIterator, class BirdirectionalIterator>
  68 void insertion_sort_copy(ForwardIterator first1, ForwardIterator last1, BirdirectionalIterator first2, Compare comp)
  69 {
  70    insertion_sort_op(first1, last1, first2, comp, move_op());
  71 }
  72
  73 // @endcond
  74
  75 template <class Compare, class BirdirectionalIterator>
  76 void insertion_sort(BirdirectionalIterator first, BirdirectionalIterator last, Compare comp)
  77 {
  78    typedef typename boost::movelib::iterator_traits<BirdirectionalIterator>::value_type value_type;
  79    if (first != last){
  80       BirdirectionalIterator i = first;
  81       for (++i; i != last; ++i){
  82          BirdirectionalIterator j = i;
  83          if (comp(*i,  *--j)) {
  84             value_type tmp(::boost::move(*i));
  85             *i = ::boost::move(*j);
  86             for (BirdirectionalIterator k = j; k != first && comp(tmp,  *--k); --j) {
  87                *j = ::boost::move(*k);
  88             }
  89             *j = ::boost::move(tmp);
  90          }
  91       }
  92    }
  93 }
  94
  95 template <class Compare, class BirdirectionalIterator, class BirdirectionalRawIterator>
  96 void insertion_sort_uninitialized_copy
  97    (BirdirectionalIterator first1, BirdirectionalIterator const last1
  98    , BirdirectionalRawIterator const first2
  99    , Compare comp)
 100 {
 101    typedef typename iterator_traits<BirdirectionalIterator>::value_type value_type;
 102    if (first1 != last1){
 103       BirdirectionalRawIterator last2 = first2;
 104       ::new((iterator_to_raw_pointer)(last2), boost_move_new_t()) value_type(::boost::move(*first1));
 105       destruct_n<value_type, BirdirectionalRawIterator> d(first2);
 106       d.incr();
 107       for (++last2; ++first1 != last1; ++last2){
 108          BirdirectionalRawIterator j2 = last2;
 109          BirdirectionalRawIterator k2 = j2;
 110          if (comp(*first1, *--k2)){
 111             ::new((iterator_to_raw_pointer)(j2), boost_move_new_t()) value_type(::boost::move(*k2));
 112             d.incr();
 113             for (--j2; k2 != first2 && comp(*first1, *--k2); --j2)
 114                *j2 = ::boost::move(*k2);
 115             *j2 = ::boost::move(*first1);
 116          }
 117          else{
 118             ::new((iterator_to_raw_pointer)(j2), boost_move_new_t()) value_type(::boost::move(*first1));
 119             d.incr();
 120          }
 121       }
 122       d.release();
 123    }
 124 }
 125
 126 }} //namespace boost {  namespace movelib{
 127
 128 #endif //#ifndef BOOST_MOVE_DETAIL_INSERT_SORT_HPP