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 <iterator>
32#include <numeric>
33#include <vector>
34
35#include "type_algorithms.h"
36#include "test_execution_policies.h"
37#include "test_iterators.h"
38
39template <class Iter1, class Iter2>
40struct Test {
41 template <class Policy>
42 void operator()(Policy&& policy) {
43 { // simple test
44 int a[] = {1, 3, 5, 7, 9};
45 int b[] = {2, 4, 6, 8, 10};
46 std::array<int, std::size(a) + std::size(b)> out;
47 std::merge(
48 policy, Iter1(std::begin(arr&: a)), Iter1(std::end(arr&: a)), Iter2(std::begin(arr&: b)), Iter2(std::end(arr&: b)), std::begin(cont&: out));
49 assert((out == std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}));
50 }
51
52 { // check that it works with both ranges being empty
53 std::array<int, 0> a;
54 std::array<int, 0> b;
55 std::array<int, std::size(cont: a) + std::size(cont: b)> out;
56 std::merge(policy,
57 Iter1(std::data(cont&: a)),
58 Iter1(std::data(cont&: a) + std::size(cont: a)),
59 Iter2(std::data(cont&: b)),
60 Iter2(std::data(cont&: b) + std::size(cont: b)),
61 std::begin(cont&: out));
62 }
63 { // check that it works with the first range being empty
64 std::array<int, 0> a;
65 int b[] = {2, 4, 6, 8, 10};
66 std::array<int, std::size(cont: a) + std::size(b)> out;
67 std::merge(policy,
68 Iter1(std::data(cont&: a)),
69 Iter1(std::data(cont&: a) + std::size(cont: a)),
70 Iter2(std::begin(arr&: b)),
71 Iter2(std::end(arr&: b)),
72 std::begin(cont&: out));
73 assert((out == std::array{2, 4, 6, 8, 10}));
74 }
75
76 { // check that it works with the second range being empty
77 int a[] = {2, 4, 6, 8, 10};
78 std::array<int, 0> b;
79 std::array<int, std::size(a) + std::size(cont: b)> out;
80 std::merge(policy,
81 Iter1(std::begin(arr&: a)),
82 Iter1(std::end(arr&: a)),
83 Iter2(std::data(cont&: b)),
84 Iter2(std::data(cont&: b) + std::size(cont: b)),
85 std::begin(cont&: out));
86 assert((out == std::array{2, 4, 6, 8, 10}));
87 }
88
89 { // check that it works when the ranges don't have the same length
90 int a[] = {2, 4, 6, 8, 10};
91 int b[] = {3, 4};
92 std::array<int, std::size(a) + std::size(b)> out;
93 std::merge(
94 policy, Iter1(std::begin(arr&: a)), Iter1(std::end(arr&: a)), Iter2(std::begin(arr&: b)), Iter2(std::end(arr&: b)), std::begin(cont&: out));
95 assert((out == std::array{2, 3, 4, 4, 6, 8, 10}));
96 }
97
98 { // check that large ranges work
99 std::vector<int> a(100);
100 std::vector<int> b(100);
101 {
102 int i = 0;
103 for (auto& e : a) {
104 e = i;
105 i += 2;
106 }
107 }
108
109 {
110 int i = 1;
111 for (auto& e : b) {
112 e = i;
113 i += 2;
114 }
115 }
116
117 std::vector<int> out(std::size(cont: a) + std::size(cont: b));
118 std::merge(policy,
119 Iter1(a.data()),
120 Iter1(a.data() + a.size()),
121 Iter2(b.data()),
122 Iter2(b.data() + b.size()),
123 std::begin(cont&: out));
124 std::vector<int> expected(200);
125 std::iota(first: expected.begin(), last: expected.end(), value: 0);
126 assert(std::equal(out.begin(), out.end(), expected.begin()));
127 }
128
129 { // check that the predicate is used
130 int a[] = {10, 9, 8, 7};
131 int b[] = {8, 4, 3};
132 std::array<int, std::size(a) + std::size(b)> out;
133 std::merge(
134 policy,
135 Iter1(std::begin(arr&: a)),
136 Iter1(std::end(arr&: a)),
137 Iter2(std::begin(arr&: b)),
138 Iter2(std::end(arr&: b)),
139 std::begin(cont&: out),
140 std::greater{});
141 assert((out == std::array{10, 9, 8, 8, 7, 4, 3}));
142 }
143 }
144};
145
146int main(int, char**) {
147 types::for_each(types::forward_iterator_list<int*>{}, types::apply_type_identity{[](auto v) {
148 using Iter = typename decltype(v)::type;
149 types::for_each(
150 types::forward_iterator_list<int*>{},
151 TestIteratorWithPolicies<types::partial_instantiation<Test, Iter>::template apply>{});
152 }});
153
154 return 0;
155}
156

source code of libcxx/test/std/algorithms/alg.sorting/alg.merge/pstl.merge.pass.cpp