1// Copyright (C) 2006, 2007, 2009 Free Software Foundation, Inc. 2// 3// This file is part of the GNU ISO C++ Library. This library is free 4// software; you can redistribute it and/or modify it under the 5// terms of the GNU General Public License as published by the 6// Free Software Foundation; either version 3, or (at your option) 7// any later version. 8 9// This library is distributed in the hope that it will be useful, 10// but WITHOUT ANY WARRANTY; without even the implied warranty of 11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12// GNU General Public License for more details. 13 14// You should have received a copy of the GNU General Public License along 15// with this library; see the file COPYING3. If not see 16// <http://www.gnu.org/licenses/>. 17 18// 25.3.2 [lib.alg.nth.element] 19 20// { dg-options "-DMAX_SIZE=256" { target simulator } } 21 22#ifndef MAX_SIZE 23#define MAX_SIZE (1 << 10) 24#endif 25 26#include <vector> 27#include <algorithm> 28#include <testsuite_hooks.h> 29 30void 31test_set(std::vector<unsigned>& v, unsigned size) 32{ 33 v.clear(); 34 35 for (unsigned i = 0; i < size; i += 4) 36 { 37 v.push_back(i / 2); 38 v.push_back((size - 2) - (i / 2)); 39 } 40 for (unsigned i = 1; i < size; i += 2) 41 v.push_back(i); 42} 43 44void 45do_test01(unsigned size) 46{ 47 bool test __attribute__((unused)) = true; 48 49 std::vector<unsigned> v, s; 50 51 for (unsigned j = 0; j < size; ++j) 52 { 53 test_set(v, size); 54 s = v; 55 std::sort(s.begin(), s.end()); 56 57 std::nth_element(v.begin(), v.begin() + j, v.end()); 58 59 VERIFY( v[j] == s[j] ); 60 61 for (unsigned i = 0; i < j; ++i) 62 VERIFY( !(v[j] < v[i]) ); 63 64 for (unsigned i = j; i < v.size(); ++i) 65 VERIFY( !(v[i] < v[j]) ); 66 } 67} 68 69void 70test01() 71{ 72 for (unsigned size = 4; size <= MAX_SIZE; size <<= 1) 73 do_test01(size); 74} 75 76int main() 77{ 78 test01(); 79 return 0; 80} 81