WPILibC++  2020.3.2-60-g3011ebe
STLExtras.h
1 //===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file contains some templates that are useful if you are working with the
11 // STL at all.
12 //
13 // No library is required when using these functions.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #ifndef WPIUTIL_WPI_STLEXTRAS_H
18 #define WPIUTIL_WPI_STLEXTRAS_H
19 
20 #include "wpi/SmallVector.h"
21 #include "wpi/iterator.h"
22 #include "wpi/iterator_range.h"
23 #include "wpi/ErrorHandling.h"
24 #include <algorithm>
25 #include <cassert>
26 #include <cstddef>
27 #include <cstdint>
28 #include <cstdlib>
29 #include <functional>
30 #include <initializer_list>
31 #include <iterator>
32 #include <limits>
33 #include <memory>
34 #include <optional>
35 #include <tuple>
36 #include <type_traits>
37 #include <utility>
38 
39 namespace wpi {
40 
41 // Only used by compiler if both template types are the same. Useful when
42 // using SFINAE to test for the existence of member functions.
43 template <typename T, T> struct SameType;
44 
45 namespace detail {
46 
47 template <typename RangeT>
48 using IterOfRange = decltype(std::begin(std::declval<RangeT &>()));
49 
50 template <typename RangeT>
51 using ValueOfRange = typename std::remove_reference<decltype(
52  *std::begin(std::declval<RangeT &>()))>::type;
53 
54 } // end namespace detail
55 
56 //===----------------------------------------------------------------------===//
57 // Extra additions to <type_traits>
58 //===----------------------------------------------------------------------===//
59 
60 template <typename T> struct make_const_ptr {
61  using type =
62  typename std::add_pointer<typename std::add_const<T>::type>::type;
63 };
64 
65 template <typename T> struct make_const_ref {
66  using type = typename std::add_lvalue_reference<
67  typename std::add_const<T>::type>::type;
68 };
69 
70 //===----------------------------------------------------------------------===//
71 // Extra additions to <functional>
72 //===----------------------------------------------------------------------===//
73 
74 template <class Ty> struct identity {
75  using argument_type = Ty;
76 
77  Ty &operator()(Ty &self) const {
78  return self;
79  }
80  const Ty &operator()(const Ty &self) const {
81  return self;
82  }
83 };
84 
85 template <class Ty> struct less_ptr {
86  bool operator()(const Ty* left, const Ty* right) const {
87  return *left < *right;
88  }
89 };
90 
91 template <class Ty> struct greater_ptr {
92  bool operator()(const Ty* left, const Ty* right) const {
93  return *right < *left;
94  }
95 };
96 
103 template<typename Fn> class function_ref;
104 
105 template<typename Ret, typename ...Params>
106 class function_ref<Ret(Params...)> {
107  Ret (*callback)(intptr_t callable, Params ...params) = nullptr;
108  intptr_t callable;
109 
110  template<typename Callable>
111  static Ret callback_fn(intptr_t callable, Params ...params) {
112  return (*reinterpret_cast<Callable*>(callable))(
113  std::forward<Params>(params)...);
114  }
115 
116 public:
117  function_ref() = default;
118  function_ref(std::nullptr_t) {}
119 
120  template <typename Callable>
121  function_ref(Callable &&callable,
122  typename std::enable_if<
123  !std::is_same<typename std::remove_reference<Callable>::type,
124  function_ref>::value>::type * = nullptr)
125  : callback(callback_fn<typename std::remove_reference<Callable>::type>),
126  callable(reinterpret_cast<intptr_t>(&callable)) {}
127 
128  Ret operator()(Params ...params) const {
129  return callback(callable, std::forward<Params>(params)...);
130  }
131 
132  explicit operator bool() const { return callback; }
133 };
134 
135 // deleter - Very very very simple method that is used to invoke operator
136 // delete on something. It is used like this:
137 //
138 // for_each(V.begin(), B.end(), deleter<Interval>);
139 template <class T>
140 inline void deleter(T *Ptr) {
141  delete Ptr;
142 }
143 
144 //===----------------------------------------------------------------------===//
145 // Extra additions to <iterator>
146 //===----------------------------------------------------------------------===//
147 
148 namespace adl_detail {
149 
150 using std::begin;
151 
152 template <typename ContainerTy>
153 auto adl_begin(ContainerTy &&container)
154  -> decltype(begin(std::forward<ContainerTy>(container))) {
155  return begin(std::forward<ContainerTy>(container));
156 }
157 
158 using std::end;
159 
160 template <typename ContainerTy>
161 auto adl_end(ContainerTy &&container)
162  -> decltype(end(std::forward<ContainerTy>(container))) {
163  return end(std::forward<ContainerTy>(container));
164 }
165 
166 using std::swap;
167 
168 template <typename T>
169 void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval<T>(),
170  std::declval<T>()))) {
171  swap(std::forward<T>(lhs), std::forward<T>(rhs));
172 }
173 
174 } // end namespace adl_detail
175 
176 template <typename ContainerTy>
177 auto adl_begin(ContainerTy &&container)
178  -> decltype(adl_detail::adl_begin(std::forward<ContainerTy>(container))) {
179  return adl_detail::adl_begin(std::forward<ContainerTy>(container));
180 }
181 
182 template <typename ContainerTy>
183 auto adl_end(ContainerTy &&container)
184  -> decltype(adl_detail::adl_end(std::forward<ContainerTy>(container))) {
185  return adl_detail::adl_end(std::forward<ContainerTy>(container));
186 }
187 
188 template <typename T>
189 void adl_swap(T &&lhs, T &&rhs) noexcept(
190  noexcept(adl_detail::adl_swap(std::declval<T>(), std::declval<T>()))) {
191  adl_detail::adl_swap(std::forward<T>(lhs), std::forward<T>(rhs));
192 }
193 
195 template <typename T>
196 constexpr bool empty(const T &RangeOrContainer) {
197  return adl_begin(RangeOrContainer) == adl_end(RangeOrContainer);
198 }
199 
200 // mapped_iterator - This is a simple iterator adapter that causes a function to
201 // be applied whenever operator* is invoked on the iterator.
202 
203 template <typename ItTy, typename FuncTy,
204  typename FuncReturnTy =
205  decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))>
207  : public iterator_adaptor_base<
208  mapped_iterator<ItTy, FuncTy>, ItTy,
209  typename std::iterator_traits<ItTy>::iterator_category,
210  typename std::remove_reference<FuncReturnTy>::type> {
211 public:
212  mapped_iterator(ItTy U, FuncTy F)
213  : mapped_iterator::iterator_adaptor_base(std::move(U)), F(std::move(F)) {}
214 
215  ItTy getCurrent() { return this->I; }
216 
217  FuncReturnTy operator*() { return F(*this->I); }
218 
219 private:
220  FuncTy F;
221 };
222 
223 // map_iterator - Provide a convenient way to create mapped_iterators, just like
224 // make_pair is useful for creating pairs...
225 template <class ItTy, class FuncTy>
226 inline mapped_iterator<ItTy, FuncTy> map_iterator(ItTy I, FuncTy F) {
227  return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F));
228 }
229 
231 template <typename Ty> class has_rbegin_impl {
232  using yes = char[1];
233  using no = char[2];
234 
235  template <typename Inner>
236  static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr);
237 
238  template <typename>
239  static no& test(...);
240 
241 public:
242  static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes);
243 };
244 
246 template <typename Ty>
247 struct has_rbegin : has_rbegin_impl<typename std::remove_reference<Ty>::type> {
248 };
249 
250 // Returns an iterator_range over the given container which iterates in reverse.
251 // Note that the container must have rbegin()/rend() methods for this to work.
252 template <typename ContainerTy>
253 auto reverse(ContainerTy &&C,
254  typename std::enable_if<has_rbegin<ContainerTy>::value>::type * =
255  nullptr) -> decltype(make_range(C.rbegin(), C.rend())) {
256  return make_range(C.rbegin(), C.rend());
257 }
258 
259 // Returns a std::reverse_iterator wrapped around the given iterator.
260 template <typename IteratorTy>
261 std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) {
262  return std::reverse_iterator<IteratorTy>(It);
263 }
264 
265 // Returns an iterator_range over the given container which iterates in reverse.
266 // Note that the container must have begin()/end() methods which return
267 // bidirectional iterators for this to work.
268 template <typename ContainerTy>
269 auto reverse(
270  ContainerTy &&C,
271  typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr)
272  -> decltype(make_range(wpi::make_reverse_iterator(std::end(C)),
273  wpi::make_reverse_iterator(std::begin(C)))) {
274  return make_range(wpi::make_reverse_iterator(std::end(C)),
275  wpi::make_reverse_iterator(std::begin(C)));
276 }
277 
294 template <typename WrappedIteratorT, typename PredicateT, typename IterTag>
296  : public iterator_adaptor_base<
297  filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
298  WrappedIteratorT,
299  typename std::common_type<
300  IterTag, typename std::iterator_traits<
301  WrappedIteratorT>::iterator_category>::type> {
304  WrappedIteratorT,
305  typename std::common_type<
306  IterTag, typename std::iterator_traits<
307  WrappedIteratorT>::iterator_category>::type>;
308 
309 protected:
310  WrappedIteratorT End;
311  PredicateT Pred;
312 
313  void findNextValid() {
314  while (this->I != End && !Pred(*this->I))
315  BaseT::operator++();
316  }
317 
318  // Construct the iterator. The begin iterator needs to know where the end
319  // is, so that it can properly stop when it gets there. The end iterator only
320  // needs the predicate to support bidirectional iteration.
321  filter_iterator_base(WrappedIteratorT Begin, WrappedIteratorT End,
322  PredicateT Pred)
323  : BaseT(Begin), End(End), Pred(Pred) {
324  findNextValid();
325  }
326 
327 public:
328  using BaseT::operator++;
329 
330  filter_iterator_base &operator++() {
331  BaseT::operator++();
332  findNextValid();
333  return *this;
334  }
335 };
336 
338 template <typename WrappedIteratorT, typename PredicateT,
339  typename IterTag = std::forward_iterator_tag>
341  : public filter_iterator_base<WrappedIteratorT, PredicateT, IterTag> {
343 
344 public:
345  filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
346  PredicateT Pred)
347  : BaseT(Begin, End, Pred) {}
348 };
349 
351 template <typename WrappedIteratorT, typename PredicateT>
352 class filter_iterator_impl<WrappedIteratorT, PredicateT,
353  std::bidirectional_iterator_tag>
354  : public filter_iterator_base<WrappedIteratorT, PredicateT,
355  std::bidirectional_iterator_tag> {
356  using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT,
357  std::bidirectional_iterator_tag>;
358  void findPrevValid() {
359  while (!this->Pred(*this->I))
360  BaseT::operator--();
361  }
362 
363 public:
364  using BaseT::operator--;
365 
366  filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
367  PredicateT Pred)
368  : BaseT(Begin, End, Pred) {}
369 
370  filter_iterator_impl &operator--() {
371  BaseT::operator--();
372  findPrevValid();
373  return *this;
374  }
375 };
376 
377 namespace detail {
378 
379 template <bool is_bidirectional> struct fwd_or_bidi_tag_impl {
380  using type = std::forward_iterator_tag;
381 };
382 
383 template <> struct fwd_or_bidi_tag_impl<true> {
384  using type = std::bidirectional_iterator_tag;
385 };
386 
390 template <typename IterT> struct fwd_or_bidi_tag {
391  using type = typename fwd_or_bidi_tag_impl<std::is_base_of<
392  std::bidirectional_iterator_tag,
393  typename std::iterator_traits<IterT>::iterator_category>::value>::type;
394 };
395 
396 } // namespace detail
397 
400 template <typename WrappedIteratorT, typename PredicateT>
402  WrappedIteratorT, PredicateT,
403  typename detail::fwd_or_bidi_tag<WrappedIteratorT>::type>;
404 
412 template <typename RangeT, typename PredicateT>
414 make_filter_range(RangeT &&Range, PredicateT Pred) {
415  using FilterIteratorT =
417  return make_range(
418  FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
419  std::end(std::forward<RangeT>(Range)), Pred),
420  FilterIteratorT(std::end(std::forward<RangeT>(Range)),
421  std::end(std::forward<RangeT>(Range)), Pred));
422 }
423 
424 // forward declarations required by zip_shortest/zip_first
425 template <typename R, typename UnaryPredicate>
426 bool all_of(R &&range, UnaryPredicate P);
427 template <typename R, typename UnaryPredicate>
428 bool any_of(R &&range, UnaryPredicate P);
429 
430 namespace detail {
431 
432 using std::declval;
433 
434 // We have to alias this since inlining the actual type at the usage site
435 // in the parameter list of iterator_facade_base<> below ICEs MSVC 2017.
436 template<typename... Iters> struct ZipTupleType {
437  using type = std::tuple<decltype(*declval<Iters>())...>;
438 };
439 
440 template <typename ZipType, typename... Iters>
442  ZipType, typename std::common_type<std::bidirectional_iterator_tag,
443  typename std::iterator_traits<
444  Iters>::iterator_category...>::type,
445  // ^ TODO: Implement random access methods.
446  typename ZipTupleType<Iters...>::type,
447  typename std::iterator_traits<typename std::tuple_element<
448  0, std::tuple<Iters...>>::type>::difference_type,
449  // ^ FIXME: This follows boost::make_zip_iterator's assumption that all
450  // inner iterators have the same difference_type. It would fail if, for
451  // instance, the second field's difference_type were non-numeric while the
452  // first is.
453  typename ZipTupleType<Iters...>::type *,
454  typename ZipTupleType<Iters...>::type>;
455 
456 template <typename ZipType, typename... Iters>
457 struct zip_common : public zip_traits<ZipType, Iters...> {
458  using Base = zip_traits<ZipType, Iters...>;
459  using value_type = typename Base::value_type;
460 
461  std::tuple<Iters...> iterators;
462 
463 protected:
464  template <size_t... Ns> value_type deref(std::index_sequence<Ns...>) const {
465  return value_type(*std::get<Ns>(iterators)...);
466  }
467 
468  template <size_t... Ns>
469  decltype(iterators) tup_inc(std::index_sequence<Ns...>) const {
470  return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...);
471  }
472 
473  template <size_t... Ns>
474  decltype(iterators) tup_dec(std::index_sequence<Ns...>) const {
475  return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...);
476  }
477 
478 public:
479  zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
480 
481  value_type operator*() { return deref(std::index_sequence_for<Iters...>{}); }
482 
483  const value_type operator*() const {
484  return deref(std::index_sequence_for<Iters...>{});
485  }
486 
487  ZipType &operator++() {
488  iterators = tup_inc(std::index_sequence_for<Iters...>{});
489  return *reinterpret_cast<ZipType *>(this);
490  }
491 
492  ZipType &operator--() {
493  static_assert(Base::IsBidirectional,
494  "All inner iterators must be at least bidirectional.");
495  iterators = tup_dec(std::index_sequence_for<Iters...>{});
496  return *reinterpret_cast<ZipType *>(this);
497  }
498 };
499 
500 template <typename... Iters>
501 struct zip_first : public zip_common<zip_first<Iters...>, Iters...> {
502  using Base = zip_common<zip_first<Iters...>, Iters...>;
503 
504  bool operator==(const zip_first<Iters...> &other) const {
505  return std::get<0>(this->iterators) == std::get<0>(other.iterators);
506  }
507 
508  zip_first(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
509 };
510 
511 template <typename... Iters>
512 class zip_shortest : public zip_common<zip_shortest<Iters...>, Iters...> {
513  template <size_t... Ns>
514  bool test(const zip_shortest<Iters...> &other, std::index_sequence<Ns...>) const {
515  return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
516  std::get<Ns>(other.iterators)...},
517  identity<bool>{});
518  }
519 
520 public:
521  using Base = zip_common<zip_shortest<Iters...>, Iters...>;
522 
523  zip_shortest(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
524 
525  bool operator==(const zip_shortest<Iters...> &other) const {
526  return !test(other, std::index_sequence_for<Iters...>{});
527  }
528 };
529 
530 template <template <typename...> class ItType, typename... Args> class zippy {
531 public:
532  using iterator = ItType<decltype(std::begin(std::declval<Args>()))...>;
533  using iterator_category = typename iterator::iterator_category;
534  using value_type = typename iterator::value_type;
535  using difference_type = typename iterator::difference_type;
536  using pointer = typename iterator::pointer;
537  using reference = typename iterator::reference;
538 
539 private:
540  std::tuple<Args...> ts;
541 
542  template <size_t... Ns> iterator begin_impl(std::index_sequence<Ns...>) const {
543  return iterator(std::begin(std::get<Ns>(ts))...);
544  }
545  template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) const {
546  return iterator(std::end(std::get<Ns>(ts))...);
547  }
548 
549 public:
550  zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
551 
552  iterator begin() const { return begin_impl(std::index_sequence_for<Args...>{}); }
553  iterator end() const { return end_impl(std::index_sequence_for<Args...>{}); }
554 };
555 
556 } // end namespace detail
557 
559 template <typename T, typename U, typename... Args>
560 detail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u,
561  Args &&... args) {
562  return detail::zippy<detail::zip_shortest, T, U, Args...>(
563  std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
564 }
565 
568 template <typename T, typename U, typename... Args>
569 detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u,
570  Args &&... args) {
571  return detail::zippy<detail::zip_first, T, U, Args...>(
572  std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
573 }
574 
575 namespace detail {
576 template <typename Iter>
577 static Iter next_or_end(const Iter &I, const Iter &End) {
578  if (I == End)
579  return End;
580  return std::next(I);
581 }
582 
583 template <typename Iter>
584 static auto deref_or_none(const Iter &I, const Iter &End)
585  -> std::optional<typename std::remove_const<
586  typename std::remove_reference<decltype(*I)>::type>::type> {
587  if (I == End)
588  return std::nullopt;
589  return *I;
590 }
591 
592 template <typename Iter> struct ZipLongestItemType {
593  using type =
594  std::optional<typename std::remove_const<typename std::remove_reference<
595  decltype(*std::declval<Iter>())>::type>::type>;
596 };
597 
598 template <typename... Iters> struct ZipLongestTupleType {
599  using type = std::tuple<typename ZipLongestItemType<Iters>::type...>;
600 };
601 
602 template <typename... Iters>
604  : public iterator_facade_base<
605  zip_longest_iterator<Iters...>,
606  typename std::common_type<
607  std::forward_iterator_tag,
608  typename std::iterator_traits<Iters>::iterator_category...>::type,
609  typename ZipLongestTupleType<Iters...>::type,
610  typename std::iterator_traits<typename std::tuple_element<
611  0, std::tuple<Iters...>>::type>::difference_type,
612  typename ZipLongestTupleType<Iters...>::type *,
613  typename ZipLongestTupleType<Iters...>::type> {
614 public:
615  using value_type = typename ZipLongestTupleType<Iters...>::type;
616 
617 private:
618  std::tuple<Iters...> iterators;
619  std::tuple<Iters...> end_iterators;
620 
621  template <size_t... Ns>
622  bool test(const zip_longest_iterator<Iters...> &other,
623  std::index_sequence<Ns...>) const {
624  return wpi::any_of(
625  std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
626  std::get<Ns>(other.iterators)...},
627  identity<bool>{});
628  }
629 
630  template <size_t... Ns> value_type deref(std::index_sequence<Ns...>) const {
631  return value_type(
632  deref_or_none(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
633  }
634 
635  template <size_t... Ns>
636  decltype(iterators) tup_inc(std::index_sequence<Ns...>) const {
637  return std::tuple<Iters...>(
638  next_or_end(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
639  }
640 
641 public:
642  zip_longest_iterator(std::pair<Iters &&, Iters &&>... ts)
643  : iterators(std::forward<Iters>(ts.first)...),
644  end_iterators(std::forward<Iters>(ts.second)...) {}
645 
646  value_type operator*() { return deref(std::index_sequence_for<Iters...>{}); }
647 
648  value_type operator*() const { return deref(std::index_sequence_for<Iters...>{}); }
649 
650  zip_longest_iterator<Iters...> &operator++() {
651  iterators = tup_inc(std::index_sequence_for<Iters...>{});
652  return *this;
653  }
654 
655  bool operator==(const zip_longest_iterator<Iters...> &other) const {
656  return !test(other, std::index_sequence_for<Iters...>{});
657  }
658 };
659 
660 template <typename... Args> class zip_longest_range {
661 public:
662  using iterator =
664  using iterator_category = typename iterator::iterator_category;
665  using value_type = typename iterator::value_type;
666  using difference_type = typename iterator::difference_type;
667  using pointer = typename iterator::pointer;
668  using reference = typename iterator::reference;
669 
670 private:
671  std::tuple<Args...> ts;
672 
673  template <size_t... Ns> iterator begin_impl(std::index_sequence<Ns...>) const {
674  return iterator(std::make_pair(adl_begin(std::get<Ns>(ts)),
675  adl_end(std::get<Ns>(ts)))...);
676  }
677 
678  template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) const {
679  return iterator(std::make_pair(adl_end(std::get<Ns>(ts)),
680  adl_end(std::get<Ns>(ts)))...);
681  }
682 
683 public:
684  zip_longest_range(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
685 
686  iterator begin() const { return begin_impl(std::index_sequence_for<Args...>{}); }
687  iterator end() const { return end_impl(std::index_sequence_for<Args...>{}); }
688 };
689 } // namespace detail
690 
694 template <typename T, typename U, typename... Args>
695 detail::zip_longest_range<T, U, Args...> zip_longest(T &&t, U &&u,
696  Args &&... args) {
697  return detail::zip_longest_range<T, U, Args...>(
698  std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
699 }
700 
711 template <typename ValueT, typename... IterTs>
713  : public iterator_facade_base<concat_iterator<ValueT, IterTs...>,
714  std::forward_iterator_tag, ValueT> {
715  using BaseT = typename concat_iterator::iterator_facade_base;
716 
723  std::tuple<IterTs...> Begins;
724  std::tuple<IterTs...> Ends;
725 
730  template <size_t Index> bool incrementHelper() {
731  auto &Begin = std::get<Index>(Begins);
732  auto &End = std::get<Index>(Ends);
733  if (Begin == End)
734  return false;
735 
736  ++Begin;
737  return true;
738  }
739 
743  template <size_t... Ns> void increment(std::index_sequence<Ns...>) {
744  // Build a sequence of functions to increment each iterator if possible.
745  bool (concat_iterator::*IncrementHelperFns[])() = {
746  &concat_iterator::incrementHelper<Ns>...};
747 
748  // Loop over them, and stop as soon as we succeed at incrementing one.
749  for (auto &IncrementHelperFn : IncrementHelperFns)
750  if ((this->*IncrementHelperFn)())
751  return;
752 
753  assert(false && "Attempted to increment an end concat iterator!");
754  }
755 
759  template <size_t Index> ValueT *getHelper() const {
760  auto &Begin = std::get<Index>(Begins);
761  auto &End = std::get<Index>(Ends);
762  if (Begin == End)
763  return nullptr;
764 
765  return &*Begin;
766  }
767 
772  template <size_t... Ns> ValueT &get(std::index_sequence<Ns...>) const {
773  // Build a sequence of functions to get from iterator if possible.
774  ValueT *(concat_iterator::*GetHelperFns[])() const = {
775  &concat_iterator::getHelper<Ns>...};
776 
777  // Loop over them, and return the first result we find.
778  for (auto &GetHelperFn : GetHelperFns)
779  if (ValueT *P = (this->*GetHelperFn)())
780  return *P;
781 
782  assert(false && "Attempted to get a pointer from an end concat iterator!");
783  }
784 
785 public:
790  template <typename... RangeTs>
791  explicit concat_iterator(RangeTs &&... Ranges)
792  : Begins(std::begin(Ranges)...), Ends(std::end(Ranges)...) {}
793 
794  using BaseT::operator++;
795 
796  concat_iterator &operator++() {
797  increment(std::index_sequence_for<IterTs...>());
798  return *this;
799  }
800 
801  ValueT &operator*() const { return get(std::index_sequence_for<IterTs...>()); }
802 
803  bool operator==(const concat_iterator &RHS) const {
804  return Begins == RHS.Begins && Ends == RHS.Ends;
805  }
806 };
807 
808 namespace detail {
809 
815 template <typename ValueT, typename... RangeTs> class concat_range {
816 public:
817  using iterator =
818  concat_iterator<ValueT,
819  decltype(std::begin(std::declval<RangeTs &>()))...>;
820 
821 private:
822  std::tuple<RangeTs...> Ranges;
823 
824  template <size_t... Ns> iterator begin_impl(std::index_sequence<Ns...>) {
825  return iterator(std::get<Ns>(Ranges)...);
826  }
827  template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) {
828  return iterator(make_range(std::end(std::get<Ns>(Ranges)),
829  std::end(std::get<Ns>(Ranges)))...);
830  }
831 
832 public:
833  concat_range(RangeTs &&... Ranges)
834  : Ranges(std::forward<RangeTs>(Ranges)...) {}
835 
836  iterator begin() { return begin_impl(std::index_sequence_for<RangeTs...>{}); }
837  iterator end() { return end_impl(std::index_sequence_for<RangeTs...>{}); }
838 };
839 
840 } // end namespace detail
841 
845 template <typename ValueT, typename... RangeTs>
846 detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) {
847  static_assert(sizeof...(RangeTs) > 1,
848  "Need more than one range to concatenate!");
849  return detail::concat_range<ValueT, RangeTs...>(
850  std::forward<RangeTs>(Ranges)...);
851 }
852 
853 //===----------------------------------------------------------------------===//
854 // Extra additions to <utility>
855 //===----------------------------------------------------------------------===//
856 
859 struct less_first {
860  template <typename T> bool operator()(const T &lhs, const T &rhs) const {
861  return lhs.first < rhs.first;
862  }
863 };
864 
867 struct less_second {
868  template <typename T> bool operator()(const T &lhs, const T &rhs) const {
869  return lhs.second < rhs.second;
870  }
871 };
872 
875 template<typename FuncTy>
876 struct on_first {
877  FuncTy func;
878 
879  template <typename T>
880  auto operator()(const T &lhs, const T &rhs) const
881  -> decltype(func(lhs.first, rhs.first)) {
882  return func(lhs.first, rhs.first);
883  }
884 };
885 
888 template <int N> struct rank : rank<N - 1> {};
889 template <> struct rank<0> {};
890 
893 template <typename T, typename... Ts> struct is_one_of {
894  static const bool value = false;
895 };
896 
897 template <typename T, typename U, typename... Ts>
898 struct is_one_of<T, U, Ts...> {
899  static const bool value =
900  std::is_same<T, U>::value || is_one_of<T, Ts...>::value;
901 };
902 
905 template <typename T, typename... Ts> struct are_base_of {
906  static const bool value = true;
907 };
908 
909 template <typename T, typename U, typename... Ts>
910 struct are_base_of<T, U, Ts...> {
911  static const bool value =
912  std::is_base_of<T, U>::value && are_base_of<T, Ts...>::value;
913 };
914 
915 //===----------------------------------------------------------------------===//
916 // Extra additions for arrays
917 //===----------------------------------------------------------------------===//
918 
920 template <class T, std::size_t N>
921 constexpr inline size_t array_lengthof(T (&)[N]) {
922  return N;
923 }
924 
926 template<typename T>
927 inline int array_pod_sort_comparator(const void *P1, const void *P2) {
928  if (std::less<T>()(*reinterpret_cast<const T*>(P1),
929  *reinterpret_cast<const T*>(P2)))
930  return -1;
931  if (std::less<T>()(*reinterpret_cast<const T*>(P2),
932  *reinterpret_cast<const T*>(P1)))
933  return 1;
934  return 0;
935 }
936 
939 template<typename T>
940 inline int (*get_array_pod_sort_comparator(const T &))
941  (const void*, const void*) {
942  return array_pod_sort_comparator<T>;
943 }
944 
959 template<class IteratorTy>
960 inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
961  // Don't inefficiently call qsort with one element or trigger undefined
962  // behavior with an empty sequence.
963  auto NElts = End - Start;
964  if (NElts <= 1) return;
965  qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
966 }
967 
968 template <class IteratorTy>
969 inline void array_pod_sort(
970  IteratorTy Start, IteratorTy End,
971  int (*Compare)(
972  const typename std::iterator_traits<IteratorTy>::value_type *,
973  const typename std::iterator_traits<IteratorTy>::value_type *)) {
974  // Don't inefficiently call qsort with one element or trigger undefined
975  // behavior with an empty sequence.
976  auto NElts = End - Start;
977  if (NElts <= 1) return;
978  qsort(&*Start, NElts, sizeof(*Start),
979  reinterpret_cast<int (*)(const void *, const void *)>(Compare));
980 }
981 
982 //===----------------------------------------------------------------------===//
983 // Extra additions to <algorithm>
984 //===----------------------------------------------------------------------===//
985 
988 template<typename Container>
989 void DeleteContainerPointers(Container &C) {
990  for (auto V : C)
991  delete V;
992  C.clear();
993 }
994 
997 template<typename Container>
998 void DeleteContainerSeconds(Container &C) {
999  for (auto &V : C)
1000  delete V.second;
1001  C.clear();
1002 }
1003 
1006 template <typename R>
1007 auto size(R &&Range, typename std::enable_if<
1008  std::is_same<typename std::iterator_traits<decltype(
1009  Range.begin())>::iterator_category,
1010  std::random_access_iterator_tag>::value,
1011  void>::type * = nullptr)
1012  -> decltype(std::distance(Range.begin(), Range.end())) {
1013  return std::distance(Range.begin(), Range.end());
1014 }
1015 
1018 template <typename R, typename UnaryPredicate>
1019 UnaryPredicate for_each(R &&Range, UnaryPredicate P) {
1020  return std::for_each(adl_begin(Range), adl_end(Range), P);
1021 }
1022 
1025 template <typename R, typename UnaryPredicate>
1026 bool all_of(R &&Range, UnaryPredicate P) {
1027  return std::all_of(adl_begin(Range), adl_end(Range), P);
1028 }
1029 
1032 template <typename R, typename UnaryPredicate>
1033 bool any_of(R &&Range, UnaryPredicate P) {
1034  return std::any_of(adl_begin(Range), adl_end(Range), P);
1035 }
1036 
1039 template <typename R, typename UnaryPredicate>
1040 bool none_of(R &&Range, UnaryPredicate P) {
1041  return std::none_of(adl_begin(Range), adl_end(Range), P);
1042 }
1043 
1046 template <typename R, typename T>
1047 auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range)) {
1048  return std::find(adl_begin(Range), adl_end(Range), Val);
1049 }
1050 
1053 template <typename R, typename UnaryPredicate>
1054 auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
1055  return std::find_if(adl_begin(Range), adl_end(Range), P);
1056 }
1057 
1058 template <typename R, typename UnaryPredicate>
1059 auto find_if_not(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
1060  return std::find_if_not(adl_begin(Range), adl_end(Range), P);
1061 }
1062 
1065 template <typename R, typename UnaryPredicate>
1066 auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
1067  return std::remove_if(adl_begin(Range), adl_end(Range), P);
1068 }
1069 
1072 template <typename R, typename OutputIt, typename UnaryPredicate>
1073 OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) {
1074  return std::copy_if(adl_begin(Range), adl_end(Range), Out, P);
1075 }
1076 
1077 template <typename R, typename OutputIt>
1078 OutputIt copy(R &&Range, OutputIt Out) {
1079  return std::copy(adl_begin(Range), adl_end(Range), Out);
1080 }
1081 
1084 template <typename R, typename E>
1085 bool is_contained(R &&Range, const E &Element) {
1086  return std::find(adl_begin(Range), adl_end(Range), Element) != adl_end(Range);
1087 }
1088 
1091 template <typename R, typename E>
1092 auto count(R &&Range, const E &Element) ->
1093  typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
1094  return std::count(adl_begin(Range), adl_end(Range), Element);
1095 }
1096 
1099 template <typename R, typename UnaryPredicate>
1100 auto count_if(R &&Range, UnaryPredicate P) ->
1101  typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
1102  return std::count_if(adl_begin(Range), adl_end(Range), P);
1103 }
1104 
1107 template <typename R, typename OutputIt, typename UnaryPredicate>
1108 OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P) {
1109  return std::transform(adl_begin(Range), adl_end(Range), d_first, P);
1110 }
1111 
1114 template <typename R, typename UnaryPredicate>
1115 auto partition(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
1116  return std::partition(adl_begin(Range), adl_end(Range), P);
1117 }
1118 
1121 template <typename R, typename ForwardIt>
1122 auto lower_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range)) {
1123  return std::lower_bound(adl_begin(Range), adl_end(Range), I);
1124 }
1125 
1126 template <typename R, typename ForwardIt, typename Compare>
1127 auto lower_bound(R &&Range, ForwardIt I, Compare C)
1128  -> decltype(adl_begin(Range)) {
1129  return std::lower_bound(adl_begin(Range), adl_end(Range), I, C);
1130 }
1131 
1134 template <typename R, typename ForwardIt>
1135 auto upper_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range)) {
1136  return std::upper_bound(adl_begin(Range), adl_end(Range), I);
1137 }
1138 
1139 template <typename R, typename ForwardIt, typename Compare>
1140 auto upper_bound(R &&Range, ForwardIt I, Compare C)
1141  -> decltype(adl_begin(Range)) {
1142  return std::upper_bound(adl_begin(Range), adl_end(Range), I, C);
1143 }
1146 template <typename R>
1147 bool is_splat(R &&Range) {
1148  size_t range_size = size(Range);
1149  return range_size != 0 && (range_size == 1 ||
1150  std::equal(adl_begin(Range) + 1, adl_end(Range), adl_begin(Range)));
1151 }
1152 
1156 template <unsigned Size, typename R>
1157 SmallVector<typename std::remove_const<detail::ValueOfRange<R>>::type, Size>
1158 to_vector(R &&Range) {
1159  return {adl_begin(Range), adl_end(Range)};
1160 }
1161 
1169 template <typename Container, typename UnaryPredicate>
1170 void erase_if(Container &C, UnaryPredicate P) {
1171  C.erase(remove_if(C, P), C.end());
1172 }
1173 
1174 //===----------------------------------------------------------------------===//
1175 // Extra additions to <memory>
1176 //===----------------------------------------------------------------------===//
1177 
1178 struct FreeDeleter {
1179  void operator()(void* v) {
1180  ::free(v);
1181  }
1182 };
1183 
1184 template<typename First, typename Second>
1185 struct pair_hash {
1186  size_t operator()(const std::pair<First, Second> &P) const {
1187  return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second);
1188  }
1189 };
1190 
1193 template <typename T> struct deref {
1194  T func;
1195 
1196  // Could be further improved to cope with non-derivable functors and
1197  // non-binary functors (should be a variadic template member function
1198  // operator()).
1199  template <typename A, typename B>
1200  auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) {
1201  assert(lhs);
1202  assert(rhs);
1203  return func(*lhs, *rhs);
1204  }
1205 };
1206 
1207 namespace detail {
1208 
1209 template <typename R> class enumerator_iter;
1210 
1211 template <typename R> struct result_pair {
1212  friend class enumerator_iter<R>;
1213 
1214  result_pair() = default;
1215  result_pair(std::size_t Index, IterOfRange<R> Iter)
1216  : Index(Index), Iter(Iter) {}
1217 
1218  result_pair<R> &operator=(const result_pair<R> &Other) {
1219  Index = Other.Index;
1220  Iter = Other.Iter;
1221  return *this;
1222  }
1223 
1224  std::size_t index() const { return Index; }
1225  const ValueOfRange<R> &value() const { return *Iter; }
1226  ValueOfRange<R> &value() { return *Iter; }
1227 
1228 private:
1229  std::size_t Index = (std::numeric_limits<std::size_t>::max)();
1230  IterOfRange<R> Iter;
1231 };
1232 
1233 template <typename R>
1234 class enumerator_iter
1235  : public iterator_facade_base<
1236  enumerator_iter<R>, std::forward_iterator_tag, result_pair<R>,
1237  typename std::iterator_traits<IterOfRange<R>>::difference_type,
1238  typename std::iterator_traits<IterOfRange<R>>::pointer,
1239  typename std::iterator_traits<IterOfRange<R>>::reference> {
1240  using result_type = result_pair<R>;
1241 
1242 public:
1243  explicit enumerator_iter(IterOfRange<R> EndIter)
1244  : Result((std::numeric_limits<size_t>::max)(), EndIter) {}
1245 
1246  enumerator_iter(std::size_t Index, IterOfRange<R> Iter)
1247  : Result(Index, Iter) {}
1248 
1249  result_type &operator*() { return Result; }
1250  const result_type &operator*() const { return Result; }
1251 
1252  enumerator_iter<R> &operator++() {
1253  assert(Result.Index != (std::numeric_limits<size_t>::max)());
1254  ++Result.Iter;
1255  ++Result.Index;
1256  return *this;
1257  }
1258 
1259  bool operator==(const enumerator_iter<R> &RHS) const {
1260  // Don't compare indices here, only iterators. It's possible for an end
1261  // iterator to have different indices depending on whether it was created
1262  // by calling std::end() versus incrementing a valid iterator.
1263  return Result.Iter == RHS.Result.Iter;
1264  }
1265 
1266  enumerator_iter<R> &operator=(const enumerator_iter<R> &Other) {
1267  Result = Other.Result;
1268  return *this;
1269  }
1270 
1271 private:
1272  result_type Result;
1273 };
1274 
1275 template <typename R> class enumerator {
1276 public:
1277  explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {}
1278 
1279  enumerator_iter<R> begin() {
1280  return enumerator_iter<R>(0, std::begin(TheRange));
1281  }
1282 
1283  enumerator_iter<R> end() {
1284  return enumerator_iter<R>(std::end(TheRange));
1285  }
1286 
1287 private:
1288  R TheRange;
1289 };
1290 
1291 } // end namespace detail
1292 
1308 template <typename R> detail::enumerator<R> enumerate(R &&TheRange) {
1309  return detail::enumerator<R>(std::forward<R>(TheRange));
1310 }
1311 
1314 template <typename IterTy>
1316  IterTy &&Begin, IterTy &&End, unsigned N,
1317  typename std::enable_if<
1318  !std::is_same<
1319  typename std::iterator_traits<typename std::remove_reference<
1320  decltype(Begin)>::type>::iterator_category,
1321  std::random_access_iterator_tag>::value,
1322  void>::type * = nullptr) {
1323  for (; N; --N, ++Begin)
1324  if (Begin == End)
1325  return false; // Too few.
1326  return Begin == End;
1327 }
1328 
1331 template <typename IterTy>
1333  IterTy &&Begin, IterTy &&End, unsigned N,
1334  typename std::enable_if<
1335  !std::is_same<
1336  typename std::iterator_traits<typename std::remove_reference<
1337  decltype(Begin)>::type>::iterator_category,
1338  std::random_access_iterator_tag>::value,
1339  void>::type * = nullptr) {
1340  for (; N; --N, ++Begin)
1341  if (Begin == End)
1342  return false; // Too few.
1343  return true;
1344 }
1345 
1346 } // end namespace wpi
1347 
1348 #endif // LLVM_ADT_STLEXTRAS_H
wpi::identity
Definition: STLExtras.h:74
wpi::detail::zip_longest_range
Definition: STLExtras.h:660
wpi::detail::zip_shortest
Definition: STLExtras.h:512
wpi::detail::ZipLongestItemType
Definition: STLExtras.h:592
wpi::detail::fwd_or_bidi_tag
Helper which sets its type member to forward_iterator_tag if the category of IterT does not derive fr...
Definition: STLExtras.h:390
wpi::detail::result_pair
Definition: STLExtras.h:1211
wpi::has_rbegin_impl
Helper to determine if type T has a member called rbegin().
Definition: STLExtras.h:231
wpi::concat
detail::concat_range< ValueT, RangeTs... > concat(RangeTs &&... Ranges)
Concatenated range across two or more ranges.
Definition: STLExtras.h:846
wpi::FreeDeleter
Definition: STLExtras.h:1178
wpi::detail::zip_first
Definition: STLExtras.h:501
wpi::zip_longest
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.
Definition: STLExtras.h:695
wpi::detail::ZipTupleType
Definition: STLExtras.h:436
wpi::erase_if
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Definition: STLExtras.h:1170
wpi::pair_hash
Definition: STLExtras.h:1185
wpi::find_if
auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1054
wpi::array_pod_sort_comparator
int array_pod_sort_comparator(const void *P1, const void *P2)
Adapt std::less<T> for array_pod_sort.
Definition: STLExtras.h:927
wpi::empty
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:196
wpi::enumerate
detail::enumerator< R > enumerate(R &&TheRange)
Given an input range, returns a new range whose values are are pair (A,B) such that A is the 0-based ...
Definition: STLExtras.h:1308
wpi::count_if
auto count_if(R &&Range, UnaryPredicate P) -> typename std::iterator_traits< decltype(adl_begin(Range))>::difference_type
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
Definition: STLExtras.h:1100
wpi::iterator_adaptor_base
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:206
wpi::less_second
Function object to check whether the second component of a std::pair compares less than the second co...
Definition: STLExtras.h:867
wpi::is_one_of
traits class for checking whether type T is one of any of the given types in the variadic list.
Definition: STLExtras.h:893
wpi::to_vector
SmallVector< typename std::remove_const< detail::ValueOfRange< R > >::type, Size > to_vector(R &&Range)
Given a range of type R, iterate the entire range and return a SmallVector with elements of the vecto...
Definition: STLExtras.h:1158
wpi::filter_iterator_base
An iterator adaptor that filters the elements of given inner iterators.
Definition: STLExtras.h:295
wpi::partition
auto partition(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::partition which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1115
wpi::SameType
Definition: STLExtras.h:43
wpi::transform
OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P)
Wrapper function around std::transform to apply a function to a range and store the result elsewhere.
Definition: STLExtras.h:1108
wpi::make_filter_range
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...
Definition: STLExtras.h:414
wpi::zip_first
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.
Definition: STLExtras.h:569
wpi::has_rbegin
Metafunction to determine if T& or T has a member called rbegin().
Definition: STLExtras.h:247
wpi::less_first
Function object to check whether the first component of a std::pair compares less than the first comp...
Definition: STLExtras.h:859
wpi::zip
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&... args)
zip iterator for two or more iteratable types.
Definition: STLExtras.h:560
wpi::filter_iterator_impl
Specialization of filter_iterator_base for forward iteration only.
Definition: STLExtras.h:340
wpi::lower_bound
auto lower_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range))
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1122
wpi::hasNItemsOrMore
bool hasNItemsOrMore(IterTy &&Begin, IterTy &&End, unsigned N, typename std::enable_if< !std::is_same< typename std::iterator_traits< typename std::remove_reference< decltype(Begin)>::type >::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr)
Return true if the sequence [Begin, End) has N or more items.
Definition: STLExtras.h:1332
wpi::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:32
wpi::detail::fwd_or_bidi_tag_impl
Definition: STLExtras.h:379
wpi::none_of
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1040
wpi::make_const_ref
Definition: STLExtras.h:65
wpi::on_first
Function object to apply a binary function to the first component of a std::pair.
Definition: STLExtras.h:876
wpi::find
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1047
wpi::is_splat
bool is_splat(R &&Range)
Wrapper function around std::equal to detect if all elements in a container are same.
Definition: STLExtras.h:1147
wpi::DeleteContainerPointers
void DeleteContainerPointers(Container &C)
For a container of pointers, deletes the pointers and then clears the container.
Definition: STLExtras.h:989
wpi
WPILib C++ utilities (wpiutil) namespace.
Definition: Endian.h:31
wpi::get_array_pod_sort_comparator
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...
Definition: STLExtras.h:940
wpi::DeleteContainerSeconds
void DeleteContainerSeconds(Container &C)
In a container of pairs (usually a map) whose second element is a pointer, deletes the second element...
Definition: STLExtras.h:998
wpi::detail::zippy
Definition: STLExtras.h:530
wpi::any_of
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1033
wpi::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:54
wpi::mapped_iterator
Definition: STLExtras.h:206
wpi::greater_ptr
Definition: STLExtras.h:91
wpi::array_pod_sort
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
Definition: STLExtras.h:960
wpi::deref
Binary functor that adapts to any other binary functor after dereferencing operands.
Definition: STLExtras.h:1193
iterator_range.h
wpi::less_ptr
Definition: STLExtras.h:85
wpi::detail::ZipLongestTupleType
Definition: STLExtras.h:598
wpi::iterator_facade_base
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:68
wpi::detail::concat_range
Helper to store a sequence of ranges being concatenated and access them.
Definition: STLExtras.h:815
wpi::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:103
wpi::concat_iterator
Iterator wrapper that concatenates sequences together.
Definition: STLExtras.h:712
wpi::array_lengthof
constexpr size_t array_lengthof(T(&)[N])
Find the length of an array.
Definition: STLExtras.h:921
wpi::concat_iterator::concat_iterator
concat_iterator(RangeTs &&... Ranges)
Constructs an iterator from a squence of ranges.
Definition: STLExtras.h:791
wpi::size
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Definition: STLExtras.h:1007
wpi::make_const_ptr
Definition: STLExtras.h:60
wpi::detail::enumerator_iter
Definition: STLExtras.h:1209
wpi::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1085
wpi::detail::zip_longest_iterator
Definition: STLExtras.h:603
wpi::remove_if
auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1066
wpi::rank
Utility type to build an inheritance chain that makes it easy to rank overload candidates.
Definition: STLExtras.h:888
wpi::count
auto count(R &&Range, const E &Element) -> typename std::iterator_traits< decltype(adl_begin(Range))>::difference_type
Wrapper function around std::count to count the number of times an element Element occurs in the give...
Definition: STLExtras.h:1092
wpi::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1026
wpi::copy_if
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.
Definition: STLExtras.h:1073
wpi::detail::zip_common
Definition: STLExtras.h:457
wpi::for_each
UnaryPredicate for_each(R &&Range, UnaryPredicate P)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1019
wpi::detail::enumerator
Definition: STLExtras.h:1275
wpi::are_base_of
traits class for checking whether type T is a base class for all the given types in the variadic list...
Definition: STLExtras.h:905
wpi::upper_bound
auto upper_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range))
Provide wrappers to std::upper_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1135
wpi::hasNItems
bool hasNItems(IterTy &&Begin, IterTy &&End, unsigned N, typename std::enable_if< !std::is_same< typename std::iterator_traits< typename std::remove_reference< decltype(Begin)>::type >::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr)
Return true if the sequence [Begin, End) has exactly N items.
Definition: STLExtras.h:1315