More constexpr algorithms from P0202: lower_bound, upper_bound, equal_range, binary_search

llvm-svn: 322529

8 files changed, 153 insertions, 20 deletions

diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/binary_search.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/binary_search.pass.cpp
index d4d31cb3088..04c4c258be8 100644
--- a/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/binary_search.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/binary_search.pass.cpp
@@ -10,9 +10,7 @@
 // <algorithm>
 
 // template<ForwardIterator Iter, class T>
-//   requires HasLess<T, Iter::value_type>
-//         && HasLess<Iter::value_type, T>
-//   bool
+//   constexpr bool      // constexpr after C++17
 //   binary_search(Iter first, Iter last, const T& value);
 
 #include <algorithm>
@@ -20,8 +18,22 @@
 #include <cassert>
 #include <cstddef>
 
+#include "test_macros.h"
 #include "test_iterators.h"
 
+#if TEST_STD_VER > 17
+TEST_CONSTEXPR bool lt(int a, int b) { return a < b; }
+
+TEST_CONSTEXPR bool test_constexpr() {
+    int ia[] = {1, 3, 3, 6, 7};
+
+    return  std::binary_search(std::begin(ia), std::end(ia), 1)
+        &&  std::binary_search(std::begin(ia), std::end(ia), 3)
+        && !std::binary_search(std::begin(ia), std::end(ia), 9)
+        ;
+    }
+#endif
+
 template <class Iter, class T>
 void
 test(Iter first, Iter last, const T& value, bool x)
@@ -61,4 +73,8 @@ int main()
     test<bidirectional_iterator<const int*> >();
     test<random_access_iterator<const int*> >();
     test<const int*>();
+
+#if TEST_STD_VER > 17
+    static_assert(test_constexpr());
+#endif
 }
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/binary_search_comp.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/binary_search_comp.pass.cpp
index e0b148499ca..b27861022c4 100644
--- a/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/binary_search_comp.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/binary_search_comp.pass.cpp
@@ -10,9 +10,7 @@
 // <algorithm>
 
 // template<ForwardIterator Iter, class T, CopyConstructible Compare>
-//   requires Predicate<Compare, T, Iter::value_type>
-//         && Predicate<Compare, Iter::value_type, T>
-//   bool
+//   constexpr bool      // constexpr after C++17
 //   binary_search(Iter first, Iter last, const T& value, Compare comp);
 
 #include <algorithm>
@@ -21,8 +19,22 @@
 #include <cassert>
 #include <cstddef>
 
+#include "test_macros.h"
 #include "test_iterators.h"
 
+#if TEST_STD_VER > 17
+TEST_CONSTEXPR bool lt(int a, int b) { return a < b; }
+
+TEST_CONSTEXPR bool test_constexpr() {
+    int ia[] = {1, 3, 3, 6, 7};
+
+    return  std::binary_search(std::begin(ia), std::end(ia), 1, lt)
+        &&  std::binary_search(std::begin(ia), std::end(ia), 3, lt)
+        && !std::binary_search(std::begin(ia), std::end(ia), 9, lt)
+        ;
+    }
+#endif
+
 template <class Iter, class T>
 void
 test(Iter first, Iter last, const T& value, bool x)
@@ -62,4 +74,8 @@ int main()
     test<bidirectional_iterator<const int*> >();
     test<random_access_iterator<const int*> >();
     test<const int*>();
+
+#if TEST_STD_VER > 17
+    static_assert(test_constexpr());
+#endif
 }
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/equal.range/equal_range.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/equal.range/equal_range.pass.cpp
index bc968f5b2aa..02aea475c59 100644
--- a/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/equal.range/equal_range.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/equal.range/equal_range.pass.cpp
@@ -12,7 +12,7 @@
 // template<ForwardIterator Iter, class T>
 //   requires HasLess<T, Iter::value_type>
 //         && HasLess<Iter::value_type, T>
-//   pair<Iter, Iter>
+//   constexpr pair<Iter, Iter>   // constexpr after c++17
 //   equal_range(Iter first, Iter last, const T& value);
 
 #include <algorithm>
@@ -20,8 +20,22 @@
 #include <cassert>
 #include <cstddef>
 
+#include "test_macros.h"
 #include "test_iterators.h"
 
+#if TEST_STD_VER > 17
+TEST_CONSTEXPR bool lt(int a, int b) { return a < b; }
+
+TEST_CONSTEXPR bool test_constexpr() {
+    int ia[] = {1, 3, 3, 6, 7};
+
+    return (std::equal_range(std::begin(ia), std::end(ia), 1, lt) == std::pair<int *, int *>(ia+0, ia+1))
+        && (std::equal_range(std::begin(ia), std::end(ia), 3, lt) == std::pair<int *, int *>(ia+1, ia+3))
+        && (std::equal_range(std::begin(ia), std::end(ia), 9, lt) == std::pair<int *, int *>(std::end(ia), std::end(ia)))
+        ;
+    }
+#endif
+
 template <class Iter, class T>
 void
 test(Iter first, Iter last, const T& value)
@@ -67,4 +81,8 @@ int main()
     test<bidirectional_iterator<const int*> >();
     test<random_access_iterator<const int*> >();
     test<const int*>();
+
+#if TEST_STD_VER > 17
+    static_assert(test_constexpr());
+#endif
 }
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/equal.range/equal_range_comp.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/equal.range/equal_range_comp.pass.cpp
index de0bbf25613..960e2c1fa56 100644
--- a/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/equal.range/equal_range_comp.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/equal.range/equal_range_comp.pass.cpp
@@ -10,9 +10,7 @@
 // <algorithm>
 
 // template<ForwardIterator Iter, class T, CopyConstructible Compare>
-//   requires Predicate<Compare, T, Iter::value_type>
-//         && Predicate<Compare, Iter::value_type, T>
-//   pair<Iter, Iter>
+//   constexpr pair<Iter, Iter>   // constexpr after c++17
 //   equal_range(Iter first, Iter last, const T& value, Compare comp);
 
 #include <algorithm>
@@ -21,8 +19,22 @@
 #include <cassert>
 #include <cstddef>
 
+#include "test_macros.h"
 #include "test_iterators.h"
 
+#if TEST_STD_VER > 17
+TEST_CONSTEXPR bool lt(int a, int b) { return a < b; }
+
+TEST_CONSTEXPR bool test_constexpr() {
+    int ia[] = {1, 3, 3, 6, 7};
+
+    return (std::equal_range(std::begin(ia), std::end(ia), 1, lt) == std::pair<int *, int *>(ia+0, ia+1))
+        && (std::equal_range(std::begin(ia), std::end(ia), 3, lt) == std::pair<int *, int *>(ia+1, ia+3))
+        && (std::equal_range(std::begin(ia), std::end(ia), 9, lt) == std::pair<int *, int *>(std::end(ia), std::end(ia)))
+        ;
+    }
+#endif
+
 template <class Iter, class T>
 void
 test(Iter first, Iter last, const T& value)
@@ -68,4 +80,8 @@ int main()
     test<bidirectional_iterator<const int*> >();
     test<random_access_iterator<const int*> >();
     test<const int*>();
+
+#if TEST_STD_VER > 17
+    static_assert(test_constexpr());
+#endif
 }
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/lower_bound.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/lower_bound.pass.cpp
index 1fff1d7f5b6..b6848ec9ef6 100644
--- a/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/lower_bound.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/lower_bound.pass.cpp
@@ -10,8 +10,7 @@
 // <algorithm>
 
 // template<ForwardIterator Iter, class T>
-//   requires HasLess<Iter::value_type, T>
-//   Iter
+//   constexpr Iter    // constexpr after c++17
 //   lower_bound(Iter first, Iter last, const T& value);
 
 #include <algorithm>
@@ -19,8 +18,23 @@
 #include <cassert>
 #include <cstddef>
 
+#include "test_macros.h"
 #include "test_iterators.h"
 
+#if TEST_STD_VER > 17
+TEST_CONSTEXPR bool eq(int a, int b) { return a == b; }
+
+TEST_CONSTEXPR bool test_constexpr() {
+    int ia[] = {1, 3, 6, 7};
+
+    return (std::lower_bound(std::begin(ia), std::end(ia), 2) == ia+1)
+        && (std::lower_bound(std::begin(ia), std::end(ia), 3) == ia+1)
+        && (std::lower_bound(std::begin(ia), std::end(ia), 9) == std::end(ia))
+        ;
+    }
+#endif
+
+
 template <class Iter, class T>
 void
 test(Iter first, Iter last, const T& value)
@@ -62,4 +76,8 @@ int main()
     test<bidirectional_iterator<const int*> >();
     test<random_access_iterator<const int*> >();
     test<const int*>();
+
+#if TEST_STD_VER > 17
+    static_assert(test_constexpr());
+#endif
 }
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/lower_bound_comp.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/lower_bound_comp.pass.cpp
index 4ec5f6c000d..b3ef70eb022 100644
--- a/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/lower_bound_comp.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/lower_bound_comp.pass.cpp
@@ -9,10 +9,9 @@
 
 // <algorithm>
 
-// template<ForwardIterator Iter, class T>
-//   requires HasLess<Iter::value_type, T>
-//   Iter
-//   lower_bound(Iter first, Iter last, const T& value);
+// template<ForwardIterator Iter, class T, class Compare>
+//   constexpr Iter    // constexpr after c++17
+//   lower_bound(Iter first, Iter last, const T& value, Compare comp);
 
 #include <algorithm>
 #include <functional>
@@ -20,8 +19,22 @@
 #include <cassert>
 #include <cstddef>
 
+#include "test_macros.h"
 #include "test_iterators.h"
 
+#if TEST_STD_VER > 17
+TEST_CONSTEXPR bool lt(int a, int b) { return a < b; }
+
+TEST_CONSTEXPR bool test_constexpr() {
+    int ia[] = {1, 3, 6, 7};
+
+    return (std::lower_bound(std::begin(ia), std::end(ia), 2, lt) == ia+1)
+        && (std::lower_bound(std::begin(ia), std::end(ia), 3, lt) == ia+1)
+        && (std::lower_bound(std::begin(ia), std::end(ia), 9, lt) == std::end(ia))
+        ;
+    }
+#endif
+
 template <class Iter, class T>
 void
 test(Iter first, Iter last, const T& value)
@@ -63,4 +76,8 @@ int main()
     test<bidirectional_iterator<const int*> >();
     test<random_access_iterator<const int*> >();
     test<const int*>();
+
+#if TEST_STD_VER > 17
+    static_assert(test_constexpr());
+#endif
 }
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/upper.bound/upper_bound.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/upper.bound/upper_bound.pass.cpp
index 710edb61c9b..43bb4c3cceb 100644
--- a/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/upper.bound/upper_bound.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/upper.bound/upper_bound.pass.cpp
@@ -10,8 +10,7 @@
 // <algorithm>
 
 // template<ForwardIterator Iter, class T>
-//   requires HasLess<T, Iter::value_type>
-//   Iter
+//   constexpr Iter    // constexpr after c++17
 //   upper_bound(Iter first, Iter last, const T& value);
 
 #include <algorithm>
@@ -19,8 +18,20 @@
 #include <cassert>
 #include <cstddef>
 
+#include "test_macros.h"
 #include "test_iterators.h"
 
+#if TEST_STD_VER > 17
+TEST_CONSTEXPR bool test_constexpr() {
+    int ia[] = {1, 3, 6, 7};
+
+    return (std::upper_bound(std::begin(ia), std::end(ia), 2) == ia+1)
+        && (std::upper_bound(std::begin(ia), std::end(ia), 3) == ia+2)
+        && (std::upper_bound(std::begin(ia), std::end(ia), 9) == std::end(ia))
+        ;
+    }
+#endif
+
 template <class Iter, class T>
 void
 test(Iter first, Iter last, const T& value)
@@ -62,4 +73,8 @@ int main()
     test<bidirectional_iterator<const int*> >();
     test<random_access_iterator<const int*> >();
     test<const int*>();
+
+#if TEST_STD_VER > 17
+    static_assert(test_constexpr());
+#endif
 }
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/upper.bound/upper_bound_comp.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/upper.bound/upper_bound_comp.pass.cpp
index 3268075b1b0..fa8e934b9d6 100644
--- a/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/upper.bound/upper_bound_comp.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.binary.search/upper.bound/upper_bound_comp.pass.cpp
@@ -10,8 +10,7 @@
 // <algorithm>
 
 // template<ForwardIterator Iter, class T, Predicate<auto, T, Iter::value_type> Compare>
-//   requires CopyConstructible<Compare>
-//   Iter
+//   constexpr Iter    // constexpr after c++17
 //   upper_bound(Iter first, Iter last, const T& value, Compare comp);
 
 #include <algorithm>
@@ -20,8 +19,22 @@
 #include <cassert>
 #include <cstddef>
 
+#include "test_macros.h"
 #include "test_iterators.h"
 
+#if TEST_STD_VER > 17
+TEST_CONSTEXPR bool lt(int a, int b) { return a < b; }
+
+TEST_CONSTEXPR bool test_constexpr() {
+    int ia[] = {1, 3, 6, 7};
+
+    return (std::upper_bound(std::begin(ia), std::end(ia), 2, lt) == ia+1)
+        && (std::upper_bound(std::begin(ia), std::end(ia), 3, lt) == ia+2)
+        && (std::upper_bound(std::begin(ia), std::end(ia), 9, lt) == std::end(ia))
+        ;
+    }
+#endif
+
 template <class Iter, class T>
 void
 test(Iter first, Iter last, const T& value)
@@ -63,4 +76,8 @@ int main()
     test<bidirectional_iterator<const int*> >();
     test<random_access_iterator<const int*> >();
     test<const int*>();
+
+#if TEST_STD_VER > 17
+    static_assert(test_constexpr());
+#endif
 }