Traversal.h

Go to the documentation of this file.

//
// Copyright Contributors to the MaterialX Project
// SPDX-License-Identifier: Apache-2.0
//
 
#ifndef MATERIALX_TRAVERSAL_H
#define MATERIALX_TRAVERSAL_H

 
#include <MaterialXCore/Exception.h>
 
MATERIALX_NAMESPACE_BEGIN
 
class Element;
 
using ElementPtr = shared_ptr<Element>;
using ConstElementPtr = shared_ptr<const Element>;

class MX_CORE_API Edge
{
  public:
    Edge(ElementPtr elemDown, ElementPtr elemConnect, ElementPtr elemUp) :
        _elemDown(elemDown),
        _elemConnect(elemConnect),
        _elemUp(elemUp)
    {
    }
    ~Edge() { }
 
    bool operator==(const Edge& rhs) const
    {
        return _elemDown == rhs._elemDown &&
               _elemConnect == rhs._elemConnect &&
               _elemUp == rhs._elemUp;
    }
    bool operator!=(const Edge& rhs) const
    {
        return !(*this == rhs);
    }
    bool operator<(const Edge& rhs) const
    {
        return std::tie(_elemDown, _elemConnect, _elemUp) < std::tie(rhs._elemDown, rhs._elemConnect, rhs._elemUp);
    }
 
    operator bool() const;

    ElementPtr getDownstreamElement() const
    {
        return _elemDown;
    }

    ElementPtr getConnectingElement() const
    {
        return _elemConnect;
    }

    ElementPtr getUpstreamElement() const
    {
        return _elemUp;
    }

    string getName() const;
 
  private:
    ElementPtr _elemDown;
    ElementPtr _elemConnect;
    ElementPtr _elemUp;
};

class MX_CORE_API TreeIterator
{
  public:
    explicit TreeIterator(ElementPtr elem) :
        _elem(elem),
        _prune(false),
        _holdCount(0)
    {
    }
    ~TreeIterator() { }
 
  private:
    using StackFrame = std::pair<ElementPtr, size_t>;
 
  public:
    bool operator==(const TreeIterator& rhs) const
    {
        return _elem == rhs._elem &&
               _stack == rhs._stack &&
               _prune == rhs._prune;
    }
    bool operator!=(const TreeIterator& rhs) const
    {
        return !(*this == rhs);
    }

    ElementPtr operator*() const
    {
        return _elem;
    }

    TreeIterator& operator++();


    ElementPtr getElement() const
    {
        return _elem;
    }


    size_t getElementDepth() const
    {
        return _stack.size();
    }


    void setPruneSubtree(bool prune)
    {
        _prune = prune;
    }

    bool getPruneSubtree() const
    {
        return _prune;
    }


    TreeIterator& begin(size_t holdCount = 0)
    {
        _holdCount = holdCount;
        return *this;
    }

    static const TreeIterator& end();

 
  private:
    ElementPtr _elem;
    vector<StackFrame> _stack;
    bool _prune;
    size_t _holdCount;
};

class MX_CORE_API GraphIterator
{
  public:
    explicit GraphIterator(ElementPtr elem) :
        _upstreamElem(elem),
        _prune(false),
        _holdCount(0)
    {
        _pathElems.insert(elem);
    }
    ~GraphIterator() { }
 
  private:
    using ElementSet = std::set<ElementPtr>;
    using StackFrame = std::pair<ElementPtr, size_t>;
 
  public:
    bool operator==(const GraphIterator& rhs) const
    {
        return _upstreamElem == rhs._upstreamElem &&
               _stack == rhs._stack &&
               _prune == rhs._prune;
    }
    bool operator!=(const GraphIterator& rhs) const
    {
        return !(*this == rhs);
    }

    Edge operator*() const
    {
        return Edge(getDownstreamElement(),
                    getConnectingElement(),
                    getUpstreamElement());
    }

    GraphIterator& operator++();


    ElementPtr getDownstreamElement() const
    {
        return !_stack.empty() ? _stack.back().first : ElementPtr();
    }

    ElementPtr getConnectingElement() const
    {
        return _connectingElem;
    }

    ElementPtr getUpstreamElement() const
    {
        return _upstreamElem;
    }

    size_t getUpstreamIndex() const
    {
        return !_stack.empty() ? _stack.back().second : 0;
    }


    size_t getElementDepth() const
    {
        return _stack.size();
    }

    size_t getNodeDepth() const;


    void setPruneSubgraph(bool prune)
    {
        _prune = prune;
    }

    bool getPruneSubgraph() const
    {
        return _prune;
    }


    GraphIterator& begin(size_t holdCount = 0)
    {
        // Increment once to generate a valid edge.
        if (_stack.empty())
        {
            operator++();
        }
 
        _holdCount = holdCount;
        return *this;
    }

    static const GraphIterator& end();

 
  private:
    void extendPathUpstream(ElementPtr upstreamElem, ElementPtr connectingElem);
    void returnPathDownstream(ElementPtr upstreamElem);
    bool skipOrMarkAsVisited(const Edge&);
 
  private:
    ElementPtr _upstreamElem;
    ElementPtr _connectingElem;
    ElementSet _pathElems;
    vector<StackFrame> _stack;
    std::set<Edge> _visitedEdges;
    bool _prune;
    size_t _holdCount;
};

class MX_CORE_API InheritanceIterator
{
  public:
    explicit InheritanceIterator(ConstElementPtr elem) :
        _elem(elem),
        _holdCount(0)
    {
        _pathElems.insert(elem);
    }
    ~InheritanceIterator() { }
 
  private:
    using ConstElementSet = std::set<ConstElementPtr>;
 
  public:
    bool operator==(const InheritanceIterator& rhs) const
    {
        return _elem == rhs._elem;
    }
    bool operator!=(const InheritanceIterator& rhs) const
    {
        return !(*this == rhs);
    }

    ConstElementPtr operator*() const
    {
        return _elem;
    }

    InheritanceIterator& operator++();

    InheritanceIterator& begin(size_t holdCount = 0)
    {
        _holdCount = holdCount;
        return *this;
    }

    static const InheritanceIterator& end();
 
  private:
    ConstElementPtr _elem;
    ConstElementSet _pathElems;
    size_t _holdCount;
};

class MX_CORE_API ExceptionFoundCycle : public Exception
{
  public:
    using Exception::Exception;
};
 
extern MX_CORE_API const Edge NULL_EDGE;
 
extern MX_CORE_API const TreeIterator NULL_TREE_ITERATOR;
extern MX_CORE_API const GraphIterator NULL_GRAPH_ITERATOR;
extern MX_CORE_API const InheritanceIterator NULL_INHERITANCE_ITERATOR;
 
MATERIALX_NAMESPACE_END
 
#endif