include/llvm/ADT/STLExtras.h

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