1 //===----------------------------------------------------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is dual licensed under the MIT and the University of Illinois Open 6 // Source Licenses. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 // <algorithm> 11 12 // template<BidirectionalIterator Iter, StrictWeakOrder<auto, Iter::value_type> Compare> 13 // requires ShuffleIterator<Iter> 14 // && CopyConstructible<Compare> 15 // bool 16 // next_permutation(Iter first, Iter last, Compare comp); 17 18 #include <algorithm> 19 #include <functional> 20 #include <cassert> 21 22 #include "test_iterators.h" 23 24 #include <cstdio> 25 26 int factorial(int x) 27 { 28 int r = 1; 29 for (; x; --x) 30 r *= x; 31 return r; 32 } 33 34 template <class Iter> 35 void 36 test() 37 { 38 typedef std::greater<int> C; 39 int ia[] = {6, 5, 4, 3, 2, 1}; 40 const int sa = sizeof(ia)/sizeof(ia[0]); 41 int prev[sa]; 42 for (int e = 0; e <= sa; ++e) 43 { 44 int count = 0; 45 bool x; 46 do 47 { 48 std::copy(ia, ia+e, prev); 49 x = std::next_permutation(Iter(ia), Iter(ia+e), C()); 50 if (e > 1) 51 { 52 if (x) 53 assert(std::lexicographical_compare(prev, prev+e, ia, ia+e, C())); 54 else 55 assert(std::lexicographical_compare(ia, ia+e, prev, prev+e, C())); 56 } 57 ++count; 58 } while (x); 59 assert(count == factorial(e)); 60 } 61 } 62 63 int main() 64 { 65 test<bidirectional_iterator<int*> >(); 66 test<random_access_iterator<int*> >(); 67 test<int*>(); 68 } 69