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 #include <boost/config.hpp> 32 33 namespace boost { 34 35 namespace detail { // for obtaining a uniform version of minmax_element 36 // that compiles with VC++ 6.0 -- avoid the iterator_traits by 37 // having comparison object over iterator, not over dereferenced value 38 39 template <typename Iterator> 40 struct less_over_iter { operator ()boost::detail::less_over_iter41 bool operator()(Iterator const& it1, 42 Iterator const& it2) const { return *it1 < *it2; } 43 }; 44 45 template <typename Iterator, class BinaryPredicate> 46 struct binary_pred_over_iter { binary_pred_over_iterboost::detail::binary_pred_over_iter47 explicit binary_pred_over_iter(BinaryPredicate const& p ) : m_p( p ) {} operator ()boost::detail::binary_pred_over_iter48 bool operator()(Iterator const& it1, 49 Iterator const& it2) const { return m_p(*it1, *it2); } 50 private: 51 BinaryPredicate m_p; 52 }; 53 54 // common base for the two minmax_element overloads 55 56 template <typename ForwardIter, class Compare > 57 std::pair<ForwardIter,ForwardIter> basic_minmax_element(ForwardIter first,ForwardIter last,Compare comp)58 basic_minmax_element(ForwardIter first, ForwardIter last, Compare comp) 59 { 60 if (first == last) 61 return std::make_pair(last,last); 62 63 ForwardIter min_result = first; 64 ForwardIter max_result = first; 65 66 // if only one element 67 ForwardIter second = first; ++second; 68 if (second == last) 69 return std::make_pair(min_result, max_result); 70 71 // treat first pair separately (only one comparison for first two elements) 72 ForwardIter potential_min_result = last; 73 if (comp(first, second)) 74 max_result = second; 75 else { 76 min_result = second; 77 potential_min_result = first; 78 } 79 80 // then each element by pairs, with at most 3 comparisons per pair 81 first = ++second; if (first != last) ++second; 82 while (second != last) { 83 if (comp(first, second)) { 84 if (comp(first, min_result)) { 85 min_result = first; 86 potential_min_result = last; 87 } 88 if (comp(max_result, second)) 89 max_result = second; 90 } else { 91 if (comp(second, min_result)) { 92 min_result = second; 93 potential_min_result = first; 94 } 95 if (comp(max_result, first)) 96 max_result = first; 97 } 98 first = ++second; 99 if (first != last) ++second; 100 } 101 102 // if odd number of elements, treat last element 103 if (first != last) { // odd number of elements 104 if (comp(first, min_result)) { 105 min_result = first; 106 potential_min_result = last; 107 } 108 else if (comp(max_result, first)) 109 max_result = first; 110 } 111 112 // resolve min_result being incorrect with one extra comparison 113 // (in which case potential_min_result is necessarily the correct result) 114 if (potential_min_result != last 115 && !comp(min_result, potential_min_result)) 116 min_result = potential_min_result; 117 118 return std::make_pair(min_result,max_result); 119 } 120 121 } // namespace detail 122 123 template <typename ForwardIter> 124 std::pair<ForwardIter,ForwardIter> minmax_element(ForwardIter first,ForwardIter last)125 minmax_element(ForwardIter first, ForwardIter last) 126 { 127 return detail::basic_minmax_element(first, last, 128 detail::less_over_iter<ForwardIter>() ); 129 } 130 131 template <typename ForwardIter, class BinaryPredicate> 132 std::pair<ForwardIter,ForwardIter> minmax_element(ForwardIter first,ForwardIter last,BinaryPredicate comp)133 minmax_element(ForwardIter first, ForwardIter last, BinaryPredicate comp) 134 { 135 return detail::basic_minmax_element(first, last, 136 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); 137 } 138 139 } 140 141 /* PROPOSED BOOST EXTENSIONS 142 * In the description below, [rfirst,rlast) denotes the reversed range 143 * of [first,last). Even though the iterator type of first and last may 144 * be only a Forward Iterator, it is possible to explain the semantics 145 * by assuming that it is a Bidirectional Iterator. In the sequel, 146 * reverse(ForwardIterator&) returns the reverse_iterator adaptor. 147 * This is not how the functions would be implemented! 148 * 149 * first_min_element(first, last) 150 * Effect: std::min_element(first, last); 151 * 152 * first_min_element(first, last, comp) 153 * Effect: std::min_element(first, last, comp); 154 * 155 * last_min_element(first, last) 156 * Effect: reverse( std::min_element(reverse(last), reverse(first)) ); 157 * 158 * last_min_element(first, last, comp) 159 * Effect: reverse( std::min_element(reverse(last), reverse(first), comp) ); 160 * 161 * first_max_element(first, last) 162 * Effect: std::max_element(first, last); 163 * 164 * first_max_element(first, last, comp) 165 * Effect: max_element(first, last); 166 * 167 * last_max_element(first, last) 168 * Effect: reverse( std::max_element(reverse(last), reverse(first)) ); 169 * 170 * last_max_element(first, last, comp) 171 * Effect: reverse( std::max_element(reverse(last), reverse(first), comp) ); 172 * 173 * first_min_first_max_element(first, last) 174 * Effect: std::make_pair( first_min_element(first, last), 175 * first_max_element(first, last) ); 176 * 177 * first_min_first_max_element(first, last, comp) 178 * Effect: std::make_pair( first_min_element(first, last, comp), 179 * first_max_element(first, last, comp) ); 180 * 181 * first_min_last_max_element(first, last) 182 * Effect: std::make_pair( first_min_element(first, last), 183 * last_max_element(first, last) ); 184 * 185 * first_min_last_max_element(first, last, comp) 186 * Effect: std::make_pair( first_min_element(first, last, comp), 187 * last_max_element(first, last, comp) ); 188 * 189 * last_min_first_max_element(first, last) 190 * Effect: std::make_pair( last_min_element(first, last), 191 * first_max_element(first, last) ); 192 * 193 * last_min_first_max_element(first, last, comp) 194 * Effect: std::make_pair( last_min_element(first, last, comp), 195 * first_max_element(first, last, comp) ); 196 * 197 * last_min_last_max_element(first, last) 198 * Effect: std::make_pair( last_min_element(first, last), 199 * last_max_element(first, last) ); 200 * 201 * last_min_last_max_element(first, last, comp) 202 * Effect: std::make_pair( last_min_element(first, last, comp), 203 * last_max_element(first, last, comp) ); 204 */ 205 206 namespace boost { 207 208 // Min_element and max_element variants 209 210 namespace detail { // common base for the overloads 211 212 template <typename ForwardIter, class BinaryPredicate> 213 ForwardIter 214 basic_first_min_element(ForwardIter first, ForwardIter last, 215 BinaryPredicate comp) 216 { 217 if (first == last) return last; 218 ForwardIter min_result = first; 219 while (++first != last) 220 if (comp(first, min_result)) 221 min_result = first; 222 return min_result; 223 } 224 225 template <typename ForwardIter, class BinaryPredicate> 226 ForwardIter 227 basic_last_min_element(ForwardIter first, ForwardIter last, 228 BinaryPredicate comp) 229 { 230 if (first == last) return last; 231 ForwardIter min_result = first; 232 while (++first != last) 233 if (!comp(min_result, first)) 234 min_result = first; 235 return min_result; 236 } 237 238 template <typename ForwardIter, class BinaryPredicate> 239 ForwardIter 240 basic_first_max_element(ForwardIter first, ForwardIter last, 241 BinaryPredicate comp) 242 { 243 if (first == last) return last; 244 ForwardIter max_result = first; 245 while (++first != last) 246 if (comp(max_result, first)) 247 max_result = first; 248 return max_result; 249 } 250 251 template <typename ForwardIter, class BinaryPredicate> 252 ForwardIter 253 basic_last_max_element(ForwardIter first, ForwardIter last, 254 BinaryPredicate comp) 255 { 256 if (first == last) return last; 257 ForwardIter max_result = first; 258 while (++first != last) 259 if (!comp(first, max_result)) 260 max_result = first; 261 return max_result; 262 } 263 264 } // namespace detail 265 266 template <typename ForwardIter> 267 ForwardIter first_min_element(ForwardIter first,ForwardIter last)268 first_min_element(ForwardIter first, ForwardIter last) 269 { 270 return detail::basic_first_min_element(first, last, 271 detail::less_over_iter<ForwardIter>() ); 272 } 273 274 template <typename ForwardIter, class BinaryPredicate> 275 ForwardIter 276 first_min_element(ForwardIter first, ForwardIter last, BinaryPredicate comp) 277 { 278 return detail::basic_first_min_element(first, last, 279 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); 280 } 281 282 template <typename ForwardIter> 283 ForwardIter last_min_element(ForwardIter first,ForwardIter last)284 last_min_element(ForwardIter first, ForwardIter last) 285 { 286 return detail::basic_last_min_element(first, last, 287 detail::less_over_iter<ForwardIter>() ); 288 } 289 290 template <typename ForwardIter, class BinaryPredicate> 291 ForwardIter 292 last_min_element(ForwardIter first, ForwardIter last, BinaryPredicate comp) 293 { 294 return detail::basic_last_min_element(first, last, 295 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); 296 } 297 298 template <typename ForwardIter> 299 ForwardIter first_max_element(ForwardIter first,ForwardIter last)300 first_max_element(ForwardIter first, ForwardIter last) 301 { 302 return detail::basic_first_max_element(first, last, 303 detail::less_over_iter<ForwardIter>() ); 304 } 305 306 template <typename ForwardIter, class BinaryPredicate> 307 ForwardIter 308 first_max_element(ForwardIter first, ForwardIter last, BinaryPredicate comp) 309 { 310 return detail::basic_first_max_element(first, last, 311 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); 312 } 313 314 template <typename ForwardIter> 315 ForwardIter last_max_element(ForwardIter first,ForwardIter last)316 last_max_element(ForwardIter first, ForwardIter last) 317 { 318 return detail::basic_last_max_element(first, last, 319 detail::less_over_iter<ForwardIter>() ); 320 } 321 322 template <typename ForwardIter, class BinaryPredicate> 323 ForwardIter 324 last_max_element(ForwardIter first, ForwardIter last, BinaryPredicate comp) 325 { 326 return detail::basic_last_max_element(first, last, 327 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); 328 } 329 330 331 // Minmax_element variants -- comments removed 332 333 namespace detail { 334 335 template <typename ForwardIter, class BinaryPredicate> 336 std::pair<ForwardIter,ForwardIter> basic_first_min_last_max_element(ForwardIter first,ForwardIter last,BinaryPredicate comp)337 basic_first_min_last_max_element(ForwardIter first, ForwardIter last, 338 BinaryPredicate comp) 339 { 340 if (first == last) 341 return std::make_pair(last,last); 342 343 ForwardIter min_result = first; 344 ForwardIter max_result = first; 345 346 ForwardIter second = ++first; 347 if (second == last) 348 return std::make_pair(min_result, max_result); 349 350 if (comp(second, min_result)) 351 min_result = second; 352 else 353 max_result = second; 354 355 first = ++second; if (first != last) ++second; 356 while (second != last) { 357 if (!comp(second, first)) { 358 if (comp(first, min_result)) 359 min_result = first; 360 if (!comp(second, max_result)) 361 max_result = second; 362 } else { 363 if (comp(second, min_result)) 364 min_result = second; 365 if (!comp(first, max_result)) 366 max_result = first; 367 } 368 first = ++second; if (first != last) ++second; 369 } 370 371 if (first != last) { 372 if (comp(first, min_result)) 373 min_result = first; 374 else if (!comp(first, max_result)) 375 max_result = first; 376 } 377 378 return std::make_pair(min_result, max_result); 379 } 380 381 template <typename ForwardIter, class BinaryPredicate> 382 std::pair<ForwardIter,ForwardIter> basic_last_min_first_max_element(ForwardIter first,ForwardIter last,BinaryPredicate comp)383 basic_last_min_first_max_element(ForwardIter first, ForwardIter last, 384 BinaryPredicate comp) 385 { 386 if (first == last) return std::make_pair(last,last); 387 388 ForwardIter min_result = first; 389 ForwardIter max_result = first; 390 391 ForwardIter second = ++first; 392 if (second == last) 393 return std::make_pair(min_result, max_result); 394 395 if (comp(max_result, second)) 396 max_result = second; 397 else 398 min_result = second; 399 400 first = ++second; if (first != last) ++second; 401 while (second != last) { 402 if (comp(first, second)) { 403 if (!comp(min_result, first)) 404 min_result = first; 405 if (comp(max_result, second)) 406 max_result = second; 407 } else { 408 if (!comp(min_result, second)) 409 min_result = second; 410 if (comp(max_result, first)) 411 max_result = first; 412 } 413 first = ++second; if (first != last) ++second; 414 } 415 416 if (first != last) { 417 if (!comp(min_result, first)) 418 min_result = first; 419 else if (comp(max_result, first)) 420 max_result = first; 421 } 422 423 return std::make_pair(min_result, max_result); 424 } 425 426 template <typename ForwardIter, class BinaryPredicate> 427 std::pair<ForwardIter,ForwardIter> basic_last_min_last_max_element(ForwardIter first,ForwardIter last,BinaryPredicate comp)428 basic_last_min_last_max_element(ForwardIter first, ForwardIter last, 429 BinaryPredicate comp) 430 { 431 if (first == last) return std::make_pair(last,last); 432 433 ForwardIter min_result = first; 434 ForwardIter max_result = first; 435 436 ForwardIter second = first; ++second; 437 if (second == last) 438 return std::make_pair(min_result,max_result); 439 440 ForwardIter potential_max_result = last; 441 if (comp(first, second)) 442 max_result = second; 443 else { 444 min_result = second; 445 potential_max_result = second; 446 } 447 448 first = ++second; if (first != last) ++second; 449 while (second != last) { 450 if (comp(first, second)) { 451 if (!comp(min_result, first)) 452 min_result = first; 453 if (!comp(second, max_result)) { 454 max_result = second; 455 potential_max_result = last; 456 } 457 } else { 458 if (!comp(min_result, second)) 459 min_result = second; 460 if (!comp(first, max_result)) { 461 max_result = first; 462 potential_max_result = second; 463 } 464 } 465 first = ++second; 466 if (first != last) ++second; 467 } 468 469 if (first != last) { 470 if (!comp(min_result, first)) 471 min_result = first; 472 if (!comp(first, max_result)) { 473 max_result = first; 474 potential_max_result = last; 475 } 476 } 477 478 if (potential_max_result != last 479 && !comp(potential_max_result, max_result)) 480 max_result = potential_max_result; 481 482 return std::make_pair(min_result,max_result); 483 } 484 485 } // namespace detail 486 487 template <typename ForwardIter> 488 inline std::pair<ForwardIter,ForwardIter> first_min_first_max_element(ForwardIter first,ForwardIter last)489 first_min_first_max_element(ForwardIter first, ForwardIter last) 490 { 491 return minmax_element(first, last); 492 } 493 494 template <typename ForwardIter, class BinaryPredicate> 495 inline std::pair<ForwardIter,ForwardIter> first_min_first_max_element(ForwardIter first,ForwardIter last,BinaryPredicate comp)496 first_min_first_max_element(ForwardIter first, ForwardIter last, 497 BinaryPredicate comp) 498 { 499 return minmax_element(first, last, comp); 500 } 501 502 template <typename ForwardIter> 503 std::pair<ForwardIter,ForwardIter> first_min_last_max_element(ForwardIter first,ForwardIter last)504 first_min_last_max_element(ForwardIter first, ForwardIter last) 505 { 506 return detail::basic_first_min_last_max_element(first, last, 507 detail::less_over_iter<ForwardIter>() ); 508 } 509 510 template <typename ForwardIter, class BinaryPredicate> 511 inline std::pair<ForwardIter,ForwardIter> first_min_last_max_element(ForwardIter first,ForwardIter last,BinaryPredicate comp)512 first_min_last_max_element(ForwardIter first, ForwardIter last, 513 BinaryPredicate comp) 514 { 515 return detail::basic_first_min_last_max_element(first, last, 516 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); 517 } 518 519 template <typename ForwardIter> 520 std::pair<ForwardIter,ForwardIter> last_min_first_max_element(ForwardIter first,ForwardIter last)521 last_min_first_max_element(ForwardIter first, ForwardIter last) 522 { 523 return detail::basic_last_min_first_max_element(first, last, 524 detail::less_over_iter<ForwardIter>() ); 525 } 526 527 template <typename ForwardIter, class BinaryPredicate> 528 inline std::pair<ForwardIter,ForwardIter> last_min_first_max_element(ForwardIter first,ForwardIter last,BinaryPredicate comp)529 last_min_first_max_element(ForwardIter first, ForwardIter last, 530 BinaryPredicate comp) 531 { 532 return detail::basic_last_min_first_max_element(first, last, 533 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); 534 } 535 536 template <typename ForwardIter> 537 std::pair<ForwardIter,ForwardIter> last_min_last_max_element(ForwardIter first,ForwardIter last)538 last_min_last_max_element(ForwardIter first, ForwardIter last) 539 { 540 return detail::basic_last_min_last_max_element(first, last, 541 detail::less_over_iter<ForwardIter>() ); 542 } 543 544 template <typename ForwardIter, class BinaryPredicate> 545 inline std::pair<ForwardIter,ForwardIter> last_min_last_max_element(ForwardIter first,ForwardIter last,BinaryPredicate comp)546 last_min_last_max_element(ForwardIter first, ForwardIter last, 547 BinaryPredicate comp) 548 { 549 return detail::basic_last_min_last_max_element(first, last, 550 detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); 551 } 552 553 } // namespace boost 554 555 #endif // BOOST_ALGORITHM_MINMAX_ELEMENT_HPP 556