iterator.h

Go to the documentation of this file.

//
// Copyright 2016 Pixar
//
// Licensed under the terms set forth in the LICENSE.txt file available at
// https://openusd.org/license.
//
#ifndef PXR_BASE_TF_ITERATOR_H
#define PXR_BASE_TF_ITERATOR_H
 
 
#include "pxr/pxr.h"
#include "pxr/base/arch/hints.h"
#include "pxr/base/tf/diagnosticLite.h"
 
#include <iterator>
#include <type_traits>
#include <utility>
 
PXR_NAMESPACE_OPEN_SCOPE
 
// May be specialized by container proxies and container "views" to indicate
// they should be copied for TfIterator iteration.
template <class T>
struct Tf_ShouldIterateOverCopy : std::false_type {};
 
// IteratorInterface abstracts the differences between forward/backward and
// const/non-const iteration so that TfIterator doesn't have to think about
// them.  It simply provides the IteratorType (which is either iterator,
// const_iterator, reverse_iterator, or reverse_const_iterator) and Begin and
// End which call the correct functions in the container (begin, rbegin, end,
// rend).
template <class T, bool Reverse>
struct Tf_IteratorInterface {
    typedef typename T::iterator IteratorType;
    static IteratorType Begin(T &c) { return c.begin(); }
    static IteratorType End(T &c) { return c.end(); }
};
 
template <class T, bool Reverse>
struct Tf_IteratorInterface<const T, Reverse> {
    typedef typename T::const_iterator IteratorType;
    static IteratorType Begin(T const &c) { return c.begin(); }
    static IteratorType End(T const &c) { return c.end(); }
};
 
template <class T>
struct Tf_IteratorInterface<T, true> {
    typedef typename T::reverse_iterator IteratorType;
    static IteratorType Begin(T &c) { return c.rbegin(); }
    static IteratorType End(T &c) { return c.rend(); }
};
 
template <class T>
struct Tf_IteratorInterface<const T, true> {
    typedef typename T::const_reverse_iterator IteratorType;
    static IteratorType Begin(T const &c) { return c.rbegin(); }
    static IteratorType End(T const &c) { return c.rend(); }
};
 
template <class T, bool Reverse=false>
class TfIterator {
 
    // Forward declare implementation structs.
    struct _IteratorPairAndCopy;
    struct _IteratorPair;
 
    // Select the correct data storage depending on whether we should iterate
    // over a copy of the container.
    typedef typename std::conditional<
        Tf_ShouldIterateOverCopy<T>::value, 
        _IteratorPairAndCopy, _IteratorPair
        >::type _Data;
 
public:
    // Choose either iterator or const_iterator for Iterator depending on
    // whether T is const.
    typedef Tf_IteratorInterface<T, Reverse> IterInterface;
    typedef typename IterInterface::IteratorType Iterator;
 
    typedef typename std::iterator_traits<Iterator>::reference Reference;
 
    TfIterator() { }
 
    TfIterator(T &container) : _data(container) {}
 
    TfIterator(T &&container)
        : _data(container)
    {
        static_assert(
            Tf_ShouldIterateOverCopy<typename std::decay<T>::type>::value,
            "TfIterator only allows rvalues that it has been told to copy "
            "via Tf_ShouldIterateOverCopy");
    }
 
    TfIterator(Iterator const &begin, Iterator const &end)
        : _data(begin, end)
    {
    }
 
    bool operator!() const {
        return _data.current == _data.end;
    }
 
    bool operator==(const TfIterator& iterator) const {
        return _data.current == iterator._data.current;
    }
 
    bool operator!=(const TfIterator& iterator) const {
        return !(*this == iterator);
    }
 
    TfIterator& operator++() {
        if (!*this) {
            TF_CODING_ERROR("iterator exhausted");
            return *this;
        }
 
        ++_data.current;
        return *this;
    }
 
    TfIterator operator++(int) {
        TfIterator iterator = *this;
        ++(*this);
        return iterator;
    }
 
    Reference operator*() {
        if (ARCH_UNLIKELY(!*this))
            TF_FATAL_ERROR("iterator exhausted");
        return *_data.current;
    }
 
    Reference operator*() const {
        if (ARCH_UNLIKELY(!*this))
            TF_FATAL_ERROR("iterator exhausted");
        return *_data.current;
    }
 
    Iterator& operator->() {
        if (ARCH_UNLIKELY(!*this))
            TF_FATAL_ERROR("iterator exhausted");
        return _data.current;
    }   
 
    explicit operator bool() const {
        return !(_data.current == _data.end);
    }
 
    operator Iterator() const {
        return _data.current;
    }
 
    const Iterator& base() const {
        return _data.current;
    }
 
    TfIterator GetNext() const {
        TfIterator next = *this;
        ++next;
        return next;
    }
 
  private:  // state
 
    // Normal iteration just holds onto the begin/end pair of iterators.
    struct _IteratorPair {
        _IteratorPair() {}
        explicit _IteratorPair(T &c) {
            // Use assignment rather than initializer-list here to work around
            // a GCC 4.1.2 bug when using TfIterator with TfHashMap.
            current = IterInterface::Begin(c);
            end = IterInterface::End(c);
        }
        _IteratorPair(Iterator const &b, Iterator const &e) :
            current(b), end(e) {}
        Iterator current;
        Iterator end;
    };
 
    // Iterating over copies which is appropriate for proxies retains a copy of
    // 'container' and iterators into the copy.
    struct _IteratorPairAndCopy : public _IteratorPair {
        _IteratorPairAndCopy() {}
        explicit _IteratorPairAndCopy(T const &c) : _IteratorPair(), _copy(c) {
            current = IterInterface::Begin(_copy);
            end = IterInterface::End(_copy);
        }
        using _IteratorPair::current;
        using _IteratorPair::end;
    private:
        T _copy;
    };
 
    _Data _data;
 
};
 
template <class T>
TfIterator<typename std::remove_reference<T>::type>
TfMakeIterator(T&& container)
{
    return TfIterator<typename std::remove_reference<T>::type>(
        std::forward<T>(container));
}
 
template <class T>
TfIterator<typename std::remove_reference<T>::type, /* Reverse = */ true>
TfMakeReverseIterator(T&& container)
{
    return TfIterator<typename std::remove_reference<T>::type, true>(
        std::forward<T>(container));
}
 
#define TF_FOR_ALL(iter, c) \
    for (auto iter = TfMakeIterator(c); iter; ++iter)
 
#define TF_REVERSE_FOR_ALL(iter, c) \
    for (auto iter = TfMakeReverseIterator(c); iter; ++iter)
 
template <class T, size_t N>
constexpr size_t TfArraySize(const T (&array)[N]) noexcept
{
    return N;
}
 
template <typename UnderlyingIterator>
class Tf_ProxyReferenceReverseIterator :
    private std::reverse_iterator<UnderlyingIterator> {
    // private API for interacting with an STL reverse_iterator of the
    // UnderlyingIterator
    using ReverseIterator = std::reverse_iterator<UnderlyingIterator>;
    const ReverseIterator& _reverse_iterator() const {  return *this; }
    ReverseIterator& _reverse_iterator() { return *this; }
    explicit Tf_ProxyReferenceReverseIterator(const ReverseIterator& it)
        : ReverseIterator(it) {}
    explicit Tf_ProxyReferenceReverseIterator(ReverseIterator&& it)
        : ReverseIterator(it) {}
public:
    using iterator_type = typename ReverseIterator::iterator_type;
    using iterator_category = typename ReverseIterator::iterator_category;
    using value_type = typename ReverseIterator::value_type;
    using reference = typename ReverseIterator::reference;
    using pointer = typename ReverseIterator::pointer;
    using difference_type = typename ReverseIterator::difference_type;
 
    static_assert(!std::is_reference<reference>::value,
                 "Tf_ProxyReferenceReverseIterator should only be used "
                 "when the underlying iterator's reference type is a "
                 "proxy (MyTypeRef) and not a true reference (MyType&)."
                 "Use std::reverse_iterator instead.");
    static_assert(std::is_same<iterator_category,
                               std::random_access_iterator_tag>::value,
                 "Tf_ProxyReferenceReverseIterator must wrap a random "
                 "access iterator.");
 
    Tf_ProxyReferenceReverseIterator() = default;
    explicit Tf_ProxyReferenceReverseIterator(UnderlyingIterator it) :
        ReverseIterator(it) {
    }
 
    // Operators and functions which can just use the underlying STL
    // implementation
    using ReverseIterator::base;
    using ReverseIterator::operator*;
    using ReverseIterator::operator[];
 
    pointer operator->() const { return std::prev(base()).operator->(); }
 
    // Many  methods can use the underlying STL implementation but need to
    // avoid returning a `std::reverse_iterator`
    Tf_ProxyReferenceReverseIterator& operator++() {
        ++_reverse_iterator();
        return *this;
    }
 
    Tf_ProxyReferenceReverseIterator operator++(int) {
        Tf_ProxyReferenceReverseIterator result{_reverse_iterator()};
        ++_reverse_iterator();
        return result;
    }
 
    Tf_ProxyReferenceReverseIterator& operator--() {
        --_reverse_iterator();
        return *this;
    }
 
    Tf_ProxyReferenceReverseIterator operator--(int) {
        Tf_ProxyReferenceReverseIterator result{_reverse_iterator()};
        --_reverse_iterator();
        return result;
    }
 
    Tf_ProxyReferenceReverseIterator operator+(difference_type increment) const {
        return Tf_ProxyReferenceReverseIterator(_reverse_iterator() + increment);
    }
 
    Tf_ProxyReferenceReverseIterator operator-(difference_type decrement) const {
        return Tf_ProxyReferenceReverseIterator(_reverse_iterator() - decrement);
    }
 
    template <typename OtherIt>
    difference_type operator-(
        const Tf_ProxyReferenceReverseIterator<OtherIt>& other) const {
        return _reverse_iterator() - other._reverse_iterator();
    }
 
    Tf_ProxyReferenceReverseIterator& operator+=(difference_type increment) {
        _reverse_iterator() += increment;
        return *this;
    }
 
    Tf_ProxyReferenceReverseIterator& operator-=(difference_type decrement) {
        _reverse_iterator() -= decrement;
        return *this;
    }
 
    inline friend Tf_ProxyReferenceReverseIterator
    operator+(const difference_type increment,
              const Tf_ProxyReferenceReverseIterator& iterator) {
        return Tf_ProxyReferenceReverseIterator(
            increment + iterator._reverse_iterator());
    }
 
    // Comparison operators defer to the STL implementation
    template <typename OtherIt>
    inline friend bool operator==(const Tf_ProxyReferenceReverseIterator& lhs,
                                  const Tf_ProxyReferenceReverseIterator<OtherIt>& rhs) {
        return lhs._reverse_iterator() == rhs._reverse_iterator();
    }
 
    template <typename OtherIt>
    inline friend bool operator!=(const Tf_ProxyReferenceReverseIterator& lhs,
                                  const Tf_ProxyReferenceReverseIterator<OtherIt>& rhs) {
        return lhs._reverse_iterator() != rhs._reverse_iterator();
    }
 
    template <typename OtherIt>
    inline friend bool operator<(const Tf_ProxyReferenceReverseIterator& lhs,
                                 const Tf_ProxyReferenceReverseIterator<OtherIt>& rhs) {
        return lhs._reverse_iterator() < rhs._reverse_iterator();
    }
 
    template <typename OtherIt>
    inline friend bool operator>(const Tf_ProxyReferenceReverseIterator& lhs,
                                 const Tf_ProxyReferenceReverseIterator<OtherIt>& rhs) {
        return lhs._reverse_iterator() > rhs._reverse_iterator();
    }
 
    template <typename OtherIt>
    inline friend bool operator<=(const Tf_ProxyReferenceReverseIterator& lhs,
                                  const Tf_ProxyReferenceReverseIterator<OtherIt>& rhs) {
        return lhs._reverse_iterator() <= rhs._reverse_iterator();
    }
 
    template <typename OtherIt>
    inline friend bool operator>=(const Tf_ProxyReferenceReverseIterator& lhs,
                                  const Tf_ProxyReferenceReverseIterator<OtherIt>& rhs) {
        return lhs._reverse_iterator() >= rhs._reverse_iterator();
    }
};
 
PXR_NAMESPACE_CLOSE_SCOPE
 
#endif  // PXR_BASE_TF_ITERATOR_H