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 TF_ITERATOR_H
25 #define 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 
413 
414 #endif // TF_ITERATOR_H
TfIterator< typename std::remove_reference< T >::type, true > TfMakeReverseIterator(T &&container)
Definition: iterator.h:367
TfIterator GetNext() const
Definition: iterator.h:314
static IteratorType Begin(T &c)
Definition: iterator.h:69
constexpr size_t TfArraySize(const T(&array)[N]) noexcept
Definition: iterator.h:407
FMT_CONSTEXPR auto begin(const C &c) -> decltype(c.begin())
Definition: format.h:251
bool operator!=(const TfIterator &iterator) const
Definition: iterator.h:241
Reference operator*()
Definition: iterator.h:269
#define TF_CODING_ERROR
TfIterator()
Default constructor. This iterator is uninitialized.
Definition: iterator.h:198
TfIterator(Iterator const &begin, Iterator const &end)
Definition: iterator.h:220
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
#define ARCH_UNLIKELY(x)
Definition: hints.h:47
const Iterator & base() const
Definition: iterator.h:307
static IteratorType Begin(T const &c)
Definition: iterator.h:62
GLuint GLuint end
Definition: glew.h:1253
static IteratorType End(T const &c)
Definition: iterator.h:77
#define TF_FATAL_ERROR
const GLfloat * c
Definition: glew.h:16296
static IteratorType End(T &c)
Definition: iterator.h:56
bool operator==(const TfIterator &iterator) const
Definition: iterator.h:235
T::reverse_iterator IteratorType
Definition: iterator.h:68
GLuint GLuint GLsizei GLenum type
Definition: glew.h:1253
T::iterator IteratorType
Definition: iterator.h:54
GLdouble GLdouble GLdouble b
Definition: glew.h:9122
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:1245
static IteratorType Begin(T const &c)
Definition: iterator.h:76
Reference operator*() const
Definition: iterator.h:277
bool operator!() const
Definition: iterator.h:227
static IteratorType End(T &c)
Definition: iterator.h:70
TfIterator & operator++()
Definition: iterator.h:248
TfIterator operator++(int)
Definition: iterator.h:261
#define PXR_NAMESPACE_CLOSE_SCOPE
Definition: pxr.h:83
GA_API const UT_StringHolder N
static IteratorType End(T const &c)
Definition: iterator.h:63
Tf_IteratorInterface< T, Reverse > IterInterface
Definition: iterator.h:192
GLenum const void GLuint GLint reference
Definition: glew.h:13644
IterInterface::IteratorType Iterator
Definition: iterator.h:193
GLenum array
Definition: glew.h:9066
#define const
Definition: zconf.h:214
Iterator & operator->()
Definition: iterator.h:285
GLsizei const GLfloat * value
Definition: glew.h:1849
T::const_reverse_iterator IteratorType
Definition: iterator.h:75
TfIterator< typename std::remove_reference< T >::type > TfMakeIterator(T &&container)
Definition: iterator.h:359
type
Definition: core.h:528