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, Predicate<auto, Iter::value_type> Pred>
13//   requires ShuffleIterator<Iter>
14//         && CopyConstructible<Pred>
15//   Iter
16//   partition(Iter first, Iter last, Pred pred);
17
18#include <algorithm>
19#include <cassert>
20#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
21#include <memory>
22#endif
23
24#include "test_iterators.h"
25
26struct is_odd
27{
28    bool operator()(const int& i) const {return i & 1;}
29};
30
31template <class Iter>
32void
33test()
34{
35    // check mixed
36    int ia[] = {1, 2, 3, 4, 5, 6, 7, 8 ,9};
37    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
38    Iter r = std::partition(Iter(ia), Iter(ia + sa), is_odd());
39    assert(base(r) == ia + 5);
40    for (int* i = ia; i < base(r); ++i)
41        assert(is_odd()(*i));
42    for (int* i = base(r); i < ia+sa; ++i)
43        assert(!is_odd()(*i));
44    // check empty
45    r = std::partition(Iter(ia), Iter(ia), is_odd());
46    assert(base(r) == ia);
47    // check all false
48    for (unsigned i = 0; i < sa; ++i)
49        ia[i] = 2*i;
50    r = std::partition(Iter(ia), Iter(ia+sa), is_odd());
51    assert(base(r) == ia);
52    // check all true
53    for (unsigned i = 0; i < sa; ++i)
54        ia[i] = 2*i+1;
55    r = std::partition(Iter(ia), Iter(ia+sa), is_odd());
56    assert(base(r) == ia+sa);
57    // check all true but last
58    for (unsigned i = 0; i < sa; ++i)
59        ia[i] = 2*i+1;
60    ia[sa-1] = 10;
61    r = std::partition(Iter(ia), Iter(ia+sa), is_odd());
62    assert(base(r) == ia+sa-1);
63    for (int* i = ia; i < base(r); ++i)
64        assert(is_odd()(*i));
65    for (int* i = base(r); i < ia+sa; ++i)
66        assert(!is_odd()(*i));
67    // check all true but first
68    for (unsigned i = 0; i < sa; ++i)
69        ia[i] = 2*i+1;
70    ia[0] = 10;
71    r = std::partition(Iter(ia), Iter(ia+sa), is_odd());
72    assert(base(r) == ia+sa-1);
73    for (int* i = ia; i < base(r); ++i)
74        assert(is_odd()(*i));
75    for (int* i = base(r); i < ia+sa; ++i)
76        assert(!is_odd()(*i));
77    // check all false but last
78    for (unsigned i = 0; i < sa; ++i)
79        ia[i] = 2*i;
80    ia[sa-1] = 11;
81    r = std::partition(Iter(ia), Iter(ia+sa), is_odd());
82    assert(base(r) == ia+1);
83    for (int* i = ia; i < base(r); ++i)
84        assert(is_odd()(*i));
85    for (int* i = base(r); i < ia+sa; ++i)
86        assert(!is_odd()(*i));
87    // check all false but first
88    for (unsigned i = 0; i < sa; ++i)
89        ia[i] = 2*i;
90    ia[0] = 11;
91    r = std::partition(Iter(ia), Iter(ia+sa), is_odd());
92    assert(base(r) == ia+1);
93    for (int* i = ia; i < base(r); ++i)
94        assert(is_odd()(*i));
95    for (int* i = base(r); i < ia+sa; ++i)
96        assert(!is_odd()(*i));
97}
98
99int main()
100{
101    test<bidirectional_iterator<int*> >();
102    test<random_access_iterator<int*> >();
103    test<int*>();
104}
105