1 //===----------------------------------------------------------------------===//
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
7 //===----------------------------------------------------------------------===//
9 // UNSUPPORTED: c++03, c++11, c++14
13 // template <class PopulationIterator, class SampleIterator, class Distance,
14 // class UniformRandomNumberGenerator>
15 // SampleIterator sample(PopulationIterator first, PopulationIterator last,
16 // SampleIterator out, Distance n,
17 // UniformRandomNumberGenerator &&g);
21 #include <type_traits>
25 #include "test_iterators.h"
26 #include "test_macros.h"
28 struct ReservoirSampleExpectations
{
34 int ReservoirSampleExpectations::oa1
[] = {10, 5, 9, 4};
35 int ReservoirSampleExpectations::oa2
[] = {5, 2, 10, 4};
37 struct SelectionSampleExpectations
{
43 int SelectionSampleExpectations::oa1
[] = {1, 4, 6, 7};
44 int SelectionSampleExpectations::oa2
[] = {1, 2, 6, 8};
46 template <class IteratorCategory
> struct TestExpectations
47 : public SelectionSampleExpectations
{};
50 struct TestExpectations
<std::input_iterator_tag
>
51 : public ReservoirSampleExpectations
{};
53 template <template<class...> class PopulationIteratorType
, class PopulationItem
,
54 template<class...> class SampleIteratorType
, class SampleItem
>
56 typedef PopulationIteratorType
<PopulationItem
*> PopulationIterator
;
57 typedef SampleIteratorType
<SampleItem
*> SampleIterator
;
58 PopulationItem ia
[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
59 const unsigned is
= sizeof(ia
) / sizeof(ia
[0]);
60 typedef TestExpectations
<typename
std::iterator_traits
<
61 PopulationIterator
>::iterator_category
> Expectations
;
62 const unsigned os
= Expectations::os
;
64 const int *oa1
= Expectations::oa1
;
65 ((void)oa1
); // Prevent unused warning
66 const int *oa2
= Expectations::oa2
;
67 ((void)oa2
); // Prevent unused warning
69 SampleIterator end
= std::sample(PopulationIterator(ia
),
70 PopulationIterator(ia
+ is
),
71 SampleIterator(oa
), os
, g
);
72 assert(static_cast<std::size_t>(base(end
) - oa
) == std::min(os
, is
));
73 // sample() is deterministic but non-reproducible;
74 // its results can vary between implementations.
75 LIBCPP_ASSERT(std::equal(oa
, oa
+ os
, oa1
));
76 end
= std::sample(PopulationIterator(ia
),
77 PopulationIterator(ia
+ is
),
78 SampleIterator(oa
), os
, std::move(g
));
79 assert(static_cast<std::size_t>(base(end
) - oa
) == std::min(os
, is
));
80 LIBCPP_ASSERT(std::equal(oa
, oa
+ os
, oa2
));
83 template <template<class...> class PopulationIteratorType
, class PopulationItem
,
84 template<class...> class SampleIteratorType
, class SampleItem
>
85 void test_empty_population() {
86 typedef PopulationIteratorType
<PopulationItem
*> PopulationIterator
;
87 typedef SampleIteratorType
<SampleItem
*> SampleIterator
;
88 PopulationItem ia
[] = {42};
89 const unsigned os
= 4;
93 std::sample(PopulationIterator(ia
), PopulationIterator(ia
),
94 SampleIterator(oa
), os
, g
);
95 assert(base(end
) == oa
);
98 template <template<class...> class PopulationIteratorType
, class PopulationItem
,
99 template<class...> class SampleIteratorType
, class SampleItem
>
100 void test_empty_sample() {
101 typedef PopulationIteratorType
<PopulationItem
*> PopulationIterator
;
102 typedef SampleIteratorType
<SampleItem
*> SampleIterator
;
103 PopulationItem ia
[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
104 const unsigned is
= sizeof(ia
) / sizeof(ia
[0]);
108 std::sample(PopulationIterator(ia
), PopulationIterator(ia
+ is
),
109 SampleIterator(oa
), 0, g
);
110 assert(base(end
) == oa
);
113 template <template<class...> class PopulationIteratorType
, class PopulationItem
,
114 template<class...> class SampleIteratorType
, class SampleItem
>
115 void test_small_population() {
116 // The population size is less than the sample size.
117 typedef PopulationIteratorType
<PopulationItem
*> PopulationIterator
;
118 typedef SampleIteratorType
<SampleItem
*> SampleIterator
;
119 PopulationItem ia
[] = {1, 2, 3, 4, 5};
120 const unsigned is
= sizeof(ia
) / sizeof(ia
[0]);
121 const unsigned os
= 8;
123 const SampleItem oa1
[] = {1, 2, 3, 4, 5};
125 SampleIterator end
= std::sample(PopulationIterator(ia
),
126 PopulationIterator(ia
+ is
),
127 SampleIterator(oa
), os
, g
);
128 assert(static_cast<std::size_t>(base(end
) - oa
) == std::min(os
, is
));
129 typedef typename
std::iterator_traits
<PopulationIterator
>::iterator_category PopulationCategory
;
130 if (std::is_base_of
<std::forward_iterator_tag
, PopulationCategory
>::value
) {
131 assert(std::equal(oa
, base(end
), oa1
));
133 assert(std::is_permutation(oa
, base(end
), oa1
));
137 int main(int, char**) {
138 test
<cpp17_input_iterator
, int, random_access_iterator
, int>();
139 test
<forward_iterator
, int, cpp17_output_iterator
, int>();
140 test
<forward_iterator
, int, random_access_iterator
, int>();
142 test
<cpp17_input_iterator
, int, random_access_iterator
, double>();
143 test
<forward_iterator
, int, cpp17_output_iterator
, double>();
144 test
<forward_iterator
, int, random_access_iterator
, double>();
146 test_empty_population
<cpp17_input_iterator
, int, random_access_iterator
, int>();
147 test_empty_population
<forward_iterator
, int, cpp17_output_iterator
, int>();
148 test_empty_population
<forward_iterator
, int, random_access_iterator
, int>();
150 test_empty_sample
<cpp17_input_iterator
, int, random_access_iterator
, int>();
151 test_empty_sample
<forward_iterator
, int, cpp17_output_iterator
, int>();
152 test_empty_sample
<forward_iterator
, int, random_access_iterator
, int>();
154 test_small_population
<cpp17_input_iterator
, int, random_access_iterator
, int>();
155 test_small_population
<forward_iterator
, int, cpp17_output_iterator
, int>();
156 test_small_population
<forward_iterator
, int, random_access_iterator
, int>();