primRange.h

//
// 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_USD_USD_PRIM_RANGE_H
#define PXR_USD_USD_PRIM_RANGE_H

#include "pxr/pxr.h"
#include "pxr/usd/usd/api.h"
#include "pxr/usd/usd/common.h"
#include "pxr/usd/usd/prim.h"
#include "pxr/usd/usd/primFlags.h"

#include <vector>
#include <iterator>

PXR_NAMESPACE_OPEN_SCOPE

class UsdPrimRange
{
public:
    class iterator;

    class EndSentinel {
    private:
        friend class UsdPrimRange;
        explicit EndSentinel(UsdPrimRange const *range) : _range(range) {}
        friend class UsdPrimRange::iterator;
        UsdPrimRange const *_range;
    };

    class iterator : public boost::iterator_adaptor<
        iterator,                      // crtp base.
        Usd_PrimDataConstPtr,          // base iterator.
        UsdPrim,                       // value type.
        boost::forward_traversal_tag,  // traversal.
        UsdPrim>                       // reference type.
    {
    public:
        iterator() : iterator_adaptor_(nullptr) {}

        iterator(EndSentinel e)
            : iterator_adaptor_(e._range->_end)
            , _range(e._range) {}
        
        bool IsPostVisit() const { return _isPost; }

        USD_API void PruneChildren();

        inline bool operator==(iterator const &other) const {
            return _range == other._range &&
                base() == other.base() &&
                _proxyPrimPath == other._proxyPrimPath &&
                _depth == other._depth &&
                _pruneChildrenFlag == other._pruneChildrenFlag &&
                _isPost == other._isPost;
        }

        inline bool operator==(EndSentinel const &other) const {
            return _range == other._range && base() == _range->_end;
        }

        inline bool operator!=(iterator const &other) const {
            return !(*this == other);
        }

        inline bool operator!=(EndSentinel const &other) const {
            return !(*this == other);
        }
         
    private:
        friend class UsdPrimRange;
        friend class boost::iterator_core_access;
        
        iterator(UsdPrimRange const *range,
                 Usd_PrimDataConstPtr prim,
                 SdfPath proxyPrimPath,
                 unsigned int depth)
            : iterator_adaptor_(prim)
            , _range(range)
            , _proxyPrimPath(proxyPrimPath)
            , _depth(depth) {}

        USD_API void increment();
        
        inline reference dereference() const { 
            return UsdPrim(base(), _proxyPrimPath);
        }

        UsdPrimRange const *_range = nullptr;
        SdfPath _proxyPrimPath;
        unsigned int _depth = 0;

        // True when the client has asked that the next increment skips the
        // children of the current prim.
        bool _pruneChildrenFlag = false;
        // True when we're on the post-side of a prim.  Unused if
        // _range->_postOrder is false.
        bool _isPost = false;
    };

    using const_iterator = iterator;

    UsdPrimRange()
        : _begin(nullptr)
        , _end(nullptr)
        , _initDepth(0)
        , _postOrder(false) {}

    explicit UsdPrimRange(const UsdPrim &start) {
        Usd_PrimDataConstPtr p = get_pointer(start._Prim());
        _Init(p, p ? p->GetNextPrim() : nullptr, start._ProxyPrimPath());
    }

    UsdPrimRange(const UsdPrim &start,
                 const Usd_PrimFlagsPredicate &predicate) {
        Usd_PrimDataConstPtr p = get_pointer(start._Prim());
        _Init(p, p ? p->GetNextPrim() : nullptr,
              start._ProxyPrimPath(), predicate);
    }

    static UsdPrimRange
    PreAndPostVisit(const UsdPrim &start) {
        UsdPrimRange result(start);
        result._postOrder = true;
        return result;
    }

    static UsdPrimRange
    PreAndPostVisit(const UsdPrim &start,
                    const Usd_PrimFlagsPredicate &predicate) {
        UsdPrimRange result(start, predicate);
        result._postOrder = true;
        return result;
    }

    static UsdPrimRange
    AllPrims(const UsdPrim &start) {
        return UsdPrimRange(start, UsdPrimAllPrimsPredicate);
    }

    static UsdPrimRange
    AllPrimsPreAndPostVisit(const UsdPrim &start) {
        return PreAndPostVisit(start, UsdPrimAllPrimsPredicate);
    }

    USD_API
    static UsdPrimRange
    Stage(const UsdStagePtr &stage,
          const Usd_PrimFlagsPredicate &predicate = UsdPrimDefaultPredicate);

    iterator begin() const {
        return iterator(this, _begin, _initProxyPrimPath, _initDepth);
    }
    const_iterator cbegin() const {
        return iterator(this, _begin, _initProxyPrimPath, _initDepth);
    }

    UsdPrim front() const { return *begin(); }

    // XXX C++11 & 14 require that c/end() return the same type as c/begin() for
    // range-based-for loops to work correctly.  C++17 relaxes that requirement.
    // Change the return type to EndSentinel once we are on C++17.

    iterator end() const { return EndSentinel(this); }
    const_iterator cend() const { return EndSentinel(this); }

    void increment_begin() {
        set_begin(++begin());
    }

    void set_begin(iterator const &newBegin) {
        TF_VERIFY(!newBegin.IsPostVisit());
        _begin = newBegin.base();
        _initProxyPrimPath = newBegin._proxyPrimPath;
        _initDepth = newBegin._depth;
    }

    bool empty() const { return begin() == end(); }

    explicit operator bool() const { return !empty(); }

    bool operator==(UsdPrimRange const &other) const {
        return this == &other ||
            (_begin == other._begin &&
             _end == other._end &&
             _initProxyPrimPath == other._initProxyPrimPath &&
             _predicate == other._predicate &&
             _postOrder == other._postOrder &&
             _initDepth == other._initDepth);
    }

    bool operator!=(UsdPrimRange const &other) const {
        return !(*this == other);
    }

private:
    UsdPrimRange(Usd_PrimDataConstPtr begin,
                 Usd_PrimDataConstPtr end,
                 const SdfPath& proxyPrimPath,
                 const Usd_PrimFlagsPredicate &predicate =
                 UsdPrimDefaultPredicate) {
        _Init(begin, end, proxyPrimPath, predicate);
    }

    // Helpers.
    void _Init(const Usd_PrimData *first,
               const Usd_PrimData *last,
               const SdfPath &proxyPrimPath,
               const Usd_PrimFlagsPredicate &predicate = 
               UsdPrimDefaultPredicate) {
        _begin = first;
        _end = last;
        _initProxyPrimPath = proxyPrimPath;
        _predicate = _begin ? 
            Usd_CreatePredicateForTraversal(_begin, proxyPrimPath, predicate) :
            predicate;
        _postOrder = false;
        _initDepth = 0;

        // Advance to the first prim that passes the predicate.
        iterator b = begin();
        if (b.base() != _end &&
            !Usd_EvalPredicate(_predicate, b.base(), proxyPrimPath)) {
            b._pruneChildrenFlag = true;
            set_begin(++b);
        }
    }

    // Data members.

    // These members are fixed for the life of the range.
    Usd_PrimDataConstPtr _begin;
    Usd_PrimDataConstPtr _end;
    SdfPath _initProxyPrimPath;
    Usd_PrimFlagsPredicate _predicate;
    unsigned int _initDepth;
    bool _postOrder;
};


PXR_NAMESPACE_CLOSE_SCOPE

#endif // PXR_USD_USD_PRIM_RANGE_H