blob: 7810dec2fe1b2fea48523cc5e4419549734e75ed [file] [log] [blame] [edit]
//===----------------------------------------------------------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file is dual licensed under the MIT and the University of Illinois Open
// Source Licenses. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
// <algorithm>
// template<BidirectionalIterator Iter, Predicate<auto, Iter::value_type> Pred>
// requires ShuffleIterator<Iter>
// && CopyConstructible<Pred>
// Iter
// stable_partition(Iter first, Iter last, Pred pred);
#include <algorithm>
#include <cassert>
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
#include <memory>
#endif
#include "test_iterators.h"
struct is_odd
{
bool operator()(const int& i) const {return i & 1;}
};
struct odd_first
{
bool operator()(const std::pair<int,int>& p) const
{return p.first & 1;}
};
template <class Iter>
void
test()
{
{ // check mixed
typedef std::pair<int,int> P;
P array[] =
{
P(0, 1),
P(0, 2),
P(1, 1),
P(1, 2),
P(2, 1),
P(2, 2),
P(3, 1),
P(3, 2),
P(4, 1),
P(4, 2)
};
const unsigned size = sizeof(array)/sizeof(array[0]);
Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());
assert(base(r) == array + 4);
assert(array[0] == P(1, 1));
assert(array[1] == P(1, 2));
assert(array[2] == P(3, 1));
assert(array[3] == P(3, 2));
assert(array[4] == P(0, 1));
assert(array[5] == P(0, 2));
assert(array[6] == P(2, 1));
assert(array[7] == P(2, 2));
assert(array[8] == P(4, 1));
assert(array[9] == P(4, 2));
}
{
typedef std::pair<int,int> P;
P array[] =
{
P(0, 1),
P(0, 2),
P(1, 1),
P(1, 2),
P(2, 1),
P(2, 2),
P(3, 1),
P(3, 2),
P(4, 1),
P(4, 2)
};
const unsigned size = sizeof(array)/sizeof(array[0]);
Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());
assert(base(r) == array + 4);
assert(array[0] == P(1, 1));
assert(array[1] == P(1, 2));
assert(array[2] == P(3, 1));
assert(array[3] == P(3, 2));
assert(array[4] == P(0, 1));
assert(array[5] == P(0, 2));
assert(array[6] == P(2, 1));
assert(array[7] == P(2, 2));
assert(array[8] == P(4, 1));
assert(array[9] == P(4, 2));
// check empty
r = std::stable_partition(Iter(array), Iter(array), odd_first());
assert(base(r) == array);
// check one true
r = std::stable_partition(Iter(array), Iter(array+1), odd_first());
assert(base(r) == array+1);
assert(array[0] == P(1, 1));
// check one false
r = std::stable_partition(Iter(array+4), Iter(array+5), odd_first());
assert(base(r) == array+4);
assert(array[4] == P(0, 1));
}
{ // check all false
typedef std::pair<int,int> P;
P array[] =
{
P(0, 1),
P(0, 2),
P(2, 1),
P(2, 2),
P(4, 1),
P(4, 2),
P(6, 1),
P(6, 2),
P(8, 1),
P(8, 2)
};
const unsigned size = sizeof(array)/sizeof(array[0]);
Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());
assert(base(r) == array);
assert(array[0] == P(0, 1));
assert(array[1] == P(0, 2));
assert(array[2] == P(2, 1));
assert(array[3] == P(2, 2));
assert(array[4] == P(4, 1));
assert(array[5] == P(4, 2));
assert(array[6] == P(6, 1));
assert(array[7] == P(6, 2));
assert(array[8] == P(8, 1));
assert(array[9] == P(8, 2));
}
{ // check all true
typedef std::pair<int,int> P;
P array[] =
{
P(1, 1),
P(1, 2),
P(3, 1),
P(3, 2),
P(5, 1),
P(5, 2),
P(7, 1),
P(7, 2),
P(9, 1),
P(9, 2)
};
const unsigned size = sizeof(array)/sizeof(array[0]);
Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());
assert(base(r) == array + size);
assert(array[0] == P(1, 1));
assert(array[1] == P(1, 2));
assert(array[2] == P(3, 1));
assert(array[3] == P(3, 2));
assert(array[4] == P(5, 1));
assert(array[5] == P(5, 2));
assert(array[6] == P(7, 1));
assert(array[7] == P(7, 2));
assert(array[8] == P(9, 1));
assert(array[9] == P(9, 2));
}
{ // check all false but first true
typedef std::pair<int,int> P;
P array[] =
{
P(1, 1),
P(0, 2),
P(2, 1),
P(2, 2),
P(4, 1),
P(4, 2),
P(6, 1),
P(6, 2),
P(8, 1),
P(8, 2)
};
const unsigned size = sizeof(array)/sizeof(array[0]);
Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());
assert(base(r) == array + 1);
assert(array[0] == P(1, 1));
assert(array[1] == P(0, 2));
assert(array[2] == P(2, 1));
assert(array[3] == P(2, 2));
assert(array[4] == P(4, 1));
assert(array[5] == P(4, 2));
assert(array[6] == P(6, 1));
assert(array[7] == P(6, 2));
assert(array[8] == P(8, 1));
assert(array[9] == P(8, 2));
}
{ // check all false but last true
typedef std::pair<int,int> P;
P array[] =
{
P(0, 1),
P(0, 2),
P(2, 1),
P(2, 2),
P(4, 1),
P(4, 2),
P(6, 1),
P(6, 2),
P(8, 1),
P(1, 2)
};
const unsigned size = sizeof(array)/sizeof(array[0]);
Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());
assert(base(r) == array + 1);
assert(array[0] == P(1, 2));
assert(array[1] == P(0, 1));
assert(array[2] == P(0, 2));
assert(array[3] == P(2, 1));
assert(array[4] == P(2, 2));
assert(array[5] == P(4, 1));
assert(array[6] == P(4, 2));
assert(array[7] == P(6, 1));
assert(array[8] == P(6, 2));
assert(array[9] == P(8, 1));
}
{ // check all true but first false
typedef std::pair<int,int> P;
P array[] =
{
P(0, 1),
P(1, 2),
P(3, 1),
P(3, 2),
P(5, 1),
P(5, 2),
P(7, 1),
P(7, 2),
P(9, 1),
P(9, 2)
};
const unsigned size = sizeof(array)/sizeof(array[0]);
Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());
assert(base(r) == array + size-1);
assert(array[0] == P(1, 2));
assert(array[1] == P(3, 1));
assert(array[2] == P(3, 2));
assert(array[3] == P(5, 1));
assert(array[4] == P(5, 2));
assert(array[5] == P(7, 1));
assert(array[6] == P(7, 2));
assert(array[7] == P(9, 1));
assert(array[8] == P(9, 2));
assert(array[9] == P(0, 1));
}
{ // check all true but last false
typedef std::pair<int,int> P;
P array[] =
{
P(1, 1),
P(1, 2),
P(3, 1),
P(3, 2),
P(5, 1),
P(5, 2),
P(7, 1),
P(7, 2),
P(9, 1),
P(0, 2)
};
const unsigned size = sizeof(array)/sizeof(array[0]);
Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());
assert(base(r) == array + size-1);
assert(array[0] == P(1, 1));
assert(array[1] == P(1, 2));
assert(array[2] == P(3, 1));
assert(array[3] == P(3, 2));
assert(array[4] == P(5, 1));
assert(array[5] == P(5, 2));
assert(array[6] == P(7, 1));
assert(array[7] == P(7, 2));
assert(array[8] == P(9, 1));
assert(array[9] == P(0, 2));
}
}
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
struct is_null
{
template <class P>
bool operator()(const P& p) {return p == 0;}
};
template <class Iter>
void
test1()
{
const unsigned size = 5;
std::unique_ptr<int> array[size];
Iter r = std::stable_partition(Iter(array), Iter(array+size), is_null());
}
#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
int main()
{
test<bidirectional_iterator<std::pair<int,int>*> >();
test<random_access_iterator<std::pair<int,int>*> >();
test<std::pair<int,int>*>();
#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
test1<bidirectional_iterator<std::unique_ptr<int>*> >();
#endif
}