1 //----------------------------------------------------------------------------
2 /// @file insert.hpp
3 /// @brief
4 ///
5 /// @author Copyright (c) 2016 Francisco José Tapia (fjtapia@gmail.com )\n
6 /// Distributed under the Boost Software License, Version 1.0.\n
7 /// ( See accompanying file LICENSE_1_0.txt or copy at
8 /// http://www.boost.org/LICENSE_1_0.txt )
9 /// @version 0.1
10 ///
11 /// @remarks
12 //-----------------------------------------------------------------------------
13 #ifndef __BOOST_SORT_COMMON_UTIL_INSERT_HPP
14 #define __BOOST_SORT_COMMON_UTIL_INSERT_HPP
15
16 //#include <boost/sort/spinsort/util/indirect.hpp>
17 #include <boost/sort/common/util/insert.hpp>
18 #include <boost/sort/common/util/traits.hpp>
19 #include <boost/sort/common/util/algorithm.hpp>
20 #include <cstdlib>
21 #include <functional>
22 #include <iterator>
23 #include <memory>
24 #include <type_traits>
25 #include <vector>
26 #include <cstddef>
27
28 namespace boost
29 {
30 namespace sort
31 {
32 namespace common
33 {
34 namespace util
35 {
36 namespace here = boost::sort::common::util;
37 //
38 //############################################################################
39 //
40 // D E F I N I T I O N S O F F U N C T I O N S
41 //
42 // template < class Iter1_t, class Iter2_t, typename Compare>
43 // void insert_sorted (Iter1_t first, Iter1_t mid, Iter1_t last,
44 // Compare comp, Iter2_t it_aux)
45 //
46 //############################################################################
47 //
48 //-----------------------------------------------------------------------------
49 // function : insert_sorted
50 /// @brief : Insertion sort of elements sorted
51 /// @param first: iterator to the first element of the range
52 /// @param mid : last pointer of the sorted data, and first pointer to the
53 /// elements to insert
54 /// @param last : iterator to the next element of the last in the range
55 /// @param comp :
56 /// @comments : the two ranges are sorted and in it_aux there is spave for
57 /// to store temporally the elements to insert
58 //-----------------------------------------------------------------------------
59 template<class Iter1_t, class Iter2_t, typename Compare>
insert_sorted(Iter1_t first,Iter1_t mid,Iter1_t last,Compare comp,Iter2_t it_aux)60 static void insert_sorted(Iter1_t first, Iter1_t mid, Iter1_t last,
61 Compare comp, Iter2_t it_aux)
62 {
63 //------------------------------------------------------------------------
64 // metaprogram
65 //------------------------------------------------------------------------
66 typedef value_iter<Iter1_t> value_t;
67 typedef value_iter<Iter2_t> value2_t;
68 static_assert (std::is_same< value_t, value2_t>::value,
69 "Incompatible iterators\n");
70
71 //--------------------------------------------------------------------
72 // program
73 //--------------------------------------------------------------------
74 if (mid == last) return;
75 if (first == mid) return;
76
77 //------------------------------------------------------------------------
78 // creation of the vector of elements to insert and their position in the
79 // sorted part
80 // the data are inserted in it_aux
81 //-----------------------------------------------------------------------
82 move_forward(it_aux, mid, last);
83
84 // search of the iterators where insert the new elements
85 size_t ndata = last - mid;
86 Iter1_t mv_first = mid, mv_last = mid;
87
88 for (size_t i = ndata; i > 0; --i)
89 {
90 mv_last = mv_first;
91 mv_first = std::upper_bound(first, mv_last, it_aux[i - 1], comp);
92 Iter1_t it1 = here::move_backward(mv_last + i, mv_first, mv_last);
93 *(it1 - 1) = std::move(it_aux[i - 1]);
94 };
95 };
96
97 template<class Iter1_t, class Iter2_t, typename Compare>
insert_sorted_backward(Iter1_t first,Iter1_t mid,Iter1_t last,Compare comp,Iter2_t it_aux)98 static void insert_sorted_backward(Iter1_t first, Iter1_t mid, Iter1_t last,
99 Compare comp, Iter2_t it_aux)
100 {
101 //------------------------------------------------------------------------
102 // metaprogram
103 //------------------------------------------------------------------------
104 typedef value_iter<Iter1_t> value_t;
105 typedef value_iter<Iter2_t> value2_t;
106 static_assert (std::is_same< value_t, value2_t>::value,
107 "Incompatible iterators\n");
108
109 //--------------------------------------------------------------------
110 // program
111 //--------------------------------------------------------------------
112 if (mid == last) return;
113 if (first == mid) return;
114 //------------------------------------------------------------------------
115 // creation of the vector of elements to insert and their position in the
116 // sorted part
117 // the data are inserted in it_aux
118 //-----------------------------------------------------------------------
119 move_forward(it_aux, first, mid);
120
121 // search of the iterators where insert the new elements
122 size_t ndata = mid - first;
123 Iter1_t mv_first = mid, mv_last = mid;
124
125 for (size_t i = 0; i < ndata; ++i)
126 {
127 mv_first = mv_last;
128 mv_last = std::lower_bound(mv_first, last, it_aux[i], comp);
129 Iter1_t it1 = move_forward(mv_first - (ndata - i), mv_first, mv_last);
130 *(it1) = std::move(it_aux[i]);
131 };
132
133 };
134 //
135 //****************************************************************************
136 };// End namespace util
137 };// End namepspace common
138 };// End namespace sort
139 };// End namepspace boost
140 //****************************************************************************
141 //
142 #endif
143