EIC code displayed by LXR |
|
|
|
|||
File indexing completed on 2025-01-18 09:51:46
0001 //---------------------------------------------------------------------------- 0002 /// @file search.hpp 0003 /// @brief 0004 /// @author Copyright (c) 2017 Francisco José Tapia (fjtapia@gmail.com )\n 0005 /// Distributed under the Boost Software License, Version 1.0.\n 0006 /// ( See copy at http://www.boost.org/LICENSE_1_0.txt ) 0007 /// @remarks 0008 //----------------------------------------------------------------------------- 0009 #ifndef __BOOST_SORT_COMMON_SEARCH_HPP 0010 #define __BOOST_SORT_COMMON_SEARCH_HPP 0011 0012 #include <ciso646> 0013 #include <cassert> 0014 #include <boost/sort/common/util/traits.hpp> 0015 0016 0017 namespace boost 0018 { 0019 namespace sort 0020 { 0021 namespace common 0022 { 0023 namespace util 0024 { 0025 0026 template<class T> 0027 struct filter_pass 0028 { 0029 typedef T key; 0030 const key & operator()(const T & val) const 0031 { 0032 return val; 0033 }; 0034 }; 0035 0036 // 0037 //########################################################################### 0038 // ## 0039 // ################################################################ ## 0040 // # # ## 0041 // # I N T E R N A L F U N C T I O N S # ## 0042 // # # ## 0043 // ################################################################ ## 0044 // ## 0045 // I M P O R T A N T ## 0046 // ## 0047 // These functions are not directly callable by the user, are for internal ## 0048 // use only. ## 0049 // These functions don't check the parameters ## 0050 // ## 0051 //########################################################################### 0052 // 0053 //----------------------------------------------------------------------------- 0054 // function : internal_find_first 0055 /// @brief find if a value exist in the range [first, last). 0056 /// Always return as valid iterator in the range [first, last-1] 0057 /// If exist return the iterator to the first occurrence. If don't exist 0058 /// return the first greater than val. 0059 /// If val is greater than the *(last-1), return (last-1) 0060 /// If val is lower than (*first), return first 0061 // 0062 /// @param [in] first : iterator to the first element of the range 0063 /// @param [in] last : iterator to the last element of the range 0064 /// @param [in] val : value to find 0065 /// @param [in] comp : object for to compare two value_t objects 0066 /// @return iterator to the element found, 0067 //----------------------------------------------------------------------------- 0068 template <class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >, 0069 class Compare = std::less<typename Filter::key> > 0070 inline Iter_t internal_find_first(Iter_t first, Iter_t last, 0071 const typename Filter::key &val, 0072 const Compare & comp = Compare(), 0073 Filter flt = Filter()) 0074 { 0075 Iter_t LI = first, LS = last - 1, it_out = first; 0076 while (LI != LS) 0077 { 0078 it_out = LI + ((LS - LI) >> 1); 0079 if (comp(flt(*it_out), val)) 0080 LI = it_out + 1; 0081 else LS = it_out; 0082 }; 0083 return LS; 0084 }; 0085 // 0086 //----------------------------------------------------------------------------- 0087 // function : internal_find_last 0088 /// @brief find if a value exist in the range [first, last). 0089 /// Always return as valid iterator in the range [first, last-1] 0090 /// If exist return the iterator to the last occurrence. 0091 /// If don't exist return the first lower than val. 0092 /// If val is greater than *(last-1) return (last-1). 0093 /// If is lower than the first, return first 0094 // 0095 /// @param [in] first : iterator to the first element of the range 0096 /// @param [in] last : iterator to the last element of the range 0097 /// @param [in] val : value to find 0098 /// @param [in] comp : object for to compare two value_t objects 0099 /// @return iterator to the element found, if not found return last 0100 0101 //----------------------------------------------------------------------------- 0102 template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >, 0103 class Compare = std::less<typename Filter::key> > 0104 inline Iter_t internal_find_last(Iter_t first, Iter_t last, 0105 const typename Filter::key &val, 0106 const Compare & comp = Compare(), Filter flt = 0107 Filter()) 0108 { 0109 Iter_t LI = first, LS = last - 1, it_out = first; 0110 while (LI != LS) 0111 { 0112 it_out = LI + ((LS - LI + 1) >> 1); 0113 if (comp(val, flt(*it_out))) LS = it_out - 1; 0114 else LI = it_out; 0115 }; 0116 return LS; 0117 }; 0118 0119 // 0120 //########################################################################### 0121 // ## 0122 // ################################################################ ## 0123 // # # ## 0124 // # P U B L I C F U N C T I O N S # ## 0125 // # # ## 0126 // ################################################################ ## 0127 // ## 0128 //########################################################################### 0129 // 0130 //----------------------------------------------------------------------------- 0131 // function : find_first 0132 /// @brief find if a value exist in the range [first, last). If exist return the 0133 /// iterator to the first occurrence. If don't exist return last 0134 // 0135 /// @param [in] first : iterator to the first element of the range 0136 /// @param [in] last : iterator to the last element of the range 0137 /// @param [in] val : value to find 0138 /// @param [in] comp : object for to compare two value_t objects 0139 /// @return iterator to the element found, and if not last 0140 //----------------------------------------------------------------------------- 0141 template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >, 0142 class Compare = std::less<typename Filter::key> > 0143 inline Iter_t find_first(Iter_t first, Iter_t last, 0144 const typename Filter::key &val, 0145 const Compare & comp = Compare(), 0146 Filter flt = Filter()) 0147 { 0148 assert((last - first) >= 0); 0149 if (first == last) return last; 0150 Iter_t LS = internal_find_first(first, last, val, comp, flt); 0151 return (comp(flt(*LS), val) or comp(val, flt(*LS))) ? last : LS; 0152 }; 0153 // 0154 //----------------------------------------------------------------------------- 0155 // function : find_last 0156 /// @brief find if a value exist in the range [first, last). If exist return the 0157 /// iterator to the last occurrence. If don't exist return last 0158 // 0159 /// @param [in] first : iterator to the first element of the range 0160 /// @param [in] last : iterator to the last element of the range 0161 /// @param [in] val : value to find 0162 /// @param [in] comp : object for to compare two value_t objects 0163 /// @return iterator to the element found, if not found return last 0164 0165 //----------------------------------------------------------------------------- 0166 template <class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >, 0167 class Compare = std::less<typename Filter::key> > 0168 inline Iter_t find_last(Iter_t first, Iter_t last, 0169 const typename Filter::key &val, 0170 const Compare & comp = Compare(), 0171 Filter flt = Filter()) 0172 { 0173 assert((last - first) >= 0); 0174 if (last == first) return last; 0175 Iter_t LS = internal_find_last(first, last, val, comp, flt); 0176 return (comp(flt(*LS), val) or comp(val, flt(*LS))) ? last : LS; 0177 }; 0178 0179 //---------------------------------------------------------------------------- 0180 // function : lower_bound 0181 /// @brief Returns an iterator pointing to the first element in the range 0182 /// [first, last) that is not less than (i.e. greater or equal to) val. 0183 /// @param [in] last : iterator to the last element of the range 0184 /// @param [in] val : value to find 0185 /// @param [in] comp : object for to compare two value_t objects 0186 /// @return iterator to the element found 0187 //----------------------------------------------------------------------------- 0188 template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >, 0189 class Compare = std::less<typename Filter::key> > 0190 inline Iter_t lower_bound(Iter_t first, Iter_t last, 0191 const typename Filter::key &val, 0192 const Compare & comp = Compare(), 0193 Filter flt = Filter()) 0194 { 0195 assert((last - first) >= 0); 0196 if (last == first) return last; 0197 Iter_t itaux = internal_find_first(first, last, val, comp, flt); 0198 return (itaux == (last - 1) and comp(flt(*itaux), val)) ? last : itaux; 0199 }; 0200 //---------------------------------------------------------------------------- 0201 // function :upper_bound 0202 /// @brief return the first element greather than val.If don't exist 0203 /// return last 0204 // 0205 /// @param [in] first : iterator to the first element of the range 0206 /// @param [in] last : iterator to the last element of the range 0207 /// @param [in] val : value to find 0208 /// @param [in] comp : object for to compare two value_t objects 0209 /// @return iterator to the element found 0210 /// @remarks 0211 //----------------------------------------------------------------------------- 0212 template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >, 0213 class Compare = std::less<typename Filter::key> > 0214 inline Iter_t upper_bound(Iter_t first, Iter_t last, 0215 const typename Filter::key &val, 0216 const Compare & comp = Compare(), 0217 Filter flt = Filter()) 0218 { 0219 assert((last - first) >= 0); 0220 if (last == first) return last; 0221 Iter_t itaux = internal_find_last(first, last, val, comp, flt); 0222 return (itaux == first and comp(val, flt(*itaux))) ? itaux : itaux + 1; 0223 } 0224 ; 0225 //---------------------------------------------------------------------------- 0226 // function :equal_range 0227 /// @brief return a pair of lower_bound and upper_bound with the value val.If 0228 /// don't exist return last in the two elements of the pair 0229 // 0230 /// @param [in] first : iterator to the first element of the range 0231 /// @param [in] last : iterator to the last element of the range 0232 /// @param [in] val : value to find 0233 /// @param [in] comp : object for to compare two value_t objects 0234 /// @return pair of iterators 0235 //----------------------------------------------------------------------------- 0236 template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >, 0237 class Compare = std::less<typename Filter::key> > 0238 inline std::pair<Iter_t, Iter_t> equal_range(Iter_t first, Iter_t last, 0239 const typename Filter::key &val, 0240 const Compare & comp = Compare(), 0241 Filter flt = Filter()) 0242 { 0243 return std::make_pair(lower_bound(first, last, val, comp, flt), 0244 upper_bound(first, last, val, comp, flt)); 0245 }; 0246 // 0247 //----------------------------------------------------------------------------- 0248 // function : insert_first 0249 /// @brief find if a value exist in the range [first, last). If exist return the 0250 /// iterator to the first occurrence. If don't exist return last 0251 // 0252 /// @param [in] first : iterator to the first element of the range 0253 /// @param [in] last : iterator to the last element of the range 0254 /// @param [in] val : value to find 0255 /// @param [in] comp : object for to compare two value_t objects 0256 /// @return iterator to the element found, and if not last 0257 //----------------------------------------------------------------------------- 0258 template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >, 0259 class Compare = std::less<typename Filter::key> > 0260 inline Iter_t insert_first(Iter_t first, Iter_t last, 0261 const typename Filter::key &val, 0262 const Compare & comp = Compare(), Filter flt = 0263 Filter()) 0264 { 0265 return lower_bound(first, last, val, comp, flt); 0266 }; 0267 // 0268 //----------------------------------------------------------------------------- 0269 // function : insert_last 0270 /// @brief find if a value exist in the range [first, last). If exist return the 0271 /// iterator to the last occurrence. If don't exist return last 0272 // 0273 /// @param [in] first : iterator to the first element of the range 0274 /// @param [in] last : iterator to the last element of the range 0275 /// @param [in] val : value to find 0276 /// @param [in] comp : object for to compare two value_t objects 0277 /// @return iterator to the element found, if not found return last 0278 0279 //----------------------------------------------------------------------------- 0280 template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >, 0281 class Compare = std::less<typename Filter::key> > 0282 inline Iter_t insert_last(Iter_t first, Iter_t last, 0283 const typename Filter::key &val, 0284 const Compare & comp = Compare(), Filter flt = 0285 Filter()) 0286 { 0287 return upper_bound(first, last, val, comp, flt); 0288 }; 0289 0290 /* 0291 0292 // 0293 //########################################################################### 0294 // ## 0295 // ################################################################ ## 0296 // # # ## 0297 // # I N T E R N A L F U N C T I O N S # ## 0298 // # # ## 0299 // ################################################################ ## 0300 // ## 0301 // I M P O R T A N T ## 0302 // ## 0303 // These functions are not directly callable by the user, are for internal ## 0304 // use only. ## 0305 // These functions don't check the parameters ## 0306 // ## 0307 //########################################################################### 0308 // 0309 //----------------------------------------------------------------------------- 0310 // function : internal_find_first 0311 /// @brief find if a value exist in the range [first, last). 0312 /// Always return as valid iterator in the range [first, last-1] 0313 /// If exist return the iterator to the first occurrence. If don't exist 0314 /// return the first greater than val. 0315 /// If val is greater than the *(last-1), return (last-1) 0316 /// If val is lower than (*first), return first 0317 // 0318 /// @param [in] first : iterator to the first element of the range 0319 /// @param [in] last : iterator to the last element of the range 0320 /// @param [in] val : value to find 0321 /// @param [in] comp : object for to compare two value_t objects 0322 /// @return iterator to the element found, 0323 //----------------------------------------------------------------------------- 0324 template < class Iter_t, class Compare = compare_iter<Iter_t> > 0325 inline Iter_t internal_find_first ( Iter_t first, Iter_t last, 0326 const value_iter<Iter_t> &val, 0327 const Compare & comp= Compare() ) 0328 { 0329 Iter_t LI = first , LS = last - 1, it_out = first; 0330 while ( LI != LS) 0331 { it_out = LI + ( (LS - LI) >> 1); 0332 if ( comp ( *it_out, val)) LI = it_out + 1 ; else LS = it_out ; 0333 }; 0334 return LS ; 0335 }; 0336 // 0337 //----------------------------------------------------------------------------- 0338 // function : internal_find_last 0339 /// @brief find if a value exist in the range [first, last). 0340 /// Always return as valid iterator in the range [first, last-1] 0341 /// If exist return the iterator to the last occurrence. 0342 /// If don't exist return the first lower than val. 0343 /// If val is greater than *(last-1) return (last-1). 0344 /// If is lower than the first, return first 0345 // 0346 /// @param [in] first : iterator to the first element of the range 0347 /// @param [in] last : iterator to the last element of the range 0348 /// @param [in] val : value to find 0349 /// @param [in] comp : object for to compare two value_t objects 0350 /// @return iterator to the element found, if not found return last 0351 0352 //----------------------------------------------------------------------------- 0353 template < class Iter_t, class Compare = compare_iter<Iter_t> > 0354 inline Iter_t internal_find_last ( Iter_t first, Iter_t last , 0355 const value_iter<Iter_t> &val, 0356 const Compare &comp= Compare() ) 0357 { 0358 Iter_t LI = first , LS = last - 1, it_out = first ; 0359 while ( LI != LS) 0360 { it_out = LI + ( (LS - LI + 1) >> 1); 0361 if ( comp (val, *it_out)) LS = it_out - 1 ; else LI = it_out ; 0362 }; 0363 return LS ; 0364 }; 0365 0366 // 0367 //########################################################################### 0368 // ## 0369 // ################################################################ ## 0370 // # # ## 0371 // # P U B L I C F U N C T I O N S # ## 0372 // # # ## 0373 // ################################################################ ## 0374 // ## 0375 //########################################################################### 0376 // 0377 //----------------------------------------------------------------------------- 0378 // function : find_first 0379 /// @brief find if a value exist in the range [first, last). If exist return the 0380 /// iterator to the first occurrence. If don't exist return last 0381 // 0382 /// @param [in] first : iterator to the first element of the range 0383 /// @param [in] last : iterator to the last element of the range 0384 /// @param [in] val : value to find 0385 /// @param [in] comp : object for to compare two value_t objects 0386 /// @return iterator to the element found, and if not last 0387 //----------------------------------------------------------------------------- 0388 template < class Iter_t, class Compare = compare_iter<Iter_t> > 0389 inline Iter_t find_first ( Iter_t first, Iter_t last, 0390 const value_iter<Iter_t> &val, 0391 Compare comp = Compare() ) 0392 { 0393 assert ( (last - first) >= 0 ); 0394 if ( first == last) return last ; 0395 Iter_t LS = internal_find_first ( first, last, val, comp); 0396 return (comp (*LS, val) or comp (val, *LS))?last:LS; 0397 }; 0398 // 0399 //----------------------------------------------------------------------------- 0400 // function : find_last 0401 /// @brief find if a value exist in the range [first, last). If exist return the 0402 /// iterator to the last occurrence. If don't exist return last 0403 // 0404 /// @param [in] first : iterator to the first element of the range 0405 /// @param [in] last : iterator to the last element of the range 0406 /// @param [in] val : value to find 0407 /// @param [in] comp : object for to compare two value_t objects 0408 /// @return iterator to the element found, if not found return last 0409 0410 //----------------------------------------------------------------------------- 0411 template < class Iter_t, class Compare = compare_iter<Iter_t> > 0412 inline Iter_t find_last ( Iter_t first, Iter_t last , 0413 const value_iter<Iter_t> &val, 0414 Compare comp = Compare()) 0415 { 0416 assert ( (last - first ) >= 0 ); 0417 if ( last == first ) return last ; 0418 Iter_t LS = internal_find_last (first, last, val, comp); 0419 return (comp (*LS, val) or comp (val, *LS))?last:LS ; 0420 }; 0421 0422 //---------------------------------------------------------------------------- 0423 // function : lower_bound 0424 /// @brief Returns an iterator pointing to the first element in the range 0425 /// [first, last) that is not less than (i.e. greater or equal to) val. 0426 /// @param [in] last : iterator to the last element of the range 0427 /// @param [in] val : value to find 0428 /// @param [in] comp : object for to compare two value_t objects 0429 /// @return iterator to the element found 0430 //----------------------------------------------------------------------------- 0431 template < class Iter_t, class Compare = compare_iter<Iter_t> > 0432 inline Iter_t lower_bound ( Iter_t first, Iter_t last , 0433 const value_iter<Iter_t> &val, 0434 Compare &comp = Compare() ) 0435 { 0436 assert ( (last - first ) >= 0 ); 0437 if ( last == first ) return last ; 0438 Iter_t itaux = internal_find_first( first, last, val,comp); 0439 return (itaux == (last - 1) and comp (*itaux, val))?last: itaux; 0440 }; 0441 //---------------------------------------------------------------------------- 0442 // function :upper_bound 0443 /// @brief return the first element greather than val.If don't exist 0444 /// return last 0445 // 0446 /// @param [in] first : iterator to the first element of the range 0447 /// @param [in] last : iterator to the last element of the range 0448 /// @param [in] val : value to find 0449 /// @param [in] comp : object for to compare two value_t objects 0450 /// @return iterator to the element found 0451 /// @remarks 0452 //----------------------------------------------------------------------------- 0453 template < class Iter_t, class Compare = compare_iter<Iter_t> > 0454 inline Iter_t upper_bound ( Iter_t first, Iter_t last , 0455 const value_iter<Iter_t> &val, 0456 Compare &comp = Compare() ) 0457 { 0458 assert ( (last - first ) >= 0 ); 0459 if ( last == first ) return last ; 0460 Iter_t itaux = internal_find_last( first, last, val,comp); 0461 return ( itaux == first and comp (val,*itaux))? itaux: itaux + 1; 0462 }; 0463 //---------------------------------------------------------------------------- 0464 // function :equal_range 0465 /// @brief return a pair of lower_bound and upper_bound with the value val.If 0466 /// don't exist return last in the two elements of the pair 0467 // 0468 /// @param [in] first : iterator to the first element of the range 0469 /// @param [in] last : iterator to the last element of the range 0470 /// @param [in] val : value to find 0471 /// @param [in] comp : object for to compare two value_t objects 0472 /// @return pair of iterators 0473 //----------------------------------------------------------------------------- 0474 template < class Iter_t, class Compare = compare_iter<Iter_t> > 0475 inline std::pair<Iter_t, Iter_t> equal_range ( Iter_t first, Iter_t last , 0476 const value_iter<Iter_t> &val, 0477 Compare &comp = Compare() ) 0478 { 0479 return std::make_pair(lower_bound(first, last, val,comp), 0480 upper_bound(first, last, val,comp)); 0481 }; 0482 // 0483 //----------------------------------------------------------------------------- 0484 // function : insert_first 0485 /// @brief find if a value exist in the range [first, last). If exist return the 0486 /// iterator to the first occurrence. If don't exist return last 0487 // 0488 /// @param [in] first : iterator to the first element of the range 0489 /// @param [in] last : iterator to the last element of the range 0490 /// @param [in] val : value to find 0491 /// @param [in] comp : object for to compare two value_t objects 0492 /// @return iterator to the element found, and if not last 0493 //----------------------------------------------------------------------------- 0494 template < class Iter_t, class Compare = compare_iter<Iter_t> > 0495 inline Iter_t insert_first ( Iter_t first, Iter_t last, 0496 const value_iter<Iter_t> &val, 0497 Compare comp = Compare() ) 0498 { 0499 return lower_bound (first, last, val, comp); 0500 }; 0501 // 0502 //----------------------------------------------------------------------------- 0503 // function : insert_last 0504 /// @brief find if a value exist in the range [first, last). If exist return the 0505 /// iterator to the last occurrence. If don't exist return last 0506 // 0507 /// @param [in] first : iterator to the first element of the range 0508 /// @param [in] last : iterator to the last element of the range 0509 /// @param [in] val : value to find 0510 /// @param [in] comp : object for to compare two value_t objects 0511 /// @return iterator to the element found, if not found return last 0512 0513 //----------------------------------------------------------------------------- 0514 template < class Iter_t, class Compare = compare_iter<Iter_t> > 0515 inline Iter_t insert_last ( Iter_t first, Iter_t last , 0516 const value_iter<Iter_t> &val, 0517 Compare comp = Compare()) 0518 { 0519 return upper_bound (first, last, val, comp); 0520 }; 0521 0522 */ 0523 // 0524 //**************************************************************************** 0525 };// End namespace util 0526 };// End namespace common 0527 };// End namespace sort 0528 };// End namespace boost 0529 //**************************************************************************** 0530 // 0531 #endif
| [ Source navigation ] | [ Diff markup ] | [ Identifier search ] | [ general search ] |
|
This page was automatically generated by the 2.3.7 LXR engine. The LXR team |
|