1//===----------------------------------------------------------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is dual licensed under the MIT and the University of Illinois Open 6// Source Licenses. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9 10#ifndef ITERATORS_H 11#define ITERATORS_H 12 13#include <iterator> 14 15template <class It> 16class output_iterator 17{ 18 It it_; 19 20 template <class U> friend class output_iterator; 21public: 22 typedef std::output_iterator_tag iterator_category; 23 typedef void value_type; 24 typedef typename std::iterator_traits<It>::difference_type difference_type; 25 typedef It pointer; 26 typedef typename std::iterator_traits<It>::reference reference; 27 28 It base() const {return it_;} 29 30 output_iterator () {} 31 explicit output_iterator(It it) : it_(it) {} 32 template <class U> 33 output_iterator(const output_iterator<U>& u) :it_(u.it_) {} 34 35 reference operator*() const {return *it_;} 36 37 output_iterator& operator++() {++it_; return *this;} 38 output_iterator operator++(int) 39 {output_iterator tmp(*this); ++(*this); return tmp;} 40}; 41 42template <class It> 43class input_iterator 44{ 45 It it_; 46 47 template <class U> friend class input_iterator; 48public: 49 typedef std::input_iterator_tag iterator_category; 50 typedef typename std::iterator_traits<It>::value_type value_type; 51 typedef typename std::iterator_traits<It>::difference_type difference_type; 52 typedef It pointer; 53 typedef typename std::iterator_traits<It>::reference reference; 54 55 It base() const {return it_;} 56 57 input_iterator() : it_() {} 58 explicit input_iterator(It it) : it_(it) {} 59 template <class U> 60 input_iterator(const input_iterator<U>& u) :it_(u.it_) {} 61 62 reference operator*() const {return *it_;} 63 pointer operator->() const {return it_;} 64 65 input_iterator& operator++() {++it_; return *this;} 66 input_iterator operator++(int) 67 {input_iterator tmp(*this); ++(*this); return tmp;} 68 69 friend bool operator==(const input_iterator& x, const input_iterator& y) 70 {return x.it_ == y.it_;} 71 friend bool operator!=(const input_iterator& x, const input_iterator& y) 72 {return !(x == y);} 73}; 74 75template <class T, class U> 76inline 77bool 78operator==(const input_iterator<T>& x, const input_iterator<U>& y) 79{ 80 return x.base() == y.base(); 81} 82 83template <class T, class U> 84inline 85bool 86operator!=(const input_iterator<T>& x, const input_iterator<U>& y) 87{ 88 return !(x == y); 89} 90 91template <class It> 92class forward_iterator 93{ 94 It it_; 95 96 template <class U> friend class forward_iterator; 97public: 98 typedef std::forward_iterator_tag iterator_category; 99 typedef typename std::iterator_traits<It>::value_type value_type; 100 typedef typename std::iterator_traits<It>::difference_type difference_type; 101 typedef It pointer; 102 typedef typename std::iterator_traits<It>::reference reference; 103 104 It base() const {return it_;} 105 106 forward_iterator() : it_() {} 107 explicit forward_iterator(It it) : it_(it) {} 108 template <class U> 109 forward_iterator(const forward_iterator<U>& u) :it_(u.it_) {} 110 111 reference operator*() const {return *it_;} 112 pointer operator->() const {return it_;} 113 114 forward_iterator& operator++() {++it_; return *this;} 115 forward_iterator operator++(int) 116 {forward_iterator tmp(*this); ++(*this); return tmp;} 117 118 friend bool operator==(const forward_iterator& x, const forward_iterator& y) 119 {return x.it_ == y.it_;} 120 friend bool operator!=(const forward_iterator& x, const forward_iterator& y) 121 {return !(x == y);} 122}; 123 124template <class T, class U> 125inline 126bool 127operator==(const forward_iterator<T>& x, const forward_iterator<U>& y) 128{ 129 return x.base() == y.base(); 130} 131 132template <class T, class U> 133inline 134bool 135operator!=(const forward_iterator<T>& x, const forward_iterator<U>& y) 136{ 137 return !(x == y); 138} 139 140template <class It> 141class bidirectional_iterator 142{ 143 It it_; 144 145 template <class U> friend class bidirectional_iterator; 146public: 147 typedef std::bidirectional_iterator_tag iterator_category; 148 typedef typename std::iterator_traits<It>::value_type value_type; 149 typedef typename std::iterator_traits<It>::difference_type difference_type; 150 typedef It pointer; 151 typedef typename std::iterator_traits<It>::reference reference; 152 153 It base() const {return it_;} 154 155 bidirectional_iterator() : it_() {} 156 explicit bidirectional_iterator(It it) : it_(it) {} 157 template <class U> 158 bidirectional_iterator(const bidirectional_iterator<U>& u) :it_(u.it_) {} 159 160 reference operator*() const {return *it_;} 161 pointer operator->() const {return it_;} 162 163 bidirectional_iterator& operator++() {++it_; return *this;} 164 bidirectional_iterator operator++(int) 165 {bidirectional_iterator tmp(*this); ++(*this); return tmp;} 166 167 bidirectional_iterator& operator--() {--it_; return *this;} 168 bidirectional_iterator operator--(int) 169 {bidirectional_iterator tmp(*this); --(*this); return tmp;} 170}; 171 172template <class T, class U> 173inline 174bool 175operator==(const bidirectional_iterator<T>& x, const bidirectional_iterator<U>& y) 176{ 177 return x.base() == y.base(); 178} 179 180template <class T, class U> 181inline 182bool 183operator!=(const bidirectional_iterator<T>& x, const bidirectional_iterator<U>& y) 184{ 185 return !(x == y); 186} 187 188template <class It> 189class random_access_iterator 190{ 191 It it_; 192 193 template <class U> friend class random_access_iterator; 194public: 195 typedef std::random_access_iterator_tag iterator_category; 196 typedef typename std::iterator_traits<It>::value_type value_type; 197 typedef typename std::iterator_traits<It>::difference_type difference_type; 198 typedef It pointer; 199 typedef typename std::iterator_traits<It>::reference reference; 200 201 It base() const {return it_;} 202 203 random_access_iterator() : it_() {} 204 explicit random_access_iterator(It it) : it_(it) {} 205 template <class U> 206 random_access_iterator(const random_access_iterator<U>& u) :it_(u.it_) {} 207 208 reference operator*() const {return *it_;} 209 pointer operator->() const {return it_;} 210 211 random_access_iterator& operator++() {++it_; return *this;} 212 random_access_iterator operator++(int) 213 {random_access_iterator tmp(*this); ++(*this); return tmp;} 214 215 random_access_iterator& operator--() {--it_; return *this;} 216 random_access_iterator operator--(int) 217 {random_access_iterator tmp(*this); --(*this); return tmp;} 218 219 random_access_iterator& operator+=(difference_type n) {it_ += n; return *this;} 220 random_access_iterator operator+(difference_type n) const 221 {random_access_iterator tmp(*this); tmp += n; return tmp;} 222 friend random_access_iterator operator+(difference_type n, random_access_iterator x) 223 {x += n; return x;} 224 random_access_iterator& operator-=(difference_type n) {return *this += -n;} 225 random_access_iterator operator-(difference_type n) const 226 {random_access_iterator tmp(*this); tmp -= n; return tmp;} 227 228 reference operator[](difference_type n) const {return it_[n];} 229}; 230 231template <class T, class U> 232inline 233bool 234operator==(const random_access_iterator<T>& x, const random_access_iterator<U>& y) 235{ 236 return x.base() == y.base(); 237} 238 239template <class T, class U> 240inline 241bool 242operator!=(const random_access_iterator<T>& x, const random_access_iterator<U>& y) 243{ 244 return !(x == y); 245} 246 247template <class T, class U> 248inline 249bool 250operator<(const random_access_iterator<T>& x, const random_access_iterator<U>& y) 251{ 252 return x.base() < y.base(); 253} 254 255template <class T, class U> 256inline 257bool 258operator<=(const random_access_iterator<T>& x, const random_access_iterator<U>& y) 259{ 260 return !(y < x); 261} 262 263template <class T, class U> 264inline 265bool 266operator>(const random_access_iterator<T>& x, const random_access_iterator<U>& y) 267{ 268 return y < x; 269} 270 271template <class T, class U> 272inline 273bool 274operator>=(const random_access_iterator<T>& x, const random_access_iterator<U>& y) 275{ 276 return !(x < y); 277} 278 279template <class T, class U> 280inline 281typename std::iterator_traits<T>::difference_type 282operator-(const random_access_iterator<T>& x, const random_access_iterator<U>& y) 283{ 284 return x.base() - y.base(); 285} 286 287template <class Iter> 288inline Iter base(output_iterator<Iter> i) { return i.base(); } 289 290template <class Iter> 291inline Iter base(input_iterator<Iter> i) { return i.base(); } 292 293template <class Iter> 294inline Iter base(forward_iterator<Iter> i) { return i.base(); } 295 296template <class Iter> 297inline Iter base(bidirectional_iterator<Iter> i) { return i.base(); } 298 299template <class Iter> 300inline Iter base(random_access_iterator<Iter> i) { return i.base(); } 301 302template <class Iter> // everything else 303inline Iter base(Iter i) { return i; } 304 305#endif // ITERATORS_H 306