algo/detail/insertion_sort.hpp

0001 //////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Ion Gaztanaga 2014-2014.
0004 // Distributed under the Boost Software License, Version 1.0.
0005 // (See accompanying file LICENSE_1_0.txt or copy at
0006 // http://www.boost.org/LICENSE_1_0.txt)
0007 //
0008 // See http://www.boost.org/libs/move for documentation.
0009 //
0010 //////////////////////////////////////////////////////////////////////////////
0011
0012 //! \file
0013
0014 #ifndef BOOST_MOVE_DETAIL_INSERT_SORT_HPP
0015 #define BOOST_MOVE_DETAIL_INSERT_SORT_HPP
0016
0017 #ifndef BOOST_CONFIG_HPP
0018 #  include <boost/config.hpp>
0019 #endif
0020 #
0021 #if defined(BOOST_HAS_PRAGMA_ONCE)
0022 #  pragma once
0023 #endif
0024
0025 #include <boost/move/utility_core.hpp>
0026 #include <boost/move/algo/move.hpp>
0027 #include <boost/move/detail/iterator_traits.hpp>
0028 #include <boost/move/adl_move_swap.hpp>
0029 #include <boost/move/utility_core.hpp>
0030 #include <boost/move/detail/placement_new.hpp>
0031 #include <boost/move/detail/destruct_n.hpp>
0032 #include <boost/move/algo/detail/basic_op.hpp>
0033 #include <boost/move/detail/placement_new.hpp>
0034 #include <boost/move/detail/iterator_to_raw_pointer.hpp>
0035
0036 #if defined(BOOST_CLANG) || (defined(BOOST_GCC) && (BOOST_GCC >= 40600))
0037 #pragma GCC diagnostic push
0038 #pragma GCC diagnostic ignored "-Wsign-conversion"
0039 #endif
0040
0041 namespace boost {  namespace movelib{
0042
0043 // @cond
0044
0045 template <class Compare, class ForwardIterator, class BirdirectionalIterator, class Op>
0046 void insertion_sort_op(ForwardIterator first1, ForwardIterator last1, BirdirectionalIterator first2, Compare comp, Op op)
0047 {
0048    if (first1 != last1){
0049       BirdirectionalIterator last2 = first2;
0050       op(first1, last2);
0051       for (++last2; ++first1 != last1; ++last2){
0052          BirdirectionalIterator j2 = last2;
0053          BirdirectionalIterator i2 = j2;
0054          if (comp(*first1, *--i2)){
0055             op(i2, j2);
0056             for (--j2; i2 != first2 && comp(*first1, *--i2); --j2) {
0057                op(i2, j2);
0058             }
0059          }
0060          op(first1, j2);
0061       }
0062    }
0063 }
0064
0065 template <class Compare, class ForwardIterator, class BirdirectionalIterator>
0066 void insertion_sort_swap(ForwardIterator first1, ForwardIterator last1, BirdirectionalIterator first2, Compare comp)
0067 {
0068    insertion_sort_op(first1, last1, first2, comp, swap_op());
0069 }
0070
0071
0072 template <class Compare, class ForwardIterator, class BirdirectionalIterator>
0073 void insertion_sort_copy(ForwardIterator first1, ForwardIterator last1, BirdirectionalIterator first2, Compare comp)
0074 {
0075    insertion_sort_op(first1, last1, first2, comp, move_op());
0076 }
0077
0078 // @endcond
0079
0080 template <class Compare, class BirdirectionalIterator>
0081 void insertion_sort(BirdirectionalIterator first, BirdirectionalIterator last, Compare comp)
0082 {
0083    typedef typename boost::movelib::iterator_traits<BirdirectionalIterator>::value_type value_type;
0084    if (first != last){
0085       BirdirectionalIterator i = first;
0086       for (++i; i != last; ++i){
0087          BirdirectionalIterator j = i;
0088          if (comp(*i,  *--j)) {
0089             value_type tmp(::boost::move(*i));
0090             *i = ::boost::move(*j);
0091             for (BirdirectionalIterator k = j; k != first && comp(tmp,  *--k); --j) {
0092                *j = ::boost::move(*k);
0093             }
0094             *j = ::boost::move(tmp);
0095          }
0096       }
0097    }
0098 }
0099
0100 template <class Compare, class BirdirectionalIterator, class BirdirectionalRawIterator>
0101 void insertion_sort_uninitialized_copy
0102    (BirdirectionalIterator first1, BirdirectionalIterator const last1
0103    , BirdirectionalRawIterator const first2
0104    , Compare comp)
0105 {
0106    typedef typename iterator_traits<BirdirectionalIterator>::value_type value_type;
0107    if (first1 != last1){
0108       BirdirectionalRawIterator last2 = first2;
0109       ::new((iterator_to_raw_pointer)(last2), boost_move_new_t()) value_type(::boost::move(*first1));
0110       destruct_n<value_type, BirdirectionalRawIterator> d(first2);
0111       d.incr();
0112       for (++last2; ++first1 != last1; ++last2){
0113          BirdirectionalRawIterator j2 = last2;
0114          BirdirectionalRawIterator k2 = j2;
0115          if (comp(*first1, *--k2)){
0116             ::new((iterator_to_raw_pointer)(j2), boost_move_new_t()) value_type(::boost::move(*k2));
0117             d.incr();
0118             for (--j2; k2 != first2 && comp(*first1, *--k2); --j2)
0119                *j2 = ::boost::move(*k2);
0120             *j2 = ::boost::move(*first1);
0121          }
0122          else{
0123             ::new((iterator_to_raw_pointer)(j2), boost_move_new_t()) value_type(::boost::move(*first1));
0124             d.incr();
0125          }
0126       }
0127       d.release();
0128    }
0129 }
0130
0131 }} //namespace boost {  namespace movelib{
0132
0133 #if defined(BOOST_CLANG) || (defined(BOOST_GCC) && (BOOST_GCC >= 40600))
0134 #pragma GCC diagnostic pop
0135 #endif
0136
0137 #endif //#ifndef BOOST_MOVE_DETAIL_INSERT_SORT_HPP