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 ">#
0022 #if defined(BOOST_HAS_PRAGMA_ONCE)
0023 #  pragma once
0024 #endif
0025
0026 #include <boost/move/utility_core.hpp>
0027 #include <boost/move/algo/move.hpp>
0028 #include <boost/move/detail/iterator_traits.hpp>
0029 #include <boost/move/adl_move_swap.hpp>
0030 #include <boost/move/utility_core.hpp>
0031 #include <boost/move/detail/placement_new.hpp>
0032 #include <boost/move/detail/destruct_n.hpp>
0033 #include <boost/move/algo/detail/basic_op.hpp>
0034 #include <boost/move/detail/placement_new.hpp>
0035 #include <boost/move/detail/iterator_to_raw_pointer.hpp>
0036
0037 #if defined(BOOST_CLANG) || (defined(BOOST_GCC) && (BOOST_GCC >= 40600))
0038 #pragma GCC diagnostic push
0039 #pragma GCC diagnostic ignored "-Wsign-conversion"
0040 #endif
0041
0042 namespace boost {  namespace movelib{
0043
0044 // @cond
0045
0046 template <class Compare, class ForwardIterator, class BirdirectionalIterator, class Op>
0047 void insertion_sort_op(ForwardIterator first1, ForwardIterator last1, BirdirectionalIterator first2, Compare comp, Op op)
0048 {
0049    if (first1 != last1){
0050       BirdirectionalIterator last2 = first2;
0051       op(first1, last2);
0052       for (++last2; ++first1 != last1; ++last2){
0053          BirdirectionalIterator j2 = last2;
0054          BirdirectionalIterator i2 = j2;
0055          if (comp(*first1, *--i2)){
0056             op(i2, j2);
0057             for (--j2; i2 != first2 && comp(*first1, *--i2); --j2) {
0058                op(i2, j2);
0059             }
0060          }
0061          op(first1, j2);
0062       }
0063    }
0064 }
0065
0066 template <class Compare, class ForwardIterator, class BirdirectionalIterator>
0067 void insertion_sort_swap(ForwardIterator first1, ForwardIterator last1, BirdirectionalIterator first2, Compare comp)
0068 {
0069    insertion_sort_op(first1, last1, first2, comp, swap_op());
0070 }
0071
0072
0073 template <class Compare, class ForwardIterator, class BirdirectionalIterator>
0074 void insertion_sort_copy(ForwardIterator first1, ForwardIterator last1, BirdirectionalIterator first2, Compare comp)
0075 {
0076    insertion_sort_op(first1, last1, first2, comp, move_op());
0077 }
0078
0079 // @endcond
0080
0081 template <class Compare, class BirdirectionalIterator>
0082 void insertion_sort(BirdirectionalIterator first, BirdirectionalIterator last, Compare comp)
0083 {
0084    typedef typename boost::movelib::iterator_traits<BirdirectionalIterator>::value_type value_type;
0085    if (first != last){
0086       BirdirectionalIterator i = first;
0087       for (++i; i != last; ++i){
0088          BirdirectionalIterator j = i;
0089          if (comp(*i,  *--j)) {
0090             value_type tmp(::boost::move(*i));
0091             *i = ::boost::move(*j);
0092             for (BirdirectionalIterator k = j; k != first && comp(tmp,  *--k); --j) {
0093                *j = ::boost::move(*k);
0094             }
0095             *j = ::boost::move(tmp);
0096          }
0097       }
0098    }
0099 }
0100
0101 template <class Compare, class BirdirectionalIterator, class BirdirectionalRawIterator>
0102 void insertion_sort_uninitialized_copy
0103    (BirdirectionalIterator first1, BirdirectionalIterator const last1
0104    , BirdirectionalRawIterator const first2
0105    , Compare comp)
0106 {
0107    typedef typename iterator_traits<BirdirectionalIterator>::value_type value_type;
0108    if (first1 != last1){
0109       BirdirectionalRawIterator last2 = first2;
0110       ::new((iterator_to_raw_pointer)(last2), boost_move_new_t()) value_type(::boost::move(*first1));
0111       destruct_n<value_type, BirdirectionalRawIterator> d(first2);
0112       d.incr();
0113       for (++last2; ++first1 != last1; ++last2){
0114          BirdirectionalRawIterator j2 = last2;
0115          BirdirectionalRawIterator k2 = j2;
0116          if (comp(*first1, *--k2)){
0117             ::new((iterator_to_raw_pointer)(j2), boost_move_new_t()) value_type(::boost::move(*k2));
0118             d.incr();
0119             for (--j2; k2 != first2 && comp(*first1, *--k2); --j2)
0120                *j2 = ::boost::move(*k2);
0121             *j2 = ::boost::move(*first1);
0122          }
0123          else{
0124             ::new((iterator_to_raw_pointer)(j2), boost_move_new_t()) value_type(::boost::move(*first1));
0125             d.incr();
0126          }
0127       }
0128       d.release();
0129    }
0130 }
0131
0132 }} //namespace boost {  namespace movelib{
0133
0134 #if defined(BOOST_CLANG) || (defined(BOOST_GCC) && (BOOST_GCC >= 40600))
0135 #pragma GCC diagnostic pop
0136 #endif
0137
0138 #endif //#ifndef BOOST_MOVE_DETAIL_INSERT_SORT_HPP