255 lines · 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-exception6//7//===----------------------------------------------------------------------===//8 9// <algorithm>10 11#include <algorithm>12#include <cassert>13#include <compare>14#include <cstddef>15#include <deque>16#include <ranges>17#include <type_traits>18#include <vector>19 20#include "test_macros.h"21 22template <class T>23struct Less {24 int* copies_;25 TEST_CONSTEXPR explicit Less(int* copies) : copies_(copies) {}26 TEST_CONSTEXPR_CXX14 Less(const Less& rhs) : copies_(rhs.copies_) { *copies_ += 1; }27 TEST_CONSTEXPR_CXX14 Less& operator=(const Less&) = default;28 TEST_CONSTEXPR bool operator()(T, T) const { return false; }29};30 31template <class T>32struct Equal {33 int* copies_;34 TEST_CONSTEXPR explicit Equal(int* copies) : copies_(copies) {}35 TEST_CONSTEXPR_CXX14 Equal(const Equal& rhs) : copies_(rhs.copies_) { *copies_ += 1; }36 TEST_CONSTEXPR_CXX14 Equal& operator=(const Equal&) = default;37 TEST_CONSTEXPR bool operator()(T, T) const { return true; }38};39 40template <class T>41struct UnaryVoid {42 int* copies_;43 TEST_CONSTEXPR explicit UnaryVoid(int* copies) : copies_(copies) {}44 TEST_CONSTEXPR_CXX14 UnaryVoid(const UnaryVoid& rhs) : copies_(rhs.copies_) { *copies_ += 1; }45 TEST_CONSTEXPR_CXX14 UnaryVoid& operator=(const UnaryVoid&) = default;46 TEST_CONSTEXPR_CXX14 void operator()(T) const {}47};48 49template <class T>50struct UnaryTrue {51 int* copies_;52 TEST_CONSTEXPR explicit UnaryTrue(int* copies) : copies_(copies) {}53 TEST_CONSTEXPR_CXX14 UnaryTrue(const UnaryTrue& rhs) : copies_(rhs.copies_) { *copies_ += 1; }54 TEST_CONSTEXPR_CXX14 UnaryTrue& operator=(const UnaryTrue&) = default;55 TEST_CONSTEXPR bool operator()(T) const { return true; }56};57 58template <class T>59struct NullaryValue {60 int* copies_;61 TEST_CONSTEXPR explicit NullaryValue(int* copies) : copies_(copies) {}62 TEST_CONSTEXPR_CXX14 NullaryValue(const NullaryValue& rhs) : copies_(rhs.copies_) { *copies_ += 1; }63 TEST_CONSTEXPR_CXX14 NullaryValue& operator=(const NullaryValue&) = default;64 TEST_CONSTEXPR T operator()() const { return 0; }65};66 67template <class T>68struct UnaryTransform {69 int* copies_;70 TEST_CONSTEXPR explicit UnaryTransform(int* copies) : copies_(copies) {}71 TEST_CONSTEXPR_CXX14 UnaryTransform(const UnaryTransform& rhs) : copies_(rhs.copies_) { *copies_ += 1; }72 TEST_CONSTEXPR_CXX14 UnaryTransform& operator=(const UnaryTransform&) = default;73 TEST_CONSTEXPR T operator()(T) const { return 0; }74};75 76template <class T>77struct BinaryTransform {78 int* copies_;79 TEST_CONSTEXPR explicit BinaryTransform(int* copies) : copies_(copies) {}80 TEST_CONSTEXPR_CXX14 BinaryTransform(const BinaryTransform& rhs) : copies_(rhs.copies_) { *copies_ += 1; }81 TEST_CONSTEXPR_CXX14 BinaryTransform& operator=(const BinaryTransform&) = default;82 TEST_CONSTEXPR T operator()(T, T) const { return 0; }83};84 85template <class T>86TEST_CONSTEXPR_CXX20 bool all_the_algorithms() {87 T a[10] = {};88 T b[10] = {};89 T* first = a;90 T* mid = a + 5;91 T* last = a + 10;92 T* first2 = b;93 T* mid2 = b + 5;94 T* last2 = b + 10;95 T value = 0;96 int count = 1;97 98 int copies = 0;99 (void)std::adjacent_find(first, last, Equal<T>(&copies));100 assert(copies == 0);101 (void)std::binary_search(first, last, value, Less<T>(&copies));102 assert(copies == 0);103 (void)std::count_if(first, last, UnaryTrue<T>(&copies));104 assert(copies == 0);105 (void)std::copy_if(first, last, first2, UnaryTrue<T>(&copies));106 assert(copies == 0);107 (void)std::equal(first, last, first2, Equal<T>(&copies));108 assert(copies == 0);109 (void)std::equal_range(first, last, value, Less<T>(&copies));110 assert(copies == 0);111 (void)std::find_end(first, last, first2, mid2, Equal<T>(&copies));112 assert(copies == 0);113 (void)std::find_first_of(first, last, first2, last2, Equal<T>(&copies));114 assert(copies == 0);115 (void)std::find_if(first, last, UnaryTrue<T>(&copies));116 assert(copies == 0);117 (void)std::find_if_not(first, last, UnaryTrue<T>(&copies));118 assert(copies == 0);119 (void)std::for_each(first, last, UnaryVoid<T>(&copies));120 assert(copies == 1);121 copies = 0;122 (void)std::generate(first, last, NullaryValue<T>(&copies));123 assert(copies == 0);124 (void)std::generate_n(first, count, NullaryValue<T>(&copies));125 assert(copies == 0);126 (void)std::includes(first, last, first2, last2, Less<T>(&copies));127 assert(copies == 0);128 (void)std::is_heap(first, last, Less<T>(&copies));129 assert(copies == 0);130 (void)std::is_heap_until(first, last, Less<T>(&copies));131 assert(copies == 0);132 (void)std::is_partitioned(first, last, UnaryTrue<T>(&copies));133 assert(copies == 0);134 (void)std::is_permutation(first, last, first2, Equal<T>(&copies));135 assert(copies == 0);136 (void)std::is_sorted(first, last, Less<T>(&copies));137 assert(copies == 0);138 (void)std::is_sorted_until(first, last, Less<T>(&copies));139 assert(copies == 0);140 if (!TEST_IS_CONSTANT_EVALUATED) {141 (void)std::inplace_merge(first, mid, last, Less<T>(&copies));142 assert(copies == 0);143 }144 (void)std::lexicographical_compare(first, last, first2, last2, Less<T>(&copies));145 assert(copies == 0);146 (void)std::lower_bound(first, last, value, Less<T>(&copies));147 assert(copies == 0);148 (void)std::make_heap(first, last, Less<T>(&copies));149 assert(copies == 0);150 (void)std::max(value, value, Less<T>(&copies));151 assert(copies == 0);152 (void)std::max_element(first, last, Less<T>(&copies));153 assert(copies == 0);154 (void)std::merge(first, mid, mid, last, first2, Less<T>(&copies));155 assert(copies == 0);156 (void)std::min(value, value, Less<T>(&copies));157 assert(copies == 0);158 (void)std::min_element(first, last, Less<T>(&copies));159 assert(copies == 0);160 (void)std::minmax(value, value, Less<T>(&copies));161 assert(copies == 0);162 (void)std::minmax_element(first, last, Less<T>(&copies));163 assert(copies == 0);164 (void)std::mismatch(first, last, first2, Equal<T>(&copies));165 assert(copies == 0);166 (void)std::next_permutation(first, last, Less<T>(&copies));167 assert(copies == 0);168 (void)std::nth_element(first, mid, last, Less<T>(&copies));169 assert(copies == 0);170 (void)std::partial_sort(first, mid, last, Less<T>(&copies));171 assert(copies == 0);172 (void)std::partial_sort_copy(first, last, first2, mid2, Less<T>(&copies));173 assert(copies == 0);174 (void)std::partition(first, last, UnaryTrue<T>(&copies));175 assert(copies == 0);176 (void)std::partition_copy(first, last, first2, last2, UnaryTrue<T>(&copies));177 assert(copies == 0);178 (void)std::partition_point(first, last, UnaryTrue<T>(&copies));179 assert(copies == 0);180 (void)std::pop_heap(first, last, Less<T>(&copies));181 assert(copies == 0);182 (void)std::prev_permutation(first, last, Less<T>(&copies));183 assert(copies == 0);184 (void)std::push_heap(first, last, Less<T>(&copies));185 assert(copies == 0);186 (void)std::remove_copy_if(first, last, first2, UnaryTrue<T>(&copies));187 assert(copies == 0);188 (void)std::remove_if(first, last, UnaryTrue<T>(&copies));189 assert(copies == 0);190 (void)std::replace_copy_if(first, last, first2, UnaryTrue<T>(&copies), value);191 assert(copies == 0);192 (void)std::replace_if(first, last, UnaryTrue<T>(&copies), value);193 assert(copies == 0);194 (void)std::search(first, last, first2, mid2, Equal<T>(&copies));195 assert(copies == 0);196 (void)std::search_n(first, last, count, value, Equal<T>(&copies));197 assert(copies == 0);198 (void)std::set_difference(first, mid, mid, last, first2, Less<T>(&copies));199 assert(copies == 0);200 (void)std::set_intersection(first, mid, mid, last, first2, Less<T>(&copies));201 assert(copies == 0);202 (void)std::set_symmetric_difference(first, mid, mid, last, first2, Less<T>(&copies));203 assert(copies == 0);204 (void)std::set_union(first, mid, mid, last, first2, Less<T>(&copies));205 assert(copies == 0);206 (void)std::sort(first, first + 3, Less<T>(&copies));207 assert(copies == 0);208 (void)std::sort(first, first + 4, Less<T>(&copies));209 assert(copies == 0);210 (void)std::sort(first, first + 5, Less<T>(&copies));211 assert(copies == 0);212 (void)std::sort(first, last, Less<T>(&copies));213 assert(copies == 0);214 (void)std::sort_heap(first, last, Less<T>(&copies));215 assert(copies == 0);216 if (!TEST_IS_CONSTANT_EVALUATED) {217 (void)std::stable_partition(first, last, UnaryTrue<T>(&copies));218 assert(copies == 0);219 }220 if (!TEST_IS_CONSTANT_EVALUATED) {221 (void)std::stable_sort(first, last, Less<T>(&copies));222 assert(copies == 0);223 }224 (void)std::transform(first, last, first2, UnaryTransform<T>(&copies));225 assert(copies == 0);226 (void)std::transform(first, mid, mid, first2, BinaryTransform<T>(&copies));227 assert(copies == 0);228 (void)std::unique(first, last, Equal<T>(&copies));229 assert(copies == 0);230 (void)std::unique_copy(first, last, first2, Equal<T>(&copies));231 assert(copies == 0);232 (void)std::upper_bound(first, last, value, Less<T>(&copies));233 assert(copies == 0);234 235 return true;236}237 238bool test_segmented_iterator() {239 int copies = 0;240 std::deque<int> dq(10);241 (void)std::for_each(dq.begin(), dq.end(), UnaryVoid<int>(&copies));242 assert(copies == 1);243 copies = 0;244 245 return true;246}247 248int main(int, char**) {249 all_the_algorithms<void*>();250 all_the_algorithms<int>();251 assert(test_segmented_iterator());252 253 return 0;254}255