EIC code displayed by LXR |
|
|
|
|||
File indexing completed on 2025-01-18 09:51:47
0001 //---------------------------------------------------------------------------- 0002 /// @file sort_basic.hpp 0003 /// @brief Spin Sort algorithm 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_SORT_BASIC_HPP 0014 #define __BOOST_SORT_COMMON_SORT_BASIC_HPP 0015 0016 #include <ciso646> 0017 #include <cstdlib> 0018 #include <functional> 0019 #include <iterator> 0020 #include <memory> 0021 #include <type_traits> 0022 #include <vector> 0023 #include <cstddef> 0024 #include <boost/sort/insert_sort/insert_sort.hpp> 0025 #include <boost/sort/common/util/traits.hpp> 0026 #include <boost/sort/common/range.hpp> 0027 0028 namespace boost 0029 { 0030 namespace sort 0031 { 0032 namespace common 0033 { 0034 0035 //---------------------------------------------------------------------------- 0036 // USING SENTENCES 0037 //---------------------------------------------------------------------------- 0038 using boost::sort::insert_sort; 0039 0040 //----------------------------------------------------------------------------- 0041 // function : is_stable_sorted_forward 0042 /// @brief examine the elements in the range first, last if they are stable 0043 /// sorted, and return an iterator to the first element not sorted 0044 /// @param first : iterator to the first element in the range 0045 /// @param last : ierator after the last element of the range 0046 /// @param comp : object for to compare two elements 0047 /// @return iterator to the first element not stable sorted. The number of 0048 /// elements sorted is the iterator returned minus first 0049 //----------------------------------------------------------------------------- 0050 template<class Iter_t, class Compare = std::less<value_iter<Iter_t> > > 0051 inline Iter_t is_stable_sorted_forward (Iter_t first, Iter_t last, 0052 Compare comp = Compare()) 0053 { 0054 #ifdef __BS_DEBUG 0055 assert ( (last- first) >= 0); 0056 #endif 0057 if ((last - first) < 2) return first; 0058 Iter_t it2 = first + 1; 0059 for (Iter_t it1 = first; it2 != last and not comp(*it2, *it1); it1 = it2++); 0060 return it2; 0061 } 0062 //----------------------------------------------------------------------------- 0063 // function : is_reverse_stable_sorted_forward 0064 /// @brief examine the elements in the range first, last if they are reverse 0065 /// stable sorted, and return an iterator to the first element not 0066 /// reverse stable sorted 0067 /// @param first : iterator to the first element in the range 0068 /// @param last : ierator after the last element of the range 0069 /// @param comp : object for to compare two elements 0070 /// @return iterator to the first element not reverse stable sorted. The number 0071 /// of elements sorted is the iterator returned minus first 0072 //----------------------------------------------------------------------------- 0073 template<class Iter_t, class Compare = std::less<value_iter<Iter_t> > > 0074 inline Iter_t is_reverse_stable_sorted_forward(Iter_t first, Iter_t last, 0075 Compare comp = Compare()) 0076 { 0077 #ifdef __BS_DEBUG 0078 assert ( (last- first) >= 0); 0079 #endif 0080 if ((last - first) < 2) return first; 0081 Iter_t it2 = first + 1; 0082 for (Iter_t it1 = first; it2 != last and comp(*it2, *it1); it1 = it2++); 0083 return it2; 0084 }; 0085 //----------------------------------------------------------------------------- 0086 // function : number_stable_sorted_forward 0087 /// @brief examine the elements in the range first, last if they are stable 0088 /// sorted, and return the number of elements sorted 0089 /// @param first : iterator to the first element in the range 0090 /// @param last : ierator after the last element of the range 0091 /// @param comp : object for to compare two elements 0092 /// @param min_process : minimal number of elements to be consideer 0093 /// @return number of element sorted. I f the number is lower than min_process 0094 /// return 0 0095 //----------------------------------------------------------------------------- 0096 template<class Iter_t, class Compare = std::less<value_iter<Iter_t> > > 0097 size_t number_stable_sorted_forward (Iter_t first, Iter_t last, 0098 size_t min_process, 0099 Compare comp = Compare()) 0100 { 0101 #ifdef __BS_DEBUG 0102 assert ( (last- first) >= 0); 0103 #endif 0104 if ((last - first) < 2) return 0; 0105 0106 // sorted elements 0107 Iter_t it2 = first + 1; 0108 for (Iter_t it1 = first; it2 != last and not comp(*it2, *it1); it1 = it2++); 0109 size_t nsorted = size_t ( it2 - first); 0110 if ( nsorted != 1) 0111 return (nsorted >= min_process) ? nsorted: 0; 0112 0113 // reverse sorted elements 0114 it2 = first + 1; 0115 for (Iter_t it1 = first; it2 != last and comp(*it2, *it1); it1 = it2++); 0116 nsorted = size_t ( it2 - first); 0117 0118 if ( nsorted < min_process) return 0 ; 0119 util::reverse ( first , it2); 0120 return nsorted; 0121 }; 0122 0123 //----------------------------------------------------------------------------- 0124 // function : is_stable_sorted_backward 0125 /// @brief examine the elements in the range first, last beginning at end, and 0126 /// if they are stablesorted, and return an iterator to the last element 0127 /// sorted 0128 /// @param first : iterator to the first element in the range 0129 /// @param last : ierator after the last element of the range 0130 /// @param comp : object for to compare two elements 0131 /// @return iterator to the last element stable sorted. The number of 0132 /// elements sorted is the last minus the iterator returned 0133 //----------------------------------------------------------------------------- 0134 template<class Iter_t, class Compare = std::less<value_iter<Iter_t> > > 0135 inline Iter_t is_stable_sorted_backward(Iter_t first, Iter_t last, 0136 Compare comp = Compare()) 0137 { 0138 #ifdef __BS_DEBUG 0139 assert ( (last- first) >= 0); 0140 #endif 0141 if ((last - first) < 2) return first; 0142 Iter_t itaux = last - 1; 0143 while (itaux != first and not comp(*itaux, *(itaux - 1))) {--itaux; }; 0144 return itaux; 0145 } 0146 //----------------------------------------------------------------------------- 0147 // function : is_reverse_stable_sorted_backward 0148 /// @brief examine the elements in the range first, last beginning at end, and 0149 /// if they are stablesorted, and return an iterator to the last element 0150 /// sorted 0151 /// @param first : iterator to the first element in the range 0152 /// @param last : ierator after the last element of the range 0153 /// @param comp : object for to compare two elements 0154 /// @return iterator to the last element stable sorted. The number of 0155 /// elements sorted is the last minus the iterator returned 0156 //----------------------------------------------------------------------------- 0157 template<class Iter_t, class Compare = std::less<value_iter<Iter_t> > > 0158 inline Iter_t is_reverse_stable_sorted_backward (Iter_t first, Iter_t last, 0159 Compare comp = Compare()) 0160 { 0161 #ifdef __BS_DEBUG 0162 assert ( (last- first) >= 0); 0163 #endif 0164 if ((last - first) < 2) return first; 0165 Iter_t itaux = last - 1; 0166 for (; itaux != first and comp(*itaux, *(itaux - 1)); --itaux); 0167 return itaux; 0168 } 0169 0170 //----------------------------------------------------------------------------- 0171 // function : number_stable_sorted_backward 0172 /// @brief examine the elements in the range first, last if they are stable 0173 /// sorted, and return the number of elements sorted 0174 /// @param first : iterator to the first element in the range 0175 /// @param last : ierator after the last element of the range 0176 /// @param comp : object for to compare two elements 0177 /// @param min_process : minimal number of elements to be consideer 0178 /// @return number of element sorted. I f the number is lower than min_process 0179 /// return 0 0180 //----------------------------------------------------------------------------- 0181 template<class Iter_t, class Compare = std::less<value_iter<Iter_t> > > 0182 size_t number_stable_sorted_backward (Iter_t first, Iter_t last, 0183 size_t min_process, 0184 Compare comp = Compare()) 0185 { 0186 #ifdef __BS_DEBUG 0187 assert ( (last- first) >= 0); 0188 #endif 0189 if ((last - first) < 2) return 0; 0190 Iter_t itaux = last - 1; 0191 while (itaux != first and not comp(*itaux, *(itaux - 1))) {--itaux; }; 0192 size_t nsorted = size_t ( last - itaux); 0193 if ( nsorted != 1) 0194 return ( nsorted >= min_process)?nsorted: 0 ; 0195 0196 itaux = last - 1; 0197 for (; itaux != first and comp(*itaux, *(itaux - 1)); --itaux); 0198 nsorted = size_t ( last - itaux); 0199 if ( nsorted < min_process) return 0 ; 0200 util::reverse ( itaux, last ); 0201 return nsorted; 0202 } 0203 //----------------------------------------------------------------------------- 0204 // function : internal_sort 0205 /// @brief this function divide r_input in two parts, sort it,and merge moving 0206 /// the elements to range_buf 0207 /// @param range_input : range with the elements to sort 0208 /// @param range_buffer : range with the elements sorted 0209 /// @param comp : object for to compare two elements 0210 /// @param level : when is 1, sort with the insertionsort algorithm 0211 /// if not make a recursive call splitting the ranges 0212 // 0213 //----------------------------------------------------------------------------- 0214 template <class Iter1_t, class Iter2_t, class Compare> 0215 inline void internal_sort (const range<Iter1_t> &rng1, 0216 const range<Iter2_t> &rng2, 0217 Compare comp, uint32_t level, bool even = true) 0218 { 0219 //----------------------------------------------------------------------- 0220 // metaprogram 0221 //----------------------------------------------------------------------- 0222 typedef value_iter<Iter1_t> value_t; 0223 typedef value_iter<Iter2_t> value2_t; 0224 static_assert (std::is_same< value_t, value2_t>::value, 0225 "Incompatible iterators\n"); 0226 0227 //----------------------------------------------------------------------- 0228 // program 0229 //----------------------------------------------------------------------- 0230 #ifdef __BS_DEBUG 0231 assert (rng1.size ( ) == rng2.size ( ) ); 0232 #endif 0233 size_t nelem = (rng1.size() + 1) >> 1; 0234 0235 range<Iter1_t> rng1_left(rng1.first, rng1.first + nelem), 0236 rng1_right(rng1.first + nelem, rng1.last); 0237 0238 range<Iter2_t> rng2_left(rng2.first, rng2.first + nelem), 0239 rng2_right(rng2.first + nelem, rng2.last); 0240 0241 if (nelem <= 32 and (level & 1) == even) 0242 { 0243 insert_sort(rng1_left.first, rng1_left.last, comp); 0244 insert_sort(rng1_right.first, rng1_right.last, comp); 0245 } 0246 else 0247 { 0248 internal_sort(rng2_left, rng1_left, comp, level + 1, even); 0249 internal_sort(rng2_right, rng1_right, comp, level + 1, even); 0250 }; 0251 merge(rng2, rng1_left, rng1_right, comp); 0252 }; 0253 //----------------------------------------------------------------------------- 0254 // function : range_sort_data 0255 /// @brief this sort elements using the range_sort function and receiving a 0256 /// buffer of initialized memory 0257 /// @param rng_data : range with the elements to sort 0258 /// @param rng_aux : range of at least the same memory than rng_data used as 0259 /// auxiliary memory in the sorting 0260 /// @param comp : object for to compare two elements 0261 //----------------------------------------------------------------------------- 0262 template<class Iter1_t, class Iter2_t, class Compare> 0263 static void range_sort_data (const range<Iter1_t> & rng_data, 0264 const range<Iter2_t> & rng_aux, Compare comp) 0265 { 0266 //----------------------------------------------------------------------- 0267 // metaprogram 0268 //----------------------------------------------------------------------- 0269 typedef value_iter<Iter1_t> value_t; 0270 typedef value_iter<Iter2_t> value2_t; 0271 static_assert (std::is_same< value_t, value2_t>::value, 0272 "Incompatible iterators\n"); 0273 0274 //------------------------------------------------------------------------ 0275 // program 0276 //------------------------------------------------------------------------ 0277 #ifdef __BS_DEBUG 0278 assert ( rng_data.size() == rng_aux.size()); 0279 #endif 0280 // minimal number of element before to jump to insertionsort 0281 const uint32_t sort_min = 32; 0282 if (rng_data.size() <= sort_min) 0283 { 0284 insert_sort(rng_data.first, rng_data.last, comp); 0285 return; 0286 }; 0287 0288 internal_sort(rng_aux, rng_data, comp, 0, true); 0289 }; 0290 //----------------------------------------------------------------------------- 0291 // function : range_sort_buffer 0292 /// @brief this sort elements using the range_sort function and receiving a 0293 /// buffer of initialized memory 0294 /// @param rng_data : range with the elements to sort 0295 /// @param rng_aux : range of at least the same memory than rng_data used as 0296 /// auxiliary memory in the sorting 0297 /// @param comp : object for to compare two elements 0298 //----------------------------------------------------------------------------- 0299 template<class Iter1_t, class Iter2_t, class Compare> 0300 static void range_sort_buffer(const range<Iter1_t> & rng_data, 0301 const range<Iter2_t> & rng_aux, Compare comp) 0302 { 0303 //----------------------------------------------------------------------- 0304 // metaprogram 0305 //----------------------------------------------------------------------- 0306 typedef value_iter<Iter1_t> value_t; 0307 typedef value_iter<Iter2_t> value2_t; 0308 static_assert (std::is_same< value_t, value2_t>::value, 0309 "Incompatible iterators\n"); 0310 0311 //------------------------------------------------------------------------ 0312 // program 0313 //------------------------------------------------------------------------ 0314 #ifdef __BS_DEBUG 0315 assert ( rng_data.size() == rng_aux.size()); 0316 #endif 0317 // minimal number of element before to jump to insertionsort 0318 const uint32_t sort_min = 32; 0319 if (rng_data.size() <= sort_min) 0320 { 0321 insert_sort(rng_data.first, rng_data.last, comp); 0322 move_forward(rng_aux, rng_data); 0323 return; 0324 }; 0325 0326 internal_sort(rng_data, rng_aux, comp, 0, false); 0327 }; 0328 //**************************************************************************** 0329 };// End namespace common 0330 };// End namespace sort 0331 };// End namepspace boost 0332 //**************************************************************************** 0333 // 0334 #endif
| [ Source navigation ] | [ Diff markup ] | [ Identifier search ] | [ general search ] |
|
This page was automatically generated by the 2.3.7 LXR engine. The LXR team |
|