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