1 | // -*- C++ -*- |
---|
2 | /*************************************************************************** |
---|
3 | * blitz/array/iter.h Basic iterator for arrays. |
---|
4 | * |
---|
5 | * $Id$ |
---|
6 | * |
---|
7 | * Copyright (C) 1997-2011 Todd Veldhuizen <tveldhui@acm.org> |
---|
8 | * |
---|
9 | * This file is a part of Blitz. |
---|
10 | * |
---|
11 | * Blitz is free software: you can redistribute it and/or modify |
---|
12 | * it under the terms of the GNU Lesser General Public License |
---|
13 | * as published by the Free Software Foundation, either version 3 |
---|
14 | * of the License, or (at your option) any later version. |
---|
15 | * |
---|
16 | * Blitz is distributed in the hope that it will be useful, |
---|
17 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
---|
18 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
---|
19 | * GNU Lesser General Public License for more details. |
---|
20 | * |
---|
21 | * You should have received a copy of the GNU Lesser General Public |
---|
22 | * License along with Blitz. If not, see <http://www.gnu.org/licenses/>. |
---|
23 | * |
---|
24 | * Suggestions: blitz-devel@lists.sourceforge.net |
---|
25 | * Bugs: blitz-support@lists.sourceforge.net |
---|
26 | * |
---|
27 | * For more information, please see the Blitz++ Home Page: |
---|
28 | * https://sourceforge.net/projects/blitz/ |
---|
29 | * |
---|
30 | ****************************************************************************/ |
---|
31 | #ifndef BZ_ARRAY_H |
---|
32 | #error <blitz/array/iter.h> must be included via <blitz/array.h> |
---|
33 | #endif |
---|
34 | |
---|
35 | #ifndef BZ_ARRAY_ITER_H |
---|
36 | #define BZ_ARRAY_ITER_H |
---|
37 | |
---|
38 | #ifdef BZ_HAVE_STL |
---|
39 | #include <iterator> |
---|
40 | #endif |
---|
41 | |
---|
42 | #if defined(BZ_DEBUG) |
---|
43 | #define CheckIteratorValidity(X,Y) \ |
---|
44 | BZPRECHECK(data_!=0, X " invalid iterator (empty array)"); \ |
---|
45 | BZPRECHECK((data_>=beg_+Y && data_<=end_+Y), ((data_<beg_+Y) ? \ |
---|
46 | X " invalid iterator (before beginning of array)" : \ |
---|
47 | X " invalid iterator (past end of array)")); |
---|
48 | #else |
---|
49 | #define CheckIteratorValidity(X,Y) |
---|
50 | #endif |
---|
51 | |
---|
52 | BZ_NAMESPACE(blitz) |
---|
53 | |
---|
54 | template<typename T, int N> |
---|
55 | class ConstArrayIterator { |
---|
56 | private: |
---|
57 | // Initialization common to begin,end constructors. |
---|
58 | // |
---|
59 | void Init(const Array<T,N>& array) { |
---|
60 | // Making internal copies of these avoids keeping |
---|
61 | // a pointer to the array and doing indirection. |
---|
62 | lbound_ = array.lbound(); |
---|
63 | order_ = array.ordering(); |
---|
64 | |
---|
65 | ubound_(0) = array.ubound(0)+1; |
---|
66 | dataincr_(order_(0)) = array.stride(order_(0)); |
---|
67 | for (int i=1,r,s=order_(0);i<N;s=r,++i) { |
---|
68 | r = order_(i); |
---|
69 | ubound_(i) = array.ubound(i)+1; |
---|
70 | dataincr_(r) = array.stride(r)-array.extent(s)*array.stride(s); |
---|
71 | } |
---|
72 | #if defined(BZ_DEBUG) |
---|
73 | beg_ = array.data(); |
---|
74 | end_ = end_value(array)-1; |
---|
75 | if (beg_>end_) |
---|
76 | std::swap(beg_,end_); |
---|
77 | #endif |
---|
78 | } |
---|
79 | |
---|
80 | public: |
---|
81 | ConstArrayIterator() : data_(0) { } |
---|
82 | |
---|
83 | ConstArrayIterator(const Array<T,N>& array) : |
---|
84 | data_(const_cast<T*>(array.data())) { |
---|
85 | Init(array); |
---|
86 | pos_ = lbound_; |
---|
87 | } |
---|
88 | |
---|
89 | ConstArrayIterator(const Array<T,N>& array, const int) : |
---|
90 | data_(end_value(array)) { |
---|
91 | Init(array); |
---|
92 | pos_ = array.ubound(); |
---|
93 | ++pos_(order_(0)); |
---|
94 | } |
---|
95 | |
---|
96 | bool operator==(const ConstArrayIterator<T,N>& x) const |
---|
97 | { return data_ == x.data_; } |
---|
98 | |
---|
99 | bool operator!=(const ConstArrayIterator<T,N>& x) const |
---|
100 | { return data_ != x.data_; } |
---|
101 | |
---|
102 | const T& operator*() const { |
---|
103 | CheckIteratorValidity("Attempted to dereference",0); |
---|
104 | return *data_; |
---|
105 | } |
---|
106 | |
---|
107 | const T* restrict operator->() const { |
---|
108 | CheckIteratorValidity("Attempted to dereference",0); |
---|
109 | return data_; |
---|
110 | } |
---|
111 | |
---|
112 | ConstArrayIterator<T,N>& operator++(); |
---|
113 | ConstArrayIterator<T,N>& operator--(); |
---|
114 | |
---|
115 | ConstArrayIterator<T,N> operator++(int) { |
---|
116 | ConstArrayIterator<T,N> tmp = *this; |
---|
117 | ++(*this); |
---|
118 | return tmp; |
---|
119 | } |
---|
120 | |
---|
121 | ConstArrayIterator<T,N> operator--(int) { |
---|
122 | ConstArrayIterator<T,N> tmp = *this; |
---|
123 | --(*this); |
---|
124 | return tmp; |
---|
125 | } |
---|
126 | |
---|
127 | // get the current position of the Array iterator in index space |
---|
128 | const TinyVector<int,N>& position() const { |
---|
129 | CheckIteratorValidity("Array<T,N>::iterator::position() called on",0); |
---|
130 | return pos_; |
---|
131 | } |
---|
132 | |
---|
133 | private: |
---|
134 | TinyVector<int,N> dataincr_, lbound_, ubound_, order_; |
---|
135 | |
---|
136 | static T* end_value(const Array<T,N>& array) { |
---|
137 | T* endval = const_cast<T*>(array.data()) + |
---|
138 | array.stride(array.ordering(0)); |
---|
139 | for (int i=0;i<N;++i) |
---|
140 | endval += array.stride(i)*(array.extent(i)-1); |
---|
141 | return endval; |
---|
142 | } |
---|
143 | |
---|
144 | protected: |
---|
145 | TinyVector<int,N> pos_; |
---|
146 | T * restrict data_; |
---|
147 | #if defined(BZ_DEBUG) |
---|
148 | const T* restrict beg_; |
---|
149 | const T* restrict end_; |
---|
150 | #endif |
---|
151 | }; |
---|
152 | |
---|
153 | |
---|
154 | template<typename T, int N> |
---|
155 | class ArrayIterator : public ConstArrayIterator<T,N> { |
---|
156 | private: |
---|
157 | typedef ConstArrayIterator<T,N> T_base; |
---|
158 | using T_base::data_; |
---|
159 | |
---|
160 | #if defined(BZ_DEBUG) |
---|
161 | using T_base::beg_; |
---|
162 | using T_base::end_; |
---|
163 | #endif |
---|
164 | |
---|
165 | public: |
---|
166 | ArrayIterator() { } |
---|
167 | |
---|
168 | ArrayIterator(Array<T,N>& x) : T_base(x) { } |
---|
169 | |
---|
170 | ArrayIterator(const Array<T,N>& array, const int): T_base(array,0) { } |
---|
171 | |
---|
172 | T& operator*() const { |
---|
173 | CheckIteratorValidity("Attempted to dereference",0); |
---|
174 | return *data_; |
---|
175 | } |
---|
176 | |
---|
177 | T* restrict operator->() const { |
---|
178 | CheckIteratorValidity("Attempted to dereference",0); |
---|
179 | return data_; |
---|
180 | } |
---|
181 | |
---|
182 | ArrayIterator<T,N>& operator++() { |
---|
183 | T_base::operator++(); |
---|
184 | return *this; |
---|
185 | } |
---|
186 | |
---|
187 | ArrayIterator<T,N> operator++(int) { |
---|
188 | ArrayIterator<T,N> tmp = *this; |
---|
189 | ++(*this); |
---|
190 | return tmp; |
---|
191 | } |
---|
192 | |
---|
193 | ArrayIterator<T,N>& operator--() { |
---|
194 | T_base::operator--(); |
---|
195 | return *this; |
---|
196 | } |
---|
197 | |
---|
198 | ArrayIterator<T,N> operator--(int) { |
---|
199 | ArrayIterator<T,N> tmp = *this; |
---|
200 | --(*this); |
---|
201 | return tmp; |
---|
202 | } |
---|
203 | }; |
---|
204 | |
---|
205 | template<typename T, int N> |
---|
206 | ConstArrayIterator<T,N>& ConstArrayIterator<T,N>::operator++() { |
---|
207 | CheckIteratorValidity("Attempted to increment",0); |
---|
208 | |
---|
209 | // The first loop iteration is peeled as it increases performance. |
---|
210 | // The same improvement can be obtained by telling the compiler that |
---|
211 | // the test is likely to be true, but this has too many portability issues |
---|
212 | // for now. |
---|
213 | |
---|
214 | // With a compiler peeling loops correctly (or with an effective BZ_LIKELY |
---|
215 | // macro, this could be simply written as: |
---|
216 | // |
---|
217 | // for (int i=0;i<N;++i) { |
---|
218 | // const int r = order_(i); |
---|
219 | // data_ += dataincr_[r]; |
---|
220 | // if (BZ_LIKELY(++pos_(r)!=ubound_(r))) |
---|
221 | // return *this; |
---|
222 | // pos_(r) = lbound_(r); |
---|
223 | // } |
---|
224 | |
---|
225 | |
---|
226 | const int r0 = order_(0); |
---|
227 | data_ += dataincr_[r0]; |
---|
228 | if (BZ_LIKELY(++pos_(r0)!=ubound_(r0))) |
---|
229 | return *this; |
---|
230 | pos_(r0) = lbound_(r0); |
---|
231 | |
---|
232 | for (int i=1;i<N;++i) { |
---|
233 | const int r = order_(i); |
---|
234 | data_ += dataincr_[r]; |
---|
235 | if (BZ_LIKELY(++pos_(r)!=ubound_(r))) |
---|
236 | return *this; |
---|
237 | pos_(r) = lbound_(r); |
---|
238 | } |
---|
239 | |
---|
240 | // At this place the value of data_ should match that of the end iterator. |
---|
241 | // Do the proper correction to achieve that. |
---|
242 | |
---|
243 | for (int i=1;i<N;++i) { |
---|
244 | const int r = order_(i); |
---|
245 | data_ -= dataincr_[r]; |
---|
246 | pos_(r) = ubound_(r)-1; |
---|
247 | } |
---|
248 | pos_(r0) = ubound_(r0); |
---|
249 | |
---|
250 | return *this; |
---|
251 | } |
---|
252 | |
---|
253 | template<typename T, int N> |
---|
254 | ConstArrayIterator<T,N>& ConstArrayIterator<T,N>::operator--() { |
---|
255 | CheckIteratorValidity("Attempted to decrement",1); |
---|
256 | |
---|
257 | // The first loop iteration is peeled as it increases performance. |
---|
258 | // The same improvement can be obtained by telling the compiler that |
---|
259 | // the test is likely to be true, but this has too many portability issues |
---|
260 | // for now. |
---|
261 | |
---|
262 | // With a compiler peeling loops correctly (or with an effective BZ_LIKELY |
---|
263 | // macro, this could be simply written as: |
---|
264 | // |
---|
265 | // for (int i=0;i<N;++i) { |
---|
266 | // const int r = order_(i); |
---|
267 | // data_ -= dataincr_[r]; |
---|
268 | // if (BZ_LIKELY(pos_(r)--!=lbound_(r))) |
---|
269 | // return *this; |
---|
270 | // pos_(r) = ubound_(r)-1; |
---|
271 | // } |
---|
272 | |
---|
273 | |
---|
274 | const int r0 = order_(0); |
---|
275 | data_ -= dataincr_[r0]; |
---|
276 | if (BZ_LIKELY(pos_(r0)--!=lbound_(r0))) |
---|
277 | return *this; |
---|
278 | pos_(r0) = ubound_(r0)-1; |
---|
279 | |
---|
280 | for (int i=1;i<N;++i) { |
---|
281 | const int r = order_(i); |
---|
282 | data_ -= dataincr_[r]; |
---|
283 | if (BZ_LIKELY(pos_(r)--!=lbound_(r))) |
---|
284 | return *this; |
---|
285 | pos_(r) = ubound_(r)-1; |
---|
286 | } |
---|
287 | |
---|
288 | // At this place the value of data_ should match that of the end iterator. |
---|
289 | // No correction is needed for operator-- |
---|
290 | |
---|
291 | return *this; |
---|
292 | } |
---|
293 | |
---|
294 | BZ_NAMESPACE_END |
---|
295 | |
---|
296 | |
---|
297 | #ifdef BZ_HAVE_STL |
---|
298 | // support for std::iterator_traits |
---|
299 | BZ_NAMESPACE(std) |
---|
300 | |
---|
301 | template <typename T, int N> |
---|
302 | struct iterator_traits< BZ_BLITZ_SCOPE(ConstArrayIterator)<T,N> > { |
---|
303 | typedef bidirectional_iterator_tag iterator_category; |
---|
304 | typedef T value_type; |
---|
305 | typedef blitz::diffType difference_type; |
---|
306 | typedef const T* pointer; |
---|
307 | typedef const T& reference; |
---|
308 | }; |
---|
309 | |
---|
310 | template <typename T, int N> |
---|
311 | struct iterator_traits< BZ_BLITZ_SCOPE(ArrayIterator)<T,N> > { |
---|
312 | typedef bidirectional_iterator_tag iterator_category; |
---|
313 | typedef T value_type; |
---|
314 | typedef blitz::diffType difference_type; |
---|
315 | typedef T* pointer; |
---|
316 | typedef T& reference; |
---|
317 | }; |
---|
318 | |
---|
319 | BZ_NAMESPACE_END |
---|
320 | |
---|
321 | #endif // BZ_HAVE_STL |
---|
322 | |
---|
323 | #endif // BZ_ARRAY_ITER_H |
---|
324 | |
---|