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" 33 #include "pxr/base/tf/diagnosticLite.h" 34 35 #include <iterator> 36 #include <type_traits> 37 #include <utility> 38 39 PXR_NAMESPACE_OPEN_SCOPE 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> 53 struct Tf_IteratorInterface { 54 typedef typename T::iterator IteratorType; BeginTf_IteratorInterface55 static IteratorType Begin(T &c) { return c.begin(); } EndTf_IteratorInterface56 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< 185 Tf_ShouldIterateOverCopy<T>::value, 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. 192 typedef Tf_IteratorInterface<T, Reverse> IterInterface; 193 typedef typename IterInterface::IteratorType Iterator; 194 195 typedef typename std::iterator_traits<Iterator>::reference Reference; 196 197 /// Default constructor. This iterator is uninitialized. 198 TfIterator() { } 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( 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 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 220 TfIterator(Iterator const &begin, Iterator const &end) 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 248 TfIterator& operator++() { 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 261 TfIterator operator++(int) { 262 TfIterator iterator = *this; 263 ++(*this); 264 return iterator; 265 } 266 267 /// Returns the element referenced by this iterator. 268 /// \return element 269 Reference operator*() { 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 277 Reference operator*() const { 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 285 Iterator& operator->() { 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> 358 TfIterator<typename std::remove_reference<T>::type> 359 TfMakeIterator(T&& container) 360 { 361 return TfIterator<typename std::remove_reference<T>::type>( 362 std::forward<T>(container)); 363 } 364 365 template <class T> 366 TfIterator<typename std::remove_reference<T>::type, /* Reverse = */ true> 367 TfMakeReverseIterator(T&& container) 368 { 369 return TfIterator<typename std::remove_reference<T>::type, true>( 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 PXR_NAMESPACE_CLOSE_SCOPE 413 414 #endif // PXR_BASE_TF_ITERATOR_H 415