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
26int factorial(int x)
27{
28    int r = 1;
29    for (; x; --x)
30        r *= x;
31    return r;
32}
33
34template <class Iter>
35void
36test()
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
63int main()
64{
65    test<bidirectional_iterator<int*> >();
66    test<random_access_iterator<int*> >();
67    test<int*>();
68}
69