libstdc++-v3/testsuite/25_algorithms/pstl/alg_sorting/set.cc

   1 // -*- C++ -*-
   2 // { dg-options "-std=gnu++17 -ltbb" }
   3 // { dg-do run { target c++17 } }
   4 // { dg-timeout-factor 3 }
   5 // { dg-require-effective-target tbb-backend }
   6
   7 //===-- set.pass.cpp ------------------------------------------------------===//
   8 //
   9 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  10 // See https://llvm.org/LICENSE.txt for license information.
  11 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "pstl/pstl_test_config.h"
  16
  17 #ifdef PSTL_STANDALONE_TESTS
  18
  19 #include <cmath>
  20 #include <chrono>
  21
  22 #include "pstl/execution"
  23 #include "pstl/algorithm"
  24 #else
  25 #include <execution>
  26 #include <algorithm>
  27 #endif // PSTL_STANDALONE_TESTS
  28
  29 #include "pstl/test_utils.h"
  30
  31 using namespace TestUtils;
  32
  33 template <typename T>
  34 struct Num
  35 {
  36     T val;
  37
  38     Num() : val{} {}
  39     Num(const T& v) : val(v) {}
  40
  41     //for "includes" checks
  42     template <typename T1>
  43     bool
  44     operator<(const Num<T1>& v1) const
  45     {
  46         return val < v1.val;
  47     }
  48
  49     //The types Type1 and Type2 must be such that an object of type InputIt can be dereferenced and then implicitly converted to both of them
  50     template <typename T1>
  51     operator Num<T1>() const
  52     {
  53         return Num<T1>((T1)val);
  54     }
  55
  56     friend bool
  57     operator==(const Num& v1, const Num& v2)
  58     {
  59         return v1.val == v2.val;
  60     }
  61 };
  62
  63 struct test_one_policy
  64 {
  65     template <typename Policy, typename InputIterator1, typename InputIterator2, typename Compare>
  66     typename std::enable_if<!TestUtils::isReverse<InputIterator1>::value, void>::type
  67     operator()(Policy&& exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,
  68                Compare comp)
  69     {
  70         using T1 = typename std::iterator_traits<InputIterator1>::value_type;
  71
  72         auto n1 = std::distance(first1, last1);
  73         auto n2 = std::distance(first2, last2);
  74         auto n = n1 + n2;
  75         Sequence<T1> expect(n);
  76         Sequence<T1> out(n);
  77
  78         //1. set_union
  79         auto expect_res = std::set_union(first1, last1, first2, last2, expect.begin(), comp);
  80         auto res = std::set_union(exec, first1, last1, first2, last2, out.begin(), comp);
  81
  82         EXPECT_TRUE(expect_res - expect.begin() == res - out.begin(), "wrong result for set_union");
  83         EXPECT_EQ_N(expect.begin(), out.begin(), std::distance(out.begin(), res), "wrong set_union effect");
  84
  85         //2. set_intersection
  86         expect_res = std::set_intersection(first1, last1, first2, last2, expect.begin(), comp);
  87         res = std::set_intersection(exec, first1, last1, first2, last2, out.begin(), comp);
  88
  89         EXPECT_TRUE(expect_res - expect.begin() == res - out.begin(), "wrong result for set_intersection");
  90         EXPECT_EQ_N(expect.begin(), out.begin(), std::distance(out.begin(), res), "wrong set_intersection effect");
  91
  92         //3. set_difference
  93         expect_res = std::set_difference(first1, last1, first2, last2, expect.begin(), comp);
  94         res = std::set_difference(exec, first1, last1, first2, last2, out.begin(), comp);
  95
  96         EXPECT_TRUE(expect_res - expect.begin() == res - out.begin(), "wrong result for set_difference");
  97         EXPECT_EQ_N(expect.begin(), out.begin(), std::distance(out.begin(), res), "wrong set_difference effect");
  98
  99         //4. set_symmetric_difference
 100         expect_res = std::set_symmetric_difference(first1, last1, first2, last2, expect.begin(), comp);
 101         res = std::set_symmetric_difference(exec, first1, last1, first2, last2, out.begin(), comp);
 102
 103         EXPECT_TRUE(expect_res - expect.begin() == res - out.begin(), "wrong result for set_symmetric_difference");
 104         EXPECT_EQ_N(expect.begin(), out.begin(), std::distance(out.begin(), res),
 105                     "wrong set_symmetric_difference effect");
 106     }
 107
 108     template <typename Policy, typename InputIterator1, typename InputIterator2, typename Compare>
 109     typename std::enable_if<TestUtils::isReverse<InputIterator1>::value, void>::type
 110     operator()(Policy&& exec, InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2,
 111                Compare comp)
 112     {
 113     }
 114 };
 115
 116 template <typename T1, typename T2, typename Compare>
 117 void
 118 test_set(Compare compare)
 119 {
 120
 121     const std::size_t n_max = 100000;
 122
 123     // The rand()%(2*n+1) encourages generation of some duplicates.
 124     std::srand(4200);
 125
 126     for (std::size_t n = 0; n < n_max; n = n <= 16 ? n + 1 : size_t(3.1415 * n))
 127     {
 128         for (std::size_t m = 0; m < n_max; m = m <= 16 ? m + 1 : size_t(2.71828 * m))
 129         {
 130             //prepare the input ranges
 131             Sequence<T1> in1(n, [n](std::size_t k) { return rand() % (2 * k + 1); });
 132             Sequence<T2> in2(m, [m](std::size_t k) { return (m % 2) * rand() + rand() % (k + 1); });
 133
 134             std::sort(in1.begin(), in1.end(), compare);
 135             std::sort(in2.begin(), in2.end(), compare);
 136
 137             invoke_on_all_policies(test_one_policy(), in1.begin(), in1.end(), in2.cbegin(), in2.cend(), compare);
 138         }
 139     }
 140 }
 141
 142 template <typename T>
 143 struct test_non_const
 144 {
 145     template <typename Policy, typename InputIterator, typename OutputInterator>
 146     void
 147     operator()(Policy&& exec, InputIterator input_iter, OutputInterator out_iter)
 148     {
 149         set_difference(exec, input_iter, input_iter, input_iter, input_iter, out_iter, non_const(std::less<T>()));
 150
 151         set_intersection(exec, input_iter, input_iter, input_iter, input_iter, out_iter, non_const(std::less<T>()));
 152
 153         set_symmetric_difference(exec, input_iter, input_iter, input_iter, input_iter, out_iter,
 154                                  non_const(std::less<T>()));
 155
 156         set_union(exec, input_iter, input_iter, input_iter, input_iter, out_iter, non_const(std::less<T>()));
 157     }
 158 };
 159
 160 int32_t
 161 main()
 162 {
 163
 164     test_set<float64_t, float64_t>(__pstl::__internal::__pstl_less());
 165     test_set<Num<int64_t>, Num<int32_t>>([](const Num<int64_t>& x, const Num<int32_t>& y) { return x < y; });
 166
 167     test_algo_basic_double<int32_t>(run_for_rnd_fw<test_non_const<int32_t>>());
 168
 169     std::cout << done() << std::endl;
 170
 171     return 0;
 172 }