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>
insertion_sort_op(ForwardIterator first1,ForwardIterator last1,BirdirectionalIterator first2,Compare comp,Op 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>
insertion_sort_swap(ForwardIterator first1,ForwardIterator last1,BirdirectionalIterator first2,Compare comp)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>
insertion_sort_copy(ForwardIterator first1,ForwardIterator last1,BirdirectionalIterator first2,Compare comp)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>
insertion_sort(BirdirectionalIterator first,BirdirectionalIterator last,Compare comp)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>
insertion_sort_uninitialized_copy(BirdirectionalIterator first1,BirdirectionalIterator const last1,BirdirectionalRawIterator const first2,Compare comp)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
129