Add most non-modifying sequence operations to libcpp.algorithm (GH-3179)

* Rearrange libcpp.algorithm to match cppreference and reformat
* Add all_of, any_of and none_of to libcpp.algorithm
* Add count and count_if to libcpp.algorithm
* Add string(first, last) constructor to libcpp.string
* Add the simplest overload of mismatch to libcpp.algorithm
* Add find, find_if, and find_if_not to libcpp.algorithm
* Add find_end to libcpp.algorithm and distance to libcpp.iterator
* Add find_first_of to libcpp.algorithm
* Add adjacent_find to libcpp.algorithm
* Add search to libcpp.algorithm
* Add search_n to libcpp.algorithm
* Add exception specifiers in libcpp.algorithm
* Add predicated overload of find_end, search and search_n to libcpp.algorithm

4 files changed, 370 insertions, 33 deletions

diff --git a/Cython/Includes/libcpp/algorithm.pxd b/Cython/Includes/libcpp/algorithm.pxd
index ec7c3835b..4adc36b53 100644
--- a/Cython/Includes/libcpp/algorithm.pxd
+++ b/Cython/Includes/libcpp/algorithm.pxd
@@ -1,43 +1,85 @@
 from libcpp cimport bool
+from libcpp.utility cimport pair
+from libc.stddef import ptrdiff_t
 
 
 cdef extern from "<algorithm>" namespace "std" nogil:
-    # Sorting and searching
-    bool binary_search[Iter, T](Iter first, Iter last, const T& value)
-    bool binary_search[Iter, T, Compare](Iter first, Iter last, const T& value,
-                                         Compare comp)
+    # Non-modifying sequence operations
+    bool all_of[Iter, Pred](Iter first, Iter last, Pred pred) except +
+    bool any_of[Iter, Pred](Iter first, Iter last, Pred pred) except +
+    bool none_of[Iter, Pred](Iter first, Iter last, Pred pred) except +
+
+    ptrdiff_t count[Iter, T](Iter first, Iter last, const T& value)
+    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
+
+    Iter find[Iter, T](Iter first, Iter last, const T& value)
+    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, 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, BinaryPred](
+        Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2, BinaryPred pred) except +
+
+    Iter adjacent_find[Iter](Iter first, Iter last)
+    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, 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, BinaryPred](
+        Iter first1, Iter last1, Size count, const T& value, BinaryPred pred) except +
+
+    # Modifying sequence operations
+    OutputIter copy[InputIter, OutputIter](InputIter, InputIter, OutputIter)
+
+    Iter unique[Iter](Iter first, Iter last)
+    Iter unique[Iter, BinaryPredicate](Iter first, Iter last, BinaryPredicate p) except +
+
+    # Partitioning operations
+
+    # Sorting operations
+    void sort[Iter](Iter first, Iter last)
+    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, Compare](Iter first, Iter middle, 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, Compare](Iter first, Iter last, const T& value,
-                                       Compare comp)
+    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, Compare](Iter first, Iter last, const T& value,
-                                       Compare comp)
+    Iter upper_bound[Iter, T, Compare](Iter first, Iter last, const T& value, Compare comp) except +
 
-    void partial_sort[Iter](Iter first, Iter middle, Iter last)
-    void partial_sort[Iter, Compare](Iter first, Iter middle, Iter last,
-                                     Compare comp)
+    bool binary_search[Iter, T](Iter first, Iter last, const T& value)
+    bool binary_search[Iter, T, Compare](Iter first, Iter last, const T& value, Compare comp) except +
 
-    void sort[Iter](Iter first, Iter last)
-    void sort[Iter, Compare](Iter first, Iter last, Compare comp)
+    # Other operations on sorted ranges
 
-    # Removing duplicates
-    Iter unique[Iter](Iter first, Iter last)
-    Iter unique[Iter, BinaryPredicate](Iter first, Iter last, BinaryPredicate p)
+    # Set operations (on sorted ranges)
 
-    # Binary heaps (priority queues)
+    # Heap operations
     void make_heap[Iter](Iter first, Iter last)
-    void make_heap[Iter, Compare](Iter first, Iter last, Compare comp)
-
-    void pop_heap[Iter](Iter first, Iter last)
-    void pop_heap[Iter, Compare](Iter first, Iter last, Compare comp)
+    void make_heap[Iter, Compare](Iter first, Iter last, Compare comp) except +
 
     void push_heap[Iter](Iter first, Iter last)
-    void push_heap[Iter, Compare](Iter first, Iter last, Compare comp)
+    void push_heap[Iter, Compare](Iter first, Iter last, Compare comp) except +
+
+    void pop_heap[Iter](Iter first, Iter last)
+    void pop_heap[Iter, Compare](Iter first, Iter last, Compare comp) except +
 
     void sort_heap[Iter](Iter first, Iter last)
-    void sort_heap[Iter, Compare](Iter first, Iter last, Compare comp)
+    void sort_heap[Iter, Compare](Iter first, Iter last, Compare comp) except +
+
+    # Minimum/maximum operations
+
+    # Comparison operations
 
-    # Copy
-    OutputIter copy[InputIter,OutputIter](InputIter,InputIter,OutputIter)
+    # Permutation operations
diff --git a/Cython/Includes/libcpp/iterator.pxd b/Cython/Includes/libcpp/iterator.pxd
index e0f8bd8d6..0b50c586d 100644
--- a/Cython/Includes/libcpp/iterator.pxd
+++ b/Cython/Includes/libcpp/iterator.pxd
@@ -1,6 +1,8 @@
 #Basic reference: http://www.cplusplus.com/reference/iterator/
 #Most of these classes are in fact empty structs
 
+from libc.stddef import ptrdiff_t
+
 cdef extern from "<iterator>" namespace "std" nogil:
     cdef cppclass iterator[Category,T,Distance,Pointer,Reference]:
         pass
@@ -29,4 +31,4 @@ cdef extern from "<iterator>" namespace "std" nogil:
     ##insert_iterator<Container> inserter (Container& x, typename Container::iterator it)
     insert_iterator[CONTAINER] inserter[CONTAINER,ITERATOR](CONTAINER &, ITERATOR)
 
-
+    ptrdiff_t distance[It](It first, It last)
diff --git a/Cython/Includes/libcpp/string.pxd b/Cython/Includes/libcpp/string.pxd
index 503e664a8..a07560f2f 100644
--- a/Cython/Includes/libcpp/string.pxd
+++ b/Cython/Includes/libcpp/string.pxd
@@ -8,13 +8,6 @@ cdef extern from "<string>" namespace "std" nogil:
     size_t npos = -1
 
     cdef cppclass string:
-        string() except +
-        string(const char *) except +
-        string(const char *, size_t) except +
-        string(const string&) except +
-        # as a string formed by a repetition of character c, n times.
-        string(size_t, char) except +
-
         cppclass iterator:
             iterator()
             char& operator*()
@@ -40,6 +33,15 @@ cdef extern from "<string>" namespace "std" nogil:
         cppclass const_reverse_iterator(reverse_iterator):
             pass
 
+        string() except +
+        string(const char *) except +
+        string(const char *, size_t) except +
+        string(const string&) except +
+        # as a string formed by a repetition of character c, n times.
+        string(size_t, char) except +
+        # from a pair of iterators
+        string(iterator first, iterator last) except +
+
         iterator begin()
         const_iterator const_begin "begin"()
         iterator end()
diff --git a/tests/run/cpp_stl_algo_nonmodifying_sequence_ops.pyx b/tests/run/cpp_stl_algo_nonmodifying_sequence_ops.pyx
new file mode 100644
index 000000000..2679f4701
--- /dev/null
+++ b/tests/run/cpp_stl_algo_nonmodifying_sequence_ops.pyx
@@ -0,0 +1,291 @@
+# mode: run
+# tag: cpp, werror, cpp11
+
+from cython.operator cimport dereference as deref
+
+from libcpp cimport bool
+from libcpp.algorithm cimport all_of, any_of, none_of, count, count_if, mismatch, find, find_if, find_if_not, find_end
+from libcpp.algorithm cimport find_first_of, adjacent_find, search, search_n
+from libcpp.iterator cimport distance
+from libcpp.string cimport string
+from libcpp.vector cimport vector
+
+
+cdef bool is_odd(int i):
+    return i % 2
+
+
+def all_odd(vector[int] values):
+    """
+    Test all_of with is_odd predicate.
+
+    >>> all_odd([3, 5, 7, 11, 13, 17, 19, 23])
+    True
+    >>> all_odd([3, 4])
+    False
+    """
+    return all_of(values.begin(), values.end(), is_odd)
+
+
+def any_odd(vector[int] values):
+    """
+    Test any_of with is_odd predicate.
+
+    >>> any_odd([1, 2, 3, 4])
+    True
+    >>> any_odd([2, 4, 6, 8])
+    False
+    """
+    return any_of(values.begin(), values.end(), is_odd)
+
+
+def none_odd(vector[int] values):
+    """
+    Test none_of with is_odd predicate.
+
+    >>> none_odd([2, 4, 6, 8])
+    True
+    >>> none_odd([1, 2, 3, 4])
+    False
+    """
+    return none_of(values.begin(), values.end(), is_odd)
+
+
+def count_ones(vector[int] values):
+    """
+    Test count.
+
+    >>> count_ones([1, 2, 1, 2])
+    2
+    """
+    return count(values.begin(), values.end(), 1)
+
+
+def count_odd(vector[int]  values):
+    """
+    Test count_if with is_odd predicate.
+
+    >>> count_odd([1, 2, 3, 4])
+    2
+    >>> count_odd([2, 4, 6, 8])
+    0
+    """
+    return count_if(values.begin(), values.end(), is_odd)
+
+
+def mirror_ends(string data):
+    """
+    Test mismatch using cppreference example.
+
+    This program determines the longest substring that is simultaneously found at the very beginning of the given string
+    and at the very end of it, in reverse order (possibly overlapping).
+
+    >>> print(mirror_ends(b'abXYZba').decode('ascii'))
+    ab
+    >>> print(mirror_ends(b'abca').decode('ascii'))
+    a
+    >>> print(mirror_ends(b'aba').decode('ascii'))
+    aba
+    """
+    return string(data.begin(), mismatch(data.begin(), data.end(), data.rbegin()).first)
+
+
+def mismatch_ints(vector[int] values1, vector[int] values2):
+    """
+    Test mismatch(first1, last1, first2).
+
+    >>> mismatch_ints([1, 2, 3], [1, 2, 3])
+    >>> mismatch_ints([1, 2], [1, 2, 3])
+    >>> mismatch_ints([1, 3], [1, 2, 3])
+    (3, 2)
+    """
+    result = mismatch(values1.begin(), values1.end(), values2.begin())
+    if result.first == values1.end():
+        return
+    return deref(result.first), deref(result.second)
+
+
+def is_int_in(vector[int] values, int target):
+    """
+    Test find.
+
+    >>> is_int_in(range(5), 3)
+    True
+    >>> is_int_in(range(5), 10)
+    False
+    """
+    return find(values.begin(), values.end(), target) != values.end()
+
+
+def find_odd(vector[int] values):
+    """
+    Test find_if using is_odd predicate.
+
+    >>> find_odd([2, 3, 4])
+    3
+    >>> find_odd([2, 4, 6])
+    """
+    result = find_if(values.begin(), values.end(), is_odd)
+    if result != values.end():
+        return deref(result)
+    else:
+        return None
+
+
+def find_even(vector[int] values):
+    """
+    Test find_if_not using is_odd predicate.
+
+    >>> find_even([3, 4, 5])
+    4
+    >>> find_even([1, 3, 5])
+    """
+    result = find_if_not(values.begin(), values.end(), is_odd)
+    if result != values.end():
+        return deref(result)
+    else:
+        return None
+
+
+def find_last_int_sequence(vector[int] values, vector[int] target):
+    """
+    Test find_end.
+
+    >>> find_last_int_sequence([1, 2, 3, 1, 2, 3], [2, 3])
+    4
+    >>> find_last_int_sequence([1, 2, 3], [4, 5])
+    """
+    result = find_end(values.begin(), values.end(), target.begin(), target.end())
+    if result != values.end():
+        return distance(values.begin(), result)
+    else:
+        return None
+
+
+cdef bool is_equal(int lhs, int rhs):
+    return lhs == rhs
+
+
+def find_last_int_sequence2(vector[int] values, vector[int] target):
+    """
+    Test find_end (using is_equal predicate).
+
+    >>> find_last_int_sequence2([1, 2, 3, 1, 2, 3], [2, 3])
+    4
+    >>> find_last_int_sequence2([1, 2, 3], [4, 5])
+    """
+    result = find_end(values.begin(), values.end(), target.begin(), target.end(), <bool (*)(int, int)>is_equal)
+    if result != values.end():
+        return distance(values.begin(), result)
+    else:
+        return None
+
+
+def find_first_int_in_set(values, target):
+    """
+    Test find_first_of.
+
+    >>> find_first_int_in_set([1, 2, 3, 4, 5], [3, 5])
+    2
+    >>> find_first_int_in_set([1, 2, 3], [4, 5])
+    """
+    cdef vector[int] v = values
+    cdef vector[int] t = target
+    result = find_first_of(v.begin(), v.end(), t.begin(), t.end())
+    if result != v.end():
+        return distance(v.begin(), result)
+    else:
+        return None
+
+
+def find_first_int_in_set2(vector[int] values, vector[int] target):
+    """
+    Test find_first_of with is_equal predicate.
+
+    >>> find_first_int_in_set2([1, 2, 3, 4, 5], [3, 5])
+    2
+    >>> find_first_int_in_set2([1, 2, 3], [4, 5])
+    """
+    result = find_first_of(values.begin(), values.end(), target.begin(), target.end(), is_equal)
+    if result != values.end():
+        return distance(values.begin(), result)
+    else:
+        return None
+
+
+def find_adjacent_int(vector[int] values):
+    """
+    Test adjacent_find.
+
+    >>> find_adjacent_int([0, 1, 2, 3, 40, 40, 41, 41, 5])
+    4
+    >>> find_adjacent_int(range(5))
+    """
+    result = adjacent_find(values.begin(), values.end())
+    if result != values.end():
+        return distance(values.begin(), result)
+    else:
+        return None
+
+
+def find_adjacent_int2(vector[int] values):
+    """
+    Test find_adjacent with is_equal predicate.
+
+    >>> find_adjacent_int2([0, 1, 2, 3, 40, 40, 41, 41, 5])
+    4
+    >>> find_adjacent_int2(range(5))
+    """
+    result = adjacent_find(values.begin(), values.end(), is_equal)
+    if result != values.end():
+        return distance(values.begin(), result)
+    else:
+        return None
+
+
+def in_quote(string quote, string word):
+    """
+    Test search using cppreference example.
+
+    >>> in_quote(b"why waste time learning, when ignorance is instantaneous?", b"learning")
+    True
+    >>> in_quote(b"why waste time learning, when ignorance is instantaneous?", b"lemming")
+    False
+    """
+    return search(quote.begin(), quote.end(), word.begin(), word.end()) != quote.end()
+
+
+def in_quote2(string quote, string word):
+    """
+    Test search using cppreference example (with is_equal predicate).
+
+    >>> in_quote2(b"why waste time learning, when ignorance is instantaneous?", b"learning")
+    True
+    >>> in_quote2(b"why waste time learning, when ignorance is instantaneous?", b"lemming")
+    False
+    """
+    return search(quote.begin(), quote.end(), word.begin(), word.end(), <bool (*)(int, int)>is_equal) != quote.end()
+
+
+def consecutive_values(string c, int count, char v):
+    """
+    Test search_n using cppreference example (without std::begin and std::end).
+
+    >>> consecutive_values(b"1001010100010101001010101", 4, ord("0"))
+    False
+    >>> consecutive_values(b"1001010100010101001010101", 3, ord("0"))
+    True
+    """
+    return search_n(c.begin(), c.end(), count, v) != c.end()
+
+
+def consecutive_values2(string c, int count, char v):
+    """
+    Test search_n using cppreference example (with is_equal predicate).
+
+    >>> consecutive_values2(b"1001010100010101001010101", 4, ord("0"))
+    False
+    >>> consecutive_values2(b"1001010100010101001010101", 3, ord("0"))
+    True
+    """
+    return search_n(c.begin(), c.end(), count, v, <bool (*)(int, int)>is_equal) != c.end()