LLVM API Documentation
00001 //===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file contains some templates that are useful if you are working with the 00011 // STL at all. 00012 // 00013 // No library is required when using these functinons. 00014 // 00015 //===----------------------------------------------------------------------===// 00016 00017 #ifndef LLVM_ADT_STLEXTRAS_H 00018 #define LLVM_ADT_STLEXTRAS_H 00019 00020 #include <functional> 00021 #include <utility> // for std::pair 00022 #include "llvm/ADT/iterator" 00023 00024 namespace llvm { 00025 00026 //===----------------------------------------------------------------------===// 00027 // Extra additions to <functional> 00028 //===----------------------------------------------------------------------===// 00029 00030 // bind_obj - Often times you want to apply the member function of an object 00031 // as a unary functor. This macro is shorthand that makes it happen less 00032 // verbosely. 00033 // 00034 // Example: 00035 // struct Summer { void accumulate(int x); } 00036 // vector<int> Numbers; 00037 // Summer MyS; 00038 // for_each(Numbers.begin(), Numbers.end(), 00039 // bind_obj(&MyS, &Summer::accumulate)); 00040 // 00041 // TODO: When I get lots of extra time, convert this from an evil macro 00042 // 00043 #define bind_obj(OBJ, METHOD) std::bind1st(std::mem_fun(METHOD), OBJ) 00044 00045 00046 // bitwise_or - This is a simple functor that applys operator| on its two 00047 // arguments to get a boolean result. 00048 // 00049 template<class Ty> 00050 struct bitwise_or : public std::binary_function<Ty, Ty, bool> { 00051 bool operator()(const Ty& left, const Ty& right) const { 00052 return left | right; 00053 } 00054 }; 00055 00056 template<class Ty> 00057 struct less_ptr : public std::binary_function<Ty, Ty, bool> { 00058 bool operator()(const Ty* left, const Ty* right) const { 00059 return *left < *right; 00060 } 00061 }; 00062 00063 template<class Ty> 00064 struct greater_ptr : public std::binary_function<Ty, Ty, bool> { 00065 bool operator()(const Ty* left, const Ty* right) const { 00066 return *right < *left; 00067 } 00068 }; 00069 00070 // deleter - Very very very simple method that is used to invoke operator 00071 // delete on something. It is used like this: 00072 // 00073 // for_each(V.begin(), B.end(), deleter<Interval>); 00074 // 00075 template <class T> 00076 static inline void deleter(T *Ptr) { 00077 delete Ptr; 00078 } 00079 00080 00081 00082 //===----------------------------------------------------------------------===// 00083 // Extra additions to <iterator> 00084 //===----------------------------------------------------------------------===// 00085 00086 // mapped_iterator - This is a simple iterator adapter that causes a function to 00087 // be dereferenced whenever operator* is invoked on the iterator. 00088 // 00089 template <class RootIt, class UnaryFunc> 00090 class mapped_iterator { 00091 RootIt current; 00092 UnaryFunc Fn; 00093 public: 00094 typedef typename std::iterator_traits<RootIt>::iterator_category 00095 iterator_category; 00096 typedef typename std::iterator_traits<RootIt>::difference_type 00097 difference_type; 00098 typedef typename UnaryFunc::result_type value_type; 00099 00100 typedef void pointer; 00101 //typedef typename UnaryFunc::result_type *pointer; 00102 typedef void reference; // Can't modify value returned by fn 00103 00104 typedef RootIt iterator_type; 00105 typedef mapped_iterator<RootIt, UnaryFunc> _Self; 00106 00107 inline RootIt &getCurrent() const { return current; } 00108 00109 inline explicit mapped_iterator(const RootIt &I, UnaryFunc F) 00110 : current(I), Fn(F) {} 00111 inline mapped_iterator(const mapped_iterator &It) 00112 : current(It.current), Fn(It.Fn) {} 00113 00114 inline value_type operator*() const { // All this work to do this 00115 return Fn(*current); // little change 00116 } 00117 00118 _Self& operator++() { ++current; return *this; } 00119 _Self& operator--() { --current; return *this; } 00120 _Self operator++(int) { _Self __tmp = *this; ++current; return __tmp; } 00121 _Self operator--(int) { _Self __tmp = *this; --current; return __tmp; } 00122 _Self operator+ (difference_type n) const { return _Self(current + n); } 00123 _Self& operator+= (difference_type n) { current += n; return *this; } 00124 _Self operator- (difference_type n) const { return _Self(current - n); } 00125 _Self& operator-= (difference_type n) { current -= n; return *this; } 00126 reference operator[](difference_type n) const { return *(*this + n); } 00127 00128 inline bool operator!=(const _Self &X) const { return !operator==(X); } 00129 inline bool operator==(const _Self &X) const { return current == X.current; } 00130 inline bool operator< (const _Self &X) const { return current < X.current; } 00131 00132 inline difference_type operator-(const _Self &X) const { 00133 return current - X.current; 00134 } 00135 }; 00136 00137 template <class _Iterator, class Func> 00138 inline mapped_iterator<_Iterator, Func> 00139 operator+(typename mapped_iterator<_Iterator, Func>::difference_type N, 00140 const mapped_iterator<_Iterator, Func>& X) { 00141 return mapped_iterator<_Iterator, Func>(X.getCurrent() - N); 00142 } 00143 00144 00145 // map_iterator - Provide a convenient way to create mapped_iterators, just like 00146 // make_pair is useful for creating pairs... 00147 // 00148 template <class ItTy, class FuncTy> 00149 inline mapped_iterator<ItTy, FuncTy> map_iterator(const ItTy &I, FuncTy F) { 00150 return mapped_iterator<ItTy, FuncTy>(I, F); 00151 } 00152 00153 00154 // next/prior - These functions unlike std::advance do not modify the 00155 // passed iterator but return a copy. 00156 // 00157 // next(myIt) returns copy of myIt incremented once 00158 // next(myIt, n) returns copy of myIt incremented n times 00159 // prior(myIt) returns copy of myIt decremented once 00160 // prior(myIt, n) returns copy of myIt decremented n times 00161 00162 template <typename ItTy, typename Dist> 00163 inline ItTy next(ItTy it, Dist n) 00164 { 00165 std::advance(it, n); 00166 return it; 00167 } 00168 00169 template <typename ItTy> 00170 inline ItTy next(ItTy it) 00171 { 00172 std::advance(it, 1); 00173 return it; 00174 } 00175 00176 template <typename ItTy, typename Dist> 00177 inline ItTy prior(ItTy it, Dist n) 00178 { 00179 std::advance(it, -n); 00180 return it; 00181 } 00182 00183 template <typename ItTy> 00184 inline ItTy prior(ItTy it) 00185 { 00186 std::advance(it, -1); 00187 return it; 00188 } 00189 00190 00191 //===----------------------------------------------------------------------===// 00192 // Extra additions to <algorithm> 00193 //===----------------------------------------------------------------------===// 00194 00195 // apply_until - Apply a functor to a sequence continually, unless the 00196 // functor returns true. Return true if the functor returned true, return false 00197 // if the functor never returned true. 00198 // 00199 template <class InputIt, class Function> 00200 bool apply_until(InputIt First, InputIt Last, Function Func) { 00201 for ( ; First != Last; ++First) 00202 if (Func(*First)) return true; 00203 return false; 00204 } 00205 00206 00207 // reduce - Reduce a sequence values into a single value, given an initial 00208 // value and an operator. 00209 // 00210 template <class InputIt, class Function, class ValueType> 00211 ValueType reduce(InputIt First, InputIt Last, Function Func, ValueType Value) { 00212 for ( ; First != Last; ++First) 00213 Value = Func(*First, Value); 00214 return Value; 00215 } 00216 00217 #if 1 // This is likely to be more efficient 00218 00219 // reduce_apply - Reduce the result of applying a function to each value in a 00220 // sequence, given an initial value, an operator, a function, and a sequence. 00221 // 00222 template <class InputIt, class Function, class ValueType, class TransFunc> 00223 inline ValueType reduce_apply(InputIt First, InputIt Last, Function Func, 00224 ValueType Value, TransFunc XForm) { 00225 for ( ; First != Last; ++First) 00226 Value = Func(XForm(*First), Value); 00227 return Value; 00228 } 00229 00230 #else // This is arguably more elegant 00231 00232 // reduce_apply - Reduce the result of applying a function to each value in a 00233 // sequence, given an initial value, an operator, a function, and a sequence. 00234 // 00235 template <class InputIt, class Function, class ValueType, class TransFunc> 00236 inline ValueType reduce_apply2(InputIt First, InputIt Last, Function Func, 00237 ValueType Value, TransFunc XForm) { 00238 return reduce(map_iterator(First, XForm), map_iterator(Last, XForm), 00239 Func, Value); 00240 } 00241 #endif 00242 00243 00244 // reduce_apply_bool - Reduce the result of applying a (bool returning) function 00245 // to each value in a sequence. All of the bools returned by the mapped 00246 // function are bitwise or'd together, and the result is returned. 00247 // 00248 template <class InputIt, class Function> 00249 inline bool reduce_apply_bool(InputIt First, InputIt Last, Function Func) { 00250 return reduce_apply(First, Last, bitwise_or<bool>(), false, Func); 00251 } 00252 00253 00254 // map - This function maps the specified input sequence into the specified 00255 // output iterator, applying a unary function in between. 00256 // 00257 template <class InIt, class OutIt, class Functor> 00258 inline OutIt mapto(InIt Begin, InIt End, OutIt Dest, Functor F) { 00259 return copy(map_iterator(Begin, F), map_iterator(End, F), Dest); 00260 } 00261 00262 00263 //===----------------------------------------------------------------------===// 00264 // Extra additions to <utility> 00265 //===----------------------------------------------------------------------===// 00266 00267 // tie - this function ties two objects and returns a temporary object 00268 // that is assignable from a std::pair. This can be used to make code 00269 // more readable when using values returned from functions bundled in 00270 // a std::pair. Since an example is worth 1000 words: 00271 // 00272 // typedef std::map<int, int> Int2IntMap; 00273 // 00274 // Int2IntMap myMap; 00275 // Int2IntMap::iterator where; 00276 // bool inserted; 00277 // tie(where, inserted) = myMap.insert(std::make_pair(123,456)); 00278 // 00279 // if (inserted) 00280 // // do stuff 00281 // else 00282 // // do other stuff 00283 00284 namespace 00285 { 00286 template <typename T1, typename T2> 00287 struct tier { 00288 typedef T1 &first_type; 00289 typedef T2 &second_type; 00290 00291 first_type first; 00292 second_type second; 00293 00294 tier(first_type f, second_type s) : first(f), second(s) { } 00295 tier& operator=(const std::pair<T1, T2>& p) { 00296 first = p.first; 00297 second = p.second; 00298 return *this; 00299 } 00300 }; 00301 } 00302 00303 template <typename T1, typename T2> 00304 inline tier<T1, T2> tie(T1& f, T2& s) { 00305 return tier<T1, T2>(f, s); 00306 } 00307 00308 } // End llvm namespace 00309 00310 #endif