1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
|
//===- iterator.h - Utilities for using and defining iterators --*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ADT_ITERATOR_H
#define LLVM_ADT_ITERATOR_H
#include <iterator>
namespace llvm {
/// \brief CRTP base class which implements the entire standard iterator facade
/// in terms of a minimal subset of the interface.
///
/// Use this when it is reasonable to implement most of the iterator
/// functionality in terms of a core subset. If you need special behavior or
/// there are performance implications for this, you may want to override the
/// relevant members instead.
///
/// Note, one abstraction that this does *not* provide is implementing
/// subtraction in terms of addition by negating the difference. Negation isn't
/// always information preserving, and I can see very reasonable iterator
/// designs where this doesn't work well. It doesn't really force much added
/// boilerplate anyways.
///
/// Another abstraction that this doesn't provide is implementing increment in
/// terms of addition of one. These aren't equivalent for all iterator
/// categories, and respecting that adds a lot of complexity for little gain.
template <typename DerivedT, typename IteratorCategoryT, typename T,
typename DifferenceTypeT, typename PointerT = T *,
typename ReferenceT = T &>
struct iterator_facade_base
: std::iterator<IteratorCategoryT, T, DifferenceTypeT, PointerT,
ReferenceT> {
DerivedT operator+(DifferenceTypeT n) const {
DerivedT tmp = *static_cast<const DerivedT *>(this);
tmp += n;
return tmp;
}
friend DerivedT operator+(DifferenceTypeT n, const DerivedT &i) {
return i + n;
}
DerivedT operator-(DifferenceTypeT n) const {
DerivedT tmp = *static_cast<const DerivedT *>(this);
tmp -= n;
return tmp;
}
DerivedT &operator++() {
return static_cast<DerivedT *>(this)->operator+=(1);
}
DerivedT operator++(int) {
DerivedT tmp = *static_cast<DerivedT *>(this);
++*static_cast<DerivedT *>(this);
return tmp;
}
DerivedT &operator--() {
return static_cast<DerivedT *>(this)->operator-=(1);
}
DerivedT operator--(int) {
DerivedT tmp = *static_cast<DerivedT *>(this);
--*static_cast<DerivedT *>(this);
return tmp;
}
bool operator!=(const DerivedT &RHS) const {
return !static_cast<const DerivedT *>(this)->operator==(RHS);
}
bool operator>(const DerivedT &RHS) const {
return !static_cast<const DerivedT *>(this)->operator<(RHS) &&
!static_cast<const DerivedT *>(this)->operator==(RHS);
}
bool operator<=(const DerivedT &RHS) const {
return !static_cast<const DerivedT *>(this)->operator>(RHS);
}
bool operator>=(const DerivedT &RHS) const {
return !static_cast<const DerivedT *>(this)->operator<(RHS);
}
PointerT operator->() const {
return &static_cast<const DerivedT *>(this)->operator*();
}
ReferenceT operator[](DifferenceTypeT n) const {
return *static_cast<const DerivedT *>(this)->operator+(n);
}
};
/// \brief CRTP base class for adapting an iterator to a different type.
///
/// This class can be used through CRTP to adapt one iterator into another.
/// Typically this is done through providing in the derived class a custom \c
/// operator* implementation. Other methods can be overridden as well.
template <typename DerivedT, typename WrappedIteratorT, typename T,
typename PointerT = T *, typename ReferenceT = T &,
// Don't provide these, they are mostly to act as aliases below.
typename WrappedTraitsT = std::iterator_traits<WrappedIteratorT>>
class iterator_adaptor_base
: public iterator_facade_base<
DerivedT, typename WrappedTraitsT::iterator_category, T,
typename WrappedTraitsT::difference_type, PointerT, ReferenceT> {
typedef typename iterator_adaptor_base::iterator_facade_base BaseT;
protected:
WrappedIteratorT I;
iterator_adaptor_base() {}
template <typename U>
explicit iterator_adaptor_base(
U &&u,
typename std::enable_if<
!std::is_base_of<typename std::remove_cv<
typename std::remove_reference<U>::type>::type,
DerivedT>::value,
int>::type = 0)
: I(std::forward<U &&>(u)) {}
public:
typedef typename WrappedTraitsT::difference_type difference_type;
DerivedT &operator+=(difference_type n) {
I += n;
return *static_cast<DerivedT *>(this);
}
DerivedT &operator-=(difference_type n) {
I -= n;
return *static_cast<DerivedT *>(this);
}
using BaseT::operator-;
difference_type operator-(const DerivedT &RHS) const { return I - RHS.I; }
// We have to explicitly provide ++ and -- rather than letting the facade
// forward to += because WrappedIteratorT might not support +=.
using BaseT::operator++;
DerivedT &operator++() {
++I;
return *static_cast<DerivedT *>(this);
}
using BaseT::operator--;
DerivedT &operator--() {
--I;
return *static_cast<DerivedT *>(this);
}
bool operator==(const DerivedT &RHS) const { return I == RHS.I; }
bool operator<(const DerivedT &RHS) const { return I < RHS.I; }
ReferenceT operator*() const { return *I; }
};
/// \brief An iterator type that allows iterating over the pointees via some
/// other iterator.
///
/// The typical usage of this is to expose a type that iterates over Ts, but
/// which is implemented with some iterator over T*s:
///
/// \code
/// typedef pointee_iterator<SmallVectorImpl<T *>::iterator> iterator;
/// \endcode
template <
typename WrappedIteratorT,
typename T = typename std::remove_pointer<
typename std::iterator_traits<WrappedIteratorT>::value_type>::type>
struct pointee_iterator
: iterator_adaptor_base<pointee_iterator<WrappedIteratorT>,
WrappedIteratorT, T> {
pointee_iterator() {}
template <typename U>
pointee_iterator(U &&u)
: pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {}
T &operator*() const { return **this->I; }
};
}
#endif
|
