Add tests for stability to list::sort and forward_list::sort. Thanks to Jonathan Wakely for the notice
git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@358541 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/test/std/containers/sequences/forwardlist/forwardlist.ops/sort.pass.cpp b/test/std/containers/sequences/forwardlist/forwardlist.ops/sort.pass.cpp
index c76fe03..50dcdd4 100644
--- a/test/std/containers/sequences/forwardlist/forwardlist.ops/sort.pass.cpp
+++ b/test/std/containers/sequences/forwardlist/forwardlist.ops/sort.pass.cpp
@@ -38,6 +38,46 @@
assert(*j == i);
}
+struct Payload
+{
+ int val;
+ int side;
+ Payload(int v) : val(v), side(0) {}
+ Payload(int v, int s) : val(v), side(s) {}
+ bool operator< (const Payload &rhs) const { return val < rhs.val;}
+// bool operator==(const Payload &rhs) const { return val == rhs.val;}
+};
+
+void test_stable(int N)
+{
+ typedef Payload T;
+ typedef std::forward_list<T> C;
+ typedef std::vector<T> V;
+ V v;
+ for (int i = 0; i < N; ++i)
+ v.push_back(Payload(i/2));
+ std::shuffle(v.begin(), v.end(), randomness);
+ for (int i = 0; i < N; ++i)
+ v[i].side = i;
+
+ C c(v.begin(), v.end());
+ c.sort();
+ assert(distance(c.begin(), c.end()) == N);
+
+// Are we sorted?
+ typename C::const_iterator j = c.begin();
+ for (int i = 0; i < N; ++i, ++j)
+ assert(j->val == i/2);
+
+// Are we stable?
+ for (C::const_iterator it = c.begin(); it != c.end(); ++it)
+ {
+ C::const_iterator next = std::next(it);
+ if (next != c.end() && it->val == next->val)
+ assert(it->side < next->side);
+ }
+}
+
int main(int, char**)
{
for (int i = 0; i < 40; ++i)
@@ -47,5 +87,8 @@
test<std::forward_list<int, min_allocator<int>> >(i);
#endif
+ for (int i = 0; i < 40; ++i)
+ test_stable(i);
+
return 0;
}
diff --git a/test/std/containers/sequences/forwardlist/forwardlist.ops/sort_pred.pass.cpp b/test/std/containers/sequences/forwardlist/forwardlist.ops/sort_pred.pass.cpp
index 971508a..0e67693 100644
--- a/test/std/containers/sequences/forwardlist/forwardlist.ops/sort_pred.pass.cpp
+++ b/test/std/containers/sequences/forwardlist/forwardlist.ops/sort_pred.pass.cpp
@@ -17,11 +17,53 @@
#include <functional>
#include <random>
#include <cassert>
+#include <iostream>
#include "min_allocator.h"
std::mt19937 randomness;
+struct Payload
+{
+ int val;
+ int side;
+ Payload(int v) : val(v), side(0) {}
+ Payload(int v, int s) : val(v), side(s) {}
+ bool operator< (const Payload &rhs) const { return val < rhs.val;}
+};
+
+bool greater(const Payload &lhs, const Payload &rhs) { return lhs.val > rhs.val; }
+
+void test_stable(int N)
+{
+ typedef Payload T;
+ typedef std::forward_list<T> C;
+ typedef std::vector<T> V;
+ V v;
+ for (int i = 0; i < N; ++i)
+ v.push_back(Payload(i/2));
+ std::shuffle(v.begin(), v.end(), randomness);
+ for (int i = 0; i < N; ++i)
+ v[i].side = i;
+
+ C c(v.begin(), v.end());
+ c.sort(greater);
+ assert(distance(c.begin(), c.end()) == N);
+
+// Are we sorted?
+ typename C::const_iterator j = c.begin();
+ for (int i = 0; i < N; ++i, ++j)
+ assert(j->val == (N-1-i)/2);
+
+// Are we stable?
+ for (C::const_iterator it = c.begin(); it != c.end(); ++it)
+ {
+ C::const_iterator next = std::next(it);
+ if (next != c.end() && it->val == next->val)
+ assert(it->side < next->side);
+ }
+}
+
template <class C>
void test(int N)
{
@@ -48,5 +90,8 @@
test<std::forward_list<int, min_allocator<int>> >(i);
#endif
+ for (int i = 0; i < 40; ++i)
+ test_stable(i);
+
return 0;
}
diff --git a/test/std/containers/sequences/list/list.ops/sort.pass.cpp b/test/std/containers/sequences/list/list.ops/sort.pass.cpp
index cd229c2..8162872 100644
--- a/test/std/containers/sequences/list/list.ops/sort.pass.cpp
+++ b/test/std/containers/sequences/list/list.ops/sort.pass.cpp
@@ -11,10 +11,55 @@
// void sort();
#include <list>
+#include <random>
+#include <vector>
#include <cassert>
#include "min_allocator.h"
+std::mt19937 randomness;
+
+struct Payload
+{
+ int val;
+ int side;
+ Payload(int v) : val(v), side(0) {}
+ Payload(int v, int s) : val(v), side(s) {}
+ bool operator< (const Payload &rhs) const { return val < rhs.val;}
+// bool operator==(const Payload &rhs) const { return val == rhs.val;}
+};
+
+void test_stable(int N)
+{
+ typedef Payload T;
+ typedef std::list<T> C;
+ typedef std::vector<T> V;
+ V v;
+ for (int i = 0; i < N; ++i)
+ v.push_back(Payload(i/2));
+ std::shuffle(v.begin(), v.end(), randomness);
+ for (int i = 0; i < N; ++i)
+ v[i].side = i;
+
+ C c(v.begin(), v.end());
+ c.sort();
+ assert(distance(c.begin(), c.end()) == N);
+
+// Are we sorted?
+ typename C::const_iterator j = c.begin();
+ for (int i = 0; i < N; ++i, ++j)
+ assert(j->val == i/2);
+
+// Are we stable?
+ for (C::const_iterator it = c.begin(); it != c.end(); ++it)
+ {
+ C::const_iterator next = std::next(it);
+ if (next != c.end() && it->val == next->val)
+ assert(it->side < next->side);
+ }
+}
+
+
int main(int, char**)
{
{
@@ -34,5 +79,8 @@
}
#endif
+ for (int i = 0; i < 40; ++i)
+ test_stable(i);
+
return 0;
}
diff --git a/test/std/containers/sequences/list/list.ops/sort_comp.pass.cpp b/test/std/containers/sequences/list/list.ops/sort_comp.pass.cpp
index a87e32a..2f8b08b 100644
--- a/test/std/containers/sequences/list/list.ops/sort_comp.pass.cpp
+++ b/test/std/containers/sequences/list/list.ops/sort_comp.pass.cpp
@@ -13,10 +13,13 @@
#include <list>
#include <functional>
#include <algorithm> // for is_permutation
+#include <random>
+#include <vector>
#include <cassert>
#include "min_allocator.h"
+std::mt19937 randomness;
#ifndef TEST_HAS_NO_EXCEPTIONS
template <typename T>
@@ -35,6 +38,48 @@
#endif
+struct Payload
+{
+ int val;
+ int side;
+ Payload(int v) : val(v), side(0) {}
+ Payload(int v, int s) : val(v), side(s) {}
+ bool operator< (const Payload &rhs) const { return val < rhs.val;}
+};
+
+bool greater(const Payload &lhs, const Payload &rhs) { return lhs.val > rhs.val; }
+
+void test_stable(int N)
+{
+ typedef Payload T;
+ typedef std::list<T> C;
+ typedef std::vector<T> V;
+ V v;
+ for (int i = 0; i < N; ++i)
+ v.push_back(Payload(i/2));
+ std::shuffle(v.begin(), v.end(), randomness);
+ for (int i = 0; i < N; ++i)
+ v[i].side = i;
+
+ C c(v.begin(), v.end());
+ c.sort(greater);
+ assert(distance(c.begin(), c.end()) == N);
+
+// Are we sorted?
+ typename C::const_iterator j = c.begin();
+ for (int i = 0; i < N; ++i, ++j)
+ assert(j->val == (N-1-i)/2);
+
+// Are we stable?
+ for (C::const_iterator it = c.begin(); it != c.end(); ++it)
+ {
+ C::const_iterator next = std::next(it);
+ if (next != c.end() && it->val == next->val)
+ assert(it->side < next->side);
+ }
+}
+
+
int main(int, char**)
{
{
@@ -76,5 +121,8 @@
}
#endif
+ for (int i = 0; i < 40; ++i)
+ test_stable(i);
+
return 0;
}
