17#ifndef LLVM_ADT_STLEXTRAS_H
18#define LLVM_ADT_STLEXTRAS_H
26#include "llvm/Config/abi-breaking.h"
34#include <initializer_list>
43#ifdef EXPENSIVE_CHECKS
57template <
typename RangeT>
59 ->
decltype(begin(std::forward<RangeT>(range))) {
60 return begin(std::forward<RangeT>(range));
65template <
typename RangeT>
67 ->
decltype(end(std::forward<RangeT>(range))) {
68 return end(std::forward<RangeT>(range));
75 T &&rhs)
noexcept(
noexcept(swap(std::declval<T>(),
76 std::declval<T>()))) {
77 swap(std::forward<T>(lhs), std::forward<T>(rhs));
82template <
typename RangeT>
84 ->
decltype(
size(std::forward<RangeT>(range))) {
85 return size(std::forward<RangeT>(range));
92template <
typename RangeT>
100template <
typename RangeT>
116template <
typename RangeT>
124template <
typename RangeT>
127template <
typename RangeT>
129 std::remove_reference_t<decltype(*adl_begin(std::declval<RangeT &>()))>;
138 using type = std::add_pointer_t<std::add_const_t<T>>;
142 using type = std::add_lvalue_reference_t<std::add_const_t<T>>;
146template <
class,
template <
class...>
class Op,
class... Args>
struct detector {
149template <
template <
class...>
class Op,
class... Args>
162template <
template <
class...>
class Op,
class... Args>
169template <typename T, bool isClass = std::is_class<T>::value>
173template <
typename ClassType,
typename ReturnType,
typename... Args>
176 enum { num_args =
sizeof...(Args) };
182 template <
size_t Index>
183 using arg_t = std::tuple_element_t<
Index, std::tuple<Args...>>;
186template <
typename ClassType,
typename ReturnType,
typename... Args>
190template <
typename ReturnType,
typename... Args>
193 enum { num_args =
sizeof...(Args) };
200 using arg_t = std::tuple_element_t<i, std::tuple<Args...>>;
202template <
typename ReturnType,
typename... Args>
206template <
typename ReturnType,
typename... Args>
212template <
typename T,
typename... Ts>
213using is_one_of = std::disjunction<std::is_same<T, Ts>...>;
217template <
typename T,
typename... Ts>
222template <
typename T,
typename... Us>
224 : std::integral_constant<bool, !is_one_of<T, Us...>::value &&
225 TypesAreDistinct<Us...>::value> {};
238template <
typename... Ts>
240 : std::integral_constant<bool, detail::TypesAreDistinct<Ts...>::value> {};
253template <
typename T,
typename U,
typename... Us>
255 : std::integral_constant<size_t, 1 + FirstIndexOfType<T, Us...>::value> {};
256template <
typename T,
typename... Us>
262template <
size_t I,
typename... Ts>
267template <
typename EnumTy1,
typename EnumTy2,
268 typename UT1 = std::enable_if_t<std::is_enum<EnumTy1>::value,
269 std::underlying_type_t<EnumTy1>>,
270 typename UT2 = std::enable_if_t<std::is_enum<EnumTy2>::value,
271 std::underlying_type_t<EnumTy2>>>
273 return static_cast<UT1
>(
LHS) +
static_cast<UT2
>(
RHS);
280namespace callable_detail {
293 bool = std::is_function_v<std::remove_pointer_t<remove_cvref_t<T>>>>
295 using value_type = std::remove_reference_t<T>;
296 using reference = value_type &;
297 using const_reference = value_type
const &;
299 std::optional<value_type> Obj;
301 static_assert(!std::is_pointer_v<value_type>,
302 "Pointers to non-functions are not callable.");
314 Obj.emplace(*
Other.Obj);
321 Obj.emplace(std::move(*
Other.Obj));
325 template <
typename... Pn,
326 std::enable_if_t<std::is_invocable_v<
T, Pn...>,
int> = 0>
327 decltype(
auto)
operator()(Pn &&...Params) {
328 return (*Obj)(std::forward<Pn>(Params)...);
331 template <
typename... Pn,
332 std::enable_if_t<std::is_invocable_v<
T const, Pn...>,
int> = 0>
333 decltype(
auto)
operator()(Pn &&...Params)
const {
334 return (*Obj)(std::forward<Pn>(Params)...);
337 bool valid()
const {
return Obj != std::nullopt; }
338 bool reset() {
return Obj = std::nullopt; }
340 operator reference() {
return *Obj; }
341 operator const_reference()
const {
return *Obj; }
347 static constexpr bool IsPtr = std::is_pointer_v<remove_cvref_t<T>>;
349 using StorageT = std::conditional_t<IsPtr, T, std::remove_reference_t<T> *>;
350 using CastT = std::conditional_t<IsPtr, T, T &>;
353 StorageT Func =
nullptr;
356 template <
typename In>
static constexpr auto convertIn(In &&
I) {
357 if constexpr (IsPtr) {
376 !std::is_same_v<remove_cvref_t<FnPtrOrRef>,
Callable>,
int
381 template <
typename... Pn,
382 std::enable_if_t<std::is_invocable_v<
T, Pn...>,
int> = 0>
383 decltype(
auto)
operator()(Pn &&...Params)
const {
384 return Func(std::forward<Pn>(Params)...);
387 bool valid()
const {
return Func !=
nullptr; }
390 operator T const &()
const {
391 if constexpr (IsPtr) {
395 static_assert(std::is_reference_v<T>,
396 "Expected a reference to a function.");
407 auto B = std::begin(
C),
E = std::end(
C);
408 return B !=
E && std::next(
B) ==
E;
413template <
typename T>
auto drop_begin(
T &&RangeOrContainer,
size_t N = 1) {
420template <
typename T>
auto drop_end(
T &&RangeOrContainer,
size_t N = 1) {
422 std::prev(
adl_end(RangeOrContainer),
N));
428template <
typename ItTy,
typename FuncTy,
429 typename ReferenceTy =
430 decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))>
433 mapped_iterator<ItTy, FuncTy>, ItTy,
434 typename std::iterator_traits<ItTy>::iterator_category,
435 std::remove_reference_t<ReferenceTy>,
436 typename std::iterator_traits<ItTy>::difference_type,
437 std::remove_reference_t<ReferenceTy> *, ReferenceTy> {
455template <
class ItTy,
class FuncTy>
460template <
class ContainerTy,
class FuncTy>
470template <
typename DerivedT,
typename ItTy,
typename ReferenceTy>
474 typename std::iterator_traits<ItTy>::iterator_category,
475 std::remove_reference_t<ReferenceTy>,
476 typename std::iterator_traits<ItTy>::difference_type,
477 std::remove_reference_t<ReferenceTy> *, ReferenceTy> {
487 return static_cast<const DerivedT &
>(*this).mapElement(*this->I);
496 template <
typename Inner>
497 static yes&
test(Inner *
I,
decltype(
I->rbegin()) * =
nullptr);
500 static no&
test(...);
503 static const bool value =
sizeof(test<Ty>(
nullptr)) ==
sizeof(yes);
507template <
typename Ty>
511template <
typename ContainerTy>
auto reverse(ContainerTy &&
C) {
515 return make_range(std::make_reverse_iterator(std::end(
C)),
516 std::make_reverse_iterator(std::begin(
C)));
535template <
typename WrappedIteratorT,
typename PredicateT,
typename IterTag>
538 filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
540 std::common_type_t<IterTag,
541 typename std::iterator_traits<
542 WrappedIteratorT>::iterator_category>> {
550 while (this->I !=
End && !
Pred(*this->I))
566 using BaseT::operator++;
574 decltype(
auto)
operator*()
const {
575 assert(BaseT::wrapped() !=
End &&
"Cannot dereference end iterator!");
576 return BaseT::operator*();
579 decltype(
auto) operator->()
const {
580 assert(BaseT::wrapped() !=
End &&
"Cannot dereference end iterator!");
581 return BaseT::operator->();
587 typename IterTag = std::forward_iterator_tag>
599template <
typename WrappedIteratorT,
typename PredicateT>
601 std::bidirectional_iterator_tag>
603 std::bidirectional_iterator_tag> {
606 void findPrevValid() {
607 while (!this->
Pred(*this->I))
612 using BaseT::operator--;
630 using type = std::forward_iterator_tag;
634 using type = std::bidirectional_iterator_tag;
642 std::bidirectional_iterator_tag,
643 typename std::iterator_traits<IterT>::iterator_category>
::value>
::type;
650template <
typename WrappedIteratorT,
typename PredicateT>
662template <
typename RangeT,
typename PredicateT>
665 using FilterIteratorT =
668 FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
669 std::end(std::forward<RangeT>(Range)), Pred),
670 FilterIteratorT(std::end(std::forward<RangeT>(Range)),
671 std::end(std::forward<RangeT>(Range)), Pred));
691template <
typename WrappedIteratorT>
694 WrappedIteratorT, std::input_iterator_tag> {
697 using PointerT =
typename std::iterator_traits<WrappedIteratorT>::pointer;
700#if LLVM_ENABLE_ABI_BREAKING_CHECKS
701 bool IsEarlyIncremented =
false;
707 using BaseT::operator*;
708 decltype(*std::declval<WrappedIteratorT>())
operator*() {
709#if LLVM_ENABLE_ABI_BREAKING_CHECKS
710 assert(!IsEarlyIncremented &&
"Cannot dereference twice!");
711 IsEarlyIncremented =
true;
716 using BaseT::operator++;
718#if LLVM_ENABLE_ABI_BREAKING_CHECKS
719 assert(IsEarlyIncremented &&
"Cannot increment before dereferencing!");
720 IsEarlyIncremented =
false;
727#if LLVM_ENABLE_ABI_BREAKING_CHECKS
728 assert(!
LHS.IsEarlyIncremented &&
"Cannot compare after dereferencing!");
730 return (
const BaseT &)
LHS == (
const BaseT &)
RHS;
746template <
typename RangeT>
747iterator_range<early_inc_iterator_impl<detail::IterOfRange<RangeT>>>
749 using EarlyIncIteratorT =
751 return make_range(EarlyIncIteratorT(std::begin(std::forward<RangeT>(Range))),
752 EarlyIncIteratorT(std::end(std::forward<RangeT>(Range))));
756template <
typename R,
typename UnaryPredicate>
757bool all_of(R &&range, UnaryPredicate
P);
759template <
typename R,
typename UnaryPredicate>
760bool any_of(R &&range, UnaryPredicate
P);
762template <
typename T>
bool all_equal(std::initializer_list<T> Values);
764template <
typename R>
constexpr size_t range_size(R &&Range);
773 using type = std::tuple<decltype(*declval<Iters>())...>;
776template <
typename ZipType,
typename ReferenceTupleType,
typename... Iters>
780 std::bidirectional_iterator_tag,
781 typename std::iterator_traits<Iters>::iterator_category...>,
784 typename std::iterator_traits<
785 std::tuple_element_t<0, std::tuple<Iters...>>>::difference_type,
790 ReferenceTupleType *, ReferenceTupleType>;
792template <
typename ZipType,
typename ReferenceTupleType,
typename... Iters>
805 template <
size_t... Ns>
void tup_inc(std::index_sequence<Ns...>) {
809 template <
size_t... Ns>
void tup_dec(std::index_sequence<Ns...>) {
813 template <
size_t... Ns>
815 std::index_sequence<Ns...>)
const {
827 return static_cast<ZipType &
>(*this);
832 "All inner iterators must be at least bidirectional.");
834 return static_cast<ZipType &
>(*this);
843template <
typename... Iters>
845 typename ZipTupleType<Iters...>::type, Iters...> {
847 Iters...>::zip_common;
854template <
typename... Iters>
856 :
zip_common<zip_shortest<Iters...>, typename ZipTupleType<Iters...>::type,
859 Iters...>::zip_common;
862 return any_iterator_equals(other, std::index_sequence_for<Iters...>{});
866 template <
size_t... Ns>
868 std::index_sequence<Ns...>)
const {
875template <
template <
typename...>
class ItType,
typename TupleStorageType,
876 typename IndexSequence>
880template <
template <
typename...>
class ItType,
typename... Args,
883 std::index_sequence<Ns...>> {
885 std::get<Ns>(declval<std::tuple<Args...> &>())))...>;
889template <
template <
typename...>
class ItType,
typename... Args,
892 std::index_sequence<Ns...>> {
894 std::get<Ns>(declval<
const std::tuple<Args...> &>())))...>;
897template <
template <
typename...>
class ItType,
typename... Args>
class zippy {
899 std::tuple<Args...> storage;
900 using IndexSequence = std::index_sequence_for<Args...>;
904 IndexSequence>::type;
907 IndexSequence>::type;
923 template <
size_t... Ns>
927 template <
size_t... Ns>
iterator begin_impl(std::index_sequence<Ns...>) {
931 template <
size_t... Ns>
935 template <
size_t... Ns>
iterator end_impl(std::index_sequence<Ns...>) {
944template <
typename T,
typename U,
typename...
Args>
948 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(
args)...);
954template <
typename T,
typename U,
typename... Args>
958 "Iteratees do not have equal length");
960 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(
args)...);
967template <
typename T,
typename U,
typename... Args>
971 "First iteratee is not the shortest");
974 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(
args)...);
978template <
typename Iter>
985template <
typename Iter>
987 std::remove_const_t<std::remove_reference_t<
decltype(*I)>>> {
994 using type = std::optional<std::remove_const_t<
995 std::remove_reference_t<decltype(*std::declval<Iter>())>>>;
999 using type = std::tuple<typename ZipLongestItemType<Iters>::type...>;
1002template <
typename... Iters>
1005 zip_longest_iterator<Iters...>,
1007 std::forward_iterator_tag,
1008 typename std::iterator_traits<Iters>::iterator_category...>,
1009 typename ZipLongestTupleType<Iters...>::type,
1010 typename std::iterator_traits<
1011 std::tuple_element_t<0, std::tuple<Iters...>>>::difference_type,
1012 typename ZipLongestTupleType<Iters...>::type *,
1013 typename ZipLongestTupleType<Iters...>::type> {
1018 std::tuple<Iters...> iterators;
1019 std::tuple<Iters...> end_iterators;
1021 template <
size_t... Ns>
1023 std::index_sequence<Ns...>)
const {
1024 return ((std::get<Ns>(this->iterators) != std::get<Ns>(other.iterators)) ||
1028 template <
size_t... Ns>
value_type deref(std::index_sequence<Ns...>)
const {
1030 deref_or_none(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
1033 template <
size_t... Ns>
1034 decltype(iterators) tup_inc(std::index_sequence<Ns...>)
const {
1035 return std::tuple<Iters...>(
1036 next_or_end(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
1041 : iterators(
std::forward<Iters>(ts.first)...),
1042 end_iterators(
std::forward<Iters>(ts.second)...) {}
1045 return deref(std::index_sequence_for<Iters...>{});
1049 iterators = tup_inc(std::index_sequence_for<Iters...>{});
1054 return !
test(other, std::index_sequence_for<Iters...>{});
1069 std::tuple<Args...> ts;
1071 template <
size_t... Ns>
1072 iterator begin_impl(std::index_sequence<Ns...>)
const {
1074 adl_end(std::get<Ns>(ts)))...);
1077 template <
size_t... Ns>
iterator end_impl(std::index_sequence<Ns...>)
const {
1079 adl_end(std::get<Ns>(ts)))...);
1086 return begin_impl(std::index_sequence_for<Args...>{});
1088 iterator end()
const {
return end_impl(std::index_sequence_for<Args...>{}); }
1095template <
typename T,
typename U,
typename... Args>
1099 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(
args)...);
1112template <
typename ValueT,
typename... IterTs>
1115 std::forward_iterator_tag, ValueT> {
1116 using BaseT =
typename concat_iterator::iterator_facade_base;
1124 std::tuple<IterTs...> Begins;
1125 std::tuple<IterTs...> Ends;
1131 template <
size_t Index>
bool incrementHelper() {
1132 auto &Begin = std::get<Index>(Begins);
1133 auto &
End = std::get<Index>(Ends);
1144 template <
size_t... Ns>
void increment(std::index_sequence<Ns...>) {
1147 &concat_iterator::incrementHelper<Ns>...};
1150 for (
auto &IncrementHelperFn : IncrementHelperFns)
1151 if ((this->*IncrementHelperFn)())
1160 template <
size_t Index>
ValueT *getHelper()
const {
1161 auto &Begin = std::get<Index>(Begins);
1162 auto &
End = std::get<Index>(Ends);
1173 template <
size_t... Ns>
ValueT &get(std::index_sequence<Ns...>)
const {
1176 &concat_iterator::getHelper<Ns>...};
1179 for (
auto &GetHelperFn : GetHelperFns)
1180 if (
ValueT *
P = (this->*GetHelperFn)())
1183 llvm_unreachable(
"Attempted to get a pointer from an end concat iterator!");
1191 template <
typename... RangeTs>
1193 : Begins(
std::begin(Ranges)...), Ends(
std::end(Ranges)...) {}
1195 using BaseT::operator++;
1198 increment(std::index_sequence_for<IterTs...>());
1203 return get(std::index_sequence_for<IterTs...>());
1207 return Begins ==
RHS.Begins && Ends ==
RHS.Ends;
1222 decltype(std::begin(std::declval<RangeTs &>()))...>;
1225 std::tuple<RangeTs...> Ranges;
1227 template <
size_t... Ns>
1228 iterator begin_impl(std::index_sequence<Ns...>) {
1229 return iterator(std::get<Ns>(Ranges)...);
1231 template <
size_t... Ns>
1232 iterator begin_impl(std::index_sequence<Ns...>)
const {
1233 return iterator(std::get<Ns>(Ranges)...);
1235 template <
size_t... Ns>
iterator end_impl(std::index_sequence<Ns...>) {
1237 std::end(std::get<Ns>(Ranges)))...);
1239 template <
size_t... Ns>
iterator end_impl(std::index_sequence<Ns...>)
const {
1241 std::end(std::get<Ns>(Ranges)))...);
1246 : Ranges(
std::forward<RangeTs>(Ranges)...) {}
1249 return begin_impl(std::index_sequence_for<RangeTs...>{});
1252 return begin_impl(std::index_sequence_for<RangeTs...>{});
1255 return end_impl(std::index_sequence_for<RangeTs...>{});
1258 return end_impl(std::index_sequence_for<RangeTs...>{});
1267template <
typename ValueT,
typename... RangeTs>
1269 static_assert(
sizeof...(RangeTs) > 1,
1270 "Need more than one range to concatenate!");
1272 std::forward<RangeTs>(Ranges)...);
1277template <
typename DerivedT,
typename BaseT,
typename T,
1278 typename PointerT =
T *,
typename ReferenceT =
T &>
1281 std::random_access_iterator_tag, T,
1282 std::ptrdiff_t, PointerT, ReferenceT> {
1297 this->
index += offset;
1298 return static_cast<DerivedT &
>(*this);
1301 this->
index -= offset;
1302 return static_cast<DerivedT &
>(*this);
1329template <
typename DerivedT,
typename BaseT,
typename T,
1330 typename PointerT =
T *,
typename ReferenceT =
T &>
1337 PointerT, ReferenceT> {
1341 return DerivedT::dereference_iterator(this->
getBase(), this->
getIndex());
1373 return (*
this)[
size() - 1];
1377 template <
typename OtherT>
1379 const OtherT &rhs) {
1380 return std::equal(lhs.
begin(), lhs.
end(), rhs.begin(), rhs.end());
1382 template <
typename OtherT>
1384 const OtherT &rhs) {
1385 return !(lhs == rhs);
1395 DerivedT
slice(
size_t n,
size_t m)
const {
1396 assert(n + m <=
size() &&
"invalid size specifiers");
1397 return DerivedT(offset_base(
base, n), m);
1402 assert(
size() >= n &&
"Dropping more elements than exist");
1407 assert(
size() >= n &&
"Dropping more elements than exist");
1414 :
static_cast<const DerivedT &
>(*this);
1420 :
static_cast<const DerivedT &
>(*this);
1424 template <
typename RangeT,
typename = std::enable_if_t<std::is_constructible<
1426 operator RangeT()
const {
1435 static BaseT offset_base(
const BaseT &
base,
size_t n) {
1436 return n == 0 ?
base : DerivedT::offset_base(
base, n);
1459template <
typename DerivedT,
typename BaseT,
typename T,
1460 typename PointerT =
T *,
typename ReferenceT =
T &>
1463 DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT, ReferenceT> {
1467 DerivedT,
std::pair<BaseT,
ptrdiff_t>,
T, PointerT, ReferenceT>(
1470 DerivedT, std::pair<BaseT, ptrdiff_t>,
T, PointerT,
1480 static std::pair<BaseT, ptrdiff_t>
1484 return std::make_pair(
base.first,
base.second + index);
1490 return DerivedT::dereference(
base.first,
base.second + index);
1503 using type = std::conditional_t<std::is_reference<EltTy>::value, FirstTy,
1504 std::remove_reference_t<FirstTy>>;
1510 using EltTy =
decltype((*std::begin(c)));
1513 EltTy,
decltype((elt.first))>::type {
1520 using EltTy =
decltype((*std::begin(c)));
1522 std::forward<ContainerTy>(c),
1525 decltype((elt.second))>::type {
1539 return std::less<>()(std::get<0>(lhs), std::get<0>(rhs));
1548 return std::less<>()(std::get<1>(lhs), std::get<1>(rhs));
1554template<
typename FuncTy>
1558 template <
typename T>
1559 decltype(
auto)
operator()(
const T &lhs,
const T &rhs)
const {
1560 return func(lhs.first, rhs.first);
1571template <
typename T,
typename... Ts>
1572using is_one_of = std::disjunction<std::is_same<T, Ts>...>;
1576template <
typename T,
typename... Ts>
1577using are_base_of = std::conjunction<std::is_base_of<T, Ts>...>;
1582template <
typename HeadT,
typename... TailTs>
1588 using Visitor<TailTs...>::operator();
1626template <
typename... CallableTs>
1628 return detail::Visitor<CallableTs...>(std::forward<CallableTs>(Callables)...);
1637template <
class Iterator,
class RNG>
1642 typename std::iterator_traits<Iterator>::difference_type difference_type;
1643 for (
auto size = last - first;
size > 1; ++first, (void)--
size) {
1644 difference_type offset =
g() %
size;
1647 if (offset != difference_type(0))
1648 std::iter_swap(first, first + offset);
1655 if (std::less<T>()(*
reinterpret_cast<const T*
>(P1),
1656 *
reinterpret_cast<const T*
>(P2)))
1658 if (std::less<T>()(*
reinterpret_cast<const T*
>(P2),
1659 *
reinterpret_cast<const T*
>(P1)))
1668 (
const void*,
const void*) {
1669 return array_pod_sort_comparator<T>;
1672#ifdef EXPENSIVE_CHECKS
1675inline unsigned presortShuffleEntropy() {
1676 static unsigned Result(std::random_device{}());
1680template <
class IteratorTy>
1681inline void presortShuffle(IteratorTy Start, IteratorTy
End) {
1682 std::mt19937 Generator(presortShuffleEntropy());
1703template<
class IteratorTy>
1707 auto NElts =
End - Start;
1708 if (NElts <= 1)
return;
1709#ifdef EXPENSIVE_CHECKS
1710 detail::presortShuffle<IteratorTy>(Start,
End);
1715template <
class IteratorTy>
1717 IteratorTy Start, IteratorTy
End,
1719 const typename std::iterator_traits<IteratorTy>::value_type *,
1720 const typename std::iterator_traits<IteratorTy>::value_type *)) {
1723 auto NElts =
End - Start;
1724 if (NElts <= 1)
return;
1725#ifdef EXPENSIVE_CHECKS
1726 detail::presortShuffle<IteratorTy>(Start,
End);
1728 qsort(&*Start, NElts,
sizeof(*Start),
1729 reinterpret_cast<int (*)(
const void *,
const void *)
>(Compare));
1733template <
typename T>
1738 std::is_trivially_copyable<typename std::iterator_traits<T>::value_type>>;
1743template <
typename IteratorTy>
1744inline void sort(IteratorTy Start, IteratorTy
End) {
1750#ifdef EXPENSIVE_CHECKS
1751 detail::presortShuffle<IteratorTy>(Start,
End);
1753 std::sort(Start,
End);
1757template <
typename Container>
inline void sort(Container &&
C) {
1761template <
typename IteratorTy,
typename Compare>
1762inline void sort(IteratorTy Start, IteratorTy
End, Compare Comp) {
1763#ifdef EXPENSIVE_CHECKS
1764 detail::presortShuffle<IteratorTy>(Start,
End);
1766 std::sort(Start,
End, Comp);
1769template <
typename Container,
typename Compare>
1770inline void sort(Container &&
C, Compare Comp) {
1776template <
typename R>
1779 std::is_base_of<std::random_access_iterator_tag,
1780 typename std::iterator_traits<
decltype(
1781 Range.begin())>::iterator_category>
::value,
1782 void> * =
nullptr) {
1783 return std::distance(Range.begin(), Range.end());
1787template <
typename Range>
1789 decltype(
adl_size(std::declval<Range &>()));
1791template <
typename Range>
1803 if constexpr (detail::HasFreeFunctionSize<R>)
1806 return static_cast<size_t>(std::distance(
adl_begin(Range),
adl_end(Range)));
1811template <
typename R,
typename UnaryFunction>
1818template <
typename R,
typename UnaryPredicate>
1825template <
typename R,
typename UnaryPredicate>
1832template <
typename R,
typename UnaryPredicate>
1839template <
typename R,
typename T>
auto find(R &&Range,
const T &Val) {
1845template <
typename R,
typename UnaryPredicate>
1850template <
typename R,
typename UnaryPredicate>
1857template <
typename R,
typename UnaryPredicate>
1864template <
typename R,
typename OutputIt,
typename UnaryPredicate>
1865OutputIt
copy_if(R &&Range, OutputIt Out, UnaryPredicate
P) {
1874template <
typename T,
typename R,
typename Predicate>
1877 for (
auto *
A : Range) {
1878 if (
T *PRC =
P(
A, AllowRepeats)) {
1880 if (!AllowRepeats || PRC != RC)
1898template <
typename T,
typename R,
typename Predicate>
1900 bool AllowRepeats =
false) {
1902 for (
auto *
A : Range) {
1903 std::pair<T *, bool> PRC =
P(
A, AllowRepeats);
1905 assert(PRC.first ==
nullptr &&
1906 "Inconsistent return values in find_singleton_nested.");
1911 if (!AllowRepeats || PRC.first != RC)
1912 return {
nullptr,
true};
1920template <
typename R,
typename OutputIt>
1921OutputIt
copy(R &&Range, OutputIt Out) {
1927template <
typename R,
typename OutputIt,
typename UnaryPredicate,
typename T>
1929 const T &NewValue) {
1936template <
typename R,
typename OutputIt,
typename T>
1938 const T &NewValue) {
1945template <
typename R,
typename OutputIt>
1946OutputIt
move(R &&Range, OutputIt Out) {
1951template <
typename Range,
typename Element>
1953 decltype(std::declval<Range &>().contains(std::declval<const Element &>()));
1955template <
typename Range,
typename Element>
1959template <
typename Range,
typename Element>
1961 decltype(std::declval<Range &>().find(std::declval<const Element &>()) !=
1962 std::declval<Range &>().end());
1964template <
typename Range,
typename Element>
1975template <
typename R,
typename E>
1977 if constexpr (detail::HasMemberContains<R, E>)
1978 return Range.contains(Element);
1979 else if constexpr (detail::HasMemberFind<R, E>)
1980 return Range.find(Element) != Range.end();
1988template <
typename T,
typename E>
1991 for (
const T &V : Set)
1999template <
typename R,
typename Compare>
bool is_sorted(R &&Range, Compare
C) {
2011template <
typename R,
typename E>
auto count(R &&Range,
const E &Element) {
2017template <
typename R,
typename UnaryPredicate>
2024template <
typename R,
typename OutputIt,
typename UnaryFunction>
2025OutputIt
transform(R &&Range, OutputIt d_first, UnaryFunction
F) {
2031template <
typename R,
typename UnaryPredicate>
2040 std::forward<T>(
Value));
2043template <
typename R,
typename T,
typename Compare>
2046 std::forward<T>(
Value),
C);
2053 std::forward<T>(
Value));
2056template <
typename R,
typename T,
typename Compare>
2059 std::forward<T>(
Value),
C);
2062template <
typename R>
2067template <
typename R,
typename Compare>
2074template <
typename R,
typename Predicate,
2075 typename Val =
decltype(*
adl_begin(std::declval<R>()))>
2080template<
typename Range,
typename Predicate>
2087template <
typename L,
typename R>
bool equal(L &&LRange, R &&RRange) {
2096 return Begin ==
End || std::equal(Begin + 1,
End, Begin);
2101template <
typename T>
bool all_equal(std::initializer_list<T> Values) {
2102 return all_equal<std::initializer_list<T>>(std::move(Values));
2112template <
typename Container,
typename UnaryPredicate>
2120template <
typename Container,
typename ValueType>
2122 C.erase(std::remove(
C.begin(),
C.end(), V),
C.end());
2128template <
typename Container,
typename Range>
2135template<
typename Container,
typename RandomAccessIterator>
2136void replace(Container &Cont,
typename Container::iterator ContIt,
2137 typename Container::iterator ContEnd, RandomAccessIterator ValIt,
2138 RandomAccessIterator ValEnd) {
2140 if (ValIt == ValEnd) {
2141 Cont.erase(ContIt, ContEnd);
2143 }
else if (ContIt == ContEnd) {
2144 Cont.insert(ContIt, ValIt, ValEnd);
2147 *ContIt++ = *ValIt++;
2153template<
typename Container,
typename Range = std::initializer_list<
2154 typename Container::value_type>>
2155void replace(Container &Cont,
typename Container::iterator ContIt,
2156 typename Container::iterator ContEnd, Range R) {
2157 replace(Cont, ContIt, ContEnd, R.begin(), R.end());
2170template <
typename ForwardIterator,
typename UnaryFunctor,
2171 typename NullaryFunctor,
2172 typename = std::enable_if_t<
2173 !std::is_constructible<StringRef, UnaryFunctor>::value &&
2174 !std::is_constructible<StringRef, NullaryFunctor>::value>>
2175inline void interleave(ForwardIterator begin, ForwardIterator end,
2176 UnaryFunctor each_fn, NullaryFunctor between_fn) {
2181 for (; begin != end; ++begin) {
2187template <
typename Container,
typename UnaryFunctor,
typename NullaryFunctor,
2188 typename = std::enable_if_t<
2189 !std::is_constructible<StringRef, UnaryFunctor>::value &&
2190 !std::is_constructible<StringRef, NullaryFunctor>::value>>
2192 NullaryFunctor between_fn) {
2193 interleave(c.begin(), c.end(), each_fn, between_fn);
2197template <
typename Container,
typename UnaryFunctor,
typename StreamT,
2198 typename T = detail::ValueOfRange<Container>>
2199inline void interleave(
const Container &c, StreamT &os, UnaryFunctor each_fn,
2201 interleave(c.begin(), c.end(), each_fn, [&] { os << separator; });
2203template <
typename Container,
typename StreamT,
2204 typename T = detail::ValueOfRange<Container>>
2208 c, os, [&](
const T &a) { os << a; }, separator);
2211template <
typename Container,
typename UnaryFunctor,
typename StreamT,
2212 typename T = detail::ValueOfRange<Container>>
2214 UnaryFunctor each_fn) {
2217template <
typename Container,
typename StreamT,
2218 typename T = detail::ValueOfRange<Container>>
2233template<
typename First,
typename Second>
2236 return std::hash<First>()(
P.first) * 31 + std::hash<Second>()(
P.second);
2251 return func(*lhs, *rhs);
2260template <
typename... Iters>
2274template <
typename... Iters>
2276 EnumeratorTupleType<Iters...>, Iters...> {
2277 static_assert(
sizeof...(Iters) >= 2,
"Expected at least two iteratees");
2279 Iters...>::zip_common;
2282 return std::get<1>(this->
iterators) == std::get<1>(
Other.iterators);
2287 static constexpr std::size_t NumRefs =
sizeof...(Refs);
2288 static_assert(NumRefs != 0);
2290 static constexpr std::size_t NumValues = NumRefs + 1;
2299 :
Idx(
Index), Storage(
std::forward<Refs>(Rs)...) {}
2308 if constexpr (NumRefs == 1)
2309 return std::get<0>(Storage);
2315 template <std::
size_t I,
typename = std::enable_if_t<I == 0>>
2322 template <std::
size_t I,
typename = std::enable_if_t<I != 0>>
2327 return std::get<
I - 1>(Result.Storage);
2330 template <
typename... Ts>
2332 const std::tuple<std::size_t, Ts...> &
Other) {
2333 static_assert(NumRefs ==
sizeof...(Ts),
"Size mismatch");
2334 if (Result.Idx != std::get<0>(
Other))
2336 return Result.is_value_equal(
Other, std::make_index_sequence<NumRefs>{});
2340 template <
typename Tuple, std::size_t...
Idx>
2341 bool is_value_equal(
const Tuple &
Other, std::index_sequence<Idx...>)
const {
2342 return ((std::get<Idx>(Storage) == std::get<Idx + 1>(
Other)) && ...);
2353 mutable range_reference_tuple Storage;
2361 assert(
Index != std::numeric_limits<std::size_t>::max() &&
2362 "Attempting to increment end iterator");
2386 It.
Index = std::numeric_limits<std::size_t>::max();
2429template <
typename FirstRange,
typename... RestRanges>
2431 if constexpr (
sizeof...(Rest) != 0) {
2440 FirstRange, RestRanges...>;
2442 std::forward<RestRanges>(Rest)...);
2447template <
typename Predicate,
typename... Args>
2450 auto it = z.begin();
2453 if (!std::apply([&](
auto &&...
args) {
return P(
args...); }, *it))
2457 return it.all_equals(end);
2462template <
typename... ArgsThenPredicate,
size_t... InputIndexes>
2464 std::tuple<ArgsThenPredicate...> argsThenPredicate,
2465 std::index_sequence<InputIndexes...>) {
2466 auto constexpr OutputIndex =
2467 std::tuple_size<
decltype(argsThenPredicate)>
::value - 1;
2469 std::get<InputIndexes>(argsThenPredicate)...);
2477template <
typename... ArgsAndPredicate>
2480 std::forward_as_tuple(argsAndPredicate...),
2481 std::make_index_sequence<
sizeof...(argsAndPredicate) - 1>{});
2487template <
typename IterTy,
2488 typename Pred =
bool (*)(
const decltype(*std::declval<IterTy>()) &)>
2490 IterTy &&Begin, IterTy &&
End,
unsigned N,
2491 Pred &&ShouldBeCounted =
2492 [](
const decltype(*std::declval<IterTy>()) &) {
return true; },
2494 !std::is_base_of<std::random_access_iterator_tag,
2495 typename std::iterator_traits<std::remove_reference_t<
2496 decltype(Begin)>>::iterator_category>
::value,
2497 void> * =
nullptr) {
2498 for (;
N; ++Begin) {
2501 N -= ShouldBeCounted(*Begin);
2503 for (; Begin !=
End; ++Begin)
2504 if (ShouldBeCounted(*Begin))
2512template <
typename IterTy,
2513 typename Pred =
bool (*)(
const decltype(*std::declval<IterTy>()) &)>
2515 IterTy &&Begin, IterTy &&
End,
unsigned N,
2516 Pred &&ShouldBeCounted =
2517 [](
const decltype(*std::declval<IterTy>()) &) {
return true; },
2519 !std::is_base_of<std::random_access_iterator_tag,
2520 typename std::iterator_traits<std::remove_reference_t<
2521 decltype(Begin)>>::iterator_category>
::value,
2522 void> * =
nullptr) {
2523 for (;
N; ++Begin) {
2526 N -= ShouldBeCounted(*Begin);
2533template <
typename IterTy,
2534 typename Pred =
bool (*)(
const decltype(*std::declval<IterTy>()) &)>
2536 IterTy &&Begin, IterTy &&
End,
unsigned N,
2537 Pred &&ShouldBeCounted = [](
const decltype(*std::declval<IterTy>()) &) {
2540 assert(
N != std::numeric_limits<unsigned>::max());
2545template <
typename ContainerTy>
bool hasNItems(ContainerTy &&
C,
unsigned N) {
2550template <
typename ContainerTy>
2556template <
typename ContainerTy>
2574template <
typename... Refs>
2575struct tuple_size<
llvm::detail::enumerator_result<Refs...>>
2576 : std::integral_constant<std::size_t, sizeof...(Refs)> {};
2578template <std::size_t
I,
typename... Refs>
2579struct tuple_element<
I,
llvm::detail::enumerator_result<Refs...>>
2580 : std::tuple_element<I, std::tuple<Refs...>> {};
2582template <std::size_t
I,
typename... Refs>
2583struct tuple_element<
I,
const llvm::detail::enumerator_result<Refs...>>
2584 : std::tuple_element<I, std::tuple<Refs...>> {};
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
Given that RA is a live value
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains library features backported from future STL versions.
INLINE void g(uint32_t *state, size_t a, size_t b, size_t c, size_t d, uint32_t x, uint32_t y)
StringRef - Represent a constant reference to a string, i.e.
LLVM Value Representation.
Templated storage wrapper for a callable.
Callable & operator=(Callable &&Other)
Callable(Callable const &Other)=default
Callable & operator=(Callable const &Other)
Callable(Callable &&Other)=default
Iterator wrapper that concatenates sequences together.
concat_iterator & operator++()
bool operator==(const concat_iterator &RHS) const
ValueT & operator*() const
concat_iterator(RangeTs &&... Ranges)
Constructs an iterator from a sequence of ranges.
Helper to store a sequence of ranges being concatenated and access them.
concat_range(RangeTs &&... Ranges)
concat_iterator< ValueT, decltype(std::begin(std::declval< RangeTs & >()))... > iterator
Return a reference to the first or second member of a reference.
std::conditional_t< std::is_reference< EltTy >::value, FirstTy, std::remove_reference_t< FirstTy > > type
An iterator element of this range.
ReferenceT operator*() const
The class represents the base of a range of indexed_accessor_iterators.
friend bool operator==(const indexed_accessor_range_base &lhs, const OtherT &rhs)
Compare this range with another.
DerivedT slice(size_t n, size_t m) const
Drop the first N elements, and keep M elements.
size_t size() const
Return the size of this range.
bool empty() const
Return if the range is empty.
indexed_accessor_range_base & operator=(const indexed_accessor_range_base &)=default
DerivedT take_front(size_t n=1) const
Take the first n elements.
ReferenceT operator[](size_t Index) const
friend bool operator!=(const indexed_accessor_range_base &lhs, const OtherT &rhs)
DerivedT drop_back(size_t n=1) const
Drop the last n elements.
DerivedT take_back(size_t n=1) const
Take the last n elements.
DerivedT drop_front(size_t n=1) const
Drop the first n elements.
indexed_accessor_range_base(const indexed_accessor_range_base &)=default
indexed_accessor_range_base(BaseT base, ptrdiff_t count)
indexed_accessor_range_base(indexed_accessor_range_base &&)=default
indexed_accessor_range_base(iterator begin, iterator end)
ptrdiff_t count
The size from the owning range.
BaseT base
The base that owns the provided range of values.
indexed_accessor_range_base(const iterator_range< iterator > &range)
const BaseT & getBase() const
Returns the base of this range.
zip_longest_iterator(std::pair< Iters &&, Iters && >... ts)
value_type operator*() const
bool operator==(const zip_longest_iterator< Iters... > &other) const
zip_longest_iterator< Iters... > & operator++()
typename ZipLongestTupleType< Iters... >::type value_type
typename iterator::iterator_category iterator_category
typename iterator::pointer pointer
zip_longest_iterator< decltype(adl_begin(std::declval< Args >()))... > iterator
typename iterator::difference_type difference_type
typename iterator::reference reference
zip_longest_range(Args &&... ts_)
typename iterator::value_type value_type
typename iterator::value_type value_type
typename iterator::difference_type difference_type
typename iterator::reference reference
typename iterator::pointer pointer
typename const_iterator::reference const_reference
typename ZippyIteratorTuple< ItType, decltype(storage), IndexSequence >::type iterator
typename ZippyIteratorTuple< ItType, const decltype(storage), IndexSequence >::type const_iterator
const_iterator begin() const
typename iterator::iterator_category iterator_category
const_iterator end() const
A pseudo-iterator adaptor that is designed to implement "early increment" style loops.
friend bool operator==(const early_inc_iterator_impl &LHS, const early_inc_iterator_impl &RHS)
early_inc_iterator_impl(WrappedIteratorT I)
early_inc_iterator_impl & operator++()
An iterator adaptor that filters the elements of given inner iterators.
filter_iterator_base & operator++()
filter_iterator_base()=default
filter_iterator_base(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred)
filter_iterator_impl()=default
filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred)
filter_iterator_impl & operator--()
Specialization of filter_iterator_base for forward iteration only.
filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred)
filter_iterator_impl()=default
Helper to determine if type T has a member called rbegin().
A utility class used to implement an iterator that contains some base object and an index.
DerivedT & operator+=(ptrdiff_t offset)
const BaseT & getBase() const
Returns the current base of the iterator.
bool operator==(const indexed_accessor_iterator &rhs) const
indexed_accessor_iterator(BaseT base, ptrdiff_t index)
DerivedT & operator-=(ptrdiff_t offset)
ptrdiff_t operator-(const indexed_accessor_iterator &rhs) const
bool operator<(const indexed_accessor_iterator &rhs) const
ptrdiff_t getIndex() const
Returns the current index of the iterator.
This class provides an implementation of a range of indexed_accessor_iterators where the base is not ...
indexed_accessor_range(BaseT base, ptrdiff_t startIndex, ptrdiff_t count)
const BaseT & getBase() const
Returns the current base of the range.
ptrdiff_t getStartIndex() const
Returns the current start index of the range.
static ReferenceT dereference_iterator(const std::pair< BaseT, ptrdiff_t > &base, ptrdiff_t index)
See detail::indexed_accessor_range_base for details.
static std::pair< BaseT, ptrdiff_t > offset_base(const std::pair< BaseT, ptrdiff_t > &base, ptrdiff_t index)
See detail::indexed_accessor_range_base for details.
CRTP base class for adapting an iterator to a different type.
iterator_adaptor_base()=default
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
std::common_type_t< std::forward_iterator_tag, std::iterator_traits< Iters >::iterator_category... > iterator_category
std::iterator_traits< std::tuple_element_t< 0, std::tuple< Iters... > > >::difference_type difference_type
ZipLongestTupleType< Iters... >::type reference
ZipLongestTupleType< Iters... >::type * pointer
A range adaptor for a pair of iterators.
A base type of mapped iterator, that is useful for building derived iterators that do not need/want t...
mapped_iterator_base(ItTy U)
ReferenceTy operator*() const
mapped_iterator()=default
const FuncTy & getFunction() const
mapped_iterator(ItTy U, FuncTy F)
ReferenceTy operator*() const
friend const_iterator end(StringRef path)
Get end iterator over path.
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
@ Tail
Attemps to make calls as fast as possible while guaranteeing that tail call optimization can always b...
@ C
The default llvm calling convention, compatible with C.
constexpr auto size_impl(RangeT &&range) -> decltype(size(std::forward< RangeT >(range)))
constexpr auto end_impl(RangeT &&range) -> decltype(end(std::forward< RangeT >(range)))
constexpr void swap_impl(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval< T >(), std::declval< T >())))
constexpr auto begin_impl(RangeT &&range) -> decltype(begin(std::forward< RangeT >(range)))
auto deref_or_none(const Iter &I, const Iter &End) -> std::optional< std::remove_const_t< std::remove_reference_t< decltype(*I)> > >
decltype(std::declval< Range & >().contains(std::declval< const Element & >())) check_has_member_contains_t
decltype(std::declval< Range & >().find(std::declval< const Element & >()) !=std::declval< Range & >().end()) check_has_member_find_t
bool all_of_zip_predicate_first(Predicate &&P, Args &&...args)
static constexpr bool HasMemberFind
decltype(adl_begin(std::declval< RangeT & >())) IterOfRange
std::conjunction< std::is_pointer< T >, std::is_trivially_copyable< typename std::iterator_traits< T >::value_type > > sort_trivially_copyable
static constexpr bool HasMemberContains
bool all_of_zip_predicate_last(std::tuple< ArgsThenPredicate... > argsThenPredicate, std::index_sequence< InputIndexes... >)
std::remove_reference_t< decltype(*adl_begin(std::declval< RangeT & >()))> ValueOfRange
Iter next_or_end(const Iter &I, const Iter &End)
static constexpr bool HasFreeFunctionSize
decltype(adl_size(std::declval< Range & >())) check_has_free_function_size
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
void stable_sort(R &&Range)
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
std::conjunction< std::is_base_of< T, Ts >... > are_base_of
traits class for checking whether type T is a base class for all the given types in the variadic list...
UnaryFunction for_each(R &&Range, UnaryFunction F)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
detail::zip_longest_range< T, U, Args... > zip_longest(T &&t, U &&u, Args &&... args)
Iterate over two or more iterators at the same time.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
int(*)(const void *, const void *) get_array_pod_sort_comparator(const T &)
get_array_pod_sort_comparator - This is an internal helper function used to get type deduction of T r...
detail::zippy< detail::zip_first, T, U, Args... > zip_equal(T &&t, U &&u, Args &&...args)
zip iterator that assumes that all iteratees have the same length.
constexpr auto adl_begin(RangeT &&range) -> decltype(adl_detail::begin_impl(std::forward< RangeT >(range)))
Returns the begin iterator to range using std::begin and function found through Argument-Dependent Lo...
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are are tuples (A,...
void interleave(ForwardIterator begin, ForwardIterator end, UnaryFunctor each_fn, NullaryFunctor between_fn)
An STL-style algorithm similar to std::for_each that applies a second functor between every pair of e...
auto partition_point(R &&Range, Predicate P)
Binary search for the first iterator in a range where a predicate is false.
int array_pod_sort_comparator(const void *P1, const void *P2)
Adapt std::less<T> for array_pod_sort.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
mapped_iterator< ItTy, FuncTy > map_iterator(ItTy I, FuncTy F)
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
bool hasNItemsOrLess(IterTy &&Begin, IterTy &&End, unsigned N, Pred &&ShouldBeCounted=[](const decltype(*std::declval< IterTy >()) &) { return true;})
Returns true if the sequence [Begin, End) has N or less items.
void interleaveComma(const Container &c, StreamT &os, UnaryFunctor each_fn)
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
void shuffle(Iterator first, Iterator last, RNG &&g)
constexpr auto adl_end(RangeT &&range) -> decltype(adl_detail::end_impl(std::forward< RangeT >(range)))
Returns the end iterator to range using std::end and functions found through Argument-Dependent Looku...
auto upper_bound(R &&Range, T &&Value)
Provide wrappers to std::upper_bound which take ranges instead of having to pass begin/end explicitly...
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly.
auto map_range(ContainerTy &&C, FuncTy F)
typename detail::detector< void, Op, Args... >::value_t is_detected
Detects if a given trait holds for some set of arguments 'Args'.
bool hasNItemsOrMore(IterTy &&Begin, IterTy &&End, unsigned N, Pred &&ShouldBeCounted=[](const decltype(*std::declval< IterTy >()) &) { return true;}, std::enable_if_t< !std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< std::remove_reference_t< decltype(Begin)> >::iterator_category >::value, void > *=nullptr)
Return true if the sequence [Begin, End) has N or more items.
OutputIt transform(R &&Range, OutputIt d_first, UnaryFunction F)
Wrapper function around std::transform to apply a function to a range and store the result elsewhere.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
auto reverse(ContainerTy &&C)
constexpr size_t range_size(R &&Range)
Returns the size of the Range, i.e., the number of elements.
detail::zippy< detail::zip_first, T, U, Args... > zip_first(T &&t, U &&u, Args &&...args)
zip iterator that, for the sake of efficiency, assumes the first iteratee to be the shortest.
void sort(IteratorTy Start, IteratorTy End)
bool hasNItems(IterTy &&Begin, IterTy &&End, unsigned N, Pred &&ShouldBeCounted=[](const decltype(*std::declval< IterTy >()) &) { return true;}, std::enable_if_t< !std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< std::remove_reference_t< decltype(Begin)> >::iterator_category >::value, void > *=nullptr)
Return true if the sequence [Begin, End) has exactly N items.
auto find_if_not(R &&Range, UnaryPredicate P)
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
auto make_first_range(ContainerTy &&c)
Given a container of pairs, return a range over the first elements.
constexpr auto adl_size(RangeT &&range) -> decltype(adl_detail::size_impl(std::forward< RangeT >(range)))
Returns the size of range using std::size and functions found through Argument-Dependent Lookup (ADL)...
detail::concat_range< ValueT, RangeTs... > concat(RangeTs &&... Ranges)
Concatenated range across two or more ranges.
bool is_sorted(R &&Range, Compare C)
Wrapper function around std::is_sorted to check if elements in a range R are sorted with respect to a...
bool hasSingleElement(ContainerTy &&C)
Returns true if the given container only contains a single element.
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
std::pair< T *, bool > find_singleton_nested(R &&Range, Predicate P, bool AllowRepeats=false)
Return a pair consisting of the single value in Range that satisfies P(<member of Range> *,...
T * find_singleton(R &&Range, Predicate P, bool AllowRepeats=false)
Return the single value in Range that satisfies P(<member of Range> *, AllowRepeats)->T * returning n...
auto drop_end(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the last N elements excluded.
auto remove_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly.
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
void erase_value(Container &C, ValueType V)
Wrapper function to remove a value from a container:
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
OutputIt replace_copy_if(R &&Range, OutputIt Out, UnaryPredicate P, const T &NewValue)
Provide wrappers to std::replace_copy_if which take ranges instead of having to pass begin/end explic...
auto to_address(const Ptr &P)
Returns a raw pointer that represents the same address as the argument.
OutputIt copy(R &&Range, OutputIt Out)
auto partition(R &&Range, UnaryPredicate P)
Provide wrappers to std::partition which take ranges instead of having to pass begin/end explicitly.
std::disjunction< std::is_same< T, Ts >... > is_one_of
traits class for checking whether type T is one of any of the given types in the variadic list.
auto make_second_range(ContainerTy &&c)
Given a container of pairs, return a range over the second elements.
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
OutputIt replace_copy(R &&Range, OutputIt Out, const T &OldValue, const T &NewValue)
Provide wrappers to std::replace_copy which take ranges instead of having to pass begin/end explicitl...
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
std::tuple_element_t< I, std::tuple< Ts... > > TypeAtIndex
Find the type at a given index in a list of types.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
void replace(Container &Cont, typename Container::iterator ContIt, typename Container::iterator ContEnd, RandomAccessIterator ValIt, RandomAccessIterator ValEnd)
Given a sequence container Cont, replace the range [ContIt, ContEnd) with the range [ValIt,...
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
bool all_equal(std::initializer_list< T > Values)
Returns true if all Values in the initializer lists are equal or the list.
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
constexpr decltype(auto) makeVisitor(CallableTs &&...Callables)
Returns an opaquely-typed Callable object whose operator() overload set is the sum of the operator() ...
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
bool all_of_zip(ArgsAndPredicate &&...argsAndPredicate)
Compare two zipped ranges using the provided predicate (as last argument).
constexpr auto addEnumValues(EnumTy1 LHS, EnumTy2 RHS)
Helper which adds two underlying types of enumeration type.
constexpr void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(adl_detail::swap_impl(std::declval< T >(), std::declval< T >())))
Swaps lhs with rhs using std::swap and functions found through Argument-Dependent Lookup (ADL).
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Find the first index where a type appears in a list of types.
Determine if all types in Ts are distinct.
Binary functor that adapts to any other binary functor after dereferencing operands.
auto operator()(A &lhs, B &rhs) const
constexpr Visitor(HeadT &&Head, TailTs &&...Tail)
constexpr Visitor(HeadT &&Head)
std::optional< std::remove_const_t< std::remove_reference_t< decltype(*std::declval< Iter >())> > > type
std::tuple< typename ZipLongestItemType< Iters >::type... > type
std::tuple< decltype(*declval< Iters >())... > type
ItType< decltype(adl_begin(std::get< Ns >(declval< const std::tuple< Args... > & >())))... > type
ItType< decltype(adl_begin(std::get< Ns >(declval< std::tuple< Args... > & >())))... > type
Helper to obtain the iterator types for the tuple storage within zippy.
std::tuple< Refs... > range_reference_tuple
decltype(auto) value() const
Returns the value(s) for the current iterator.
friend decltype(auto) get(const enumerator_result &Result)
Returns the value at index I.
std::tuple< std::size_t, Refs... > value_reference_tuple
friend bool operator==(const enumerator_result &Result, const std::tuple< std::size_t, Ts... > &Other)
std::size_t index() const
Returns the 0-based index of the current position within the original input range(s).
friend std::size_t get(const enumerator_result &Result)
Returns the value at index I. This case covers the index.
enumerator_result(std::size_t Index, Refs &&...Rs)
Tuple-like type for zip_enumerator dereference.
std::bidirectional_iterator_tag type
std::forward_iterator_tag type
Helper which sets its type member to forward_iterator_tag if the category of IterT does not derive fr...
typename fwd_or_bidi_tag_impl< std::is_base_of< std::bidirectional_iterator_tag, typename std::iterator_traits< IterT >::iterator_category >::value >::type type
std::size_t operator*() const
friend bool operator==(const iterator &Lhs, const iterator &Rhs)
Infinite stream of increasing 0-based size_t indices.
std::index_sequence_for< Iters... > IndexSequence
void tup_inc(std::index_sequence< Ns... >)
zip_common(Iters &&... ts)
bool test_all_equals(const zip_common &other, std::index_sequence< Ns... >) const
std::tuple< Iters... > iterators
value_type operator*() const
typename Base::value_type value_type
bool all_equals(zip_common &other)
Return true if all the iterator are matching other's iterators.
void tup_dec(std::index_sequence< Ns... >)
value_type deref(std::index_sequence< Ns... >) const
Zippy iterator that uses the second iterator for comparisons.
bool operator==(const zip_enumerator &Other) const
bool operator==(const zip_first &other) const
bool operator==(const zip_shortest &other) const
std::tuple_element_t< Index, std::tuple< Args... > > arg_t
The type of an argument to this function.
ReturnType result_t
The result type of this function.
std::tuple_element_t< i, std::tuple< Args... > > arg_t
The type of an argument to this function.
ReturnType result_t
The result type of this function.
This class provides various trait information about a callable object.
Metafunction to determine if T& or T has a member called rbegin().
Function object to check whether the first component of a container supported by std::get (like std::...
bool operator()(const T &lhs, const T &rhs) const
Function object to check whether the second component of a container supported by std::get (like std:...
bool operator()(const T &lhs, const T &rhs) const
std::add_pointer_t< std::add_const_t< T > > type
std::add_lvalue_reference_t< std::add_const_t< T > > type
Function object to apply a binary function to the first component of a std::pair.
size_t operator()(const std::pair< First, Second > &P) const
Utility type to build an inheritance chain that makes it easy to rank overload candidates.