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 <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
  39 template <class Iter1, class Iter2>
  40 struct 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(a)), Iter1(std::end(a)), Iter2(std::begin(b)), Iter2(std::end(b)), std::begin(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(a) + std::size(b)> out;
  56       std::merge(
  57           policy, Iter1(std::begin(a)), Iter1(std::end(a)), Iter2(std::begin(b)), Iter2(std::end(b)), std::begin(out));
  58     }
  59     { // check that it works with the first range being empty
  60       std::array<int, 0> a;
  61       int b[] = {2, 4, 6, 8, 10};
  62       std::array<int, std::size(a) + std::size(b)> out;
  63       std::merge(
  64           policy, Iter1(std::begin(a)), Iter1(std::end(a)), Iter2(std::begin(b)), Iter2(std::end(b)), std::begin(out));
  65       assert((out == std::array{2, 4, 6, 8, 10}));
  66     }
  67
  68     { // check that it works with the second range being empty
  69       int a[] = {2, 4, 6, 8, 10};
  70       std::array<int, 0> b;
  71       std::array<int, std::size(a) + std::size(b)> out;
  72       std::merge(
  73           policy, Iter1(std::begin(a)), Iter1(std::end(a)), Iter2(std::begin(b)), Iter2(std::end(b)), std::begin(out));
  74       assert((out == std::array{2, 4, 6, 8, 10}));
  75     }
  76
  77     { // check that it works when the ranges don't have the same length
  78       int a[] = {2, 4, 6, 8, 10};
  79       int b[] = {3, 4};
  80       std::array<int, std::size(a) + std::size(b)> out;
  81       std::merge(
  82           policy, Iter1(std::begin(a)), Iter1(std::end(a)), Iter2(std::begin(b)), Iter2(std::end(b)), std::begin(out));
  83       assert((out == std::array{2, 3, 4, 4, 6, 8, 10}));
  84     }
  85
  86     { // check that large ranges work
  87       std::vector<int> a(100);
  88       std::vector<int> b(100);
  89       {
  90         int i = 0;
  91         for (auto& e : a) {
  92           e = i;
  93           i += 2;
  94         }
  95       }
  96
  97       {
  98         int i = 1;
  99         for (auto& e : b) {
 100           e = i;
 101           i += 2;
 102         }
 103       }
 104
 105       std::vector<int> out(std::size(a) + std::size(b));
 106       std::merge(policy,
 107                  Iter1(a.data()),
 108                  Iter1(a.data() + a.size()),
 109                  Iter2(b.data()),
 110                  Iter2(b.data() + b.size()),
 111                  std::begin(out));
 112       std::vector<int> expected(200);
 113       std::iota(expected.begin(), expected.end(), 0);
 114       assert(std::equal(out.begin(), out.end(), expected.begin()));
 115     }
 116
 117     { // check that the predicate is used
 118       int a[] = {10, 9, 8, 7};
 119       int b[] = {8, 4, 3};
 120       std::array<int, std::size(a) + std::size(b)> out;
 121       std::merge(
 122           policy,
 123           Iter1(std::begin(a)),
 124           Iter1(std::end(a)),
 125           Iter2(std::begin(b)),
 126           Iter2(std::end(b)),
 127           std::begin(out),
 128           std::greater{});
 129       assert((out == std::array{10, 9, 8, 8, 7, 4, 3}));
 130     }
 131   }
 132 };
 133
 134 int main(int, char**) {
 135   types::for_each(types::forward_iterator_list<int*>{}, types::apply_type_identity{[](auto v) {
 136                     using Iter = typename decltype(v)::type;
 137                     types::for_each(
 138                         types::forward_iterator_list<int*>{},
 139                         TestIteratorWithPolicies<types::partial_instantiation<Test, Iter>::template apply>{});
 140                   }});
 141
 142   return 0;
 143 }