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