STLExtras.h revision 718cb665ca6ce2bc4d8e8479f46a45db91b49f86 
1//===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file was developed by the LLVM research group and is distributed under
6// the University of Illinois Open Source 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 functinons.
14//
15//===----------------------------------------------------------------------===//
16
17#ifndef LLVM_ADT_STLEXTRAS_H
18#define LLVM_ADT_STLEXTRAS_H
19
20#include <functional>
21#include <utility> // for std::pair
22#include <cstring> // for std::size_t
23#include "llvm/ADT/iterator"
24
25namespace llvm {
26
27//===----------------------------------------------------------------------===//
28//     Extra additions to <functional>
29//===----------------------------------------------------------------------===//
30
31template<class Ty>
32struct greater_ptr : public std::binary_function<Ty, Ty, bool> {
33  bool operator()(const Ty* left, const Ty* right) const {
34    return *right < *left;
35  }
36};
37
38// deleter - Very very very simple method that is used to invoke operator
39// delete on something.  It is used like this:
40//
41//   for_each(V.begin(), B.end(), deleter<Interval>);
42//
43template <class T>
44static inline void deleter(T *Ptr) {
45  delete Ptr;
46}
47
48
49
50//===----------------------------------------------------------------------===//
51//     Extra additions to <iterator>
52//===----------------------------------------------------------------------===//
53
54// mapped_iterator - This is a simple iterator adapter that causes a function to
55// be dereferenced whenever operator* is invoked on the iterator.
56//
57template <class RootIt, class UnaryFunc>
58class mapped_iterator {
59  RootIt current;
60  UnaryFunc Fn;
61public:
62  typedef typename std::iterator_traits<RootIt>::iterator_category
63          iterator_category;
64  typedef typename std::iterator_traits<RootIt>::difference_type
65          difference_type;
66  typedef typename UnaryFunc::result_type value_type;
67
68  typedef void pointer;
69  //typedef typename UnaryFunc::result_type *pointer;
70  typedef void reference;        // Can't modify value returned by fn
71
72  typedef RootIt iterator_type;
73  typedef mapped_iterator<RootIt, UnaryFunc> _Self;
74
75  inline const RootIt &getCurrent() const { return current; }
76
77  inline explicit mapped_iterator(const RootIt &I, UnaryFunc F)
78    : current(I), Fn(F) {}
79  inline mapped_iterator(const mapped_iterator &It)
80    : current(It.current), Fn(It.Fn) {}
81
82  inline value_type operator*() const {   // All this work to do this
83    return Fn(*current);         // little change
84  }
85
86  _Self& operator++() { ++current; return *this; }
87  _Self& operator--() { --current; return *this; }
88  _Self  operator++(int) { _Self __tmp = *this; ++current; return __tmp; }
89  _Self  operator--(int) { _Self __tmp = *this; --current; return __tmp; }
90  _Self  operator+    (difference_type n) const { return _Self(current + n); }
91  _Self& operator+=   (difference_type n) { current += n; return *this; }
92  _Self  operator-    (difference_type n) const { return _Self(current - n); }
93  _Self& operator-=   (difference_type n) { current -= n; return *this; }
94  reference operator[](difference_type n) const { return *(*this + n); }
95
96  inline bool operator!=(const _Self &X) const { return !operator==(X); }
97  inline bool operator==(const _Self &X) const { return current == X.current; }
98  inline bool operator< (const _Self &X) const { return current <  X.current; }
99
100  inline difference_type operator-(const _Self &X) const {
101    return current - X.current;
102  }
103};
104
105template <class _Iterator, class Func>
106inline mapped_iterator<_Iterator, Func>
107operator+(typename mapped_iterator<_Iterator, Func>::difference_type N,
108          const mapped_iterator<_Iterator, Func>& X) {
109  return mapped_iterator<_Iterator, Func>(X.getCurrent() - N);
110}
111
112
113// map_iterator - Provide a convenient way to create mapped_iterators, just like
114// make_pair is useful for creating pairs...
115//
116template <class ItTy, class FuncTy>
117inline mapped_iterator<ItTy, FuncTy> map_iterator(const ItTy &I, FuncTy F) {
118  return mapped_iterator<ItTy, FuncTy>(I, F);
119}
120
121
122// next/prior - These functions unlike std::advance do not modify the
123// passed iterator but return a copy.
124//
125// next(myIt) returns copy of myIt incremented once
126// next(myIt, n) returns copy of myIt incremented n times
127// prior(myIt) returns copy of myIt decremented once
128// prior(myIt, n) returns copy of myIt decremented n times
129
130template <typename ItTy, typename Dist>
131inline ItTy next(ItTy it, Dist n)
132{
133  std::advance(it, n);
134  return it;
135}
136
137template <typename ItTy>
138inline ItTy next(ItTy it)
139{
140  std::advance(it, 1);
141  return it;
142}
143
144template <typename ItTy, typename Dist>
145inline ItTy prior(ItTy it, Dist n)
146{
147  std::advance(it, -n);
148  return it;
149}
150
151template <typename ItTy>
152inline ItTy prior(ItTy it)
153{
154  std::advance(it, -1);
155  return it;
156}
157
158//===----------------------------------------------------------------------===//
159//     Extra additions to <utility>
160//===----------------------------------------------------------------------===//
161
162// tie - this function ties two objects and returns a temporary object
163// that is assignable from a std::pair. This can be used to make code
164// more readable when using values returned from functions bundled in
165// a std::pair. Since an example is worth 1000 words:
166//
167// typedef std::map<int, int> Int2IntMap;
168//
169// Int2IntMap myMap;
170// Int2IntMap::iterator where;
171// bool inserted;
172// tie(where, inserted) = myMap.insert(std::make_pair(123,456));
173//
174// if (inserted)
175//   // do stuff
176// else
177//   // do other stuff
178
179namespace
180{
181  template <typename T1, typename T2>
182  struct tier {
183    typedef T1 &first_type;
184    typedef T2 &second_type;
185
186    first_type first;
187    second_type second;
188
189    tier(first_type f, second_type s) : first(f), second(s) { }
190    tier& operator=(const std::pair<T1, T2>& p) {
191      first = p.first;
192      second = p.second;
193      return *this;
194    }
195  };
196}
197
198template <typename T1, typename T2>
199inline tier<T1, T2> tie(T1& f, T2& s) {
200  return tier<T1, T2>(f, s);
201}
202
203//===----------------------------------------------------------------------===//
204//     Extra additions to arrays
205//===----------------------------------------------------------------------===//
206
207/// Find where an array ends (for ending iterators)
208/// This returns a pointer to the byte immediately
209/// after the end of an array.
210template<class T, std::size_t N>
211inline T *array_endof(T (&x)[N]) {
212  return x+N;
213}
214
215/// Find the length of an array.
216template<class T, std::size_t N>
217inline size_t array_lengthof(T (&x)[N]) {
218  return N;
219}
220
221} // End llvm namespace
222
223#endif
224