1 //===----------------------------------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 // UNSUPPORTED: c++03, c++11, c++14 10 // UNSUPPORTED: libcpp-has-no-incomplete-pstl 11 12 // template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, 13 // class ForwardIterator> 14 // ForwardIterator 15 // merge(ExecutionPolicy&& exec, 16 // ForwardIterator1 first1, ForwardIterator1 last1, 17 // ForwardIterator2 first2, ForwardIterator2 last2, 18 // ForwardIterator result); 19 // 20 // template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, 21 // class ForwardIterator, class Compare> 22 // ForwardIterator 23 // merge(ExecutionPolicy&& exec, 24 // ForwardIterator1 first1, ForwardIterator1 last1, 25 // ForwardIterator2 first2, ForwardIterator2 last2, 26 // ForwardIterator result, Compare comp); 27 28 #include <algorithm> 29 #include <array> 30 #include <cassert> 31 #include <functional> 32 #include <iterator> 33 #include <numeric> 34 #include <vector> 35 36 #include "type_algorithms.h" 37 #include "test_execution_policies.h" 38 #include "test_iterators.h" 39 40 template <class Iter1, class Iter2> 41 struct Test { 42 template <class Policy> 43 void operator()(Policy&& policy) { 44 { // simple test 45 int a[] = {1, 3, 5, 7, 9}; 46 int b[] = {2, 4, 6, 8, 10}; 47 std::array<int, std::size(a) + std::size(b)> out; 48 std::merge( 49 policy, Iter1(std::begin(a)), Iter1(std::end(a)), Iter2(std::begin(b)), Iter2(std::end(b)), std::begin(out)); 50 assert((out == std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10})); 51 } 52 53 { // check that it works with both ranges being empty 54 std::array<int, 0> a; 55 std::array<int, 0> b; 56 std::array<int, std::size(a) + std::size(b)> out; 57 std::merge(policy, 58 Iter1(std::data(a)), 59 Iter1(std::data(a) + std::size(a)), 60 Iter2(std::data(b)), 61 Iter2(std::data(b) + std::size(b)), 62 std::begin(out)); 63 } 64 { // check that it works with the first range being empty 65 std::array<int, 0> a; 66 int b[] = {2, 4, 6, 8, 10}; 67 std::array<int, std::size(a) + std::size(b)> out; 68 std::merge(policy, 69 Iter1(std::data(a)), 70 Iter1(std::data(a) + std::size(a)), 71 Iter2(std::begin(b)), 72 Iter2(std::end(b)), 73 std::begin(out)); 74 assert((out == std::array{2, 4, 6, 8, 10})); 75 } 76 77 { // check that it works with the second range being empty 78 int a[] = {2, 4, 6, 8, 10}; 79 std::array<int, 0> b; 80 std::array<int, std::size(a) + std::size(b)> out; 81 std::merge(policy, 82 Iter1(std::begin(a)), 83 Iter1(std::end(a)), 84 Iter2(std::data(b)), 85 Iter2(std::data(b) + std::size(b)), 86 std::begin(out)); 87 assert((out == std::array{2, 4, 6, 8, 10})); 88 } 89 90 { // check that it works when the ranges don't have the same length 91 int a[] = {2, 4, 6, 8, 10}; 92 int b[] = {3, 4}; 93 std::array<int, std::size(a) + std::size(b)> out; 94 std::merge( 95 policy, Iter1(std::begin(a)), Iter1(std::end(a)), Iter2(std::begin(b)), Iter2(std::end(b)), std::begin(out)); 96 assert((out == std::array{2, 3, 4, 4, 6, 8, 10})); 97 } 98 99 { // check that large ranges work 100 std::vector<int> a(100); 101 std::vector<int> b(100); 102 { 103 int i = 0; 104 for (auto& e : a) { 105 e = i; 106 i += 2; 107 } 108 } 109 110 { 111 int i = 1; 112 for (auto& e : b) { 113 e = i; 114 i += 2; 115 } 116 } 117 118 std::vector<int> out(std::size(a) + std::size(b)); 119 std::merge(policy, 120 Iter1(a.data()), 121 Iter1(a.data() + a.size()), 122 Iter2(b.data()), 123 Iter2(b.data() + b.size()), 124 std::begin(out)); 125 std::vector<int> expected(200); 126 std::iota(expected.begin(), expected.end(), 0); 127 assert(std::equal(out.begin(), out.end(), expected.begin())); 128 } 129 130 { // check that the predicate is used 131 int a[] = {10, 9, 8, 7}; 132 int b[] = {8, 4, 3}; 133 std::array<int, std::size(a) + std::size(b)> out; 134 std::merge( 135 policy, 136 Iter1(std::begin(a)), 137 Iter1(std::end(a)), 138 Iter2(std::begin(b)), 139 Iter2(std::end(b)), 140 std::begin(out), 141 std::greater{}); 142 assert((out == std::array{10, 9, 8, 8, 7, 4, 3})); 143 } 144 } 145 }; 146 147 int main(int, char**) { 148 types::for_each(types::forward_iterator_list<int*>{}, types::apply_type_identity{[](auto v) { 149 using Iter = typename decltype(v)::type; 150 types::for_each( 151 types::forward_iterator_list<int*>{}, 152 TestIteratorWithPolicies<types::partial_instantiation<Test, Iter>::template apply>{}); 153 }}); 154 155 return 0; 156 } 157