From 83465c79385c3a19504565ac613b81334d586bda Mon Sep 17 00:00:00 2001
From: Marshall Clow <mclow.lists@gmail.com>
Date: Wed, 17 Apr 2019 00:11:00 +0000
Subject: [PATCH] Add tests for stability to list::sort and forward_list::sort.
 Thanks to Jonathan Wakely for the notice

llvm-svn: 358541
---
 .../forwardlist/forwardlist.ops/sort.pass.cpp      | 43 +++++++++++++++++++
 .../forwardlist/forwardlist.ops/sort_pred.pass.cpp | 45 ++++++++++++++++++++
 .../sequences/list/list.ops/sort.pass.cpp          | 48 ++++++++++++++++++++++
 .../sequences/list/list.ops/sort_comp.pass.cpp     | 48 ++++++++++++++++++++++
 4 files changed, 184 insertions(+)

diff --git a/libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/sort.pass.cpp b/libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/sort.pass.cpp
index c76fe03..50dcdd4 100644
--- a/libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/sort.pass.cpp
+++ b/libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/sort.pass.cpp
@@ -38,6 +38,46 @@ void test(int N)
         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 @@ int main(int, char**)
         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/libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/sort_pred.pass.cpp b/libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/sort_pred.pass.cpp
index 971508a..0e67693 100644
--- a/libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/sort_pred.pass.cpp
+++ b/libcxx/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 @@ int main(int, char**)
         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/libcxx/test/std/containers/sequences/list/list.ops/sort.pass.cpp b/libcxx/test/std/containers/sequences/list/list.ops/sort.pass.cpp
index cd229c2..8162872 100644
--- a/libcxx/test/std/containers/sequences/list/list.ops/sort.pass.cpp
+++ b/libcxx/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 @@ int main(int, char**)
     }
 #endif
 
+    for (int i = 0; i < 40; ++i)
+        test_stable(i);
+
   return 0;
 }
diff --git a/libcxx/test/std/containers/sequences/list/list.ops/sort_comp.pass.cpp b/libcxx/test/std/containers/sequences/list/list.ops/sort_comp.pass.cpp
index a87e32a..2f8b08b 100644
--- a/libcxx/test/std/containers/sequences/list/list.ops/sort_comp.pass.cpp
+++ b/libcxx/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 @@ struct throwingLess {
 #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 @@ int main(int, char**)
     }
 #endif
 
+    for (int i = 0; i < 40; ++i)
+        test_stable(i);
+
   return 0;
 }
-- 
2.7.4