WPILibC++  2019.3.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Modules Pages
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/optional.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 <tuple>
35 #include <type_traits>
36 #include <utility>
37 
38 namespace wpi {
39 
40 // Only used by compiler if both template types are the same. Useful when
41 // using SFINAE to test for the existence of member functions.
42 template <typename T, T> struct SameType;
43 
44 namespace detail {
45 
46 template <typename RangeT>
47 using IterOfRange = decltype(std::begin(std::declval<RangeT &>()));
48 
49 template <typename RangeT>
50 using ValueOfRange = typename std::remove_reference<decltype(
51  *std::begin(std::declval<RangeT &>()))>::type;
52 
53 } // end namespace detail
54 
55 //===----------------------------------------------------------------------===//
56 // Extra additions to <functional>
57 //===----------------------------------------------------------------------===//
58 
59 template <class Ty> struct identity {
60  using argument_type = Ty;
61 
62  Ty &operator()(Ty &self) const {
63  return self;
64  }
65  const Ty &operator()(const Ty &self) const {
66  return self;
67  }
68 };
69 
70 template <class Ty> struct less_ptr {
71  bool operator()(const Ty* left, const Ty* right) const {
72  return *left < *right;
73  }
74 };
75 
76 template <class Ty> struct greater_ptr {
77  bool operator()(const Ty* left, const Ty* right) const {
78  return *right < *left;
79  }
80 };
81 
88 template<typename Fn> class function_ref;
89 
90 template<typename Ret, typename ...Params>
91 class function_ref<Ret(Params...)> {
92  Ret (*callback)(intptr_t callable, Params ...params) = nullptr;
93  intptr_t callable;
94 
95  template<typename Callable>
96  static Ret callback_fn(intptr_t callable, Params ...params) {
97  return (*reinterpret_cast<Callable*>(callable))(
98  std::forward<Params>(params)...);
99  }
100 
101 public:
102  function_ref() = default;
103  function_ref(std::nullptr_t) {}
104 
105  template <typename Callable>
106  function_ref(Callable &&callable,
107  typename std::enable_if<
108  !std::is_same<typename std::remove_reference<Callable>::type,
109  function_ref>::value>::type * = nullptr)
110  : callback(callback_fn<typename std::remove_reference<Callable>::type>),
111  callable(reinterpret_cast<intptr_t>(&callable)) {}
112 
113  Ret operator()(Params ...params) const {
114  return callback(callable, std::forward<Params>(params)...);
115  }
116 
117  explicit operator bool() const { return callback; }
118 };
119 
120 // deleter - Very very very simple method that is used to invoke operator
121 // delete on something. It is used like this:
122 //
123 // for_each(V.begin(), B.end(), deleter<Interval>);
124 template <class T>
125 inline void deleter(T *Ptr) {
126  delete Ptr;
127 }
128 
129 //===----------------------------------------------------------------------===//
130 // Extra additions to <iterator>
131 //===----------------------------------------------------------------------===//
132 
133 namespace adl_detail {
134 
135 using std::begin;
136 
137 template <typename ContainerTy>
138 auto adl_begin(ContainerTy &&container)
139  -> decltype(begin(std::forward<ContainerTy>(container))) {
140  return begin(std::forward<ContainerTy>(container));
141 }
142 
143 using std::end;
144 
145 template <typename ContainerTy>
146 auto adl_end(ContainerTy &&container)
147  -> decltype(end(std::forward<ContainerTy>(container))) {
148  return end(std::forward<ContainerTy>(container));
149 }
150 
151 using std::swap;
152 
153 template <typename T>
154 void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval<T>(),
155  std::declval<T>()))) {
156  swap(std::forward<T>(lhs), std::forward<T>(rhs));
157 }
158 
159 } // end namespace adl_detail
160 
161 template <typename ContainerTy>
162 auto adl_begin(ContainerTy &&container)
163  -> decltype(adl_detail::adl_begin(std::forward<ContainerTy>(container))) {
164  return adl_detail::adl_begin(std::forward<ContainerTy>(container));
165 }
166 
167 template <typename ContainerTy>
168 auto adl_end(ContainerTy &&container)
169  -> decltype(adl_detail::adl_end(std::forward<ContainerTy>(container))) {
170  return adl_detail::adl_end(std::forward<ContainerTy>(container));
171 }
172 
173 template <typename T>
174 void adl_swap(T &&lhs, T &&rhs) noexcept(
175  noexcept(adl_detail::adl_swap(std::declval<T>(), std::declval<T>()))) {
176  adl_detail::adl_swap(std::forward<T>(lhs), std::forward<T>(rhs));
177 }
178 
179 // mapped_iterator - This is a simple iterator adapter that causes a function to
180 // be applied whenever operator* is invoked on the iterator.
181 
182 template <typename ItTy, typename FuncTy,
183  typename FuncReturnTy =
184  decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))>
186  : public iterator_adaptor_base<
187  mapped_iterator<ItTy, FuncTy>, ItTy,
188  typename std::iterator_traits<ItTy>::iterator_category,
189  typename std::remove_reference<FuncReturnTy>::type> {
190 public:
191  mapped_iterator(ItTy U, FuncTy F)
192  : mapped_iterator::iterator_adaptor_base(std::move(U)), F(std::move(F)) {}
193 
194  ItTy getCurrent() { return this->I; }
195 
196  FuncReturnTy operator*() { return F(*this->I); }
197 
198 private:
199  FuncTy F;
200 };
201 
202 // map_iterator - Provide a convenient way to create mapped_iterators, just like
203 // make_pair is useful for creating pairs...
204 template <class ItTy, class FuncTy>
205 inline mapped_iterator<ItTy, FuncTy> map_iterator(ItTy I, FuncTy F) {
206  return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F));
207 }
208 
210 template <typename Ty> class has_rbegin_impl {
211  using yes = char[1];
212  using no = char[2];
213 
214  template <typename Inner>
215  static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr);
216 
217  template <typename>
218  static no& test(...);
219 
220 public:
221  static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes);
222 };
223 
225 template <typename Ty>
226 struct has_rbegin : has_rbegin_impl<typename std::remove_reference<Ty>::type> {
227 };
228 
229 // Returns an iterator_range over the given container which iterates in reverse.
230 // Note that the container must have rbegin()/rend() methods for this to work.
231 template <typename ContainerTy>
232 auto reverse(ContainerTy &&C,
233  typename std::enable_if<has_rbegin<ContainerTy>::value>::type * =
234  nullptr) -> decltype(make_range(C.rbegin(), C.rend())) {
235  return make_range(C.rbegin(), C.rend());
236 }
237 
238 // Returns a std::reverse_iterator wrapped around the given iterator.
239 template <typename IteratorTy>
240 std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) {
241  return std::reverse_iterator<IteratorTy>(It);
242 }
243 
244 // Returns an iterator_range over the given container which iterates in reverse.
245 // Note that the container must have begin()/end() methods which return
246 // bidirectional iterators for this to work.
247 template <typename ContainerTy>
248 auto reverse(
249  ContainerTy &&C,
250  typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr)
251  -> decltype(make_range(wpi::make_reverse_iterator(std::end(C)),
252  wpi::make_reverse_iterator(std::begin(C)))) {
253  return make_range(wpi::make_reverse_iterator(std::end(C)),
254  wpi::make_reverse_iterator(std::begin(C)));
255 }
256 
273 template <typename WrappedIteratorT, typename PredicateT, typename IterTag>
275  : public iterator_adaptor_base<
276  filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
277  WrappedIteratorT,
278  typename std::common_type<
279  IterTag, typename std::iterator_traits<
280  WrappedIteratorT>::iterator_category>::type> {
283  WrappedIteratorT,
284  typename std::common_type<
285  IterTag, typename std::iterator_traits<
286  WrappedIteratorT>::iterator_category>::type>;
287 
288 protected:
289  WrappedIteratorT End;
290  PredicateT Pred;
291 
292  void findNextValid() {
293  while (this->I != End && !Pred(*this->I))
294  BaseT::operator++();
295  }
296 
297  // Construct the iterator. The begin iterator needs to know where the end
298  // is, so that it can properly stop when it gets there. The end iterator only
299  // needs the predicate to support bidirectional iteration.
300  filter_iterator_base(WrappedIteratorT Begin, WrappedIteratorT End,
301  PredicateT Pred)
302  : BaseT(Begin), End(End), Pred(Pred) {
303  findNextValid();
304  }
305 
306 public:
307  using BaseT::operator++;
308 
309  filter_iterator_base &operator++() {
310  BaseT::operator++();
311  findNextValid();
312  return *this;
313  }
314 };
315 
317 template <typename WrappedIteratorT, typename PredicateT,
318  typename IterTag = std::forward_iterator_tag>
320  : public filter_iterator_base<WrappedIteratorT, PredicateT, IterTag> {
322 
323 public:
324  filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
325  PredicateT Pred)
326  : BaseT(Begin, End, Pred) {}
327 };
328 
330 template <typename WrappedIteratorT, typename PredicateT>
331 class filter_iterator_impl<WrappedIteratorT, PredicateT,
332  std::bidirectional_iterator_tag>
333  : public filter_iterator_base<WrappedIteratorT, PredicateT,
334  std::bidirectional_iterator_tag> {
335  using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT,
336  std::bidirectional_iterator_tag>;
337  void findPrevValid() {
338  while (!this->Pred(*this->I))
339  BaseT::operator--();
340  }
341 
342 public:
343  using BaseT::operator--;
344 
345  filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
346  PredicateT Pred)
347  : BaseT(Begin, End, Pred) {}
348 
349  filter_iterator_impl &operator--() {
350  BaseT::operator--();
351  findPrevValid();
352  return *this;
353  }
354 };
355 
356 namespace detail {
357 
358 template <bool is_bidirectional> struct fwd_or_bidi_tag_impl {
359  using type = std::forward_iterator_tag;
360 };
361 
362 template <> struct fwd_or_bidi_tag_impl<true> {
363  using type = std::bidirectional_iterator_tag;
364 };
365 
369 template <typename IterT> struct fwd_or_bidi_tag {
370  using type = typename fwd_or_bidi_tag_impl<std::is_base_of<
371  std::bidirectional_iterator_tag,
372  typename std::iterator_traits<IterT>::iterator_category>::value>::type;
373 };
374 
375 } // namespace detail
376 
379 template <typename WrappedIteratorT, typename PredicateT>
381  WrappedIteratorT, PredicateT,
382  typename detail::fwd_or_bidi_tag<WrappedIteratorT>::type>;
383 
391 template <typename RangeT, typename PredicateT>
393 make_filter_range(RangeT &&Range, PredicateT Pred) {
394  using FilterIteratorT =
396  return make_range(
397  FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
398  std::end(std::forward<RangeT>(Range)), Pred),
399  FilterIteratorT(std::end(std::forward<RangeT>(Range)),
400  std::end(std::forward<RangeT>(Range)), Pred));
401 }
402 
403 // forward declarations required by zip_shortest/zip_first
404 template <typename R, typename UnaryPredicate>
405 bool all_of(R &&range, UnaryPredicate P);
406 
407 template <size_t... I> struct index_sequence;
408 
409 template <class... Ts> struct index_sequence_for;
410 
411 namespace detail {
412 
413 using std::declval;
414 
415 // We have to alias this since inlining the actual type at the usage site
416 // in the parameter list of iterator_facade_base<> below ICEs MSVC 2017.
417 template<typename... Iters> struct ZipTupleType {
418  using type = std::tuple<decltype(*declval<Iters>())...>;
419 };
420 
421 template <typename ZipType, typename... Iters>
423  ZipType, typename std::common_type<std::bidirectional_iterator_tag,
424  typename std::iterator_traits<
425  Iters>::iterator_category...>::type,
426  // ^ TODO: Implement random access methods.
427  typename ZipTupleType<Iters...>::type,
428  typename std::iterator_traits<typename std::tuple_element<
429  0, std::tuple<Iters...>>::type>::difference_type,
430  // ^ FIXME: This follows boost::make_zip_iterator's assumption that all
431  // inner iterators have the same difference_type. It would fail if, for
432  // instance, the second field's difference_type were non-numeric while the
433  // first is.
434  typename ZipTupleType<Iters...>::type *,
435  typename ZipTupleType<Iters...>::type>;
436 
437 template <typename ZipType, typename... Iters>
438 struct zip_common : public zip_traits<ZipType, Iters...> {
439  using Base = zip_traits<ZipType, Iters...>;
440  using value_type = typename Base::value_type;
441 
442  std::tuple<Iters...> iterators;
443 
444 protected:
445  template <size_t... Ns> value_type deref(index_sequence<Ns...>) const {
446  return value_type(*std::get<Ns>(iterators)...);
447  }
448 
449  template <size_t... Ns>
450  decltype(iterators) tup_inc(index_sequence<Ns...>) const {
451  return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...);
452  }
453 
454  template <size_t... Ns>
455  decltype(iterators) tup_dec(index_sequence<Ns...>) const {
456  return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...);
457  }
458 
459 public:
460  zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
461 
462  value_type operator*() { return deref(index_sequence_for<Iters...>{}); }
463 
464  const value_type operator*() const {
466  }
467 
468  ZipType &operator++() {
469  iterators = tup_inc(index_sequence_for<Iters...>{});
470  return *reinterpret_cast<ZipType *>(this);
471  }
472 
473  ZipType &operator--() {
474  static_assert(Base::IsBidirectional,
475  "All inner iterators must be at least bidirectional.");
476  iterators = tup_dec(index_sequence_for<Iters...>{});
477  return *reinterpret_cast<ZipType *>(this);
478  }
479 };
480 
481 template <typename... Iters>
482 struct zip_first : public zip_common<zip_first<Iters...>, Iters...> {
483  using Base = zip_common<zip_first<Iters...>, Iters...>;
484 
485  bool operator==(const zip_first<Iters...> &other) const {
486  return std::get<0>(this->iterators) == std::get<0>(other.iterators);
487  }
488 
489  zip_first(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
490 };
491 
492 template <typename... Iters>
493 class zip_shortest : public zip_common<zip_shortest<Iters...>, Iters...> {
494  template <size_t... Ns>
495  bool test(const zip_shortest<Iters...> &other, index_sequence<Ns...>) const {
496  return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
497  std::get<Ns>(other.iterators)...},
498  identity<bool>{});
499  }
500 
501 public:
502  using Base = zip_common<zip_shortest<Iters...>, Iters...>;
503 
504  zip_shortest(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
505 
506  bool operator==(const zip_shortest<Iters...> &other) const {
507  return !test(other, index_sequence_for<Iters...>{});
508  }
509 };
510 
511 template <template <typename...> class ItType, typename... Args> class zippy {
512 public:
513  using iterator = ItType<decltype(std::begin(std::declval<Args>()))...>;
514  using iterator_category = typename iterator::iterator_category;
515  using value_type = typename iterator::value_type;
516  using difference_type = typename iterator::difference_type;
517  using pointer = typename iterator::pointer;
518  using reference = typename iterator::reference;
519 
520 private:
521  std::tuple<Args...> ts;
522 
523  template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) const {
524  return iterator(std::begin(std::get<Ns>(ts))...);
525  }
526  template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) const {
527  return iterator(std::end(std::get<Ns>(ts))...);
528  }
529 
530 public:
531  zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
532 
533  iterator begin() const { return begin_impl(index_sequence_for<Args...>{}); }
534  iterator end() const { return end_impl(index_sequence_for<Args...>{}); }
535 };
536 
537 } // end namespace detail
538 
540 template <typename T, typename U, typename... Args>
541 detail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u,
542  Args &&... args) {
543  return detail::zippy<detail::zip_shortest, T, U, Args...>(
544  std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
545 }
546 
549 template <typename T, typename U, typename... Args>
550 detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u,
551  Args &&... args) {
552  return detail::zippy<detail::zip_first, T, U, Args...>(
553  std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
554 }
555 
566 template <typename ValueT, typename... IterTs>
568  : public iterator_facade_base<concat_iterator<ValueT, IterTs...>,
569  std::forward_iterator_tag, ValueT> {
570  using BaseT = typename concat_iterator::iterator_facade_base;
571 
578  std::tuple<std::pair<IterTs, IterTs>...> IterPairs;
579 
584  template <size_t Index> bool incrementHelper() {
585  auto &IterPair = std::get<Index>(IterPairs);
586  if (IterPair.first == IterPair.second)
587  return false;
588 
589  ++IterPair.first;
590  return true;
591  }
592 
596  template <size_t... Ns> void increment(index_sequence<Ns...>) {
597  // Build a sequence of functions to increment each iterator if possible.
598  bool (concat_iterator::*IncrementHelperFns[])() = {
599  &concat_iterator::incrementHelper<Ns>...};
600 
601  // Loop over them, and stop as soon as we succeed at incrementing one.
602  for (auto &IncrementHelperFn : IncrementHelperFns)
603  if ((this->*IncrementHelperFn)())
604  return;
605 
606  assert(false && "Attempted to increment an end concat iterator!");
607  }
608 
612  template <size_t Index> ValueT *getHelper() const {
613  auto &IterPair = std::get<Index>(IterPairs);
614  if (IterPair.first == IterPair.second)
615  return nullptr;
616 
617  return &*IterPair.first;
618  }
619 
624  template <size_t... Ns> ValueT &get(index_sequence<Ns...>) const {
625  // Build a sequence of functions to get from iterator if possible.
626  ValueT *(concat_iterator::*GetHelperFns[])() const = {
627  &concat_iterator::getHelper<Ns>...};
628 
629  // Loop over them, and return the first result we find.
630  for (auto &GetHelperFn : GetHelperFns)
631  if (ValueT *P = (this->*GetHelperFn)())
632  return *P;
633 
634  assert(false && "Attempted to get a pointer from an end concat iterator!");
635  }
636 
637 public:
642  template <typename... RangeTs>
643  explicit concat_iterator(RangeTs &&... Ranges)
644  : IterPairs({std::begin(Ranges), std::end(Ranges)}...) {}
645 
646  using BaseT::operator++;
647 
648  concat_iterator &operator++() {
649  increment(index_sequence_for<IterTs...>());
650  return *this;
651  }
652 
653  ValueT &operator*() const { return get(index_sequence_for<IterTs...>()); }
654 
655  bool operator==(const concat_iterator &RHS) const {
656  return IterPairs == RHS.IterPairs;
657  }
658 };
659 
660 namespace detail {
661 
667 template <typename ValueT, typename... RangeTs> class concat_range {
668 public:
669  using iterator =
670  concat_iterator<ValueT,
671  decltype(std::begin(std::declval<RangeTs &>()))...>;
672 
673 private:
674  std::tuple<RangeTs...> Ranges;
675 
676  template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) {
677  return iterator(std::get<Ns>(Ranges)...);
678  }
679  template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) {
680  return iterator(make_range(std::end(std::get<Ns>(Ranges)),
681  std::end(std::get<Ns>(Ranges)))...);
682  }
683 
684 public:
685  concat_range(RangeTs &&... Ranges)
686  : Ranges(std::forward<RangeTs>(Ranges)...) {}
687 
688  iterator begin() { return begin_impl(index_sequence_for<RangeTs...>{}); }
689  iterator end() { return end_impl(index_sequence_for<RangeTs...>{}); }
690 };
691 
692 } // end namespace detail
693 
697 template <typename ValueT, typename... RangeTs>
698 detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) {
699  static_assert(sizeof...(RangeTs) > 1,
700  "Need more than one range to concatenate!");
701  return detail::concat_range<ValueT, RangeTs...>(
702  std::forward<RangeTs>(Ranges)...);
703 }
704 
705 //===----------------------------------------------------------------------===//
706 // Extra additions to <utility>
707 //===----------------------------------------------------------------------===//
708 
711 struct less_first {
712  template <typename T> bool operator()(const T &lhs, const T &rhs) const {
713  return lhs.first < rhs.first;
714  }
715 };
716 
719 struct less_second {
720  template <typename T> bool operator()(const T &lhs, const T &rhs) const {
721  return lhs.second < rhs.second;
722  }
723 };
724 
725 // A subset of N3658. More stuff can be added as-needed.
726 
728 template <class T, T... I> struct integer_sequence {
729  using value_type = T;
730 
731  static constexpr size_t size() { return sizeof...(I); }
732 };
733 
735 template <size_t... I>
736 struct index_sequence : integer_sequence<std::size_t, I...> {};
737 
738 template <std::size_t N, std::size_t... I>
739 struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {};
740 template <std::size_t... I>
741 struct build_index_impl<0, I...> : index_sequence<I...> {};
742 
744 template <class... Ts>
745 struct index_sequence_for : build_index_impl<sizeof...(Ts)> {};
746 
749 template <int N> struct rank : rank<N - 1> {};
750 template <> struct rank<0> {};
751 
754 template <typename T, typename... Ts> struct is_one_of {
755  static const bool value = false;
756 };
757 
758 template <typename T, typename U, typename... Ts>
759 struct is_one_of<T, U, Ts...> {
760  static const bool value =
761  std::is_same<T, U>::value || is_one_of<T, Ts...>::value;
762 };
763 
766 template <typename T, typename... Ts> struct are_base_of {
767  static const bool value = true;
768 };
769 
770 template <typename T, typename U, typename... Ts>
771 struct are_base_of<T, U, Ts...> {
772  static const bool value =
773  std::is_base_of<T, U>::value && are_base_of<T, Ts...>::value;
774 };
775 
776 //===----------------------------------------------------------------------===//
777 // Extra additions for arrays
778 //===----------------------------------------------------------------------===//
779 
781 template <class T, std::size_t N>
782 constexpr inline size_t array_lengthof(T (&)[N]) {
783  return N;
784 }
785 
787 template<typename T>
788 inline int array_pod_sort_comparator(const void *P1, const void *P2) {
789  if (std::less<T>()(*reinterpret_cast<const T*>(P1),
790  *reinterpret_cast<const T*>(P2)))
791  return -1;
792  if (std::less<T>()(*reinterpret_cast<const T*>(P2),
793  *reinterpret_cast<const T*>(P1)))
794  return 1;
795  return 0;
796 }
797 
800 template<typename T>
801 inline int (*get_array_pod_sort_comparator(const T &))
802  (const void*, const void*) {
803  return array_pod_sort_comparator<T>;
804 }
805 
820 template<class IteratorTy>
821 inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
822  // Don't inefficiently call qsort with one element or trigger undefined
823  // behavior with an empty sequence.
824  auto NElts = End - Start;
825  if (NElts <= 1) return;
826  qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
827 }
828 
829 template <class IteratorTy>
830 inline void array_pod_sort(
831  IteratorTy Start, IteratorTy End,
832  int (*Compare)(
833  const typename std::iterator_traits<IteratorTy>::value_type *,
834  const typename std::iterator_traits<IteratorTy>::value_type *)) {
835  // Don't inefficiently call qsort with one element or trigger undefined
836  // behavior with an empty sequence.
837  auto NElts = End - Start;
838  if (NElts <= 1) return;
839  qsort(&*Start, NElts, sizeof(*Start),
840  reinterpret_cast<int (*)(const void *, const void *)>(Compare));
841 }
842 
843 //===----------------------------------------------------------------------===//
844 // Extra additions to <algorithm>
845 //===----------------------------------------------------------------------===//
846 
849 template<typename Container>
850 void DeleteContainerPointers(Container &C) {
851  for (auto V : C)
852  delete V;
853  C.clear();
854 }
855 
858 template<typename Container>
859 void DeleteContainerSeconds(Container &C) {
860  for (auto &V : C)
861  delete V.second;
862  C.clear();
863 }
864 
867 template <typename R, typename UnaryPredicate>
868 UnaryPredicate for_each(R &&Range, UnaryPredicate P) {
869  return std::for_each(adl_begin(Range), adl_end(Range), P);
870 }
871 
874 template <typename R, typename UnaryPredicate>
875 bool all_of(R &&Range, UnaryPredicate P) {
876  return std::all_of(adl_begin(Range), adl_end(Range), P);
877 }
878 
881 template <typename R, typename UnaryPredicate>
882 bool any_of(R &&Range, UnaryPredicate P) {
883  return std::any_of(adl_begin(Range), adl_end(Range), P);
884 }
885 
888 template <typename R, typename UnaryPredicate>
889 bool none_of(R &&Range, UnaryPredicate P) {
890  return std::none_of(adl_begin(Range), adl_end(Range), P);
891 }
892 
895 template <typename R, typename T>
896 auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range)) {
897  return std::find(adl_begin(Range), adl_end(Range), Val);
898 }
899 
902 template <typename R, typename UnaryPredicate>
903 auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
904  return std::find_if(adl_begin(Range), adl_end(Range), P);
905 }
906 
907 template <typename R, typename UnaryPredicate>
908 auto find_if_not(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
909  return std::find_if_not(adl_begin(Range), adl_end(Range), P);
910 }
911 
914 template <typename R, typename UnaryPredicate>
915 auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
916  return std::remove_if(adl_begin(Range), adl_end(Range), P);
917 }
918 
921 template <typename R, typename OutputIt, typename UnaryPredicate>
922 OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) {
923  return std::copy_if(adl_begin(Range), adl_end(Range), Out, P);
924 }
925 
926 template <typename R, typename OutputIt>
927 OutputIt copy(R &&Range, OutputIt Out) {
928  return std::copy(adl_begin(Range), adl_end(Range), Out);
929 }
930 
933 template <typename R, typename E>
934 bool is_contained(R &&Range, const E &Element) {
935  return std::find(adl_begin(Range), adl_end(Range), Element) != adl_end(Range);
936 }
937 
940 template <typename R, typename E>
941 auto count(R &&Range, const E &Element) ->
942  typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
943  return std::count(adl_begin(Range), adl_end(Range), Element);
944 }
945 
948 template <typename R, typename UnaryPredicate>
949 auto count_if(R &&Range, UnaryPredicate P) ->
950  typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
951  return std::count_if(adl_begin(Range), adl_end(Range), P);
952 }
953 
956 template <typename R, typename OutputIt, typename UnaryPredicate>
957 OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P) {
958  return std::transform(adl_begin(Range), adl_end(Range), d_first, P);
959 }
960 
963 template <typename R, typename UnaryPredicate>
964 auto partition(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
965  return std::partition(adl_begin(Range), adl_end(Range), P);
966 }
967 
970 template <typename R, typename ForwardIt>
971 auto lower_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range)) {
972  return std::lower_bound(adl_begin(Range), adl_end(Range), I);
973 }
974 
978 template <unsigned Size, typename R>
979 SmallVector<typename std::remove_const<detail::ValueOfRange<R>>::type, Size>
980 to_vector(R &&Range) {
981  return {adl_begin(Range), adl_end(Range)};
982 }
983 
991 template <typename Container, typename UnaryPredicate>
992 void erase_if(Container &C, UnaryPredicate P) {
993  C.erase(remove_if(C, P), C.end());
994 }
995 
998 template <typename R>
999 auto size(R &&Range, typename std::enable_if<
1000  std::is_same<typename std::iterator_traits<decltype(
1001  Range.begin())>::iterator_category,
1002  std::random_access_iterator_tag>::value,
1003  void>::type * = nullptr)
1004  -> decltype(std::distance(Range.begin(), Range.end())) {
1005  return std::distance(Range.begin(), Range.end());
1006 }
1007 
1008 //===----------------------------------------------------------------------===//
1009 // Extra additions to <memory>
1010 //===----------------------------------------------------------------------===//
1011 
1012 // Implement make_unique according to N3656.
1013 
1021 template <class T, class... Args>
1022 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
1023 make_unique(Args &&... args) {
1024  return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
1025 }
1026 
1035 template <class T>
1036 typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0,
1037  std::unique_ptr<T>>::type
1038 make_unique(size_t n) {
1039  return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
1040 }
1041 
1043 template <class T, class... Args>
1044 typename std::enable_if<std::extent<T>::value != 0>::type
1045 make_unique(Args &&...) = delete;
1046 
1047 struct FreeDeleter {
1048  void operator()(void* v) {
1049  ::free(v);
1050  }
1051 };
1052 
1053 template<typename First, typename Second>
1054 struct pair_hash {
1055  size_t operator()(const std::pair<First, Second> &P) const {
1056  return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second);
1057  }
1058 };
1059 
1061 struct less {
1062  template <typename A, typename B> bool operator()(A &&a, B &&b) const {
1063  return std::forward<A>(a) < std::forward<B>(b);
1064  }
1065 };
1066 
1068 struct equal {
1069  template <typename A, typename B> bool operator()(A &&a, B &&b) const {
1070  return std::forward<A>(a) == std::forward<B>(b);
1071  }
1072 };
1073 
1076 template <typename T> struct deref {
1077  T func;
1078 
1079  // Could be further improved to cope with non-derivable functors and
1080  // non-binary functors (should be a variadic template member function
1081  // operator()).
1082  template <typename A, typename B>
1083  auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) {
1084  assert(lhs);
1085  assert(rhs);
1086  return func(*lhs, *rhs);
1087  }
1088 };
1089 
1090 namespace detail {
1091 
1092 template <typename R> class enumerator_iter;
1093 
1094 template <typename R> struct result_pair {
1095  friend class enumerator_iter<R>;
1096 
1097  result_pair() = default;
1098  result_pair(std::size_t Index, IterOfRange<R> Iter)
1099  : Index(Index), Iter(Iter) {}
1100 
1101  result_pair<R> &operator=(const result_pair<R> &Other) {
1102  Index = Other.Index;
1103  Iter = Other.Iter;
1104  return *this;
1105  }
1106 
1107  std::size_t index() const { return Index; }
1108  const ValueOfRange<R> &value() const { return *Iter; }
1109  ValueOfRange<R> &value() { return *Iter; }
1110 
1111 private:
1112  std::size_t Index = std::numeric_limits<std::size_t>::max();
1113  IterOfRange<R> Iter;
1114 };
1115 
1116 template <typename R>
1117 class enumerator_iter
1118  : public iterator_facade_base<
1119  enumerator_iter<R>, std::forward_iterator_tag, result_pair<R>,
1120  typename std::iterator_traits<IterOfRange<R>>::difference_type,
1121  typename std::iterator_traits<IterOfRange<R>>::pointer,
1122  typename std::iterator_traits<IterOfRange<R>>::reference> {
1123  using result_type = result_pair<R>;
1124 
1125 public:
1126  explicit enumerator_iter(IterOfRange<R> EndIter)
1127  : Result(std::numeric_limits<size_t>::max(), EndIter) {}
1128 
1129  enumerator_iter(std::size_t Index, IterOfRange<R> Iter)
1130  : Result(Index, Iter) {}
1131 
1132  result_type &operator*() { return Result; }
1133  const result_type &operator*() const { return Result; }
1134 
1135  enumerator_iter<R> &operator++() {
1136  assert(Result.Index != std::numeric_limits<size_t>::max());
1137  ++Result.Iter;
1138  ++Result.Index;
1139  return *this;
1140  }
1141 
1142  bool operator==(const enumerator_iter<R> &RHS) const {
1143  // Don't compare indices here, only iterators. It's possible for an end
1144  // iterator to have different indices depending on whether it was created
1145  // by calling std::end() versus incrementing a valid iterator.
1146  return Result.Iter == RHS.Result.Iter;
1147  }
1148 
1149  enumerator_iter<R> &operator=(const enumerator_iter<R> &Other) {
1150  Result = Other.Result;
1151  return *this;
1152  }
1153 
1154 private:
1155  result_type Result;
1156 };
1157 
1158 template <typename R> class enumerator {
1159 public:
1160  explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {}
1161 
1162  enumerator_iter<R> begin() {
1163  return enumerator_iter<R>(0, std::begin(TheRange));
1164  }
1165 
1166  enumerator_iter<R> end() {
1167  return enumerator_iter<R>(std::end(TheRange));
1168  }
1169 
1170 private:
1171  R TheRange;
1172 };
1173 
1174 } // end namespace detail
1175 
1191 template <typename R> detail::enumerator<R> enumerate(R &&TheRange) {
1192  return detail::enumerator<R>(std::forward<R>(TheRange));
1193 }
1194 
1195 namespace detail {
1196 
1197 template <typename F, typename Tuple, std::size_t... I>
1198 auto apply_tuple_impl(F &&f, Tuple &&t, index_sequence<I...>)
1199  -> decltype(std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...)) {
1200  return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...);
1201 }
1202 
1203 } // end namespace detail
1204 
1208 template <typename F, typename Tuple>
1209 auto apply_tuple(F &&f, Tuple &&t) -> decltype(detail::apply_tuple_impl(
1210  std::forward<F>(f), std::forward<Tuple>(t),
1212  std::tuple_size<typename std::decay<Tuple>::type>::value>{})) {
1213  using Indices = build_index_impl<
1214  std::tuple_size<typename std::decay<Tuple>::type>::value>;
1215 
1216  return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t),
1217  Indices{});
1218 }
1219 
1220 } // end namespace wpi
1221 
1222 #endif // LLVM_ADT_STLEXTRAS_H
Helper to store a sequence of ranges being concatenated and access them.
Definition: STLExtras.h:667
Definition: STLExtras.h:482
Function object to check whether the first component of a std::pair compares less than the first comp...
Definition: STLExtras.h:711
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:1191
A functor like C++14's std::less in its absence.
Definition: STLExtras.h:1061
Metafunction to determine if T& or T has a member called rbegin().
Definition: STLExtras.h:226
Definition: STLExtras.h:42
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:949
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:957
An iterator adaptor that filters the elements of given inner iterators.
Definition: STLExtras.h:274
Definition: STLExtras.h:493
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
int array_pod_sort_comparator(const void *P1, const void *P2)
Adapt std::less for array_pod_sort.
Definition: STLExtras.h:788
Definition: STLExtras.h:438
Iterator wrapper that concatenates sequences together.
Definition: STLExtras.h:567
Definition: optional.h:885
Utility type to build an inheritance chain that makes it easy to rank overload candidates.
Definition: STLExtras.h:749
Alias for the common case of a sequence of size_ts.
Definition: STLExtras.h:407
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:980
Specialization of filter_iterator_base for forward iteration only.
Definition: STLExtras.h:319
Definition: STLExtras.h:185
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:964
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:550
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:903
WPILib C++ utilities (wpiutil) namespace.
Definition: SmallString.h:21
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:971
Definition: STLExtras.h:511
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:208
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:68
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:88
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:393
Function object to check whether the second component of a std::pair compares less than the second co...
Definition: STLExtras.h:719
Creates a compile-time integer sequence for a parameter pack.
Definition: STLExtras.h:409
concat_iterator(RangeTs &&...Ranges)
Constructs an iterator from a squence of ranges.
Definition: STLExtras.h:643
Definition: STLExtras.h:417
A range adaptor for a pair of iterators.
Definition: iterator_range.h:32
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:859
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:896
auto apply_tuple(F &&f, Tuple &&t) -> decltype(detail::apply_tuple_impl(std::forward< F >(f), std::forward< Tuple >(t), build_index_impl< std::tuple_size< typename std::decay< Tuple >::type >::value >
Given an input tuple (a1, a2, ..., an), pass the arguments of the tuple variadically to f as if by ca...
Definition: STLExtras.h:1209
void DeleteContainerPointers(Container &C)
For a container of pointers, deletes the pointers and then clears the container.
Definition: STLExtras.h:850
std::enable_if<!std::is_array< T >::value, std::unique_ptr< T > >::type make_unique(Args &&...args)
Constructs a new T() with the given args and returns a unique_ptr which owns the object...
Definition: STLExtras.h:1023
Definition: STLExtras.h:358
Definition: json.h:243
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:889
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:541
Definition: STLExtras.h:1094
Definition: STLExtras.h:1092
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:801
Definition: STLExtras.h:739
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:882
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:54
Definition: STLExtras.h:70
Definition: STLExtras.h:59
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:875
Definition: json.h:225
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:999
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:821
Definition: STLExtras.h:1047
Represents a compile-time sequence of integers.
Definition: STLExtras.h:728
Definition: STLExtras.h:76
Definition: STLExtras.h:1158
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:941
traits class for checking whether type T is one of any of the given types in the variadic list...
Definition: STLExtras.h:754
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:922
constexpr size_t array_lengthof(T(&)[N])
Find the length of an array.
Definition: STLExtras.h:782
Definition: STLExtras.h:1054
A functor like C++14's std::equal in its absence.
Definition: STLExtras.h:1068
Helper to determine if type T has a member called rbegin().
Definition: STLExtras.h:210
traits class for checking whether type T is a base class for all the given types in the variadic list...
Definition: STLExtras.h:766
Binary functor that adapts to any other binary functor after dereferencing operands.
Definition: STLExtras.h:1076
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:868
Helper which sets its type member to forward_iterator_tag if the category of IterT does not derive fr...
Definition: STLExtras.h:369
detail::concat_range< ValueT, RangeTs...> concat(RangeTs &&...Ranges)
Concatenated range across two or more ranges.
Definition: STLExtras.h:698
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:934
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:915
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:992