1 //  (C) Copyright Herve Bronnimann 2004.

     2 //  Use, modification and distribution are subject to the

     3 //  Boost Software License, Version 1.0. (See accompanying file

     4 //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

     5 

     6 /*

     7  Revision history:

     8    1 July 2004

     9       Split the code into two headers to lessen dependence on

    10       Boost.tuple. (Herve)

    11    26 June 2004

    12       Added the code for the boost minmax library. (Herve)

    13 */

    14 

    15 #ifndef BOOST_ALGORITHM_MINMAX_ELEMENT_HPP

    16 #define BOOST_ALGORITHM_MINMAX_ELEMENT_HPP

    17 

    18 /* PROPOSED STANDARD EXTENSIONS:

    19  *

    20  * minmax_element(first, last)

    21  * Effect: std::make_pair( std::min_element(first, last),

    22  *                         std::max_element(first, last) );

    23  *

    24  * minmax_element(first, last, comp)

    25  * Effect: std::make_pair( std::min_element(first, last, comp),

    26  *                         std::max_element(first, last, comp) );

    27  */

    28 

    29 #include <utility> // for std::pair and std::make_pair

    30 

    31 namespace boost {

    32 

    33   namespace detail {  // for obtaining a uniform version of minmax_element

    34     // that compiles with VC++ 6.0 -- avoid the iterator_traits by

    35     // having comparison object over iterator, not over dereferenced value

    36 

    37     template <typename Iterator>

    38     struct less_over_iter {

    39       bool operator()(Iterator const& it1,

    40                       Iterator const& it2) const { return *it1 < *it2; }

    41     };

    42 

    43     template <typename Iterator, class BinaryPredicate>

    44     struct binary_pred_over_iter {

    45       explicit binary_pred_over_iter(BinaryPredicate const& p ) : m_p( p ) {}

    46       bool operator()(Iterator const& it1,

    47                       Iterator const& it2) const { return m_p(*it1, *it2); }

    48     private:

    49       BinaryPredicate m_p;

    50     };

    51 

    52     // common base for the two minmax_element overloads

    53 

    54     template <typename ForwardIter, class Compare >

    55     std::pair<ForwardIter,ForwardIter>

    56     basic_minmax_element(ForwardIter first, ForwardIter last, Compare comp)

    57     {

    58       if (first == last)

    59         return std::make_pair(last,last);

    60 

    61       ForwardIter min_result = first;

    62       ForwardIter max_result = first;

    63 

    64       // if only one element

    65       ForwardIter second = first; ++second;

    66       if (second == last)

    67         return std::make_pair(min_result, max_result);

    68 

    69       // treat first pair separately (only one comparison for first two elements)

    70       ForwardIter potential_min_result = last;

    71       if (comp(first, second))

    72         max_result = second;

    73       else {

    74         min_result = second;

    75         potential_min_result = first;

    76       }

    77 

    78       // then each element by pairs, with at most 3 comparisons per pair

    79       first = ++second; if (first != last) ++second;

    80       while (second != last) {

    81         if (comp(first, second)) {

    82           if (comp(first, min_result)) {

    83             min_result = first;

    84             potential_min_result = last;

    85           }

    86           if (comp(max_result, second))

    87             max_result = second;

    88         } else {

    89           if (comp(second, min_result)) {

    90             min_result = second;

    91             potential_min_result = first;

    92           }

    93           if (comp(max_result, first))

    94             max_result = first;

    95         }

    96         first = ++second;

    97         if (first != last) ++second;

    98       }

    99 

   100       // if odd number of elements, treat last element

   101       if (first != last) { // odd number of elements

   102         if (comp(first, min_result))

   103           min_result = first, potential_min_result = last;

   104         else if (comp(max_result, first))

   105           max_result = first;

   106       }

   107 

   108       // resolve min_result being incorrect with one extra comparison

   109       // (in which case potential_min_result is necessarily the correct result)

   110       if (potential_min_result != last

   111         && !comp(min_result, potential_min_result))

   112         min_result = potential_min_result;

   113 

   114       return std::make_pair(min_result,max_result);

   115     }

   116 

   117   } // namespace detail

   118 

   119   template <typename ForwardIter>

   120   std::pair<ForwardIter,ForwardIter>

   121   minmax_element(ForwardIter first, ForwardIter last)

   122   {

   123     return detail::basic_minmax_element(first, last,

   124              detail::less_over_iter<ForwardIter>() );

   125   }

   126 

   127   template <typename ForwardIter, class BinaryPredicate>

   128   std::pair<ForwardIter,ForwardIter>

   129   minmax_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)

   130   {

   131     return detail::basic_minmax_element(first, last,

   132              detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );

   133   }

   134 

   135 }

   136 

   137 /* PROPOSED BOOST EXTENSIONS

   138  * In the description below, [rfirst,rlast) denotes the reversed range

   139  * of [first,last). Even though the iterator type of first and last may

   140  * be only a Forward Iterator, it is possible to explain the semantics

   141  * by assuming that it is a Bidirectional Iterator. In the sequel,

   142  * reverse(ForwardIterator&) returns the reverse_iterator adaptor.

   143  * This is not how the functions would be implemented!

   144  *

   145  * first_min_element(first, last)

   146  * Effect: std::min_element(first, last);

   147  *

   148  * first_min_element(first, last, comp)

   149  * Effect: std::min_element(first, last, comp);

   150  *

   151  * last_min_element(first, last)

   152  * Effect: reverse( std::min_element(reverse(last), reverse(first)) );

   153  *

   154  * last_min_element(first, last, comp)

   155  * Effect: reverse( std::min_element(reverse(last), reverse(first), comp) );

   156  *

   157  * first_max_element(first, last)

   158  * Effect: std::max_element(first, last);

   159  *

   160  * first_max_element(first, last, comp)

   161  * Effect: max_element(first, last);

   162  *

   163  * last_max_element(first, last)

   164  * Effect: reverse( std::max_element(reverse(last), reverse(first)) );

   165  *

   166  * last_max_element(first, last, comp)

   167  * Effect: reverse( std::max_element(reverse(last), reverse(first), comp) );

   168  *

   169  * first_min_first_max_element(first, last)

   170  * Effect: std::make_pair( first_min_element(first, last),

   171  *                         first_max_element(first, last) );

   172  *

   173  * first_min_first_max_element(first, last, comp)

   174  * Effect: std::make_pair( first_min_element(first, last, comp),

   175  *                         first_max_element(first, last, comp) );

   176  *

   177  * first_min_last_max_element(first, last)

   178  * Effect: std::make_pair( first_min_element(first, last),

   179  *                         last_max_element(first, last) );

   180  *

   181  * first_min_last_max_element(first, last, comp)

   182  * Effect: std::make_pair( first_min_element(first, last, comp),

   183  *                         last_max_element(first, last, comp) );

   184  *

   185  * last_min_first_max_element(first, last)

   186  * Effect: std::make_pair( last_min_element(first, last),

   187  *                         first_max_element(first, last) );

   188  *

   189  * last_min_first_max_element(first, last, comp)

   190  * Effect: std::make_pair( last_min_element(first, last, comp),

   191  *                         first_max_element(first, last, comp) );

   192  *

   193  * last_min_last_max_element(first, last)

   194  * Effect: std::make_pair( last_min_element(first, last),

   195  *                         last_max_element(first, last) );

   196  *

   197  * last_min_last_max_element(first, last, comp)

   198  * Effect: std::make_pair( last_min_element(first, last, comp),

   199  *                         last_max_element(first, last, comp) );

   200  */

   201 

   202 namespace boost {

   203 

   204   // Min_element and max_element variants

   205 

   206   namespace detail {  // common base for the overloads

   207 

   208   template <typename ForwardIter, class BinaryPredicate>

   209   ForwardIter

   210   basic_first_min_element(ForwardIter first, ForwardIter last,

   211                           BinaryPredicate comp)

   212   {

   213     if (first == last) return last;

   214     ForwardIter min_result = first;

   215     while (++first != last)

   216       if (comp(first, min_result))

   217         min_result = first;

   218     return min_result;

   219   }

   220 

   221   template <typename ForwardIter, class BinaryPredicate>

   222   ForwardIter

   223   basic_last_min_element(ForwardIter first, ForwardIter last,

   224                          BinaryPredicate comp)

   225   {

   226     if (first == last) return last;

   227     ForwardIter min_result = first;

   228     while (++first != last)

   229       if (!comp(min_result, first))

   230         min_result = first;

   231     return min_result;

   232   }

   233 

   234   template <typename ForwardIter, class BinaryPredicate>

   235   ForwardIter

   236   basic_first_max_element(ForwardIter first, ForwardIter last,

   237                           BinaryPredicate comp)

   238   {

   239     if (first == last) return last;

   240     ForwardIter max_result = first;

   241     while (++first != last)

   242       if (comp(max_result, first))

   243         max_result = first;

   244     return max_result;

   245   }

   246 

   247   template <typename ForwardIter, class BinaryPredicate>

   248   ForwardIter

   249   basic_last_max_element(ForwardIter first, ForwardIter last,

   250                          BinaryPredicate comp)

   251   {

   252     if (first == last) return last;

   253     ForwardIter max_result = first;

   254     while (++first != last)

   255       if (!comp(first, max_result))

   256         max_result = first;

   257     return max_result;

   258   }

   259 

   260   } // namespace detail

   261 

   262   template <typename ForwardIter>

   263   ForwardIter

   264   first_min_element(ForwardIter first, ForwardIter last)

   265   {

   266     return detail::basic_first_min_element(first, last,

   267              detail::less_over_iter<ForwardIter>() );

   268   }

   269 

   270   template <typename ForwardIter, class BinaryPredicate>

   271   ForwardIter

   272   first_min_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)

   273   {

   274     return detail::basic_first_min_element(first, last,

   275              detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );

   276   }

   277 

   278   template <typename ForwardIter>

   279   ForwardIter

   280   last_min_element(ForwardIter first, ForwardIter last)

   281   {

   282     return detail::basic_last_min_element(first, last,

   283              detail::less_over_iter<ForwardIter>() );

   284   }

   285 

   286   template <typename ForwardIter, class BinaryPredicate>

   287   ForwardIter

   288   last_min_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)

   289   {

   290     return detail::basic_last_min_element(first, last,

   291              detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );

   292   }

   293 

   294   template <typename ForwardIter>

   295   ForwardIter

   296   first_max_element(ForwardIter first, ForwardIter last)

   297   {

   298     return detail::basic_first_max_element(first, last,

   299              detail::less_over_iter<ForwardIter>() );

   300   }

   301 

   302   template <typename ForwardIter, class BinaryPredicate>

   303   ForwardIter

   304   first_max_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)

   305   {

   306     return detail::basic_first_max_element(first, last,

   307              detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );

   308   }

   309 

   310   template <typename ForwardIter>

   311   ForwardIter

   312   last_max_element(ForwardIter first, ForwardIter last)

   313   {

   314     return detail::basic_last_max_element(first, last,

   315              detail::less_over_iter<ForwardIter>() );

   316   }

   317 

   318   template <typename ForwardIter, class BinaryPredicate>

   319   ForwardIter

   320   last_max_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)

   321   {

   322     return detail::basic_last_max_element(first, last,

   323              detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );

   324   }

   325 

   326 

   327   // Minmax_element variants -- comments removed

   328 

   329   namespace detail {

   330 

   331   template <typename ForwardIter, class BinaryPredicate>

   332   std::pair<ForwardIter,ForwardIter>

   333   basic_first_min_last_max_element(ForwardIter first, ForwardIter last,

   334                                    BinaryPredicate comp)

   335   {

   336     if (first == last)

   337       return std::make_pair(last,last);

   338 

   339     ForwardIter min_result = first;

   340     ForwardIter max_result = first;

   341 

   342     ForwardIter second = ++first;

   343     if (second == last)

   344       return std::make_pair(min_result, max_result);

   345 

   346     if (comp(second, min_result))

   347       min_result = second;

   348     else

   349       max_result = second;

   350 

   351     first = ++second; if (first != last) ++second;

   352     while (second != last) {

   353       if (!comp(second, first)) {

   354         if (comp(first, min_result))

   355                  min_result = first;

   356         if (!comp(second, max_result))

   357           max_result = second;

   358       } else {

   359         if (comp(second, min_result))

   360           min_result = second;

   361         if (!comp(first, max_result))

   362               max_result = first;

   363       }

   364       first = ++second; if (first != last) ++second;

   365     }

   366 

   367     if (first != last) {

   368       if (comp(first, min_result))

   369          min_result = first;

   370       else if (!comp(first, max_result))

   371                max_result = first;

   372     }

   373 

   374     return std::make_pair(min_result, max_result);

   375   }

   376 

   377   template <typename ForwardIter, class BinaryPredicate>

   378   std::pair<ForwardIter,ForwardIter>

   379   basic_last_min_first_max_element(ForwardIter first, ForwardIter last,

   380                                    BinaryPredicate comp)

   381   {

   382     if (first == last) return std::make_pair(last,last);

   383 

   384     ForwardIter min_result = first;

   385     ForwardIter max_result = first;

   386 

   387     ForwardIter second = ++first;

   388     if (second == last)

   389       return std::make_pair(min_result, max_result);

   390 

   391     if (comp(max_result, second))

   392       max_result = second;

   393     else

   394       min_result = second;

   395 

   396     first = ++second; if (first != last) ++second;

   397     while (second != last)  {

   398       if (comp(first, second)) {

   399         if (!comp(min_result, first))

   400           min_result = first;

   401         if (comp(max_result, second))

   402           max_result = second;

   403       } else {

   404         if (!comp(min_result, second))

   405           min_result = second;

   406         if (comp(max_result, first))

   407           max_result = first;

   408       }

   409       first = ++second; if (first != last) ++second;

   410     }

   411 

   412     if (first != last) {

   413       if (!comp(min_result, first))

   414         min_result = first;

   415       else if (comp(max_result, first))

   416         max_result = first;

   417     }

   418 

   419     return std::make_pair(min_result, max_result);

   420   }

   421 

   422   template <typename ForwardIter, class BinaryPredicate>

   423   std::pair<ForwardIter,ForwardIter>

   424   basic_last_min_last_max_element(ForwardIter first, ForwardIter last,

   425                                   BinaryPredicate comp)

   426   {

   427     if (first == last) return std::make_pair(last,last);

   428 

   429     ForwardIter min_result = first;

   430     ForwardIter max_result = first;

   431 

   432     ForwardIter second = first; ++second;

   433     if (second == last)

   434       return std::make_pair(min_result,max_result);

   435 

   436     ForwardIter potential_max_result = last;

   437     if (comp(first, second))

   438       max_result = second;

   439     else {

   440       min_result = second;

   441       potential_max_result = second;

   442     }

   443 

   444     first = ++second; if (first != last) ++second;

   445     while (second != last) {

   446       if (comp(first, second)) {

   447         if (!comp(min_result, first))

   448           min_result = first;

   449         if (!comp(second, max_result)) {

   450           max_result = second;

   451           potential_max_result = last;

   452         }

   453       } else {

   454         if (!comp(min_result, second))

   455           min_result = second;

   456         if (!comp(first, max_result)) {

   457           max_result = first;

   458           potential_max_result = second;

   459         }

   460       }

   461       first = ++second;

   462       if (first != last) ++second;

   463     }

   464 

   465     if (first != last) {

   466       if (!comp(min_result, first))

   467         min_result = first;

   468       if (!comp(first, max_result)) {

   469         max_result = first;

   470                potential_max_result = last;

   471       }

   472     }

   473 

   474     if (potential_max_result != last

   475         && !comp(potential_max_result, max_result))

   476       max_result = potential_max_result;

   477 

   478     return std::make_pair(min_result,max_result);

   479   }

   480 

   481   } // namespace detail

   482 

   483   template <typename ForwardIter>

   484   inline std::pair<ForwardIter,ForwardIter>

   485   first_min_first_max_element(ForwardIter first, ForwardIter last)

   486   {

   487     return minmax_element(first, last);

   488   }

   489 

   490   template <typename ForwardIter, class BinaryPredicate>

   491   inline std::pair<ForwardIter,ForwardIter>

   492   first_min_first_max_element(ForwardIter first, ForwardIter last,

   493                               BinaryPredicate comp)

   494   {

   495     return minmax_element(first, last, comp);

   496   }

   497 

   498   template <typename ForwardIter>

   499   std::pair<ForwardIter,ForwardIter>

   500   first_min_last_max_element(ForwardIter first, ForwardIter last)

   501   {

   502     return detail::basic_first_min_last_max_element(first, last,

   503              detail::less_over_iter<ForwardIter>() );

   504   }

   505 

   506   template <typename ForwardIter, class BinaryPredicate>

   507   inline std::pair<ForwardIter,ForwardIter>

   508   first_min_last_max_element(ForwardIter first, ForwardIter last,

   509                               BinaryPredicate comp)

   510   {

   511     return detail::basic_first_min_last_max_element(first, last,

   512              detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );

   513   }

   514 

   515   template <typename ForwardIter>

   516   std::pair<ForwardIter,ForwardIter>

   517   last_min_first_max_element(ForwardIter first, ForwardIter last)

   518   {

   519     return detail::basic_last_min_first_max_element(first, last,

   520              detail::less_over_iter<ForwardIter>() );

   521   }

   522 

   523   template <typename ForwardIter, class BinaryPredicate>

   524   inline std::pair<ForwardIter,ForwardIter>

   525   last_min_first_max_element(ForwardIter first, ForwardIter last,

   526                               BinaryPredicate comp)

   527   {

   528     return detail::basic_last_min_first_max_element(first, last,

   529              detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );

   530   }

   531 

   532   template <typename ForwardIter>

   533   std::pair<ForwardIter,ForwardIter>

   534   last_min_last_max_element(ForwardIter first, ForwardIter last)

   535   {

   536     return detail::basic_last_min_last_max_element(first, last,

   537              detail::less_over_iter<ForwardIter>() );

   538   }

   539 

   540   template <typename ForwardIter, class BinaryPredicate>

   541   inline std::pair<ForwardIter,ForwardIter>

   542   last_min_last_max_element(ForwardIter first, ForwardIter last,

   543                               BinaryPredicate comp)

   544   {

   545     return detail::basic_last_min_last_max_element(first, last,

   546              detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );

   547   }

   548 

   549 } // namespace boost

   550 

   551 #endif // BOOST_ALGORITHM_MINMAX_ELEMENT_HPP