Add partitioning and sorting operations to libcpp.algorithm (GH-3202)

* Add is_partitioned and partition to libcpp.algorithm
* Add is_sorted and is_sorted_until to libcpp.algorithm
* Add partition_copy, stable_partition, and partition_point to libcpp.algorithm
* Move tests for sort and partial_sort into cpp_stl_algo_sorting_ops, add greater to libcpp.functional
* Add partial_sort_copy to libcpp.algorithm
* Add stable_sort to libcpp.algorithm
* Add nth_element to libcpp.algorithm
* Add missing except specifiers in libcpp.algorithm

2 files changed, 72 insertions, 41 deletions

diff --git a/Cython/Includes/libcpp/algorithm.pxd b/Cython/Includes/libcpp/algorithm.pxd
index 9829101ef..c07bae139 100644
--- a/Cython/Includes/libcpp/algorithm.pxd
+++ b/Cython/Includes/libcpp/algorithm.pxd
@@ -11,44 +11,45 @@ cdef extern from "<algorithm>" namespace "std" nogil:
 
     void for_each[Iter, UnaryFunction](Iter first, Iter last, UnaryFunction f) except +  # actually returns f
 
-    ptrdiff_t count[Iter, T](Iter first, Iter last, const T& value)
+    ptrdiff_t count[Iter, T](Iter first, Iter last, const T& value) except +
     ptrdiff_t count_if[Iter, Pred](Iter first, Iter last, Pred pred) except +
 
-    pair[Iter1, Iter2] mismatch[Iter1, Iter2](Iter1 first1, Iter1 last1, Iter2 first2)  # other overloads are tricky
+    pair[Iter1, Iter2] mismatch[Iter1, Iter2](
+        Iter1 first1, Iter1 last1, Iter2 first2) except +  # other overloads are tricky
 
-    Iter find[Iter, T](Iter first, Iter last, const T& value)
+    Iter find[Iter, T](Iter first, Iter last, const T& value) except +
     Iter find_if[Iter, Pred](Iter first, Iter last, Pred pred) except +
     Iter find_if_not[Iter, Pred](Iter first, Iter last, Pred pred) except +
 
-    Iter1 find_end[Iter1, Iter2](Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2)
+    Iter1 find_end[Iter1, Iter2](Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2) except +
     Iter1 find_end[Iter1, Iter2, BinaryPred](
         Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2, BinaryPred pred) except +
 
-    Iter1 find_first_of[Iter1, Iter2](Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2)
+    Iter1 find_first_of[Iter1, Iter2](Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2) except +
     Iter1 find_first_of[Iter1, Iter2, BinaryPred](
         Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2, BinaryPred pred) except +
 
-    Iter adjacent_find[Iter](Iter first, Iter last)
+    Iter adjacent_find[Iter](Iter first, Iter last) except +
     Iter adjacent_find[Iter, BinaryPred](Iter first, Iter last, BinaryPred pred) except +
 
-    Iter1 search[Iter1, Iter2](Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2)
+    Iter1 search[Iter1, Iter2](Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2) except +
     Iter1 search[Iter1, Iter2, BinaryPred](
         Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2, BinaryPred pred) except +
-    Iter search_n[Iter, Size, T](Iter first1, Iter last1, Size count, const T& value)
+    Iter search_n[Iter, Size, T](Iter first1, Iter last1, Size count, const T& value) except +
     Iter search_n[Iter, Size, T, BinaryPred](
         Iter first1, Iter last1, Size count, const T& value, BinaryPred pred) except +
 
     # Modifying sequence operations
-    OutputIt copy[InputIt, OutputIt](InputIt first, InputIt last, OutputIt d_first)
+    OutputIt copy[InputIt, OutputIt](InputIt first, InputIt last, OutputIt d_first) except +
     OutputIt copy_if[InputIt, OutputIt, Pred](InputIt first, InputIt last, OutputIt d_first, Pred pred) except +
-    OutputIt copy_n[InputIt, Size, OutputIt](InputIt first, Size count, OutputIt result)
-    Iter2 copy_backward[Iter1, Iter2](Iter1 first, Iter1 last, Iter2 d_last)
+    OutputIt copy_n[InputIt, Size, OutputIt](InputIt first, Size count, OutputIt result) except +
+    Iter2 copy_backward[Iter1, Iter2](Iter1 first, Iter1 last, Iter2 d_last) except +
 
-    OutputIt move[InputIt, OutputIt](InputIt first, InputIt last, OutputIt d_first)
-    Iter2 move_backward[Iter1, Iter2](Iter1 first, Iter1 last, Iter2 d_last)
+    OutputIt move[InputIt, OutputIt](InputIt first, InputIt last, OutputIt d_first) except +
+    Iter2 move_backward[Iter1, Iter2](Iter1 first, Iter1 last, Iter2 d_last) except +
 
-    void fill[Iter, T](Iter first, Iter last, const T& value)
-    Iter fill_n[Iter, Size, T](Iter first, Size count, const T& value)
+    void fill[Iter, T](Iter first, Iter last, const T& value) except +
+    Iter fill_n[Iter, Size, T](Iter first, Size count, const T& value) except +
 
     OutputIt transform[InputIt, OutputIt, UnaryOp](
         InputIt first1, InputIt last1, OutputIt d_first, UnaryOp unary_op) except +
@@ -58,53 +59,75 @@ cdef extern from "<algorithm>" namespace "std" nogil:
     void generate[Iter, Generator](Iter first, Iter last, Generator g) except +
     void generate_n[Iter, Size, Generator](Iter first, Size count, Generator g) except +
 
-    Iter remove[Iter, T](Iter first, Iter last, const T& value)
-    Iter remove_if[Iter, UnaryPred](Iter first, Iter last, UnaryPred pred)
-    OutputIt remove_copy[InputIt, OutputIt, T](InputIt first, InputIt last, OutputIt d_first, const T& value)
+    Iter remove[Iter, T](Iter first, Iter last, const T& value) except +
+    Iter remove_if[Iter, UnaryPred](Iter first, Iter last, UnaryPred pred) except +
+    OutputIt remove_copy[InputIt, OutputIt, T](InputIt first, InputIt last, OutputIt d_first, const T& value) except +
     OutputIt remove_copy_if[InputIt, OutputIt, UnaryPred](
         InputIt first, InputIt last, OutputIt d_first, UnaryPred pred) except +
 
-    void replace[Iter, T](Iter first, Iter last, const T& old_value, const T& new_value)
+    void replace[Iter, T](Iter first, Iter last, const T& old_value, const T& new_value) except +
     void replace_if[Iter, UnaryPred, T](Iter first, Iter last, UnaryPred pred, const T& new_value) except +
     OutputIt replace_copy[InputIt, OutputIt, T](
-        InputIt first, InputIt last, OutputIt d_first, const T& old_value, const T& new_value)
+        InputIt first, InputIt last, OutputIt d_first, const T& old_value, const T& new_value) except +
     OutputIt replace_copy_if[InputIt, OutputIt, UnaryPred, T](
         InputIt first, InputIt last, OutputIt d_first, UnaryPred pred, const T& new_value) except +
 
-    void swap[T](T& a, T& b)  # array overload also works
-    Iter2 swap_ranges[Iter1, Iter2](Iter1 first1, Iter1 last1, Iter2 first2)
-    void iter_swap[Iter](Iter a, Iter b)
+    void swap[T](T& a, T& b) except +  # array overload also works
+    Iter2 swap_ranges[Iter1, Iter2](Iter1 first1, Iter1 last1, Iter2 first2) except +
+    void iter_swap[Iter](Iter a, Iter b) except +
 
-    void reverse[Iter](Iter first, Iter last)
-    OutputIt reverse_copy[InputIt, OutputIt](InputIt first, InputIt last, OutputIt d_first)
+    void reverse[Iter](Iter first, Iter last) except +
+    OutputIt reverse_copy[InputIt, OutputIt](InputIt first, InputIt last, OutputIt d_first) except +
 
-    Iter rotate[Iter](Iter first, Iter n_first, Iter last)
-    OutputIt rotate_copy[InputIt, OutputIt](InputIt first, InputIt n_first, InputIt last, OutputIt d_first)
+    Iter rotate[Iter](Iter first, Iter n_first, Iter last) except +
+    OutputIt rotate_copy[InputIt, OutputIt](InputIt first, InputIt n_first, InputIt last, OutputIt d_first) except +
 
-    Iter unique[Iter](Iter first, Iter last)
+    Iter unique[Iter](Iter first, Iter last) except +
     Iter unique[Iter, BinaryPred](Iter first, Iter last, BinaryPred p) except +
-    OutputIt unique_copy[InputIt, OutputIt](InputIt first, InputIt last, OutputIt d_first)
+    OutputIt unique_copy[InputIt, OutputIt](InputIt first, InputIt last, OutputIt d_first) except +
     OutputIt unique_copy[InputIt, OutputIt, BinaryPred](
         InputIt first, InputIt last, OutputIt d_first, BinaryPred pred) except +
 
-
     # Partitioning operations
+    bool is_partitioned[Iter, Pred](Iter first, Iter last, Pred p) except +
+    Iter partition[Iter, Pred](Iter first, Iter last, Pred p) except +
+    pair[OutputIt1, OutputIt2] partition_copy[InputIt, OutputIt1, OutputIt2, Pred](
+        InputIt first, InputIt last, OutputIt1 d_first_true, OutputIt2 d_first_false, Pred p) except +
+    Iter stable_partition[Iter, Pred](Iter first, Iter last, Pred p) except +
+    Iter partition_point[Iter, Pred](Iter first, Iter last, Pred p) except +
 
     # Sorting operations
-    void sort[Iter](Iter first, Iter last)
+    bool is_sorted[Iter](Iter first, Iter last) except +
+    bool is_sorted[Iter, Compare](Iter first, Iter last, Compare comp) except +
+
+    Iter is_sorted_until[Iter](Iter first, Iter last) except +
+    Iter is_sorted_until[Iter, Compare](Iter first, Iter last, Compare comp) except +
+
+    void sort[Iter](Iter first, Iter last) except +
     void sort[Iter, Compare](Iter first, Iter last, Compare comp) except +
 
-    void partial_sort[Iter](Iter first, Iter middle, Iter last)
+    void partial_sort[Iter](Iter first, Iter middle, Iter last) except +
     void partial_sort[Iter, Compare](Iter first, Iter middle, Iter last, Compare comp) except +
 
+    OutputIt partial_sort_copy[InputIt, OutputIt](
+        InputIt first, InputIt last, OutputIt d_first, OutputIt d_last) except +
+    OutputIt partial_sort_copy[InputIt, OutputIt, Compare](
+        InputIt first, InputIt last, OutputIt d_first, OutputIt d_last, Compare comp) except +
+
+    void stable_sort[Iter](Iter first, Iter last) except +
+    void stable_sort[Iter, Compare](Iter first, Iter last, Compare comp) except +
+
+    void nth_element[Iter](Iter first, Iter nth, Iter last) except +
+    void nth_element[Iter, Compare](Iter first, Iter nth, Iter last, Compare comp) except +
+
     # Binary search operations (on sorted ranges)
-    Iter lower_bound[Iter, T](Iter first, Iter last, const T& value)
+    Iter lower_bound[Iter, T](Iter first, Iter last, const T& value) except +
     Iter lower_bound[Iter, T, Compare](Iter first, Iter last, const T& value, Compare comp) except +
 
-    Iter upper_bound[Iter, T](Iter first, Iter last, const T& value)
+    Iter upper_bound[Iter, T](Iter first, Iter last, const T& value) except +
     Iter upper_bound[Iter, T, Compare](Iter first, Iter last, const T& value, Compare comp) except +
 
-    bool binary_search[Iter, T](Iter first, Iter last, const T& value)
+    bool binary_search[Iter, T](Iter first, Iter last, const T& value) except +
     bool binary_search[Iter, T, Compare](Iter first, Iter last, const T& value, Compare comp) except +
 
     # Other operations on sorted ranges
@@ -112,20 +135,20 @@ cdef extern from "<algorithm>" namespace "std" nogil:
     # Set operations (on sorted ranges)
 
     # Heap operations
-    void make_heap[Iter](Iter first, Iter last)
+    void make_heap[Iter](Iter first, Iter last) except +
     void make_heap[Iter, Compare](Iter first, Iter last, Compare comp) except +
 
-    void push_heap[Iter](Iter first, Iter last)
+    void push_heap[Iter](Iter first, Iter last) except +
     void push_heap[Iter, Compare](Iter first, Iter last, Compare comp) except +
 
-    void pop_heap[Iter](Iter first, Iter last)
+    void pop_heap[Iter](Iter first, Iter last) except +
     void pop_heap[Iter, Compare](Iter first, Iter last, Compare comp) except +
 
-    void sort_heap[Iter](Iter first, Iter last)
+    void sort_heap[Iter](Iter first, Iter last) except +
     void sort_heap[Iter, Compare](Iter first, Iter last, Compare comp) except +
 
     # Minimum/maximum operations
-    Iter min_element[Iter](Iter first, Iter last)
+    Iter min_element[Iter](Iter first, Iter last) except +
 
     # Comparison operations
 
diff --git a/Cython/Includes/libcpp/functional.pxd b/Cython/Includes/libcpp/functional.pxd
index 94cbd9e1d..4786d39eb 100644
--- a/Cython/Includes/libcpp/functional.pxd
+++ b/Cython/Includes/libcpp/functional.pxd
@@ -1,3 +1,5 @@
+from libcpp cimport bool
+
 cdef extern from "<functional>" namespace "std" nogil:
     cdef cppclass function[T]:
         function() except +
@@ -10,4 +12,10 @@ cdef extern from "<functional>" namespace "std" nogil:
         function operator=(void*)
         function operator=[U](U)
 
-        bint operator bool()
+        bool operator bool()
+
+    # Comparisons
+    cdef cppclass greater[T=*]:
+        # https://github.com/cython/cython/issues/3193
+        greater() except +
+        bool operator()(const T& lhs, const T& rhs) except +