/////////////////////////////////////////////////////////////////////////////// // Copyright (C) 2002-2016, Open Design Alliance (the "Alliance"). // All rights reserved. // // This software and its documentation and related materials are owned by // the Alliance. The software may only be incorporated into application // programs owned by members of the Alliance, subject to a signed // Membership Agreement and Supplemental Software License Agreement with the // Alliance. The structure and organization of this software are the valuable // trade secrets of the Alliance and its suppliers. The software is also // protected by copyright law and international treaty provisions. Application // programs incorporating this software must include the following statement // with their copyright notices: // // This application incorporates Teigha(R) software pursuant to a license // agreement with Open Design Alliance. // Teigha(R) Copyright (C) 2002-2016 by Open Design Alliance. // All rights reserved. // // By use of this software, its documentation or related materials, you // acknowledge and accept the above terms. /////////////////////////////////////////////////////////////////////////////// #ifndef _ODDBGRAPH_H_INCLUDED_ #define _ODDBGRAPH_H_INCLUDED_ #include "TD_PackPush.h" #include "OdaDefs.h" #include "RxObject.h" #include "OdArray.h" class OdDbGraph; class OdDbGraphNode; /** \details This template class is a specialization of the OdArray class for OdDbGraphNode object pointers. */ typedef OdArray > OdDbGraphNodeArray; /** \details This class implements generic node objects for generic graphs. \remarks A graph consists of a collection of nodes bi-directionally linked by directional edges. An edge connected to a node is represented as a pointer or reference to the node at the other end of the edge. References are classified as either incoming or outgoing. Every incoming reference has a corresponding outgoing reference and vice versa. Each GraphNode object can have any number of references associated with it, enabling the implementation of any graph structure. \sa * OdDbGraph * OdDbGraphStack * OdDbXrefGraph * OdDbXrefGraphNode Library: TD_Db */ class TOOLKIT_EXPORT OdDbGraphNode : public OdRxObject { friend class OdDbGraph; public: OdDbGraphNode() : m_pData(0), m_flags(0), m_pOwner(0) {} ODRX_DECLARE_MEMBERS(OdDbGraphNode); virtual ~OdDbGraphNode(); enum Flags { kNone = 0x00, // None. kVisited = 0x01, // Used internally by OdDbGraph::findCycles() and while traversing a graphs with cycles. kOutsideRefed = 0x02, // Used internally by Xref detach. kSelected = 0x04, // User selection. Set by getOutgoing. kInList = 0x08, // Is *in* list. Set by getOutgoing. kListAll = 0x0E, // Used to *clear* kSelected, kInList, and kOutsideRefed. kFirstLevel = 0x10, // The *node* is connected to the root *node*. Read Only. kUnresTree = 0x20, // The tree is unresolved. kAll = 0x2F // Used to *clear* all but kFirstLevel. }; /** \details Returns the data associated with this GraphNode object. */ void* data() const { return m_pData; } /** \details Sets the data associated with this GraphNode object. \param pData [in] Pointer to the data. */ void setData( void* pData) { m_pData = pData; } /** \details Return the number of outgoing references associated with this GraphNode object. */ int numOut() const { return m_outgoing.size(); } /** \details Return the number of incoming references associated with this GraphNode object. */ int numIn() const { return m_incoming.size(); } /** \details Returns the specified incoming reference of this GraphNode object. \param refIndex [in] Reference index. \remarks Returns a null pointer if and only if the index is not valid. */ OdDbGraphNode* in( int refIndex) const { return m_incoming.at(refIndex); } /** \details Returns the specified outgoing reference of this GraphNode object. \param refIndex [in] Reference index. \remarks Returns a null pointer if and only if the index is not valid. */ OdDbGraphNode* out( int refIndex) const { return m_outgoing.at(refIndex); } /** \details Creates an outgoing reference, in this GraphNode object, to the specified GraphNode object. \param pTo [in] Pointer to the outgoing GraphNode. \remarks Creates an incoming reference to this GraphNode object in *pTo. Throws: OdError(eInvalidOwnerObject) if the specified GraphNode object are not in the same Graph object as this GraphNode object. \sa OdDbGraph::addEdge */ void addRefTo( OdDbGraphNode* pTo); /** \details Removes the outgoing reference, in this GraphNode object, to the specified GraphNode object. \param pTo [in] Pointer to the outgoing GraphNode. \remarks Removes the incoming reference to this GraphNode object in the outgoing GraphNode object. The specified GraphNode object must be part of the same graph as this GraphNode object. */ void removeRefTo( OdDbGraphNode* pNode); /** \details Removes all references in and to this GraphNode object. \remarks Always called by ~OdDbGraphNode(). */ void disconnectAll(); /** \details Returns the Graph object to which this GraphNode object is attached. */ OdDbGraph* owner() const { return m_pOwner; } /** \details Returns true if and only if the all the specified set flag bits are set in this GraphNode object. \param flags [in] Flag bits. \remarks flags must be a combination of one or more of the following: Name Value Description kNone 0x00 None. kVisited 0x01 Used internally by OdDbGraph::findCycles() and while traversing a graphs with cycles. kOutsideRefed 0x02 Used internally by Xref detach. kSelected 0x04 User selection. Set by getOutgoing. kInList 0x08 Is in list. Set by getOutgoing. kListAll 0x0E Used to clear kSelected, kInList, kOutsideRefed. kFirstLevel 0x10 The node is connected to the root node. Read Only. kUnresTree 0x20 The tree is unresolved. kAll 0x2F Used to clear all but kFirstLevel.
*/ bool isMarkedAs( OdUInt8 flags) const { return ((m_flags & flags)==flags); } /** \details Sets the specified set flag bits in this GraphNode object. \param flags [in] Flag bits. \remarks flags must be a combination of one or more of the following: Name Value Description kNone 0x00 None. kVisited 0x01 Used internally by OdDbGraph::findCycles() and while traversing a graphs with cycles. kOutsideRefed 0x02 Used internally by Xref detach. kSelected 0x04 User selection. Set by getOutgoing. kInList 0x08 Is in list. Set by getOutgoing. kListAll 0x0E Used to clear kSelected, kInList, kOutsideRefed. kFirstLevel 0x10 The node is connected to the root node. Read Only. kUnresTree 0x20 The tree is unresolved. kAll 0x2F Used to clear all but kFirstLevel.
*/ void markAs( OdUInt8 flags) { if(!GETBIT(flags, kFirstLevel)) { m_flags |= flags; } else { throw OdError(eInvalidInput); } } /** \details Clears the specified set flag bits in this GraphNode object. \param flags [in] Flag bits. \remarks flags must be a combination of one or more of the following: Name Value Description kNone 0x00 None. kVisited 0x01 Used internally by OdDbGraph::findCycles() and while traversing a graphs with cycles. kOutsideRefed 0x02 Used internally by Xref detach. kSelected 0x04 User selection. Set by getOutgoing. kInList 0x08 Is in list. Set by getOutgoing. kListAll 0x0E Used to clear kSelected, kInList, kOutsideRefed. kFirstLevel 0x10 The node is connected to the root node. Read Only. kUnresTree 0x20 The tree is unresolved. kAll 0x2F Used to clear all but kFirstLevel.
*/ void clear( OdUInt8 flags) { if(!GETBIT(flags, kFirstLevel)) { m_flags &= (~flags); } else { throw OdError(eInvalidInput); } } /** \details Marks this GraphNode object and all nested outgoing GraphNode objects with the specified flags. \param flags [in] Flag bits. \param pNodeArray [in] Pointer to a GraphNode array. \remarks If pNodeArray is specified, this function appends this GraphNode object and all nested outgoing GraphNode objects, to the specified array. While tranversing a branch, if any GraphNode object already has the flag bits set, the branch is no longer followed. The user must clear the flags with OdDbGraph::clearAll() or OdDbGraphNode::clear() when done with them. flags must be a combination of one or more of the following: Name Value Description kNone 0x00 None. kVisited 0x01 Used internally by OdDbGraph::findCycles() and while traversing a graphs with cycles. kOutsideRefed 0x02 Used internally by Xref detach. kSelected 0x04 User selection. Set by getOutgoing. kInList 0x08 Is in list. Set by getOutgoing. kListAll 0x0E Used to clear kSelected, kInList, kOutsideRefed. kFirstLevel 0x10 The node is connected to the root node. Read Only. kUnresTree 0x20 The tree is unresolved. kAll 0x2F Used to clear all but kFirstLevel.
\note This function is not implemented, and will generate a link error if you reference it. */ void markTree( OdUInt8 flags, OdDbGraphNodeArray* pNodeArray = 0); // Circularity detection methods /** \details Returns the number of outgoing cyclical references associated with this GraphNode object. \note This function returns valid results only if OdDbGraph::findCycles() has been called with no intervening changes to the graph. */ int numCycleOut() const { return m_cycleOut.size(); } /** \details Returns the number of incoming cyclical references associated with this GraphNode object. \note This function returns valid results only if OdDbGraph::findCycles() has been called with no intervening changes to the graph. */ int numCycleIn() const { return m_cycleIn.size(); } /** \details Returns the specified incoming cyclical reference of this GraphNode object. \param refIndex [in] Reference index. \remarks Returns a null pointer if and only if the index is not valid. \note This function returns valid results only if OdDbGraph::findCycles() has been called with no intervening changes to the graph. */ OdDbGraphNode* cycleIn( int refIndex) const { return m_cycleIn[refIndex]; } /** \details Returns the specified outgoing cyclical reference of this GraphNode object. \param refIndex [in] Reference index. \remarks Returns a null pointer if and only if the index is not valid. \note This function returns valid results only if OdDbGraph::findCycles() has been called with no intervening changes to the graph. */ OdDbGraphNode* cycleOut( int refIndex) const { return m_cycleOut[refIndex]; } /** \details Returns the next outgoing cyclical reference of this GraphNode object. \remarks This function returns cycleOut(0). \remarks Returns a null pointer if cycleOut(0) == 0. \note This function returns valid results only if OdDbGraph::findCycles() has been called with no intervening changes to the graph. */ OdDbGraphNode* nextCycleNode() const { return cycleOut(0); } /** \details Returns true if and only if this GraphNode object is part of a cyclical reference. \note This function returns valid results only if OdDbGraph::findCycles() has been called with no intervening changes to the graph. */ bool isCycleNode() const { return (numCycleOut() != 0 || numCycleIn() != 0); } private: void setOwner( OdDbGraph* pGraph) { if(m_pOwner) { ODA_FAIL(); throw OdError(eInvalidOwnerObject); } m_pOwner = pGraph; } friend struct if_leaf_push_to; friend struct clear_cycles; friend void break_edge(OdDbGraphNode* , OdDbGraphNode* ); void* m_pData; OdUInt8 m_flags; OdDbGraphNodeArray m_outgoing; OdDbGraphNodeArray m_incoming; OdDbGraph* m_pOwner; OdDbGraphNodeArray m_cycleOut; OdDbGraphNodeArray m_cycleIn; }; /** \details This template class is a specialization of the OdSmartPtr class template for OdDbGraphNode object pointers. */ typedef OdSmartPtr OdDbGraphNodePtr; /** \details This class implements stacks for OdDbGraphNode object pointers. Library: TD_Db */ class OdDbGraphStack { public: /** \param initPhysicalLength [in] Initial Physical Length. \param initGrowLength [in] Initial Grow Length. \remarks Physical Length is the maximum number of entries in this Stack object before it automatically grows. Grow Length is the number of entries by which the Physical Length will grow as required. */ OdDbGraphStack( int initPhysicalLength = 0, int initGrowLength = 8) : m_stack(initPhysicalLength, initGrowLength) {} ~OdDbGraphStack() {} /** \details Pushes the specified GraphNode onto this Stack object. \param pNode [in] Pointer to the node to be pushed. */ void push( OdDbGraphNode* pNode) { m_stack.push_back(pNode); } /** \details Pops and returns the GraphNode at the top of this Stack object. \remarks Returns a null pointer if this Stack object is empty. */ OdDbGraphNode* pop() { if(!isEmpty()) { OdDbGraphNode* pRes = top(); m_stack.removeLast(); return pRes; } return 0; } /** \details Returns the OdDbGraphNode at the top of this Stack object. \remarks Returns a null pointer if this Stack object is empty. */ OdDbGraphNode* top() const { return isEmpty() ? 0 : m_stack.last(); } /** \details Returns true if and only if this Stack object is empty. */ bool isEmpty() const { return m_stack.empty(); } private: OdDbGraphNodeArray m_stack; }; /** \details This class implements generic graph objects. \remarks A graph consists of a collection of nodes bi-directionally linked by directional edges. An edge connected to a node is represented as a pointer or reference to the node at the other end of the edge. References are classified as either incoming or outgoing. Every incoming reference has a corresponding outgoing reference and vice versa. Each GraphNode object can have any number of references associated with it, enabling the implementation of any graph structure. \sa * OdDbGraphNode * OdDbGraphStack * OdDbXrefGraph * OdDbXrefGraphNode Library: TD_Db */ class TOOLKIT_EXPORT OdDbGraph { friend class OdDbGraphNode; public: OdDbGraph() : m_bDirty(false), m_nNonCycleNodes(0) {} virtual ~OdDbGraph(); /** \details Returns the specified GraphNode object of this Graph object. \param nodeIndex [in] Node index. */ OdDbGraphNode* node( int nodeIndex) const { return m_nodes.at(nodeIndex); } /** \details Returns the root (first) GraphNode object of this Graph object. \remarks Returns a null pointer if isEmpty(). */ OdDbGraphNode* rootNode() const; /** \details Returns the specified incoming reference of this Graph object. \param refIndex [in] Reference index. */ int numNodes() const { return m_nodes.size(); } /** \details Returns true if and only if this Graph object is empty. */ bool isEmpty() const { return numNodes() == 0; } /** \details Adds the specifed GraphNode object to this Graph object. \param pNode [in] Pointer to the GraphNode object. \remarks *pNode must be created with new(), and should not be deleted once added to this Graph object; This Graph object will delete the GraphNode when it is no longer needed. Throws: OdError(eInvalidOwnerObject) if the specified GraphNode object already has an owner. */ void addNode( OdDbGraphNode* pNode); /** \details Adds the specified edge to this Graph object. \param pFrom [in] Pointer to the GraphNode at the start of the edge. \param pTo [in] Pointer to the GraphNode at the end of the edge. \remarks Creates an outgoing reference to *pTo in *pFrom, and an incoming reference to *pFrom in *pTo. Throws: OdError(eInvalidOwnerObject) if the specified GraphNode objects are not in the same Graph object. */ void addEdge( OdDbGraphNode* pFrom, OdDbGraphNode* pTo); /** \details Removes the specified node from this GraphNode object, and all references to it. \param pNode [in] Pointer to the GraphNode object. */ void delNode( OdDbGraphNode* pNode); /** \details Removes all nodes and cycle nodes from this Graph object. \remarks Always called by ~OdDbGraph(). */ void reset(); /** \details Clears the specified set flag bits in the GraphNode objects of this Graph object. \param flags [in] Flag bits. \remarks flags must be a combination of one or more of the following: Name Value Description OdDbGraphNode::kNone 0x00 None. OdDbGraphNode::kVisited 0x01 Used internally by OdDbGraph::findCycles() and while traversing a graphs with cycles. OdDbGraphNode::kOutsideRefed 0x02 Used internally by Xref detach. OdDbGraphNode::kSelected 0x04 User selection. Set by getOutgoing. OdDbGraphNode::kInList 0x08 Is in list. Set by getOutgoing. OdDbGraphNode::kListAll 0x0E Used to clear kSelected, kInList, kOutsideRefed. OdDbGraphNode::kFirstLevel 0x10 The node is connected to the root node. Read Only. OdDbGraphNode::kUnresTree 0x20 The tree is unresolved. OdDbGraphNode::kAll 0x2F Used to clear all but kFirstLevel.
OdDbGraphNode::kListAll and OdDbGraphNode::kAll are intended to be used with this function. */ void clearAll( OdUInt8 flags); /** \details Adds to the specified array, the nested outgoing GraphNode objects from the specified GraphNode objects. \param outgoing [in/out] Array of GraphNode objects. \remarks The user must clear the kListAll flags with OdDbGraph::clearAll() or OdDbGraphNode::clear() when done with them. */ void getOutgoing( OdDbGraphNodeArray& outgoing); /** \details Finds the cyclical nodes for this Graph object. \param pStart [in] Pointer to the starting node from which to search. Usually defaulted. \returns Returns true if and only if there are any cyclical GraphNodes. \remarks This function must be called with no intervening changes to the graph, prior to querying cycle information. */ virtual bool findCycles( OdDbGraphNode* pStart = 0); /** \remarks Removes the specified edge, and updates the cyclical information for this Graph object. \param pFrom [in] Pointer to the GraphNode at the start of the edge. \param pTo [in] Pointer to the GraphNode at the end of the edge. */ void breakCycleEdge( OdDbGraphNode* pFrom, OdDbGraphNode* pTo); protected: /** \details Removes all cyclical information determined by findCycles. \ewmarks This function does not remove cyclical edges, and is intended only for error cleanup. \sa breakCycleEdge */ void clearAllCycles(); private: OdDbGraph( const OdDbGraph&); OdDbGraph& operator =( const OdDbGraph&); void removeLeaves( OdDbGraphStack& stack); void setDirty() { m_bDirty = true; } bool isDirty() const { return m_bDirty; } bool m_bDirty; OdDbGraphNodeArray::size_type m_nNonCycleNodes; OdDbGraphNodeArray m_nodes; }; #include "TD_PackPop.h" #endif // _ODDBGRAPH_H_INCLUDED_