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