Loading...
Searching...
No Matches
iterator.h
Go to the documentation of this file.
1//
2// Copyright 2016 Pixar
3//
4// Licensed under the Apache License, Version 2.0 (the "Apache License")
5// with the following modification; you may not use this file except in
6// compliance with the Apache License and the following modification to it:
7// Section 6. Trademarks. is deleted and replaced with:
8//
9// 6. Trademarks. This License does not grant permission to use the trade
10// names, trademarks, service marks, or product names of the Licensor
11// and its affiliates, except as required to comply with Section 4(c) of
12// the License and to reproduce the content of the NOTICE file.
13//
14// You may obtain a copy of the Apache License at
15//
16// http://www.apache.org/licenses/LICENSE-2.0
17//
18// Unless required by applicable law or agreed to in writing, software
19// distributed under the Apache License with the above modification is
20// distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
21// KIND, either express or implied. See the Apache License for the specific
22// language governing permissions and limitations under the Apache License.
23//
24#ifndef PXR_BASE_TF_ITERATOR_H
25#define PXR_BASE_TF_ITERATOR_H
26
30
31#include "pxr/pxr.h"
32#include "pxr/base/arch/hints.h"
34
35#include <iterator>
36#include <type_traits>
37#include <utility>
38
39PXR_NAMESPACE_OPEN_SCOPE
40
41// May be specialized by container proxies and container "views" to indicate
42// they should be copied for TfIterator iteration.
43template <class T>
44struct Tf_ShouldIterateOverCopy : std::false_type {};
45
46// IteratorInterface abstracts the differences between forward/backward and
47// const/non-const iteration so that TfIterator doesn't have to think about
48// them. It simply provides the IteratorType (which is either iterator,
49// const_iterator, reverse_iterator, or reverse_const_iterator) and Begin and
50// End which call the correct functions in the container (begin, rbegin, end,
51// rend).
52template <class T, bool Reverse>
53struct Tf_IteratorInterface {
54 typedef typename T::iterator IteratorType;
55 static IteratorType Begin(T &c) { return c.begin(); }
56 static IteratorType End(T &c) { return c.end(); }
57};
58
59template <class T, bool Reverse>
60struct Tf_IteratorInterface<const T, Reverse> {
61 typedef typename T::const_iterator IteratorType;
62 static IteratorType Begin(T const &c) { return c.begin(); }
63 static IteratorType End(T const &c) { return c.end(); }
64};
65
66template <class T>
67struct Tf_IteratorInterface<T, true> {
68 typedef typename T::reverse_iterator IteratorType;
69 static IteratorType Begin(T &c) { return c.rbegin(); }
70 static IteratorType End(T &c) { return c.rend(); }
71};
72
73template <class T>
74struct Tf_IteratorInterface<const T, true> {
75 typedef typename T::const_reverse_iterator IteratorType;
76 static IteratorType Begin(T const &c) { return c.rbegin(); }
77 static IteratorType End(T const &c) { return c.rend(); }
78};
79
175template <class T, bool Reverse=false>
177
178 // Forward declare implementation structs.
179 struct _IteratorPairAndCopy;
180 struct _IteratorPair;
181
182 // Select the correct data storage depending on whether we should iterate
183 // over a copy of the container.
184 typedef typename std::conditional<
185 Tf_ShouldIterateOverCopy<T>::value,
186 _IteratorPairAndCopy, _IteratorPair
187 >::type _Data;
188
189public:
190 // Choose either iterator or const_iterator for Iterator depending on
191 // whether T is const.
192 typedef Tf_IteratorInterface<T, Reverse> IterInterface;
193 typedef typename IterInterface::IteratorType Iterator;
194
195 typedef typename std::iterator_traits<Iterator>::reference Reference;
196
199
203 TfIterator(T &container) : _data(container) {}
204
206 TfIterator(T &&container)
207 : _data(container)
208 {
209 static_assert(
210 Tf_ShouldIterateOverCopy<typename std::decay<T>::type>::value,
211 "TfIterator only allows rvalues that it has been told to copy "
212 "via Tf_ShouldIterateOverCopy");
213 }
214
220 TfIterator(Iterator const &begin, Iterator const &end)
221 : _data(begin, end)
222 {
223 }
224
227 bool operator!() const {
228 return _data.current == _data.end;
229 }
230
235 bool operator==(const TfIterator& iterator) const {
236 return _data.current == iterator._data.current;
237 }
238
241 bool operator!=(const TfIterator& iterator) const {
242 return !(*this == iterator);
243 }
244
249 if (!*this) {
250 TF_CODING_ERROR("iterator exhausted");
251 return *this;
252 }
253
254 ++_data.current;
255 return *this;
256 }
257
262 TfIterator iterator = *this;
263 ++(*this);
264 return iterator;
265 }
266
269 Reference operator*() {
270 if (ARCH_UNLIKELY(!*this))
271 TF_FATAL_ERROR("iterator exhausted");
272 return *_data.current;
273 }
274
277 Reference operator*() const {
278 if (ARCH_UNLIKELY(!*this))
279 TF_FATAL_ERROR("iterator exhausted");
280 return *_data.current;
281 }
282
285 Iterator& operator->() {
286 if (ARCH_UNLIKELY(!*this))
287 TF_FATAL_ERROR("iterator exhausted");
288 return _data.current;
289 }
290
293 explicit operator bool() const {
294 return !(_data.current == _data.end);
295 }
296
300 operator Iterator() const {
301 return _data.current;
302 }
303
307 const Iterator& base() const {
308 return _data.current;
309 }
310
315 TfIterator next = *this;
316 ++next;
317 return next;
318 }
319
320 private: // state
321
322 // Normal iteration just holds onto the begin/end pair of iterators.
323 struct _IteratorPair {
324 _IteratorPair() {}
325 explicit _IteratorPair(T &c) {
326 // Use assignment rather than initializer-list here to work around
327 // a GCC 4.1.2 bug when using TfIterator with TfHashMap.
328 current = IterInterface::Begin(c);
329 end = IterInterface::End(c);
330 }
331 _IteratorPair(Iterator const &b, Iterator const &e) :
332 current(b), end(e) {}
333 Iterator current;
334 Iterator end;
335 };
336
337 // Iterating over copies which is appropriate for proxies retains a copy of
338 // 'container' and iterators into the copy.
339 struct _IteratorPairAndCopy : public _IteratorPair {
340 _IteratorPairAndCopy() {}
341 explicit _IteratorPairAndCopy(T const &c) : _IteratorPair(), _copy(c) {
342 current = IterInterface::Begin(_copy);
343 end = IterInterface::End(_copy);
344 }
345 using _IteratorPair::current;
346 using _IteratorPair::end;
347 private:
348 T _copy;
349 };
350
351 _Data _data;
352
353};
354
357template <class T>
359TfMakeIterator(T&& container)
360{
362 std::forward<T>(container));
363}
364
365template <class T>
367TfMakeReverseIterator(T&& container)
368{
370 std::forward<T>(container));
371}
372
390#define TF_FOR_ALL(iter, c) \
391 for (auto iter = TfMakeIterator(c); iter; ++iter)
392
399#define TF_REVERSE_FOR_ALL(iter, c) \
400 for (auto iter = TfMakeReverseIterator(c); iter; ++iter)
401
406template <class T, size_t N>
407constexpr size_t TfArraySize(const T (&array)[N]) noexcept
408{
409 return N;
410}
411
418template <typename UnderlyingIterator>
419class Tf_ProxyReferenceReverseIterator :
420 private std::reverse_iterator<UnderlyingIterator> {
421 // private API for interacting with an STL reverse_iterator of the
422 // UnderlyingIterator
423 using ReverseIterator = std::reverse_iterator<UnderlyingIterator>;
424 const ReverseIterator& _reverse_iterator() const { return *this; }
425 ReverseIterator& _reverse_iterator() { return *this; }
426 explicit Tf_ProxyReferenceReverseIterator(const ReverseIterator& it)
427 : ReverseIterator(it) {}
428 explicit Tf_ProxyReferenceReverseIterator(ReverseIterator&& it)
429 : ReverseIterator(it) {}
430public:
431 using iterator_type = typename ReverseIterator::iterator_type;
432 using iterator_category = typename ReverseIterator::iterator_category;
433 using value_type = typename ReverseIterator::value_type;
434 using reference = typename ReverseIterator::reference;
435 using pointer = typename ReverseIterator::pointer;
436 using difference_type = typename ReverseIterator::difference_type;
437
438 static_assert(!std::is_reference<reference>::value,
439 "Tf_ProxyReferenceReverseIterator should only be used "
440 "when the underlying iterator's reference type is a "
441 "proxy (MyTypeRef) and not a true reference (MyType&)."
442 "Use std::reverse_iterator instead.");
443 static_assert(std::is_same<iterator_category,
444 std::random_access_iterator_tag>::value,
445 "Tf_ProxyReferenceReverseIterator must wrap a random "
446 "access iterator.");
447
448 Tf_ProxyReferenceReverseIterator() = default;
449 explicit Tf_ProxyReferenceReverseIterator(UnderlyingIterator it) :
450 ReverseIterator(it) {
451 }
452
453 // Operators and functions which can just use the underlying STL
454 // implementation
455 using ReverseIterator::base;
456 using ReverseIterator::operator*;
457 using ReverseIterator::operator[];
458
461 pointer operator->() const { return std::prev(base()).operator->(); }
462
463 // Many methods can use the underlying STL implementation but need to
464 // avoid returning a `std::reverse_iterator`
465 Tf_ProxyReferenceReverseIterator& operator++() {
466 ++_reverse_iterator();
467 return *this;
468 }
469
470 Tf_ProxyReferenceReverseIterator operator++(int) {
471 Tf_ProxyReferenceReverseIterator result{_reverse_iterator()};
472 ++_reverse_iterator();
473 return result;
474 }
475
476 Tf_ProxyReferenceReverseIterator& operator--() {
477 --_reverse_iterator();
478 return *this;
479 }
480
481 Tf_ProxyReferenceReverseIterator operator--(int) {
482 Tf_ProxyReferenceReverseIterator result{_reverse_iterator()};
483 --_reverse_iterator();
484 return result;
485 }
486
487 Tf_ProxyReferenceReverseIterator operator+(difference_type increment) const {
488 return Tf_ProxyReferenceReverseIterator(_reverse_iterator() + increment);
489 }
490
491 Tf_ProxyReferenceReverseIterator operator-(difference_type decrement) const {
492 return Tf_ProxyReferenceReverseIterator(_reverse_iterator() - decrement);
493 }
494
495 template <typename OtherIt>
496 difference_type operator-(
497 const Tf_ProxyReferenceReverseIterator<OtherIt>& other) const {
498 return _reverse_iterator() - other._reverse_iterator();
499 }
500
501 Tf_ProxyReferenceReverseIterator& operator+=(difference_type increment) {
502 _reverse_iterator() += increment;
503 return *this;
504 }
505
506 Tf_ProxyReferenceReverseIterator& operator-=(difference_type decrement) {
507 _reverse_iterator() -= decrement;
508 return *this;
509 }
510
511 inline friend Tf_ProxyReferenceReverseIterator
512 operator+(const difference_type increment,
513 const Tf_ProxyReferenceReverseIterator& iterator) {
514 return Tf_ProxyReferenceReverseIterator(
515 increment + iterator._reverse_iterator());
516 }
517
518 // Comparison operators defer to the STL implementation
519 template <typename OtherIt>
520 inline friend bool operator==(const Tf_ProxyReferenceReverseIterator& lhs,
521 const Tf_ProxyReferenceReverseIterator<OtherIt>& rhs) {
522 return lhs._reverse_iterator() == rhs._reverse_iterator();
523 }
524
525 template <typename OtherIt>
526 inline friend bool operator!=(const Tf_ProxyReferenceReverseIterator& lhs,
527 const Tf_ProxyReferenceReverseIterator<OtherIt>& rhs) {
528 return lhs._reverse_iterator() != rhs._reverse_iterator();
529 }
530
531 template <typename OtherIt>
532 inline friend bool operator<(const Tf_ProxyReferenceReverseIterator& lhs,
533 const Tf_ProxyReferenceReverseIterator<OtherIt>& rhs) {
534 return lhs._reverse_iterator() < rhs._reverse_iterator();
535 }
536
537 template <typename OtherIt>
538 inline friend bool operator>(const Tf_ProxyReferenceReverseIterator& lhs,
539 const Tf_ProxyReferenceReverseIterator<OtherIt>& rhs) {
540 return lhs._reverse_iterator() > rhs._reverse_iterator();
541 }
542
543 template <typename OtherIt>
544 inline friend bool operator<=(const Tf_ProxyReferenceReverseIterator& lhs,
545 const Tf_ProxyReferenceReverseIterator<OtherIt>& rhs) {
546 return lhs._reverse_iterator() <= rhs._reverse_iterator();
547 }
548
549 template <typename OtherIt>
550 inline friend bool operator>=(const Tf_ProxyReferenceReverseIterator& lhs,
551 const Tf_ProxyReferenceReverseIterator<OtherIt>& rhs) {
552 return lhs._reverse_iterator() >= rhs._reverse_iterator();
553 }
554};
555
556PXR_NAMESPACE_CLOSE_SCOPE
557
558#endif // PXR_BASE_TF_ITERATOR_H
constexpr size_t TfArraySize(const T(&array)[N]) noexcept
Returns the number of elements in a statically sized array.
Definition: iterator.h:407
A simple iterator adapter for STL containers.
Definition: iterator.h:176
TfIterator operator++(int)
Post-increment operator.
Definition: iterator.h:261
Reference operator*() const
Returns the element referenced by this iterator.
Definition: iterator.h:277
Iterator & operator->()
Returns a pointer to the element referenced by this iterator.
Definition: iterator.h:285
bool operator!() const
Returns true if this iterator is exhausted.
Definition: iterator.h:227
TfIterator & operator++()
Pre-increment operator.
Definition: iterator.h:248
TfIterator(T &&container)
Allow rvalues only if the container type T should be copied by TfIterator.
Definition: iterator.h:206
TfIterator GetNext() const
Returns an iterator that is positioned at the next element in the sequence.
Definition: iterator.h:314
bool operator!=(const TfIterator &iterator) const
Returns false if (*this == iterator) returns true, returns true otherwise.
Definition: iterator.h:241
TfIterator(Iterator const &begin, Iterator const &end)
Constructs an iterator to traverse a subset of the elements in a container.
Definition: iterator.h:220
TfIterator()
Default constructor. This iterator is uninitialized.
Definition: iterator.h:198
TfIterator(T &container)
Constructs an iterator to traverse each element of the specified STL container object.
Definition: iterator.h:203
Reference operator*()
Returns the element referenced by this iterator.
Definition: iterator.h:269
bool operator==(const TfIterator &iterator) const
Returns true if this Iterator.has the same position in the sequence as the specified iterator.
Definition: iterator.h:235
const Iterator & base() const
Returns an STL iterator that has the same position as this iterator.
Definition: iterator.h:307
Stripped down version of diagnostic.h that doesn't define std::string.
TfIterator< typename std::remove_reference< T >::type > TfMakeIterator(T &&container)
Helper functions for creating TfIterator objects.
Definition: iterator.h:359
#define TF_FATAL_ERROR(fmt, args)
Issue a fatal error and end the program.
Definition: diagnostic.h:108
#define TF_CODING_ERROR(fmt, args)
Issue an internal programming error, but continue execution.
Definition: diagnostic.h:85
Compiler hints.