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
15 template <class It>
16 class output_iterator
17 {
18 It it_;
19
20 template <class U> friend class output_iterator;
21 public:
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
base()28 It base() const {return it_;}
29
output_iterator()30 output_iterator () {}
output_iterator(It it)31 explicit output_iterator(It it) : it_(it) {}
32 template <class U>
output_iterator(const output_iterator<U> & 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
42 template <class It>
43 class input_iterator
44 {
45 It it_;
46
47 template <class U> friend class input_iterator;
48 public:
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
base()55 It base() const {return it_;}
56
input_iterator()57 input_iterator() : it_() {}
input_iterator(It it)58 explicit input_iterator(It it) : it_(it) {}
59 template <class U>
input_iterator(const input_iterator<U> & 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
75 template <class T, class U>
76 inline
77 bool
78 operator==(const input_iterator<T>& x, const input_iterator<U>& y)
79 {
80 return x.base() == y.base();
81 }
82
83 template <class T, class U>
84 inline
85 bool
86 operator!=(const input_iterator<T>& x, const input_iterator<U>& y)
87 {
88 return !(x == y);
89 }
90
91 template <class It>
92 class forward_iterator
93 {
94 It it_;
95
96 template <class U> friend class forward_iterator;
97 public:
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
base()104 It base() const {return it_;}
105
forward_iterator()106 forward_iterator() : it_() {}
forward_iterator(It it)107 explicit forward_iterator(It it) : it_(it) {}
108 template <class U>
forward_iterator(const forward_iterator<U> & 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
124 template <class T, class U>
125 inline
126 bool
127 operator==(const forward_iterator<T>& x, const forward_iterator<U>& y)
128 {
129 return x.base() == y.base();
130 }
131
132 template <class T, class U>
133 inline
134 bool
135 operator!=(const forward_iterator<T>& x, const forward_iterator<U>& y)
136 {
137 return !(x == y);
138 }
139
140 template <class It>
141 class bidirectional_iterator
142 {
143 It it_;
144
145 template <class U> friend class bidirectional_iterator;
146 public:
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
base()153 It base() const {return it_;}
154
bidirectional_iterator()155 bidirectional_iterator() : it_() {}
bidirectional_iterator(It it)156 explicit bidirectional_iterator(It it) : it_(it) {}
157 template <class U>
bidirectional_iterator(const bidirectional_iterator<U> & 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
172 template <class T, class U>
173 inline
174 bool
175 operator==(const bidirectional_iterator<T>& x, const bidirectional_iterator<U>& y)
176 {
177 return x.base() == y.base();
178 }
179
180 template <class T, class U>
181 inline
182 bool
183 operator!=(const bidirectional_iterator<T>& x, const bidirectional_iterator<U>& y)
184 {
185 return !(x == y);
186 }
187
188 template <class It>
189 class random_access_iterator
190 {
191 It it_;
192
193 template <class U> friend class random_access_iterator;
194 public:
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
base()201 It base() const {return it_;}
202
random_access_iterator()203 random_access_iterator() : it_() {}
random_access_iterator(It it)204 explicit random_access_iterator(It it) : it_(it) {}
205 template <class U>
random_access_iterator(const random_access_iterator<U> & 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
231 template <class T, class U>
232 inline
233 bool
234 operator==(const random_access_iterator<T>& x, const random_access_iterator<U>& y)
235 {
236 return x.base() == y.base();
237 }
238
239 template <class T, class U>
240 inline
241 bool
242 operator!=(const random_access_iterator<T>& x, const random_access_iterator<U>& y)
243 {
244 return !(x == y);
245 }
246
247 template <class T, class U>
248 inline
249 bool
250 operator<(const random_access_iterator<T>& x, const random_access_iterator<U>& y)
251 {
252 return x.base() < y.base();
253 }
254
255 template <class T, class U>
256 inline
257 bool
258 operator<=(const random_access_iterator<T>& x, const random_access_iterator<U>& y)
259 {
260 return !(y < x);
261 }
262
263 template <class T, class U>
264 inline
265 bool
266 operator>(const random_access_iterator<T>& x, const random_access_iterator<U>& y)
267 {
268 return y < x;
269 }
270
271 template <class T, class U>
272 inline
273 bool
274 operator>=(const random_access_iterator<T>& x, const random_access_iterator<U>& y)
275 {
276 return !(x < y);
277 }
278
279 template <class T, class U>
280 inline
281 typename std::iterator_traits<T>::difference_type
282 operator-(const random_access_iterator<T>& x, const random_access_iterator<U>& y)
283 {
284 return x.base() - y.base();
285 }
286
287 template <class Iter>
base(output_iterator<Iter> i)288 inline Iter base(output_iterator<Iter> i) { return i.base(); }
289
290 template <class Iter>
base(input_iterator<Iter> i)291 inline Iter base(input_iterator<Iter> i) { return i.base(); }
292
293 template <class Iter>
base(forward_iterator<Iter> i)294 inline Iter base(forward_iterator<Iter> i) { return i.base(); }
295
296 template <class Iter>
base(bidirectional_iterator<Iter> i)297 inline Iter base(bidirectional_iterator<Iter> i) { return i.base(); }
298
299 template <class Iter>
base(random_access_iterator<Iter> i)300 inline Iter base(random_access_iterator<Iter> i) { return i.base(); }
301
302 template <class Iter> // everything else
base(Iter i)303 inline Iter base(Iter i) { return i; }
304
305 #endif // ITERATORS_H
306