diff options
author | Matthew Edwards <mje-nz@users.noreply.github.com> | 2019-10-22 06:58:23 +1300 |
---|---|---|
committer | Stefan Behnel <stefan_ml@behnel.de> | 2019-10-21 19:58:23 +0200 |
commit | 05059e2a9b89bf6738a7750b905057e5b1e3fe2e (patch) | |
tree | f080bc69c80ff4d29f02d0cdfe97c35ba9700f94 | |
parent | 5a8c984403ce73ac29f9e8b7c78ee5f0f4c608a3 (diff) | |
download | cython-05059e2a9b89bf6738a7750b905057e5b1e3fe2e.tar.gz |
Add most modifying sequence operations to libcpp.algorithm (GH-3188)
Also fix tests in libcpp_algo (how did this ever work?)
-rw-r--r-- | Cython/Includes/libcpp/algorithm.pxd | 51 | ||||
-rw-r--r-- | Cython/Includes/libcpp/string.pxd | 4 | ||||
-rw-r--r-- | tests/run/cpp_stl_algo_modifying_sequence_ops.pyx | 434 | ||||
-rw-r--r-- | tests/run/cpp_stl_algo_nonmodifying_sequence_ops.pyx | 28 | ||||
-rw-r--r-- | tests/run/libcpp_algo.pyx | 8 |
5 files changed, 513 insertions, 12 deletions
diff --git a/Cython/Includes/libcpp/algorithm.pxd b/Cython/Includes/libcpp/algorithm.pxd index 4adc36b53..9829101ef 100644 --- a/Cython/Includes/libcpp/algorithm.pxd +++ b/Cython/Includes/libcpp/algorithm.pxd @@ -9,6 +9,8 @@ cdef extern from "<algorithm>" namespace "std" nogil: bool any_of[Iter, Pred](Iter first, Iter last, Pred pred) except + bool none_of[Iter, Pred](Iter first, Iter last, Pred pred) except + + 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_if[Iter, Pred](Iter first, Iter last, Pred pred) except + @@ -37,10 +39,54 @@ cdef extern from "<algorithm>" namespace "std" nogil: Iter first1, Iter last1, Size count, const T& value, BinaryPred pred) except + # Modifying sequence operations - OutputIter copy[InputIter, OutputIter](InputIter, InputIter, OutputIter) + OutputIt copy[InputIt, OutputIt](InputIt first, InputIt last, OutputIt d_first) + 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 move[InputIt, OutputIt](InputIt first, InputIt last, OutputIt d_first) + Iter2 move_backward[Iter1, Iter2](Iter1 first, Iter1 last, Iter2 d_last) + + void fill[Iter, T](Iter first, Iter last, const T& value) + Iter fill_n[Iter, Size, T](Iter first, Size count, const T& value) + + OutputIt transform[InputIt, OutputIt, UnaryOp]( + InputIt first1, InputIt last1, OutputIt d_first, UnaryOp unary_op) except + + OutputIt transform[InputIt1, InputIt2, OutputIt, BinaryOp]( + InputIt1 first1, InputIt1 last1, InputIt2 first2, OutputIt d_first, BinaryOp binary_op) except + + + 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) + 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_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) + 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 reverse[Iter](Iter first, Iter last) + OutputIt reverse_copy[InputIt, OutputIt](InputIt first, InputIt last, OutputIt d_first) + + 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 unique[Iter](Iter first, Iter last) - Iter unique[Iter, BinaryPredicate](Iter first, Iter last, BinaryPredicate p) 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, BinaryPred]( + InputIt first, InputIt last, OutputIt d_first, BinaryPred pred) except + + # Partitioning operations @@ -79,6 +125,7 @@ cdef extern from "<algorithm>" namespace "std" nogil: void sort_heap[Iter, Compare](Iter first, Iter last, Compare comp) except + # Minimum/maximum operations + Iter min_element[Iter](Iter first, Iter last) # Comparison operations diff --git a/Cython/Includes/libcpp/string.pxd b/Cython/Includes/libcpp/string.pxd index a07560f2f..5d9e5b3ac 100644 --- a/Cython/Includes/libcpp/string.pxd +++ b/Cython/Includes/libcpp/string.pxd @@ -62,6 +62,10 @@ cdef extern from "<string>" namespace "std" nogil: void reserve(size_t) void clear() bint empty() + iterator erase(iterator position) + iterator erase(const_iterator position) + iterator erase(iterator first, iterator last) + iterator erase(const_iterator first, const_iterator last) char& at(size_t) char& operator[](size_t) diff --git a/tests/run/cpp_stl_algo_modifying_sequence_ops.pyx b/tests/run/cpp_stl_algo_modifying_sequence_ops.pyx new file mode 100644 index 000000000..156a28a11 --- /dev/null +++ b/tests/run/cpp_stl_algo_modifying_sequence_ops.pyx @@ -0,0 +1,434 @@ +# mode: run +# tag: cpp, werror, cpp11 + +from __future__ import print_function + +from cython.operator cimport dereference as deref +from cython.operator cimport preincrement, postincrement +from libcpp cimport bool +from libcpp.algorithm cimport copy, copy_if, copy_n, copy_backward, move, move_backward, fill, fill_n, transform +from libcpp.algorithm cimport generate, generate_n, remove, remove_if, remove_copy, remove_copy_if, replace, replace_if +from libcpp.algorithm cimport replace_copy, replace_copy_if, swap, swap_ranges, iter_swap, reverse, reverse_copy +from libcpp.algorithm cimport rotate, rotate_copy, unique, unique_copy +from libcpp.algorithm cimport sort, upper_bound, min_element +from libcpp.iterator cimport back_inserter +from libcpp.string cimport string +from libcpp.vector cimport vector + + +def copy_int(vector[int] values): + """ + Test copy. + + >>> copy_int(range(5)) + [0, 1, 2, 3, 4] + """ + cdef vector[int] out + copy(values.begin(), values.end(), back_inserter(out)) + return out + + +cdef bool is_odd(int i): + return i % 2 + + +def copy_int_if_odd(vector[int] values): + """ + Test copy_if. + + >>> copy_int_if_odd(range(5)) + [1, 3] + """ + cdef vector[int] out + copy_if(values.begin(), values.end(), back_inserter(out), is_odd) + return out + + +def copy_int_n(vector[int] values, int count): + """ + Test copy_n. + + >>> copy_int_n(range(5), 2) + [0, 1] + """ + cdef vector[int] out + copy_n(values.begin(), count, back_inserter(out)) + return out + + +def copy_int_backward(vector[int] values): + """ + Test copy_backward. + + >>> copy_int_backward(range(5)) + [0, 0, 0, 0, 1, 2, 3, 4] + """ + out = vector[int](values.size() + 3) + copy_backward(values.begin(), values.end(), out.end()) + return out + + +def move_int(vector[int] values): + """ + Test move. + + >>> move_int(range(5)) + [0, 1, 2, 3, 4] + """ + cdef vector[int] out + move(values.begin(), values.end(), back_inserter(out)) + return out + + +def move_int_backward(vector[int] values): + """ + Test move_backward. + + >>> move_int_backward(range(5)) + [0, 0, 0, 0, 1, 2, 3, 4] + """ + out = vector[int](values.size() + 3) + move_backward(values.begin(), values.end(), out.end()) + return out + + +def fill_int(vector[int] array, int value): + """ + Test fill. + + >>> fill_int(range(5), -1) + [-1, -1, -1, -1, -1] + """ + fill(array.begin(), array.end(), value) + return array + + +def fill_int_n(vector[int] array, int count, int value): + """ + Test fill_n. + + >>> fill_int_n(range(5), 3, -1) + [-1, -1, -1, 3, 4] + """ + fill_n(array.begin(), count, value) + return array + + +cdef int to_ord(unsigned char c): + return c + + +def string_to_ord(string s): + """ + Test transform (unary version). + + >> string_to_ord(b"HELLO") + [72, 69, 76, 76, 79] + """ + cdef vector[int] ordinals + transform(s.begin(), s.end(), back_inserter(ordinals), to_ord) + return ordinals + + +cdef int add_ints(int lhs, int rhs): + return lhs + rhs + + +def add_int_vectors(vector[int] lhs, vector[int] rhs): + """ + Test transform (binary version). + + >>> add_int_vectors([1, 2, 3], [4, 5, 6]) + [5, 7, 9] + """ + transform(lhs.begin(), lhs.end(), rhs.begin(), lhs.begin(), add_ints) + return lhs + + +cdef int i = 0 +cdef int generator(): + return postincrement(i) + + +def generate_ints(int count): + """ + Test generate. + + >> generate_ints(5) + [0, 1, 2, 3, 4] + """ + out = vector[int](count) + generate(out.begin(), out.end(), generator) + return out + + +cdef int j = 0 +cdef int generator2(): + return postincrement(j) + + +def generate_n_ints(int count): + """ + Test generate_n. + + >> generate_n_ints(5) + [0, 1, 2, 3, 4, 0, 0, 0] + """ + out = vector[int](count + 3) + generate_n(out.begin(), count, generator2) + return out + + +def remove_spaces(string s): + """ + Test remove. + + >>> print(remove_spaces(b"Text with some spaces").decode("ascii")) + Textwithsomespaces + """ + s.erase(remove(s.begin(), s.end(), ord(" ")), s.end()) + return s + + +cdef bool is_whitespace(unsigned char c) except -1: + # std::isspace from <cctype> + return chr(c) in " \f\n\r\t\v" + + +def remove_whitespace(string s): + r""" + Test remove_if. + + >>> print(remove_whitespace(b"Text\n with\tsome \t whitespaces\n\n").decode("ascii")) + Textwithsomewhitespaces + """ + s.erase(remove_if(s.begin(), s.end(), &is_whitespace), s.end()) + return s + + +def remove_spaces2(string s): + """ + Test remove_copy. + + >>> print(remove_spaces2(b"Text with some spaces").decode("ascii")) + Textwithsomespaces + """ + cdef string out + remove_copy(s.begin(), s.end(), back_inserter(out), ord(" ")) + return out + + +def remove_whitespace2(string s): + r""" + Test remove_copy_if. + + >>> print(remove_whitespace2(b"Text\n with\tsome \t whitespaces\n\n").decode("ascii")) + Textwithsomewhitespaces + """ + cdef string out + remove_copy_if(s.begin(), s.end(), back_inserter(out), &is_whitespace) + return out + + +def replace_ints(vector[int] values, int old, int new): + """ + Test replace. + + >>> replace_ints([5, 7, 4, 2, 8, 6, 1, 9, 0, 3], 8, 88) + [5, 7, 4, 2, 88, 6, 1, 9, 0, 3] + """ + replace(values.begin(), values.end(), old, new) + return values + + +cdef bool less_than_five(int i): + return i < 5 + + +def replace_ints_less_than_five(vector[int] values, int new): + """ + Test replace_if (using cppreference example that doesn't translate well). + + >>> replace_ints_less_than_five([5, 7, 4, 2, 88, 6, 1, 9, 0, 3], 55) + [5, 7, 55, 55, 88, 6, 55, 9, 55, 55] + """ + replace_if(values.begin(), values.end(), less_than_five, new) + return values + + +def replace_ints2(vector[int] values, int old, int new): + """ + Test replace_copy. + + >>> replace_ints2([5, 7, 4, 2, 8, 6, 1, 9, 0, 3], 8, 88) + [5, 7, 4, 2, 88, 6, 1, 9, 0, 3] + """ + cdef vector[int] out + replace_copy(values.begin(), values.end(), back_inserter(out), old, new) + return out + + +def replace_ints_less_than_five2(vector[int] values, int new): + """ + Test replace_copy_if (using cppreference example that doesn't translate well). + + >>> replace_ints_less_than_five2([5, 7, 4, 2, 88, 6, 1, 9, 0, 3], 55) + [5, 7, 55, 55, 88, 6, 55, 9, 55, 55] + """ + cdef vector[int] out + replace_copy_if(values.begin(), values.end(), back_inserter(out), less_than_five, new) + return out + + +def test_swap_ints(): + """ + >>> test_swap_ints() + 5 3 + 3 5 + """ + cdef int a = 5, b = 3 + print(a, b) + swap(a, b) + print(a, b) + + +def test_swap_vectors(): + """ + >>> test_swap_vectors() + [1, 2, 3] [4, 5, 6] + [4, 5, 6] [1, 2, 3] + """ + cdef vector[int] a = [1, 2, 3], b = [4, 5, 6] + print(a, b) + swap(a, b) + print(a, b) + + +def test_swap_ranges(): + """ + >>> test_swap_ranges() + [1, 2, 3] [4, 5, 6] + [4, 5, 6] [1, 2, 3] + """ + cdef vector[int] a = [1, 2, 3], b = [4, 5, 6] + print(a, b) + swap_ranges(a.begin(), a.end(), b.begin()) + print(a, b) + + +def selection_sort(vector[int] values): + """ + Test iter_swap using cppreference example. + + >>> selection_sort([-7, 6, 2, 4, -1, 6, -9, -1, 2, -5, 10, -9, -5, -3, -5, -3, 6, 6, 1, 8]) + [-9, -9, -7, -5, -5, -5, -3, -3, -1, -1, 1, 2, 2, 4, 6, 6, 6, 6, 8, 10] + """ + i = values.begin() + end = values.end() + while i < end: + iter_swap(i, min_element(i, end)) + preincrement(i) + return values + + +def reverse_ints(vector[int] values): + """ + Test reverse. + + >>> reverse_ints([1, 2, 3]) + [3, 2, 1] + """ + reverse(values.begin(), values.end()) + return values + + +def reverse_ints2(vector[int] values): + """ + Test reverse_copy. + + >>> reverse_ints2([1, 2, 3]) + [3, 2, 1] + """ + cdef vector[int] out + reverse_copy(values.begin(), values.end(), back_inserter(out)) + return out + + +def insertion_sort(vector[int] values): + """ + Test rotate using cppreference example. + + >>> insertion_sort([2, 4, 2, 0, 5, 10, 7, 3, 7, 1]) + [0, 1, 2, 2, 3, 4, 5, 7, 7, 10] + """ + i = values.begin() + while i < values.end(): + rotate(upper_bound(values.begin(), i, deref(i)), i, i + 1) + preincrement(i) + return values + + +def rotate_ints_about_middle(vector[int] values): + """ + Test rotate_copy. + + >>> rotate_ints_about_middle([1, 2, 3, 4, 5]) + [3, 4, 5, 1, 2] + """ + cdef vector[int] out + cdef vector[int].iterator pivot = values.begin() + values.size()/2 + rotate_copy(values.begin(), pivot, values.end(), back_inserter(out)) + return out + + +def unique_ints(vector[int] values): + """ + Test unique. + + >>> unique_ints([1, 2, 3, 1, 2, 3, 3, 4, 5, 4, 5, 6, 7]) + [1, 2, 3, 4, 5, 6, 7] + """ + sort(values.begin(), values.end()) + values.erase(unique(values.begin(), values.end()), values.end()) + return values + + +cdef bool both_space(unsigned char lhs, unsigned char rhs): + return lhs == rhs == ord(' ') + + +def collapse_spaces(string text): + """ + Test unique (predicate version) using cppreference example for unique_copy. + + >>> print(collapse_spaces(b"The string with many spaces!").decode("ascii")) + The string with many spaces! + """ + last = unique(text.begin(), text.end(), &both_space) + text.erase(last, text.end()) + return text + + +def unique_ints2(vector[int] values): + """ + Test unique_copy. + + >>> unique_ints2([1, 2, 3, 1, 2, 3, 3, 4, 5, 4, 5, 6, 7]) + [1, 2, 3, 4, 5, 6, 7] + """ + cdef vector[int] out + sort(values.begin(), values.end()) + unique_copy(values.begin(), values.end(), back_inserter(out)) + return out + + +def collapse_spaces2(string text): + """ + Test unique_copy (predicate version) using cppreference example. + + >>> print(collapse_spaces2(b"The string with many spaces!").decode("ascii")) + The string with many spaces! + """ + cdef string out + unique_copy(text.begin(), text.end(), back_inserter(out), &both_space) + return out diff --git a/tests/run/cpp_stl_algo_nonmodifying_sequence_ops.pyx b/tests/run/cpp_stl_algo_nonmodifying_sequence_ops.pyx index 2679f4701..2b001b5f2 100644 --- a/tests/run/cpp_stl_algo_nonmodifying_sequence_ops.pyx +++ b/tests/run/cpp_stl_algo_nonmodifying_sequence_ops.pyx @@ -4,8 +4,8 @@ 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.algorithm cimport all_of, any_of, none_of, for_each, count, count_if, mismatch, find, find_if, find_if_not +from libcpp.algorithm cimport find_end, find_first_of, adjacent_find, search, search_n from libcpp.iterator cimport distance from libcpp.string cimport string from libcpp.vector cimport vector @@ -61,7 +61,23 @@ def count_ones(vector[int] values): return count(values.begin(), values.end(), 1) -def count_odd(vector[int] values): +cdef void add_one(int &i): + # https://github.com/cython/cython/issues/1863 + (&i)[0] += 1 + + +def increment_ints(vector[int] values): + """ + Test for_each. + + >>> increment_ints([3, 4, 2, 8, 15, 267]) + [4, 5, 3, 9, 16, 268] + """ + for_each(values.begin(), values.end(), &add_one) + return values + + +def count_odd(vector[int] values): """ Test count_if with is_odd predicate. @@ -174,7 +190,7 @@ def find_last_int_sequence2(vector[int] values, vector[int] target): 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) + result = find_end(values.begin(), values.end(), target.begin(), target.end(), &is_equal) if result != values.end(): return distance(values.begin(), result) else: @@ -264,7 +280,7 @@ def in_quote2(string quote, string word): >>> 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() + return search(quote.begin(), quote.end(), word.begin(), word.end(), &is_equal) != quote.end() def consecutive_values(string c, int count, char v): @@ -288,4 +304,4 @@ def consecutive_values2(string c, int count, char v): >>> consecutive_values2(b"1001010100010101001010101", 3, ord("0")) True """ - return search_n(c.begin(), c.end(), count, v, <bool (*)(int, int)>is_equal) != c.end() + return search_n(c.begin(), c.end(), count, v, &is_equal) != c.end() diff --git a/tests/run/libcpp_algo.pyx b/tests/run/libcpp_algo.pyx index 17f0cc79d..f969b22a6 100644 --- a/tests/run/libcpp_algo.pyx +++ b/tests/run/libcpp_algo.pyx @@ -21,8 +21,8 @@ def heapsort(l, bool reverse=False): cdef vector[int] v = l if reverse: - make_heap(v.begin(), v.end(), greater) - sort_heap(v.begin(), v.end(), greater) + make_heap(v.begin(), v.end(), &greater) + sort_heap(v.begin(), v.end(), &greater) else: make_heap(v.begin(), v.end()) sort_heap(v.begin(), v.end()) @@ -39,7 +39,7 @@ def partialsort(l, int k, reverse=False): """ cdef vector[int] v = l if reverse: - partial_sort(v.begin(), v.begin() + k, v.end(), greater) + partial_sort(v.begin(), v.begin() + k, v.end(), &greater) else: partial_sort(v.begin(), v.begin() + k, v.end()) return v @@ -54,7 +54,7 @@ def stdsort(l, reverse=False): """ cdef vector[int] v = l if reverse: - sort(v.begin(), v.end(), greater) + sort(v.begin(), v.end(), &greater) else: sort(v.begin(), v.end()) return v |