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 
26 struct is_odd
27 {
28     bool operator()(const int& i) const {return i & 1;}
29 };
30 
31 template <class Iter>
32 void
33 test()
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 
99 int main()
100 {
101     test<bidirectional_iterator<int*> >();
102     test<random_access_iterator<int*> >();
103     test<int*>();
104 }
105