Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-18 09:28:26 

0001 //  (C) Copyright Herve Bronnimann 2004.
0002 //
0003 // Distributed under the Boost Software License, Version 1.0. (See accompanying
0004 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0005 
0006 /*
0007  Revision history:
0008    1 July 2004
0009       Split the code into two headers to lessen dependence on
0010       Boost.tuple. (Herve)
0011    26 June 2004
0012       Added the code for the boost minmax library. (Herve)
0013 */
0014 
0015 #ifndef BOOST_ALGORITHM_MINMAX_ELEMENT_HPP
0016 #define BOOST_ALGORITHM_MINMAX_ELEMENT_HPP
0017 
0018 /* PROPOSED STANDARD EXTENSIONS:
0019  *
0020  * minmax_element(first, last)
0021  * Effect: std::make_pair( std::min_element(first, last),
0022  *                         std::max_element(first, last) );
0023  *
0024  * minmax_element(first, last, comp)
0025  * Effect: std::make_pair( std::min_element(first, last, comp),
0026  *                         std::max_element(first, last, comp) );
0027  */
0028 
0029 #include <utility> // for std::pair and std::make_pair
0030 
0031 #include <boost/config.hpp>
0032 
0033 namespace boost {
0034 
0035   namespace detail {  // for obtaining a uniform version of minmax_element
0036     // that compiles with VC++ 6.0 -- avoid the iterator_traits by
0037     // having comparison object over iterator, not over dereferenced value
0038 
0039     template <typename Iterator>
0040     struct less_over_iter {
0041       bool operator()(Iterator const& it1,
0042                       Iterator const& it2) const { return *it1 < *it2; }
0043     };
0044 
0045     template <typename Iterator, class BinaryPredicate>
0046     struct binary_pred_over_iter {
0047       explicit binary_pred_over_iter(BinaryPredicate const& p ) : m_p( p ) {}
0048       bool operator()(Iterator const& it1,
0049                       Iterator const& it2) const { return m_p(*it1, *it2); }
0050     private:
0051       BinaryPredicate m_p;
0052     };
0053 
0054     // common base for the two minmax_element overloads
0055 
0056     template <typename ForwardIter, class Compare >
0057     std::pair<ForwardIter,ForwardIter>
0058     basic_minmax_element(ForwardIter first, ForwardIter last, Compare comp)
0059     {
0060       if (first == last)
0061         return std::make_pair(last,last);
0062 
0063       ForwardIter min_result = first;
0064       ForwardIter max_result = first;
0065 
0066       // if only one element
0067       ForwardIter second = first; ++second;
0068       if (second == last)
0069         return std::make_pair(min_result, max_result);
0070 
0071       // treat first pair separately (only one comparison for first two elements)
0072       ForwardIter potential_min_result = last;
0073       if (comp(first, second))
0074         max_result = second;
0075       else {
0076         min_result = second;
0077         potential_min_result = first;
0078       }
0079 
0080       // then each element by pairs, with at most 3 comparisons per pair
0081       first = ++second; if (first != last) ++second;
0082       while (second != last) {
0083         if (comp(first, second)) {
0084           if (comp(first, min_result)) {
0085             min_result = first;
0086             potential_min_result = last;
0087           }
0088           if (comp(max_result, second))
0089             max_result = second;
0090         } else {
0091           if (comp(second, min_result)) {
0092             min_result = second;
0093             potential_min_result = first;
0094           }
0095           if (comp(max_result, first))
0096             max_result = first;
0097         }
0098         first = ++second;
0099         if (first != last) ++second;
0100       }
0101 
0102       // if odd number of elements, treat last element
0103       if (first != last) { // odd number of elements
0104         if (comp(first, min_result)) {
0105           min_result = first;
0106           potential_min_result = last;
0107           }
0108         else if (comp(max_result, first))
0109           max_result = first;
0110       }
0111 
0112       // resolve min_result being incorrect with one extra comparison
0113       // (in which case potential_min_result is necessarily the correct result)
0114       if (potential_min_result != last
0115         && !comp(min_result, potential_min_result))
0116         min_result = potential_min_result;
0117 
0118       return std::make_pair(min_result,max_result);
0119     }
0120 
0121   } // namespace detail
0122 
0123   template <typename ForwardIter>
0124   std::pair<ForwardIter,ForwardIter>
0125   minmax_element(ForwardIter first, ForwardIter last)
0126   {
0127     return detail::basic_minmax_element(first, last,
0128              detail::less_over_iter<ForwardIter>() );
0129   }
0130 
0131   template <typename ForwardIter, class BinaryPredicate>
0132   std::pair<ForwardIter,ForwardIter>
0133   minmax_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
0134   {
0135     return detail::basic_minmax_element(first, last,
0136              detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
0137   }
0138 
0139 }
0140 
0141 /* PROPOSED BOOST EXTENSIONS
0142  * In the description below, [rfirst,rlast) denotes the reversed range
0143  * of [first,last). Even though the iterator type of first and last may
0144  * be only a Forward Iterator, it is possible to explain the semantics
0145  * by assuming that it is a Bidirectional Iterator. In the sequel,
0146  * reverse(ForwardIterator&) returns the reverse_iterator adaptor.
0147  * This is not how the functions would be implemented!
0148  *
0149  * first_min_element(first, last)
0150  * Effect: std::min_element(first, last);
0151  *
0152  * first_min_element(first, last, comp)
0153  * Effect: std::min_element(first, last, comp);
0154  *
0155  * last_min_element(first, last)
0156  * Effect: reverse( std::min_element(reverse(last), reverse(first)) );
0157  *
0158  * last_min_element(first, last, comp)
0159  * Effect: reverse( std::min_element(reverse(last), reverse(first), comp) );
0160  *
0161  * first_max_element(first, last)
0162  * Effect: std::max_element(first, last);
0163  *
0164  * first_max_element(first, last, comp)
0165  * Effect: max_element(first, last);
0166  *
0167  * last_max_element(first, last)
0168  * Effect: reverse( std::max_element(reverse(last), reverse(first)) );
0169  *
0170  * last_max_element(first, last, comp)
0171  * Effect: reverse( std::max_element(reverse(last), reverse(first), comp) );
0172  *
0173  * first_min_first_max_element(first, last)
0174  * Effect: std::make_pair( first_min_element(first, last),
0175  *                         first_max_element(first, last) );
0176  *
0177  * first_min_first_max_element(first, last, comp)
0178  * Effect: std::make_pair( first_min_element(first, last, comp),
0179  *                         first_max_element(first, last, comp) );
0180  *
0181  * first_min_last_max_element(first, last)
0182  * Effect: std::make_pair( first_min_element(first, last),
0183  *                         last_max_element(first, last) );
0184  *
0185  * first_min_last_max_element(first, last, comp)
0186  * Effect: std::make_pair( first_min_element(first, last, comp),
0187  *                         last_max_element(first, last, comp) );
0188  *
0189  * last_min_first_max_element(first, last)
0190  * Effect: std::make_pair( last_min_element(first, last),
0191  *                         first_max_element(first, last) );
0192  *
0193  * last_min_first_max_element(first, last, comp)
0194  * Effect: std::make_pair( last_min_element(first, last, comp),
0195  *                         first_max_element(first, last, comp) );
0196  *
0197  * last_min_last_max_element(first, last)
0198  * Effect: std::make_pair( last_min_element(first, last),
0199  *                         last_max_element(first, last) );
0200  *
0201  * last_min_last_max_element(first, last, comp)
0202  * Effect: std::make_pair( last_min_element(first, last, comp),
0203  *                         last_max_element(first, last, comp) );
0204  */
0205 
0206 namespace boost {
0207 
0208   // Min_element and max_element variants
0209 
0210   namespace detail {  // common base for the overloads
0211 
0212   template <typename ForwardIter, class BinaryPredicate>
0213   ForwardIter
0214   basic_first_min_element(ForwardIter first, ForwardIter last,
0215                           BinaryPredicate comp)
0216   {
0217     if (first == last) return last;
0218     ForwardIter min_result = first;
0219     while (++first != last)
0220       if (comp(first, min_result))
0221         min_result = first;
0222     return min_result;
0223   }
0224 
0225   template <typename ForwardIter, class BinaryPredicate>
0226   ForwardIter
0227   basic_last_min_element(ForwardIter first, ForwardIter last,
0228                          BinaryPredicate comp)
0229   {
0230     if (first == last) return last;
0231     ForwardIter min_result = first;
0232     while (++first != last)
0233       if (!comp(min_result, first))
0234         min_result = first;
0235     return min_result;
0236   }
0237 
0238   template <typename ForwardIter, class BinaryPredicate>
0239   ForwardIter
0240   basic_first_max_element(ForwardIter first, ForwardIter last,
0241                           BinaryPredicate comp)
0242   {
0243     if (first == last) return last;
0244     ForwardIter max_result = first;
0245     while (++first != last)
0246       if (comp(max_result, first))
0247         max_result = first;
0248     return max_result;
0249   }
0250 
0251   template <typename ForwardIter, class BinaryPredicate>
0252   ForwardIter
0253   basic_last_max_element(ForwardIter first, ForwardIter last,
0254                          BinaryPredicate comp)
0255   {
0256     if (first == last) return last;
0257     ForwardIter max_result = first;
0258     while (++first != last)
0259       if (!comp(first, max_result))
0260         max_result = first;
0261     return max_result;
0262   }
0263 
0264   } // namespace detail
0265 
0266   template <typename ForwardIter>
0267   ForwardIter
0268   first_min_element(ForwardIter first, ForwardIter last)
0269   {
0270     return detail::basic_first_min_element(first, last,
0271              detail::less_over_iter<ForwardIter>() );
0272   }
0273 
0274   template <typename ForwardIter, class BinaryPredicate>
0275   ForwardIter
0276   first_min_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
0277   {
0278     return detail::basic_first_min_element(first, last,
0279              detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
0280   }
0281 
0282   template <typename ForwardIter>
0283   ForwardIter
0284   last_min_element(ForwardIter first, ForwardIter last)
0285   {
0286     return detail::basic_last_min_element(first, last,
0287              detail::less_over_iter<ForwardIter>() );
0288   }
0289 
0290   template <typename ForwardIter, class BinaryPredicate>
0291   ForwardIter
0292   last_min_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
0293   {
0294     return detail::basic_last_min_element(first, last,
0295              detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
0296   }
0297 
0298   template <typename ForwardIter>
0299   ForwardIter
0300   first_max_element(ForwardIter first, ForwardIter last)
0301   {
0302     return detail::basic_first_max_element(first, last,
0303              detail::less_over_iter<ForwardIter>() );
0304   }
0305 
0306   template <typename ForwardIter, class BinaryPredicate>
0307   ForwardIter
0308   first_max_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
0309   {
0310     return detail::basic_first_max_element(first, last,
0311              detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
0312   }
0313 
0314   template <typename ForwardIter>
0315   ForwardIter
0316   last_max_element(ForwardIter first, ForwardIter last)
0317   {
0318     return detail::basic_last_max_element(first, last,
0319              detail::less_over_iter<ForwardIter>() );
0320   }
0321 
0322   template <typename ForwardIter, class BinaryPredicate>
0323   ForwardIter
0324   last_max_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
0325   {
0326     return detail::basic_last_max_element(first, last,
0327              detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
0328   }
0329 
0330 
0331   // Minmax_element variants -- comments removed
0332 
0333   namespace detail {
0334 
0335   template <typename ForwardIter, class BinaryPredicate>
0336   std::pair<ForwardIter,ForwardIter>
0337   basic_first_min_last_max_element(ForwardIter first, ForwardIter last,
0338                                    BinaryPredicate comp)
0339   {
0340     if (first == last)
0341       return std::make_pair(last,last);
0342 
0343     ForwardIter min_result = first;
0344     ForwardIter max_result = first;
0345 
0346     ForwardIter second = ++first;
0347     if (second == last)
0348       return std::make_pair(min_result, max_result);
0349 
0350     if (comp(second, min_result))
0351       min_result = second;
0352     else
0353       max_result = second;
0354 
0355     first = ++second; if (first != last) ++second;
0356     while (second != last) {
0357       if (!comp(second, first)) {
0358         if (comp(first, min_result))
0359                  min_result = first;
0360         if (!comp(second, max_result))
0361           max_result = second;
0362       } else {
0363         if (comp(second, min_result))
0364           min_result = second;
0365         if (!comp(first, max_result))
0366               max_result = first;
0367       }
0368       first = ++second; if (first != last) ++second;
0369     }
0370 
0371     if (first != last) {
0372       if (comp(first, min_result))
0373          min_result = first;
0374       else if (!comp(first, max_result))
0375                max_result = first;
0376     }
0377 
0378     return std::make_pair(min_result, max_result);
0379   }
0380 
0381   template <typename ForwardIter, class BinaryPredicate>
0382   std::pair<ForwardIter,ForwardIter>
0383   basic_last_min_first_max_element(ForwardIter first, ForwardIter last,
0384                                    BinaryPredicate comp)
0385   {
0386     if (first == last) return std::make_pair(last,last);
0387 
0388     ForwardIter min_result = first;
0389     ForwardIter max_result = first;
0390 
0391     ForwardIter second = ++first;
0392     if (second == last)
0393       return std::make_pair(min_result, max_result);
0394 
0395     if (comp(max_result, second))
0396       max_result = second;
0397     else
0398       min_result = second;
0399 
0400     first = ++second; if (first != last) ++second;
0401     while (second != last)  {
0402       if (comp(first, second)) {
0403         if (!comp(min_result, first))
0404           min_result = first;
0405         if (comp(max_result, second))
0406           max_result = second;
0407       } else {
0408         if (!comp(min_result, second))
0409           min_result = second;
0410         if (comp(max_result, first))
0411           max_result = first;
0412       }
0413       first = ++second; if (first != last) ++second;
0414     }
0415 
0416     if (first != last) {
0417       if (!comp(min_result, first))
0418         min_result = first;
0419       else if (comp(max_result, first))
0420         max_result = first;
0421     }
0422 
0423     return std::make_pair(min_result, max_result);
0424   }
0425 
0426   template <typename ForwardIter, class BinaryPredicate>
0427   std::pair<ForwardIter,ForwardIter>
0428   basic_last_min_last_max_element(ForwardIter first, ForwardIter last,
0429                                   BinaryPredicate comp)
0430   {
0431     if (first == last) return std::make_pair(last,last);
0432 
0433     ForwardIter min_result = first;
0434     ForwardIter max_result = first;
0435 
0436     ForwardIter second = first; ++second;
0437     if (second == last)
0438       return std::make_pair(min_result,max_result);
0439 
0440     ForwardIter potential_max_result = last;
0441     if (comp(first, second))
0442       max_result = second;
0443     else {
0444       min_result = second;
0445       potential_max_result = second;
0446     }
0447 
0448     first = ++second; if (first != last) ++second;
0449     while (second != last) {
0450       if (comp(first, second)) {
0451         if (!comp(min_result, first))
0452           min_result = first;
0453         if (!comp(second, max_result)) {
0454           max_result = second;
0455           potential_max_result = last;
0456         }
0457       } else {
0458         if (!comp(min_result, second))
0459           min_result = second;
0460         if (!comp(first, max_result)) {
0461           max_result = first;
0462           potential_max_result = second;
0463         }
0464       }
0465       first = ++second;
0466       if (first != last) ++second;
0467     }
0468 
0469     if (first != last) {
0470       if (!comp(min_result, first))
0471         min_result = first;
0472       if (!comp(first, max_result)) {
0473         max_result = first;
0474                potential_max_result = last;
0475       }
0476     }
0477 
0478     if (potential_max_result != last
0479         && !comp(potential_max_result, max_result))
0480       max_result = potential_max_result;
0481 
0482     return std::make_pair(min_result,max_result);
0483   }
0484 
0485   } // namespace detail
0486 
0487   template <typename ForwardIter>
0488   inline std::pair<ForwardIter,ForwardIter>
0489   first_min_first_max_element(ForwardIter first, ForwardIter last)
0490   {
0491     return minmax_element(first, last);
0492   }
0493 
0494   template <typename ForwardIter, class BinaryPredicate>
0495   inline std::pair<ForwardIter,ForwardIter>
0496   first_min_first_max_element(ForwardIter first, ForwardIter last,
0497                               BinaryPredicate comp)
0498   {
0499     return minmax_element(first, last, comp);
0500   }
0501 
0502   template <typename ForwardIter>
0503   std::pair<ForwardIter,ForwardIter>
0504   first_min_last_max_element(ForwardIter first, ForwardIter last)
0505   {
0506     return detail::basic_first_min_last_max_element(first, last,
0507              detail::less_over_iter<ForwardIter>() );
0508   }
0509 
0510   template <typename ForwardIter, class BinaryPredicate>
0511   inline std::pair<ForwardIter,ForwardIter>
0512   first_min_last_max_element(ForwardIter first, ForwardIter last,
0513                               BinaryPredicate comp)
0514   {
0515     return detail::basic_first_min_last_max_element(first, last,
0516              detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
0517   }
0518 
0519   template <typename ForwardIter>
0520   std::pair<ForwardIter,ForwardIter>
0521   last_min_first_max_element(ForwardIter first, ForwardIter last)
0522   {
0523     return detail::basic_last_min_first_max_element(first, last,
0524              detail::less_over_iter<ForwardIter>() );
0525   }
0526 
0527   template <typename ForwardIter, class BinaryPredicate>
0528   inline std::pair<ForwardIter,ForwardIter>
0529   last_min_first_max_element(ForwardIter first, ForwardIter last,
0530                               BinaryPredicate comp)
0531   {
0532     return detail::basic_last_min_first_max_element(first, last,
0533              detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
0534   }
0535 
0536   template <typename ForwardIter>
0537   std::pair<ForwardIter,ForwardIter>
0538   last_min_last_max_element(ForwardIter first, ForwardIter last)
0539   {
0540     return detail::basic_last_min_last_max_element(first, last,
0541              detail::less_over_iter<ForwardIter>() );
0542   }
0543 
0544   template <typename ForwardIter, class BinaryPredicate>
0545   inline std::pair<ForwardIter,ForwardIter>
0546   last_min_last_max_element(ForwardIter first, ForwardIter last,
0547                               BinaryPredicate comp)
0548   {
0549     return detail::basic_last_min_last_max_element(first, last,
0550              detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
0551   }
0552 
0553 } // namespace boost
0554 
0555 #endif // BOOST_ALGORITHM_MINMAX_ELEMENT_HPP
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!