iterator.h

Go to the documentation of this file.

//
// Copyright 2016 Pixar
//
// Licensed under the Apache License, Version 2.0 (the "Apache License")
// with the following modification; you may not use this file except in
// compliance with the Apache License and the following modification to it:
// Section 6. Trademarks. is deleted and replaced with:
//
// 6. Trademarks. This License does not grant permission to use the trade
//    names, trademarks, service marks, or product names of the Licensor
//    and its affiliates, except as required to comply with Section 4(c) of
//    the License and to reproduce the content of the NOTICE file.
//
// You may obtain a copy of the Apache License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the Apache License with the above modification is
// distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, either express or implied. See the Apache License for the specific
// language governing permissions and limitations under the Apache 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;
}

PXR_NAMESPACE_CLOSE_SCOPE

#endif  // PXR_BASE_TF_ITERATOR_H