HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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 
27 /// \file tf/iterator.h
28 /// \ingroup group_tf_Containers
29 /// A simple iterator adapter for \c STL containers.
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 
40 
41 // May be specialized by container proxies and container "views" to indicate
42 // they should be copied for TfIterator iteration.
43 template <class T>
44 struct 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).
52 template <class T, bool Reverse>
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 
59 template <class T, bool Reverse>
60 struct 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 
66 template <class T>
67 struct 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 
73 template <class T>
74 struct 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 
80 /// \class TfIterator
81 /// \ingroup group_tf_Containers group_tf_Stl
82 ///
83 /// A simple iterator adapter for \c STL containers.
84 ///
85 /// \c TfIterator iterates over the elements in an \c STL container, according
86 /// to the semantics of the \ref iterator_pattern "simple iterator pattern".
87 /// The following examples compare the \c TfIterator to \c STL, highlighting
88 /// the brevity of the \c TfIterator interface.
89 /// \code
90 /// std::vector<int> vector;
91 /// std::set<int> set;
92 ///
93 /// // TfIterator 'while' loop
94 /// TfIterator< std::vector<int> > i(vector);
95 /// while (i) {
96 /// int x = *i++;
97 /// }
98 ///
99 /// // STL 'while' loop
100 /// std::vector<int>::iterator i = vector.begin();
101 /// while (i != vector.end()) {
102 /// int x = *i++;
103 /// }
104 ///
105 /// // TfIterator 'for' loop
106 /// std::set<int> set;
107 /// for (TfIterator< const std::set<int> > j = set; j; ++j) {
108 /// int x = *j;
109 /// }
110 ///
111 /// // STL 'for' loop
112 /// std::set<int> set;
113 /// for (std::set<int>::iterator j = set.begin(); j != set.end(); ++j) {
114 /// int x = *j;
115 /// }
116 /// \endcode
117 ///
118 /// Note that using the \c TF_FOR_ALL() macro, even more brevity is possible.
119 /// For example, to print out all items of a \c set<int> \c s, we could write
120 /// \code
121 /// TF_FOR_ALL(i, s)
122 /// printf("%d\n", *i);
123 /// \endcode
124 ///
125 /// Typically, a \c TfIterator is used to traverse all of the elements in an
126 /// \c STL container. For ordered sets, other uses include iterating over a
127 /// subset of the elements in the container, and using a \c TfIterator as a
128 /// sentinel.
129 /// \code
130 /// // Iterate over subset
131 /// TfIterator< std::vector<int> > start, finish;
132 /// TfIterator< std::vector<int> > iterator(start, finish);
133 ///
134 /// // TfIterator sentinel
135 /// TfIterator< std::vector<int> > sentinel(finish, finish);
136 /// while (iterator != sentinel) {
137 /// int x = *iterator++;
138 /// }
139 /// \endcode
140 ///
141 /// \anchor iterator_pattern
142 /// <b>The Simple Iterator Pattern</b>
143 ///
144 /// The \e simple \e iterator pattern generalizes pointer semantics to
145 /// traverse a set of elements, much like \c STL iterators. However, the
146 /// simple iterator pattern subscribes to a simpler subset of pointer
147 /// operations: pointer assignment (\c operator=), auto-increment (\c
148 /// operator++), dereferencing (\c operator*), redirection (\c operator->),
149 /// and null pointer comparison (\c operator! and \c operator \c bool). The
150 /// simpler interface improves code legibility for the typical set traversals
151 /// for which iterators are most commonly used. It is particularly useful for
152 /// specifying iterators over sets of elements that are maintained by a user
153 /// object, since the interface calls for only one \c GetIterator() entry
154 /// point rather than dual \c begin() and \c end() calls. This is especially
155 /// desirable when the object owns many different sets.
156 /// \code
157 /// // The simple iterator pattern.
158 /// class Iterator {
159 /// Iterator(); // default c'tor
160 /// Iterator(const Iterator&); // copy c'tor
161 /// Iterator& operator=(const Iterator &); // assignment
162 /// Iterator& operator++(); // pre-increment
163 /// Iterator operator++(int); // post-increment
164 /// reference operator *(); // dereference
165 /// pointer operator->(); // redirection
166 /// bool operator==(const Iterator &) const; // equality
167 /// bool operator!=(const Iterator &) const; // inequality
168 /// bool operator!() const // is exhausted
169 /// operator bool() const; // is not exhausted
170 /// };
171 /// \endcode
172 ///
173 /// \param T container type
174 ///
175 template <class T, bool Reverse=false>
176 class TfIterator {
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<
186  _IteratorPairAndCopy, _IteratorPair
187  >::type _Data;
188 
189 public:
190  // Choose either iterator or const_iterator for Iterator depending on
191  // whether T is const.
194 
196 
197  /// Default constructor. This iterator is uninitialized.
199 
200  /// Constructs an iterator to traverse each element of the specified
201  /// \c STL container object.
202  /// \param container container object
203  TfIterator(T &container) : _data(container) {}
204 
205  /// Allow rvalues only if the container type T should be copied by TfIterator.
206  TfIterator(T &&container)
207  : _data(container)
208  {
209  static_assert(
211  "TfIterator only allows rvalues that it has been told to copy "
212  "via Tf_ShouldIterateOverCopy");
213  }
214 
215  /// Constructs an iterator to traverse a subset of the elements in a
216  /// container. This iterator is exhausted when it reaches the end
217  /// iterator.
218  /// \param begin iterator at the beginning of the sequence
219  /// \param end iterator at the end of the sequence
221  : _data(begin, end)
222  {
223  }
224 
225  /// Returns true if this iterator is exhausted.
226  /// \return true if this iterator is exhausted
227  bool operator!() const {
228  return _data.current == _data.end;
229  }
230 
231  /// Returns true if this Iterator.has the same position in the sequence as
232  /// the specified iterator. The end of the sequence need not be the same.
233  /// \param iterator iterator to compare
234  /// \return true if this Iterator.has the same position as \e iterator
235  bool operator==(const TfIterator& iterator) const {
236  return _data.current == iterator._data.current;
237  }
238 
239  /// Returns false if (*this == \a iterator) returns true, returns true
240  /// otherwise.
241  bool operator!=(const TfIterator& iterator) const {
242  return !(*this == iterator);
243  }
244 
245  /// Pre-increment operator. Advances this iterator to the next element in
246  /// the sequence.
247  /// \return this iterator
249  if (!*this) {
250  TF_CODING_ERROR("iterator exhausted");
251  return *this;
252  }
253 
254  ++_data.current;
255  return *this;
256  }
257 
258  /// Post-increment operator. Advances this iterator to the next element in
259  /// the sequence, and returns a copy of this iterator prior to the increment.
260  /// \return copy of this iterator prior to increment
262  TfIterator iterator = *this;
263  ++(*this);
264  return iterator;
265  }
266 
267  /// Returns the element referenced by this iterator.
268  /// \return element
270  if (ARCH_UNLIKELY(!*this))
271  TF_FATAL_ERROR("iterator exhausted");
272  return *_data.current;
273  }
274 
275  /// Returns the element referenced by this iterator.
276  /// \return element
278  if (ARCH_UNLIKELY(!*this))
279  TF_FATAL_ERROR("iterator exhausted");
280  return *_data.current;
281  }
282 
283  /// Returns a pointer to the element referenced by this iterator.
284  /// \return pointer to element
286  if (ARCH_UNLIKELY(!*this))
287  TF_FATAL_ERROR("iterator exhausted");
288  return _data.current;
289  }
290 
291  /// Explicit bool conversion operator.
292  /// The Iterator object converts to true if it has not been exhausted.
293  explicit operator bool() const {
294  return !(_data.current == _data.end);
295  }
296 
297  /// Returns an \c STL iterator that has the same position as this
298  /// iterator.
299  /// \return \c STL iterator at the same position as this iterator
300  operator Iterator() const {
301  return _data.current;
302  }
303 
304  /// Returns an \c STL iterator that has the same position as this
305  /// iterator.
306  /// \return \c STL iterator at the same position as this iterator
307  const Iterator& base() const {
308  return _data.current;
309  }
310 
311  /// Returns an iterator that is positioned at the next element in the
312  /// sequence.
313  /// \return iterator at next element in the sequence
314  TfIterator GetNext() const {
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 
355 /// Helper functions for creating TfIterator objects.
356 /// \ingroup group_tf_Containers
357 template <class T>
359 TfMakeIterator(T&& container)
360 {
362  std::forward<T>(container));
363 }
364 
365 template <class T>
367 TfMakeReverseIterator(T&& container)
368 {
370  std::forward<T>(container));
371 }
372 
373 /// Macro for iterating over a container.
374 ///
375 /// For any container \c c of type \c T, the following loop
376 /// \code
377 /// for (TfIterator<T> i = c.begin(); i; ++i) {
378 /// ...
379 /// }
380 /// \endcode
381 /// is equivalent to
382 /// \code
383 /// TF_FOR_ALL(i, c) {
384 /// ...
385 /// }
386 /// \endcode
387 ///
388 /// \ingroup group_tf_Containers
389 /// \hideinitializer
390 #define TF_FOR_ALL(iter, c) \
391  for (auto iter = TfMakeIterator(c); iter; ++iter)
392 
393 /// Macro for iterating over a container in reverse.
394 ///
395 /// Operates like \a TF_FOR_ALL, but iterates the container in reverse order.
396 ///
397 /// \ingroup group_tf_Containers
398 /// \hideinitializer
399 #define TF_REVERSE_FOR_ALL(iter, c) \
400  for (auto iter = TfMakeReverseIterator(c); iter; ++iter)
401 
402 /// Returns the number of elements in a statically sized array.
403 ///
404 /// This function is an implementation of the array version of C++17's
405 /// std::size()
406 template <class T, size_t N>
407 constexpr size_t TfArraySize(const T (&array)[N]) noexcept
408 {
409  return N;
410 }
411 
412 /// A reverse iterator adapter for `std::reverse_iterator` that provides
413 /// an `operator->` compatible with proxy reference types.
414 /// This should only be used when the underlying iterator's reference
415 /// is a value type and should become unnecessary in newer compilers and C++20.
416 /// This implementation was written for use with random access iterators but
417 /// could be extended to bidirectional iterators if necessary.
418 template <typename UnderlyingIterator>
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) {}
430 public:
431  using iterator_type = typename ReverseIterator::iterator_type;
432  using iterator_category = typename ReverseIterator::iterator_category;
436  using difference_type = typename ReverseIterator::difference_type;
437 
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 
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 
459  /// Customize operator-> to support proxied reference types
460  /// Compatible with the C++20 specification.
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`
466  ++_reverse_iterator();
467  return *this;
468  }
469 
471  Tf_ProxyReferenceReverseIterator result{_reverse_iterator()};
472  ++_reverse_iterator();
473  return result;
474  }
475 
477  --_reverse_iterator();
478  return *this;
479  }
480 
482  Tf_ProxyReferenceReverseIterator result{_reverse_iterator()};
483  --_reverse_iterator();
484  return result;
485  }
486 
488  return Tf_ProxyReferenceReverseIterator(_reverse_iterator() + increment);
489  }
490 
492  return Tf_ProxyReferenceReverseIterator(_reverse_iterator() - decrement);
493  }
494 
495  template <typename OtherIt>
497  const Tf_ProxyReferenceReverseIterator<OtherIt>& other) const {
498  return _reverse_iterator() - other._reverse_iterator();
499  }
500 
502  _reverse_iterator() += increment;
503  return *this;
504  }
505 
507  _reverse_iterator() -= decrement;
508  return *this;
509  }
510 
512  operator+(const difference_type increment,
513  const Tf_ProxyReferenceReverseIterator& iterator) {
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,
522  return lhs._reverse_iterator() == rhs._reverse_iterator();
523  }
524 
525  template <typename OtherIt>
526  inline friend bool operator!=(const Tf_ProxyReferenceReverseIterator& lhs,
528  return lhs._reverse_iterator() != rhs._reverse_iterator();
529  }
530 
531  template <typename OtherIt>
532  inline friend bool operator<(const Tf_ProxyReferenceReverseIterator& lhs,
534  return lhs._reverse_iterator() < rhs._reverse_iterator();
535  }
536 
537  template <typename OtherIt>
538  inline friend bool operator>(const Tf_ProxyReferenceReverseIterator& lhs,
540  return lhs._reverse_iterator() > rhs._reverse_iterator();
541  }
542 
543  template <typename OtherIt>
544  inline friend bool operator<=(const Tf_ProxyReferenceReverseIterator& lhs,
546  return lhs._reverse_iterator() <= rhs._reverse_iterator();
547  }
548 
549  template <typename OtherIt>
550  inline friend bool operator>=(const Tf_ProxyReferenceReverseIterator& lhs,
552  return lhs._reverse_iterator() >= rhs._reverse_iterator();
553  }
554 };
555 
557 
558 #endif // PXR_BASE_TF_ITERATOR_H
TfIterator< typename std::remove_reference< T >::type, true > TfMakeReverseIterator(T &&container)
Definition: iterator.h:367
pointer operator->() const
Definition: iterator.h:461
TfIterator GetNext() const
Definition: iterator.h:314
typename ReverseIterator::iterator_category iterator_category
Definition: iterator.h:432
static IteratorType Begin(T &c)
Definition: iterator.h:69
constexpr size_t TfArraySize(const T(&array)[N]) noexcept
Definition: iterator.h:407
Tf_ProxyReferenceReverseIterator & operator-=(difference_type decrement)
Definition: iterator.h:506
GLsizei const GLfloat * value
Definition: glcorearb.h:824
bool operator!=(const TfIterator &iterator) const
Definition: iterator.h:241
Reference operator*()
Definition: iterator.h:269
#define TF_CODING_ERROR
friend bool operator<(const Tf_ProxyReferenceReverseIterator &lhs, const Tf_ProxyReferenceReverseIterator< OtherIt > &rhs)
Definition: iterator.h:532
TfIterator()
Default constructor. This iterator is uninitialized.
Definition: iterator.h:198
TfIterator(Iterator const &begin, Iterator const &end)
Definition: iterator.h:220
Tf_ProxyReferenceReverseIterator(UnderlyingIterator it)
Definition: iterator.h:449
typename ReverseIterator::difference_type difference_type
Definition: iterator.h:436
**But if you need a result
Definition: thread.h:613
friend bool operator>=(const Tf_ProxyReferenceReverseIterator &lhs, const Tf_ProxyReferenceReverseIterator< OtherIt > &rhs)
Definition: iterator.h:550
uint64 value_type
Definition: GA_PrimCompat.h:29
TfIterator(T &container)
Definition: iterator.h:203
TfIterator(T &&container)
Allow rvalues only if the container type T should be copied by TfIterator.
Definition: iterator.h:206
typename ReverseIterator::pointer pointer
Definition: iterator.h:435
typename ReverseIterator::value_type value_type
Definition: iterator.h:433
#define ARCH_UNLIKELY(x)
Definition: hints.h:47
Tf_ProxyReferenceReverseIterator & operator+=(difference_type increment)
Definition: iterator.h:501
const Iterator & base() const
Definition: iterator.h:307
GLuint GLuint end
Definition: glcorearb.h:475
static IteratorType Begin(T const &c)
Definition: iterator.h:62
static IteratorType End(T const &c)
Definition: iterator.h:77
#define TF_FATAL_ERROR
Tf_ProxyReferenceReverseIterator operator-(difference_type decrement) const
Definition: iterator.h:491
static IteratorType End(T &c)
Definition: iterator.h:56
bool operator==(const TfIterator &iterator) const
Definition: iterator.h:235
Tf_ProxyReferenceReverseIterator operator+(difference_type increment) const
Definition: iterator.h:487
T::reverse_iterator IteratorType
Definition: iterator.h:68
Tf_ProxyReferenceReverseIterator & operator++()
Definition: iterator.h:465
typename ReverseIterator::iterator_type iterator_type
Definition: iterator.h:431
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1222
friend Tf_ProxyReferenceReverseIterator operator+(const difference_type increment, const Tf_ProxyReferenceReverseIterator &iterator)
Definition: iterator.h:512
T::iterator IteratorType
Definition: iterator.h:54
friend bool operator==(const Tf_ProxyReferenceReverseIterator &lhs, const Tf_ProxyReferenceReverseIterator< OtherIt > &rhs)
Definition: iterator.h:520
friend bool operator<=(const Tf_ProxyReferenceReverseIterator &lhs, const Tf_ProxyReferenceReverseIterator< OtherIt > &rhs)
Definition: iterator.h:544
GLenum void ** pointer
Definition: glcorearb.h:810
std::iterator_traits< Iterator >::reference Reference
Definition: iterator.h:195
static IteratorType Begin(T &c)
Definition: iterator.h:55
PXR_NAMESPACE_CLOSE_SCOPE PXR_NAMESPACE_OPEN_SCOPE
Definition: path.h:1432
static IteratorType Begin(T const &c)
Definition: iterator.h:76
Reference operator*() const
Definition: iterator.h:277
bool operator!() const
Definition: iterator.h:227
Tf_ProxyReferenceReverseIterator operator++(int)
Definition: iterator.h:470
Tf_ProxyReferenceReverseIterator operator--(int)
Definition: iterator.h:481
static IteratorType End(T &c)
Definition: iterator.h:70
Tf_ProxyReferenceReverseIterator & operator--()
Definition: iterator.h:476
TfIterator & operator++()
Definition: iterator.h:248
friend bool operator>(const Tf_ProxyReferenceReverseIterator &lhs, const Tf_ProxyReferenceReverseIterator< OtherIt > &rhs)
Definition: iterator.h:538
TfIterator operator++(int)
Definition: iterator.h:261
#define PXR_NAMESPACE_CLOSE_SCOPE
Definition: pxr.h:91
GA_API const UT_StringHolder N
static IteratorType End(T const &c)
Definition: iterator.h:63
typename ReverseIterator::reference reference
Definition: iterator.h:434
Tf_IteratorInterface< T, Reverse > IterInterface
Definition: iterator.h:192
difference_type operator-(const Tf_ProxyReferenceReverseIterator< OtherIt > &other) const
Definition: iterator.h:496
IterInterface::IteratorType Iterator
Definition: iterator.h:193
Definition: core.h:1131
that also have some descendant prim *whose name begins with which in turn has a child named baz where *the predicate and *a name There is also one special expression reference
type
Definition: core.h:1059
Iterator & operator->()
Definition: iterator.h:285
T::const_reverse_iterator IteratorType
Definition: iterator.h:75
TfIterator< typename std::remove_reference< T >::type > TfMakeIterator(T &&container)
Definition: iterator.h:359
friend bool operator!=(const Tf_ProxyReferenceReverseIterator &lhs, const Tf_ProxyReferenceReverseIterator< OtherIt > &rhs)
Definition: iterator.h:526
PcpNodeRef_ChildrenIterator begin(const PcpNodeRef::child_const_range &r)
Support for range-based for loops for PcpNodeRef children ranges.
Definition: node.h:558