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

   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 }