1bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant//===----------------------------------------------------------------------===// 2bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// 3f5256e16dfc425c1d466f6308d4026d529ce9e0bHoward Hinnant// The LLVM Compiler Infrastructure 4bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// 5b64f8b07c104c6cc986570ac8ee0ed16a9f23976Howard Hinnant// This file is dual licensed under the MIT and the University of Illinois Open 6b64f8b07c104c6cc986570ac8ee0ed16a9f23976Howard Hinnant// Source Licenses. See LICENSE.TXT for details. 7bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// 8bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant//===----------------------------------------------------------------------===// 9bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 10bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// <algorithm> 11bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 12eb564e76cc3904d811c981a50ecce0659f444cc9Howard Hinnant// template<class T, class Compare> 1398e5d974006989c505d7b2ec7b9e4b20b0f01e26Howard Hinnant// pair<T, T> 14bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// minmax(initializer_list<T> t, Compare comp); 155cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert// 165cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert// Complexity: At most (3/2) * t.size() applications of the corresponding predicate. 17bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 18bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant#include <algorithm> 1998e5d974006989c505d7b2ec7b9e4b20b0f01e26Howard Hinnant#include <functional> 20bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant#include <cassert> 21bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 225cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert#include "counting_predicates.hpp" 235cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert 245cb52824fc2a0caf233311e91d9a2a53368f04adDan Albertbool all_equal(int a, int b) { return false; } // everything is equal 255cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert 265cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 275cb52824fc2a0caf233311e91d9a2a53368f04adDan Albertvoid test_all_equal(std::initializer_list<int> il) 285cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert{ 295cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert binary_counting_predicate<bool(*)(int, int), int, int> pred (all_equal); 305cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert std::pair<int, int> p = std::minmax(il, std::ref(pred)); 315cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert const int *ptr = il.end(); 325cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert assert(p.first == *il.begin()); 335cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert assert(p.second == *--ptr); 345cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert assert(pred.count() <= ((3 * il.size()) / 2)); 355cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert} 365cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert#endif 375cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert 38bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnantint main() 39bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant{ 40e3e3291f3ab4af96b0403cf6e255c833143ae3f1Howard Hinnant#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 4198e5d974006989c505d7b2ec7b9e4b20b0f01e26Howard Hinnant assert((std::minmax({1, 2, 3}, std::greater<int>()) == std::pair<int, int>(3, 1))); 4298e5d974006989c505d7b2ec7b9e4b20b0f01e26Howard Hinnant assert((std::minmax({1, 3, 2}, std::greater<int>()) == std::pair<int, int>(3, 1))); 4398e5d974006989c505d7b2ec7b9e4b20b0f01e26Howard Hinnant assert((std::minmax({2, 1, 3}, std::greater<int>()) == std::pair<int, int>(3, 1))); 4498e5d974006989c505d7b2ec7b9e4b20b0f01e26Howard Hinnant assert((std::minmax({2, 3, 1}, std::greater<int>()) == std::pair<int, int>(3, 1))); 4598e5d974006989c505d7b2ec7b9e4b20b0f01e26Howard Hinnant assert((std::minmax({3, 1, 2}, std::greater<int>()) == std::pair<int, int>(3, 1))); 4698e5d974006989c505d7b2ec7b9e4b20b0f01e26Howard Hinnant assert((std::minmax({3, 2, 1}, std::greater<int>()) == std::pair<int, int>(3, 1))); 475cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert assert((std::minmax({1, 2, 3}, all_equal ) == std::pair<int, int>(1, 3))); 485cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert 495cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert binary_counting_predicate<std::greater<int>, int, int> pred ((std::greater<int>())); 505cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert assert((std::minmax({1, 2, 2, 3, 3, 3, 5, 5, 5, 5, 5, 3}, std::ref(pred)) == std::pair<int, int>(5, 1))); 515cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert assert(pred.count() <= 18); // size == 12 525cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert 535cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert test_all_equal({0}); 545cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert test_all_equal({0,1}); 555cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert test_all_equal({0,1,2}); 565cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert test_all_equal({0,1,2,3}); 575cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert test_all_equal({0,1,2,3,4}); 585cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert test_all_equal({0,1,2,3,4,5}); 595cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert test_all_equal({0,1,2,3,4,5,6}); 605cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert test_all_equal({0,1,2,3,4,5,6,7}); 615cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert test_all_equal({0,1,2,3,4,5,6,7,8}); 625cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert test_all_equal({0,1,2,3,4,5,6,7,8,9}); 635cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert test_all_equal({0,1,2,3,4,5,6,7,8,9,10}); 645cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert test_all_equal({0,1,2,3,4,5,6,7,8,9,10,11}); 655cb52824fc2a0caf233311e91d9a2a53368f04adDan Albert 669d9463a3555aa559884809b8a7fc842a3968193eMarshall Clow#if _LIBCPP_STD_VER > 11 679d9463a3555aa559884809b8a7fc842a3968193eMarshall Clow { 689d9463a3555aa559884809b8a7fc842a3968193eMarshall Clow static_assert((std::minmax({1, 2, 3}, std::greater<int>()) == std::pair<int, int>(3, 1)), ""); 699d9463a3555aa559884809b8a7fc842a3968193eMarshall Clow static_assert((std::minmax({1, 3, 2}, std::greater<int>()) == std::pair<int, int>(3, 1)), ""); 709d9463a3555aa559884809b8a7fc842a3968193eMarshall Clow static_assert((std::minmax({2, 1, 3}, std::greater<int>()) == std::pair<int, int>(3, 1)), ""); 719d9463a3555aa559884809b8a7fc842a3968193eMarshall Clow static_assert((std::minmax({2, 3, 1}, std::greater<int>()) == std::pair<int, int>(3, 1)), ""); 729d9463a3555aa559884809b8a7fc842a3968193eMarshall Clow static_assert((std::minmax({3, 1, 2}, std::greater<int>()) == std::pair<int, int>(3, 1)), ""); 739d9463a3555aa559884809b8a7fc842a3968193eMarshall Clow static_assert((std::minmax({3, 2, 1}, std::greater<int>()) == std::pair<int, int>(3, 1)), ""); 749d9463a3555aa559884809b8a7fc842a3968193eMarshall Clow } 759d9463a3555aa559884809b8a7fc842a3968193eMarshall Clow#endif 76e3e3291f3ab4af96b0403cf6e255c833143ae3f1Howard Hinnant#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 77bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant} 78