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
base()19 It base() const {return it_;}
20
output_iterator()21 output_iterator () {}
output_iterator(It it)22 explicit output_iterator(It it) : it_(it) {}
23 template <class U>
output_iterator(const output_iterator<U> & 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
base()46 It base() const {return it_;}
47
input_iterator()48 input_iterator() : it_() {}
input_iterator(It it)49 explicit input_iterator(It it) : it_(it) {}
50 template <class U>
input_iterator(const input_iterator<U> & 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
base()95 It base() const {return it_;}
96
forward_iterator()97 forward_iterator() : it_() {}
forward_iterator(It it)98 explicit forward_iterator(It it) : it_(it) {}
99 template <class U>
forward_iterator(const forward_iterator<U> & 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
base()144 It base() const {return it_;}
145
bidirectional_iterator()146 bidirectional_iterator() : it_() {}
bidirectional_iterator(It it)147 explicit bidirectional_iterator(It it) : it_(it) {}
148 template <class U>
bidirectional_iterator(const bidirectional_iterator<U> & 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
base()192 It base() const {return it_;}
193
random_access_iterator()194 random_access_iterator() : it_() {}
random_access_iterator(It it)195 explicit random_access_iterator(It it) : it_(it) {}
196 template <class U>
random_access_iterator(const random_access_iterator<U> & 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>
base(output_iterator<Iter> i)279 inline Iter base(output_iterator<Iter> i) { return i.base(); }
280
281 template <class Iter>
base(input_iterator<Iter> i)282 inline Iter base(input_iterator<Iter> i) { return i.base(); }
283
284 template <class Iter>
base(forward_iterator<Iter> i)285 inline Iter base(forward_iterator<Iter> i) { return i.base(); }
286
287 template <class Iter>
base(bidirectional_iterator<Iter> i)288 inline Iter base(bidirectional_iterator<Iter> i) { return i.base(); }
289
290 template <class Iter>
base(random_access_iterator<Iter> i)291 inline Iter base(random_access_iterator<Iter> i) { return i.base(); }
292
293 template <class Iter> // everything else
base(Iter i)294 inline Iter base(Iter i) { return i; }
295
296 #endif // ITERATORS_H
297