WPILibC++  unspecified
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 LLVM_ADT_STLEXTRAS_H
18 #define LLVM_ADT_STLEXTRAS_H
19 
20 #include <algorithm> // for std::all_of
21 #include <cassert>
22 #include <cstddef> // for std::size_t
23 #include <cstdlib> // for qsort
24 #include <functional>
25 #include <iterator>
26 #include <memory>
27 #include <utility> // for std::pair
28 
29 #include "llvm/iterator_range.h"
30 #include "llvm/Compiler.h"
31 
32 namespace llvm {
33 
34 //===----------------------------------------------------------------------===//
35 // Extra additions to <functional>
36 //===----------------------------------------------------------------------===//
37 
38 template<class Ty>
39 struct identity : public std::unary_function<Ty, Ty> {
40  Ty &operator()(Ty &self) const {
41  return self;
42  }
43  const Ty &operator()(const Ty &self) const {
44  return self;
45  }
46 };
47 
48 template<class Ty>
49 struct less_ptr : public std::binary_function<Ty, Ty, bool> {
50  bool operator()(const Ty* left, const Ty* right) const {
51  return *left < *right;
52  }
53 };
54 
55 template<class Ty>
56 struct greater_ptr : public std::binary_function<Ty, Ty, bool> {
57  bool operator()(const Ty* left, const Ty* right) const {
58  return *right < *left;
59  }
60 };
61 
68 template<typename Fn> class function_ref;
69 
70 template<typename Ret, typename ...Params>
71 class function_ref<Ret(Params...)> {
72  Ret (*callback)(intptr_t callable, Params ...params);
73  intptr_t callable;
74 
75  template<typename Callable>
76  static Ret callback_fn(intptr_t callable, Params ...params) {
77  return (*reinterpret_cast<Callable*>(callable))(
78  std::forward<Params>(params)...);
79  }
80 
81 public:
82  template <typename Callable>
83  function_ref(Callable &&callable,
84  typename std::enable_if<
85  !std::is_same<typename std::remove_reference<Callable>::type,
86  function_ref>::value>::type * = nullptr)
87  : callback(callback_fn<typename std::remove_reference<Callable>::type>),
88  callable(reinterpret_cast<intptr_t>(&callable)) {}
89  Ret operator()(Params ...params) const {
90  return callback(callable, std::forward<Params>(params)...);
91  }
92 };
93 
94 // deleter - Very very very simple method that is used to invoke operator
95 // delete on something. It is used like this:
96 //
97 // for_each(V.begin(), B.end(), deleter<Interval>);
98 //
99 template <class T>
100 inline void deleter(T *Ptr) {
101  delete Ptr;
102 }
103 
104 
105 
106 //===----------------------------------------------------------------------===//
107 // Extra additions to <iterator>
108 //===----------------------------------------------------------------------===//
109 
110 // mapped_iterator - This is a simple iterator adapter that causes a function to
111 // be dereferenced whenever operator* is invoked on the iterator.
112 //
113 template <class RootIt, class UnaryFunc>
115  RootIt current;
116  UnaryFunc Fn;
117 public:
118  typedef typename std::iterator_traits<RootIt>::iterator_category
119  iterator_category;
120  typedef typename std::iterator_traits<RootIt>::difference_type
121  difference_type;
122  typedef typename std::result_of<
123  UnaryFunc(decltype(*std::declval<RootIt>()))>
124  ::type value_type;
125 
126  typedef void pointer;
127  //typedef typename UnaryFunc::result_type *pointer;
128  typedef void reference; // Can't modify value returned by fn
129 
130  typedef RootIt iterator_type;
131 
132  inline const RootIt &getCurrent() const { return current; }
133  inline const UnaryFunc &getFunc() const { return Fn; }
134 
135  inline explicit mapped_iterator(const RootIt &I, UnaryFunc F)
136  : current(I), Fn(F) {}
137 
138  inline value_type operator*() const { // All this work to do this
139  return Fn(*current); // little change
140  }
141 
142  mapped_iterator &operator++() {
143  ++current;
144  return *this;
145  }
146  mapped_iterator &operator--() {
147  --current;
148  return *this;
149  }
150  mapped_iterator operator++(int) {
151  mapped_iterator __tmp = *this;
152  ++current;
153  return __tmp;
154  }
155  mapped_iterator operator--(int) {
156  mapped_iterator __tmp = *this;
157  --current;
158  return __tmp;
159  }
160  mapped_iterator operator+(difference_type n) const {
161  return mapped_iterator(current + n, Fn);
162  }
163  mapped_iterator &operator+=(difference_type n) {
164  current += n;
165  return *this;
166  }
167  mapped_iterator operator-(difference_type n) const {
168  return mapped_iterator(current - n, Fn);
169  }
170  mapped_iterator &operator-=(difference_type n) {
171  current -= n;
172  return *this;
173  }
174  reference operator[](difference_type n) const { return *(*this + n); }
175 
176  bool operator!=(const mapped_iterator &X) const { return !operator==(X); }
177  bool operator==(const mapped_iterator &X) const {
178  return current == X.current;
179  }
180  bool operator<(const mapped_iterator &X) const { return current < X.current; }
181 
182  difference_type operator-(const mapped_iterator &X) const {
183  return current - X.current;
184  }
185 };
186 
187 template <class Iterator, class Func>
189 operator+(typename mapped_iterator<Iterator, Func>::difference_type N,
191  return mapped_iterator<Iterator, Func>(X.getCurrent() - N, X.getFunc());
192 }
193 
194 
195 // map_iterator - Provide a convenient way to create mapped_iterators, just like
196 // make_pair is useful for creating pairs...
197 //
198 template <class ItTy, class FuncTy>
199 inline mapped_iterator<ItTy, FuncTy> map_iterator(const ItTy &I, FuncTy F) {
200  return mapped_iterator<ItTy, FuncTy>(I, F);
201 }
202 
204 template <typename T> struct has_rbegin {
205  template <typename U> static char(&f(const U &, decltype(&U::rbegin)))[1];
206  static char(&f(...))[2];
207  const static bool value = sizeof(f(std::declval<T>(), nullptr)) == 1;
208 };
209 
210 // Returns an iterator_range over the given container which iterates in reverse.
211 // Note that the container must have rbegin()/rend() methods for this to work.
212 template <typename ContainerTy>
213 auto reverse(ContainerTy &&C,
214  typename std::enable_if<has_rbegin<ContainerTy>::value>::type * =
215  nullptr) -> decltype(make_range(C.rbegin(), C.rend())) {
216  return make_range(C.rbegin(), C.rend());
217 }
218 
219 // Returns a std::reverse_iterator wrapped around the given iterator.
220 template <typename IteratorTy>
221 std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) {
222  return std::reverse_iterator<IteratorTy>(It);
223 }
224 
225 // Returns an iterator_range over the given container which iterates in reverse.
226 // Note that the container must have begin()/end() methods which return
227 // bidirectional iterators for this to work.
228 template <typename ContainerTy>
229 auto reverse(
230  ContainerTy &&C,
231  typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr)
232  -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)),
233  llvm::make_reverse_iterator(std::begin(C)))) {
234  return make_range(llvm::make_reverse_iterator(std::end(C)),
235  llvm::make_reverse_iterator(std::begin(C)));
236 }
237 
238 //===----------------------------------------------------------------------===//
239 // Extra additions to <utility>
240 //===----------------------------------------------------------------------===//
241 
244 struct less_first {
245  template <typename T> bool operator()(const T &lhs, const T &rhs) const {
246  return lhs.first < rhs.first;
247  }
248 };
249 
252 struct less_second {
253  template <typename T> bool operator()(const T &lhs, const T &rhs) const {
254  return lhs.second < rhs.second;
255  }
256 };
257 
258 // A subset of N3658. More stuff can be added as-needed.
259 
261 template <class T, T... I> struct integer_sequence {
262  typedef T value_type;
263 
264  static LLVM_CONSTEXPR size_t size() { return sizeof...(I); }
265 };
266 
268 template <size_t... I>
269 struct index_sequence : integer_sequence<std::size_t, I...> {};
270 
271 template <std::size_t N, std::size_t... I>
272 struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {};
273 template <std::size_t... I>
274 struct build_index_impl<0, I...> : index_sequence<I...> {};
275 
277 template <class... Ts>
278 struct index_sequence_for : build_index_impl<sizeof...(Ts)> {};
279 
280 //===----------------------------------------------------------------------===//
281 // Extra additions for arrays
282 //===----------------------------------------------------------------------===//
283 
285 template <class T, std::size_t N>
286 LLVM_CONSTEXPR inline size_t array_lengthof(T (&)[N]) {
287  return N;
288 }
289 
291 template<typename T>
292 inline int array_pod_sort_comparator(const void *P1, const void *P2) {
293  if (std::less<T>()(*reinterpret_cast<const T*>(P1),
294  *reinterpret_cast<const T*>(P2)))
295  return -1;
296  if (std::less<T>()(*reinterpret_cast<const T*>(P2),
297  *reinterpret_cast<const T*>(P1)))
298  return 1;
299  return 0;
300 }
301 
304 template<typename T>
305 inline int (*get_array_pod_sort_comparator(const T &))
306  (const void*, const void*) {
307  return array_pod_sort_comparator<T>;
308 }
309 
310 
325 template<class IteratorTy>
326 inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
327  // Don't inefficiently call qsort with one element or trigger undefined
328  // behavior with an empty sequence.
329  auto NElts = End - Start;
330  if (NElts <= 1) return;
331  qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
332 }
333 
334 template <class IteratorTy>
335 inline void array_pod_sort(
336  IteratorTy Start, IteratorTy End,
337  int (*Compare)(
338  const typename std::iterator_traits<IteratorTy>::value_type *,
339  const typename std::iterator_traits<IteratorTy>::value_type *)) {
340  // Don't inefficiently call qsort with one element or trigger undefined
341  // behavior with an empty sequence.
342  auto NElts = End - Start;
343  if (NElts <= 1) return;
344  qsort(&*Start, NElts, sizeof(*Start),
345  reinterpret_cast<int (*)(const void *, const void *)>(Compare));
346 }
347 
348 //===----------------------------------------------------------------------===//
349 // Extra additions to <algorithm>
350 //===----------------------------------------------------------------------===//
351 
354 template<typename Container>
355 void DeleteContainerPointers(Container &C) {
356  for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I)
357  delete *I;
358  C.clear();
359 }
360 
363 template<typename Container>
364 void DeleteContainerSeconds(Container &C) {
365  for (typename Container::iterator I = C.begin(), E = C.end(); I != E; ++I)
366  delete I->second;
367  C.clear();
368 }
369 
372 template<typename R, class UnaryPredicate>
373 bool all_of(R &&Range, UnaryPredicate &&P) {
374  return std::all_of(Range.begin(), Range.end(),
375  std::forward<UnaryPredicate>(P));
376 }
377 
380 template <typename R, class UnaryPredicate>
381 bool any_of(R &&Range, UnaryPredicate &&P) {
382  return std::any_of(Range.begin(), Range.end(),
383  std::forward<UnaryPredicate>(P));
384 }
385 
388 template <typename R, class UnaryPredicate>
389 bool none_of(R &&Range, UnaryPredicate &&P) {
390  return std::none_of(Range.begin(), Range.end(),
391  std::forward<UnaryPredicate>(P));
392 }
393 
396 template<typename R, class T>
397 auto find(R &&Range, const T &val) -> decltype(Range.begin()) {
398  return std::find(Range.begin(), Range.end(), val);
399 }
400 
403 template <typename R, class T>
404 auto find_if(R &&Range, const T &Pred) -> decltype(Range.begin()) {
405  return std::find_if(Range.begin(), Range.end(), Pred);
406 }
407 
410 template<typename R, class UnaryPredicate>
411 auto remove_if(R &&Range, UnaryPredicate &&P) -> decltype(Range.begin()) {
412  return std::remove_if(Range.begin(), Range.end(), P);
413 }
414 
417 template <typename R, typename E>
418 bool is_contained(R &&Range, const E &Element) {
419  return std::find(Range.begin(), Range.end(), Element) != Range.end();
420 }
421 
424 template <typename R, typename UnaryPredicate>
425 auto count_if(R &&Range, UnaryPredicate &&P)
426  -> typename std::iterator_traits<decltype(Range.begin())>::difference_type {
427  return std::count_if(Range.begin(), Range.end(), P);
428 }
429 
432 template <typename R, class OutputIt, typename UnaryPredicate>
433 OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate &&P) {
434  return std::transform(Range.begin(), Range.end(), d_first,
435  std::forward<UnaryPredicate>(P));
436 }
437 
438 //===----------------------------------------------------------------------===//
439 // Extra additions to <memory>
440 //===----------------------------------------------------------------------===//
441 
442 // Implement make_unique according to N3656.
443 
451 template <class T, class... Args>
452 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
453 make_unique(Args &&... args) {
454  return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
455 }
456 
465 template <class T>
466 typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0,
467  std::unique_ptr<T>>::type
468 make_unique(size_t n) {
469  return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
470 }
471 
473 template <class T, class... Args>
474 typename std::enable_if<std::extent<T>::value != 0>::type
475 make_unique(Args &&...) = delete;
476 
477 struct FreeDeleter {
478  void operator()(void* v) {
479  ::free(v);
480  }
481 };
482 
483 template<typename First, typename Second>
484 struct pair_hash {
485  size_t operator()(const std::pair<First, Second> &P) const {
486  return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second);
487  }
488 };
489 
491 struct less {
492  template <typename A, typename B> bool operator()(A &&a, B &&b) const {
493  return std::forward<A>(a) < std::forward<B>(b);
494  }
495 };
496 
498 struct equal {
499  template <typename A, typename B> bool operator()(A &&a, B &&b) const {
500  return std::forward<A>(a) == std::forward<B>(b);
501  }
502 };
503 
506 template <typename T> struct deref {
507  T func;
508  // Could be further improved to cope with non-derivable functors and
509  // non-binary functors (should be a variadic template member function
510  // operator()).
511  template <typename A, typename B>
512  auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) {
513  assert(lhs);
514  assert(rhs);
515  return func(*lhs, *rhs);
516  }
517 };
518 
519 } // End llvm namespace
520 
521 #endif
Definition: STLExtras.h:56
Definition: Path.inc:31
Function object to check whether the second component of a std::pair compares less than the second co...
Definition: STLExtras.h:252
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:68
A functor like C++14&#39;s std::less<void> in its absence.
Definition: STLExtras.h:491
Metafunction to determine if type T has a member called rbegin().
Definition: STLExtras.h:204
Alias for the common case of a sequence of size_ts.
Definition: STLExtras.h:269
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:54
Definition: STLExtras.h:49
Definition: STLExtras.h:114
Definition: STLExtras.h:272
A functor like C++14&#39;s std::equal<void> in its absence.
Definition: STLExtras.h:498
Creates a compile-time integer sequence for a parameter pack.
Definition: STLExtras.h:278
Represents a compile-time sequence of integers.
Definition: STLExtras.h:261
Definition: STLExtras.h:477
Definition: STLExtras.h:39
Binary functor that adapts to any other binary functor after dereferencing operands.
Definition: STLExtras.h:506
Definition: STLExtras.h:484
Function object to check whether the first component of a std::pair compares less than the first comp...
Definition: STLExtras.h:244