EIC code displayed by LXR |
|
|
|
|||
File indexing completed on 2025-01-18 09:51:46
0001 //---------------------------------------------------------------------------- 0002 /// @file insert.hpp 0003 /// @brief 0004 /// 0005 /// @author Copyright (c) 2016 Francisco José Tapia (fjtapia@gmail.com )\n 0006 /// Distributed under the Boost Software License, Version 1.0.\n 0007 /// ( See accompanying file LICENSE_1_0.txt or copy at 0008 /// http://www.boost.org/LICENSE_1_0.txt ) 0009 /// @version 0.1 0010 /// 0011 /// @remarks 0012 //----------------------------------------------------------------------------- 0013 #ifndef __BOOST_SORT_COMMON_UTIL_INSERT_HPP 0014 #define __BOOST_SORT_COMMON_UTIL_INSERT_HPP 0015 0016 0017 #include <ciso646> 0018 #include <cstdlib> 0019 #include <functional> 0020 #include <iterator> 0021 #include <memory> 0022 #include <type_traits> 0023 #include <vector> 0024 #include <cstddef> 0025 #include <boost/sort/common/util/traits.hpp> 0026 #include <boost/sort/common/util/algorithm.hpp> 0027 0028 namespace boost 0029 { 0030 namespace sort 0031 { 0032 namespace common 0033 { 0034 namespace util 0035 { 0036 namespace here = boost::sort::common::util; 0037 // 0038 //############################################################################ 0039 // 0040 // D E F I N I T I O N S O F F U N C T I O N S 0041 // 0042 // template < class Iter1_t, class Iter2_t, typename Compare> 0043 // void insert_sorted (Iter1_t first, Iter1_t mid, Iter1_t last, 0044 // Compare comp, Iter2_t it_aux) 0045 // 0046 //############################################################################ 0047 // 0048 //----------------------------------------------------------------------------- 0049 // function : insert_sorted 0050 /// @brief : Insertion sort of elements sorted 0051 /// @param first: iterator to the first element of the range 0052 /// @param mid : last pointer of the sorted data, and first pointer to the 0053 /// elements to insert 0054 /// @param last : iterator to the next element of the last in the range 0055 /// @param comp : 0056 /// @comments : the two ranges are sorted and in it_aux there is spave for 0057 /// to store temporally the elements to insert 0058 //----------------------------------------------------------------------------- 0059 template<class Iter1_t, class Iter2_t, typename Compare> 0060 static void insert_sorted(Iter1_t first, Iter1_t mid, Iter1_t last, 0061 Compare comp, Iter2_t it_aux) 0062 { 0063 //------------------------------------------------------------------------ 0064 // metaprogram 0065 //------------------------------------------------------------------------ 0066 typedef value_iter<Iter1_t> value_t; 0067 typedef value_iter<Iter2_t> value2_t; 0068 static_assert (std::is_same< value_t, value2_t>::value, 0069 "Incompatible iterators\n"); 0070 0071 //-------------------------------------------------------------------- 0072 // program 0073 //-------------------------------------------------------------------- 0074 if (mid == last) return; 0075 if (first == mid) return; 0076 0077 //------------------------------------------------------------------------ 0078 // creation of the vector of elements to insert and their position in the 0079 // sorted part 0080 // the data are inserted in it_aux 0081 //----------------------------------------------------------------------- 0082 move_forward(it_aux, mid, last); 0083 0084 // search of the iterators where insert the new elements 0085 size_t ndata = last - mid; 0086 Iter1_t mv_first = mid, mv_last = mid; 0087 0088 for (size_t i = ndata; i > 0; --i) 0089 { 0090 mv_last = mv_first; 0091 mv_first = std::upper_bound(first, mv_last, it_aux[i - 1], comp); 0092 Iter1_t it1 = here::move_backward(mv_last + i, mv_first, mv_last); 0093 *(it1 - 1) = std::move(it_aux[i - 1]); 0094 }; 0095 }; 0096 0097 template<class Iter1_t, class Iter2_t, typename Compare> 0098 static void insert_sorted_backward(Iter1_t first, Iter1_t mid, Iter1_t last, 0099 Compare comp, Iter2_t it_aux) 0100 { 0101 //------------------------------------------------------------------------ 0102 // metaprogram 0103 //------------------------------------------------------------------------ 0104 typedef value_iter<Iter1_t> value_t; 0105 typedef value_iter<Iter2_t> value2_t; 0106 static_assert (std::is_same< value_t, value2_t>::value, 0107 "Incompatible iterators\n"); 0108 0109 //-------------------------------------------------------------------- 0110 // program 0111 //-------------------------------------------------------------------- 0112 if (mid == last) return; 0113 if (first == mid) return; 0114 //------------------------------------------------------------------------ 0115 // creation of the vector of elements to insert and their position in the 0116 // sorted part 0117 // the data are inserted in it_aux 0118 //----------------------------------------------------------------------- 0119 move_forward(it_aux, first, mid); 0120 0121 // search of the iterators where insert the new elements 0122 size_t ndata = mid - first; 0123 Iter1_t mv_first = mid, mv_last = mid; 0124 0125 for (size_t i = 0; i < ndata; ++i) 0126 { 0127 mv_first = mv_last; 0128 mv_last = std::lower_bound(mv_first, last, it_aux[i], comp); 0129 Iter1_t it1 = move_forward(mv_first - (ndata - i), mv_first, mv_last); 0130 *(it1) = std::move(it_aux[i]); 0131 }; 0132 0133 }; 0134 // 0135 //**************************************************************************** 0136 };// End namespace util 0137 };// End namepspace common 0138 };// End namespace sort 0139 };// End namepspace boost 0140 //**************************************************************************** 0141 // 0142 #endif
| [ Source navigation ] | [ Diff markup ] | [ Identifier search ] | [ general search ] |
|
This page was automatically generated by the 2.3.7 LXR engine. The LXR team |
|