// File: NCollection_EBTree.hxx // Created: 30.07.02 09:51:33 // Author: Michael SAZONOV // Copyright: Open CASCADE 2002 #ifndef NCollection_EBTree_HeaderFile #define NCollection_EBTree_HeaderFile #include #include #include #include #include #include /** * The algorithm of unbalanced binary tree of overlapped bounding boxes with * the possibility of deleting objects from the tree. * * In addition to the requirements to the object type defined in the parent * class this class requires that the object can be hashed and compared to * another object (functions HashCode and IsEqual are defined for it), since * the class NCollection_DataMap is used where the object plays the role of * the key. */ template class NCollection_EBTree : public NCollection_UBTree { public: typedef NCollection_UBTree UBTree; typedef TYPENAME UBTree::TreeNode TreeNode; // ---------- PUBLIC METHODS ---------- /** * Constructor. */ NCollection_EBTree (const Handle(NCollection_BaseAllocator)& theAllocator=0L) : UBTree (theAllocator) {} /** * Extends the functionality of the parent method by maintaining * the map myObjNodeMap. Redefined virtual method * @return * False if the tree already contains theObj. */ Standard_EXPORT Standard_Boolean Add (const TheObjType& theObj, const TheBndType& theBnd); /** * Removes the given object and updates the tree. * @return * False if the tree does not contain theObj */ Standard_EXPORT Standard_Boolean Remove (const TheObjType& theObj); /** * @return * True if the tree contains the object. */ Standard_Boolean Contains (const TheObjType& theObj) const { return myObjNodeMap.IsBound (theObj); } /** * @return * The leaf node containing the object. */ const TreeNode& FindNode (const TheObjType& theObj) const { return *myObjNodeMap.Find (theObj); } /** * Clears the contents of the tree. Redefined virtual method */ void Clear (const Handle(NCollection_BaseAllocator)& aNewAlloc = 0L) { myObjNodeMap.Clear(); UBTree::Clear(aNewAlloc); } private: // ---------- PRIVATE METHODS ---------- /// Copy constructor (prohibited). NCollection_EBTree (const NCollection_EBTree&); /// Assignment operator (prohibited). NCollection_EBTree& operator = (const NCollection_EBTree&); // ---------- PRIVATE FIELDS ---------- NCollection_DataMap myObjNodeMap; ///< map of object to node pointer }; // ================== METHODS TEMPLATES ===================== //======================================================================= //function : Add //purpose : Updates the tree with a new object and its bounding box. // Returns false if the tree already contains theObj. //======================================================================= template Standard_Boolean NCollection_EBTree::Add (const TheObjType& theObj, const TheBndType& theBnd) { Standard_Boolean result = Standard_False; if (!Contains (theObj)) { // Add object in the tree using parent method UBTree::Add (theObj, theBnd); // Update the map TreeNode& aNewNode = ChangeLastNode(); myObjNodeMap.Bind (theObj, &aNewNode); // If the new node is not the root (has a parent) check the neighbour node if (!aNewNode.IsRoot()) { TreeNode& aNeiNode = aNewNode.ChangeParent().ChangeChild(0); if (aNeiNode.IsLeaf()) { myObjNodeMap.UnBind (aNeiNode.Object()); myObjNodeMap.Bind (aNeiNode.Object(), &aNeiNode); } } result = Standard_True; } return result; } //======================================================================= //function : Remove //purpose : Removes the given object and updates the tree. // Returns false if the tree does not contain theObj. //======================================================================= template Standard_Boolean NCollection_EBTree::Remove (const TheObjType& theObj) { Standard_Boolean result = Standard_False; if (Contains (theObj)) { TreeNode* pNode = myObjNodeMap (theObj); if (pNode->IsRoot()) { // it is the root, so clear all the tree Clear(); } else { // it is a child of some parent, // so kill the child that contains theObj // and update bounding boxes of all ancestors myObjNodeMap.UnBind (theObj); TreeNode* pParent = &pNode->ChangeParent(); pParent->Kill ((pNode == &pParent->Child(0) ? 0 : 1), this->Allocator()); if (pParent->IsLeaf()) { // the parent node became a leaf, so update the map myObjNodeMap.UnBind (pParent->Object()); myObjNodeMap.Bind (pParent->Object(), pParent); } while (!pParent->IsRoot()) { pParent = &pParent->ChangeParent(); pParent->ChangeBnd() = pParent->Child(0).Bnd(); pParent->ChangeBnd().Add (pParent->Child(1).Bnd()); } } result = Standard_True; } return result; } // ====================================================================== // Declaration of handled version of NCollection_EBTree. // In the macros below the arguments are: // _HEBTREE - the desired name of handled class // _OBJTYPE - the name of the object type // _BNDTYPE - the name of the bounding box type // _HUBTREE - the name of parent class // (defined using macro DEFINE_HUBTREE) #define DEFINE_HEBTREE(_HEBTREE, _OBJTYPE, _BNDTYPE, _HUBTREE) \ class _HEBTREE : public _HUBTREE \ { \ public: \ typedef NCollection_UBTree <_OBJTYPE, _BNDTYPE> UBTree; \ typedef NCollection_EBTree <_OBJTYPE, _BNDTYPE> EBTree; \ \ _HEBTREE () : _HUBTREE(new EBTree) {} \ /* Empty constructor */ \ \ /* Access to the methods of EBTree */ \ \ Standard_Boolean Remove (const _OBJTYPE& theObj) \ { return ChangeETree().Remove (theObj); } \ \ Standard_Boolean Contains (const _OBJTYPE& theObj) const \ { return ETree().Contains (theObj); } \ \ const UBTree::TreeNode& FindNode (const _OBJTYPE& theObj) const \ { return ETree().FindNode (theObj); } \ \ /* Access to the extended tree algorithm */ \ \ const EBTree& ETree () const { return (const EBTree&) Tree(); } \ EBTree& ChangeETree () { return (EBTree&) ChangeTree(); } \ \ DEFINE_STANDARD_RTTI (_HEBTREE) \ /* Type management */ \ }; \ DEFINE_STANDARD_HANDLE (_HEBTREE, _HUBTREE) #define IMPLEMENT_HEBTREE(_HEBTREE, _HUBTREE) \ IMPLEMENT_STANDARD_HANDLE (_HEBTREE, _HUBTREE) \ IMPLEMENT_STANDARD_RTTIEXT(_HEBTREE, _HUBTREE) #endif