]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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> | |
b32b8144 | 34 | #include <boost/move/detail/iterator_to_raw_pointer.hpp> |
7c673cae FG |
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 | ||
b32b8144 | 95 | template <class Compare, class BirdirectionalIterator, class BirdirectionalRawIterator> |
7c673cae FG |
96 | void insertion_sort_uninitialized_copy |
97 | (BirdirectionalIterator first1, BirdirectionalIterator const last1 | |
b32b8144 | 98 | , BirdirectionalRawIterator const first2 |
7c673cae FG |
99 | , Compare comp) |
100 | { | |
101 | typedef typename iterator_traits<BirdirectionalIterator>::value_type value_type; | |
102 | if (first1 != last1){ | |
b32b8144 | 103 | BirdirectionalRawIterator last2 = first2; |
11fdf7f2 | 104 | ::new((iterator_to_raw_pointer)(last2), boost_move_new_t()) value_type(::boost::move(*first1)); |
b32b8144 | 105 | destruct_n<value_type, BirdirectionalRawIterator> d(first2); |
7c673cae FG |
106 | d.incr(); |
107 | for (++last2; ++first1 != last1; ++last2){ | |
b32b8144 FG |
108 | BirdirectionalRawIterator j2 = last2; |
109 | BirdirectionalRawIterator k2 = j2; | |
7c673cae | 110 | if (comp(*first1, *--k2)){ |
11fdf7f2 | 111 | ::new((iterator_to_raw_pointer)(j2), boost_move_new_t()) value_type(::boost::move(*k2)); |
7c673cae FG |
112 | d.incr(); |
113 | for (--j2; k2 != first2 && comp(*first1, *--k2); --j2) | |
11fdf7f2 TL |
114 | *j2 = ::boost::move(*k2); |
115 | *j2 = ::boost::move(*first1); | |
7c673cae FG |
116 | } |
117 | else{ | |
11fdf7f2 | 118 | ::new((iterator_to_raw_pointer)(j2), boost_move_new_t()) value_type(::boost::move(*first1)); |
7c673cae FG |
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 |