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
40template <class Iter1, class Iter2>
41struct 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(arr&: a)), Iter1(std::end(arr&: a)), Iter2(std::begin(arr&: b)), Iter2(std::end(arr&: b)), std::begin(cont&: 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(cont: a) + std::size(cont: b)> out;
57 std::merge(policy,
58 Iter1(std::data(cont&: a)),
59 Iter1(std::data(cont&: a) + std::size(cont: a)),
60 Iter2(std::data(cont&: b)),
61 Iter2(std::data(cont&: b) + std::size(cont: b)),
62 std::begin(cont&: 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(cont: a) + std::size(b)> out;
68 std::merge(policy,
69 Iter1(std::data(cont&: a)),
70 Iter1(std::data(cont&: a) + std::size(cont: a)),
71 Iter2(std::begin(arr&: b)),
72 Iter2(std::end(arr&: b)),
73 std::begin(cont&: 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(cont: b)> out;
81 std::merge(policy,
82 Iter1(std::begin(arr&: a)),
83 Iter1(std::end(arr&: a)),
84 Iter2(std::data(cont&: b)),
85 Iter2(std::data(cont&: b) + std::size(cont: b)),
86 std::begin(cont&: 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(arr&: a)), Iter1(std::end(arr&: a)), Iter2(std::begin(arr&: b)), Iter2(std::end(arr&: b)), std::begin(cont&: 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(cont: a) + std::size(cont: 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(cont&: out));
125 std::vector<int> expected(200);
126 std::iota(first: expected.begin(), last: expected.end(), value: 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(arr&: a)),
137 Iter1(std::end(arr&: a)),
138 Iter2(std::begin(arr&: b)),
139 Iter2(std::end(arr&: b)),
140 std::begin(cont&: out),
141 std::greater{});
142 assert((out == std::array{10, 9, 8, 8, 7, 4, 3}));
143 }
144 }
145};
146
147int 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

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