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