DbGraph.h

Go to the documentation of this file.

// Copyright (C) 2002-2017, 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-2017 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 "DbExport.h"
#include "RxObject.h"
#include "OdArray.h"
 
class OdDbGraph;
class OdDbGraphNode;
 
typedef OdArray<OdDbGraphNode*, OdMemoryAllocator<OdDbGraphNode*> > OdDbGraphNodeArray;
 
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.
  };
  
  void* data() const { return m_pData; }
 
  void setData(
    void* pData) { m_pData = pData; }
  
  int numOut() const { return m_outgoing.size(); }
  
  int numIn() const { return m_incoming.size(); } 
   
  OdDbGraphNode* in(
    int refIndex) const { return m_incoming.at(refIndex); }
 
  OdDbGraphNode* out(
    int refIndex) const { return m_outgoing.at(refIndex); }
  
  void addRefTo(
    OdDbGraphNode* pTo);
  
  void removeRefTo(
    OdDbGraphNode* pNode);
 
  void disconnectAll();
  
  OdDbGraph* owner() const { return m_pOwner; }
  
  bool isMarkedAs(
    OdUInt8 flags) const { return ((m_flags & flags)==flags); }
  
  void markAs(
    OdUInt8 flags)
  {
    if(!GETBIT(flags, kFirstLevel))
    {
      m_flags |= flags;
    }
    else
    {
      throw OdError(eInvalidInput);
    }
  }
 
  void clear(
    OdUInt8 flags)
  {
    if(!GETBIT(flags, kFirstLevel))
    {
      m_flags &= (~flags);
    }
    else
    {
      throw OdError(eInvalidInput);
    }
  }
 
    
  void markTree(
    OdUInt8 flags, 
    OdDbGraphNodeArray* pNodeArray = 0);
  
  // Circularity detection methods
  
  int numCycleOut() const { return m_cycleOut.size(); }
 
  int numCycleIn() const { return m_cycleIn.size(); }
  
  OdDbGraphNode* cycleIn(
    int refIndex) const { return m_cycleIn[refIndex]; }
 
  OdDbGraphNode* cycleOut(
    int refIndex) const  { return m_cycleOut[refIndex]; }
  
  OdDbGraphNode* nextCycleNode() const { return cycleOut(0); }
  
  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;
};
typedef OdSmartPtr<OdDbGraphNode> OdDbGraphNodePtr;
 
class OdDbGraphStack
{
public:
  OdDbGraphStack(
    int initPhysicalLength = 0, 
    int initGrowLength = 8)
    : m_stack(initPhysicalLength, initGrowLength) {}
 
  ~OdDbGraphStack() {}
 
  void push(
    OdDbGraphNode* pNode) { m_stack.push_back(pNode); }
 
  OdDbGraphNode* pop()
  {
    if(!isEmpty())
    {
      OdDbGraphNode* pRes = top();
      m_stack.removeLast();
      return pRes;
    }
    return 0;
  }
 
 
  OdDbGraphNode* top() const { return isEmpty() ? 0 : m_stack.last(); }
 
  bool isEmpty() const { return m_stack.empty(); }
private:
  OdDbGraphNodeArray  m_stack;
};
 
class TOOLKIT_EXPORT OdDbGraph
{
  friend class OdDbGraphNode;
public:
  OdDbGraph() : m_bDirty(false), m_nNonCycleNodes(0) {}
  virtual ~OdDbGraph();
  
  OdDbGraphNode* node(
    int nodeIndex) const { return m_nodes.at(nodeIndex); }
  
  OdDbGraphNode* rootNode() const;
  
  int numNodes() const { return m_nodes.size(); }
 
  bool isEmpty() const { return numNodes() == 0; }
  
    void addNode(
    OdDbGraphNode* pNode);
  
    void addEdge(
    OdDbGraphNode* pFrom, 
    OdDbGraphNode* pTo);
  
    void delNode(
    OdDbGraphNode* pNode);
  
  void reset();
 
  void clearAll(
    OdUInt8 flags);
  
  void getOutgoing(
    OdDbGraphNodeArray& outgoing);
  
  virtual bool findCycles(
    OdDbGraphNode* pStart = 0);
  void breakCycleEdge(
    OdDbGraphNode* pFrom, 
    OdDbGraphNode* pTo);
  
protected:
  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_