boost/algorithm/minmax_element.hpp

   1 //  (C) Copyright Herve Bronnimann 2004.
   2 //
   3 // Distributed under the Boost Software License, Version 1.0. (See accompanying
   4 // file 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