include/opencascade/NCollection_EBTree.hxx

0001 // Created on: 2002-07-30
0002 // Created by: Michael SAZONOV
0003 // Copyright (c) 2002-2014 OPEN CASCADE SAS
0004 //
0005 // This file is part of Open CASCADE Technology software library.
0006 //
0007 // This library is free software; you can redistribute it and/or modify it under
0008 // the terms of the GNU Lesser General Public License version 2.1 as published
0009 // by the Free Software Foundation, with special exception defined in the file
0010 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
0011 // distribution for complete text of the license and disclaimer of any warranty.
0012 //
0013 // Alternatively, this file may be used under the terms of Open CASCADE
0014 // commercial license or contractual agreement.
0015
0016 #ifndef NCollection_EBTree_HeaderFile
0017 #define NCollection_EBTree_HeaderFile
0018
0019 #include <NCollection_UBTree.hxx>
0020 #include <Standard_Type.hxx>
0021 #include <Standard_Transient.hxx>
0022 #include <NCollection_List.hxx>
0023 #include <TColStd_SequenceOfInteger.hxx>
0024 #include <NCollection_DataMap.hxx>
0025
0026 /**
0027  * The algorithm of unbalanced binary  tree of overlapped bounding boxes with
0028  * the possibility of deleting objects from the tree.
0029  *
0030  * In addition to  the requirements to the object type  defined in the parent
0031  * class this  class requires that the  object can be hashed  and compared to
0032  * another object (functions HashCode and  IsEqual are defined for it), since
0033  * the class NCollection_DataMap  is used where the object  plays the role of
0034  * the key.
0035  */
0036 template <class TheObjType, class TheBndType> class NCollection_EBTree
0037   : public NCollection_UBTree <TheObjType, TheBndType>
0038 {
0039  public:
0040   typedef NCollection_UBTree <TheObjType, TheBndType> UBTree;
0041   typedef typename UBTree::TreeNode TreeNode;
0042   // ---------- PUBLIC METHODS ----------
0043
0044   /**
0045    * Constructor.
0046    */
0047   NCollection_EBTree (const Handle(NCollection_BaseAllocator)& theAllocator=0L)
0048     : UBTree (theAllocator) {}
0049
0050   /**
0051    * Updates the tree with a new object and its bounding box.
0052    * Extends the functionality of the parent method by maintaining
0053    * the map myObjNodeMap. Redefined virtual method.
0054    * @return
0055    *   False if the tree already contains theObj.
0056    */
0057   Standard_Boolean Add (const TheObjType& theObj, const TheBndType& theBnd) Standard_OVERRIDE
0058   {
0059     Standard_Boolean result = Standard_False;
0060     if (!Contains (theObj))
0061     {
0062       // Add object in the tree using parent method
0063       UBTree::Add (theObj, theBnd);
0064
0065       // Update the map
0066       TreeNode& aNewNode = this->ChangeLastNode ();
0067       myObjNodeMap.Bind (theObj, &aNewNode);
0068       // If the new node is not the root (has a parent) check the neighbour node
0069       if (!aNewNode.IsRoot ())
0070       {
0071         TreeNode& aNeiNode = aNewNode.ChangeParent ().ChangeChild (0);
0072         if (aNeiNode.IsLeaf ())
0073         {
0074           myObjNodeMap.UnBind (aNeiNode.Object ());
0075           myObjNodeMap.Bind (aNeiNode.Object (), &aNeiNode);
0076         }
0077       }
0078       result = Standard_True;
0079     }
0080     return result;
0081   }
0082
0083   /**
0084    * Removes the given object and updates the tree.
0085    * @return
0086    *   False if the tree does not contain theObj
0087    */
0088   Standard_Boolean Remove (const TheObjType& theObj);
0089
0090   /**
0091    * @return
0092    *   True if the tree contains the object.
0093    */
0094   Standard_Boolean Contains (const TheObjType& theObj) const
0095         { return myObjNodeMap.IsBound (theObj); }
0096
0097   /**
0098    * @return
0099    *   The leaf node containing the object.
0100    */
0101   const TreeNode& FindNode (const TheObjType& theObj) const
0102         { return *myObjNodeMap.Find (theObj); }
0103
0104   /**
0105    * Clears the contents of the tree. Redefined virtual method
0106    */
0107   void Clear (const Handle(NCollection_BaseAllocator)& aNewAlloc = 0L) Standard_OVERRIDE
0108   {
0109     myObjNodeMap.Clear ();
0110     UBTree::Clear (aNewAlloc);
0111   }
0112
0113  private:
0114   // ---------- PRIVATE METHODS ----------
0115
0116   /// Copy constructor (prohibited).
0117   NCollection_EBTree (const NCollection_EBTree&);
0118
0119   /// Assignment operator (prohibited).
0120   NCollection_EBTree& operator = (const NCollection_EBTree&);
0121
0122   // ---------- PRIVATE FIELDS ----------
0123
0124   NCollection_DataMap <TheObjType, TreeNode*>
0125                             myObjNodeMap;   ///< map of object to node pointer
0126 };
0127
0128 // ================== METHODS TEMPLATES =====================
0129
0130 //=======================================================================
0131 //function : Remove
0132 //purpose  : Removes the given object and updates the tree.
0133 //           Returns false if the tree does not contain theObj.
0134 //=======================================================================
0135
0136 template <class TheObjType, class TheBndType>
0137 Standard_Boolean NCollection_EBTree<TheObjType,TheBndType>::Remove
0138                                 (const TheObjType& theObj)
0139 {
0140   Standard_Boolean result = Standard_False;
0141   if (Contains (theObj)) {
0142     TreeNode* pNode = myObjNodeMap (theObj);
0143     if (pNode->IsRoot()) {
0144       // it is the root, so clear all the tree
0145       Clear();
0146     }
0147     else {
0148       // it is a child of some parent,
0149       // so kill the child that contains theObj
0150       // and update bounding boxes of all ancestors
0151       myObjNodeMap.UnBind (theObj);
0152       TreeNode* pParent = &pNode->ChangeParent();
0153       pParent->Kill ((pNode == &pParent->Child(0) ? 0 : 1),
0154                      this->Allocator());
0155       if (pParent->IsLeaf()) {
0156         // the parent node became a leaf, so update the map
0157         myObjNodeMap.UnBind (pParent->Object());
0158         myObjNodeMap.Bind (pParent->Object(), pParent);
0159       }
0160       while (!pParent->IsRoot()) {
0161         pParent = &pParent->ChangeParent();
0162         pParent->ChangeBnd() = pParent->Child(0).Bnd();
0163         pParent->ChangeBnd().Add (pParent->Child(1).Bnd());
0164       }
0165     }
0166     result = Standard_True;
0167   }
0168   return result;
0169 }
0170
0171 // ======================================================================
0172 // Declaration of handled version of NCollection_EBTree.
0173 // In the macros below the arguments are:
0174 // _HEBTREE      - the desired name of handled class
0175 // _OBJTYPE      - the name of the object type
0176 // _BNDTYPE      - the name of the bounding box type
0177 // _HUBTREE      - the name of parent class
0178 //                 (defined using macro DEFINE_HUBTREE)
0179
0180 #define DEFINE_HEBTREE(_HEBTREE, _OBJTYPE, _BNDTYPE, _HUBTREE)          \
0181 class _HEBTREE : public _HUBTREE                                        \
0182 {                                                                       \
0183  public:                                                                \
0184   typedef NCollection_UBTree <_OBJTYPE, _BNDTYPE> UBTree;               \
0185   typedef NCollection_EBTree <_OBJTYPE, _BNDTYPE> EBTree;               \
0186                                                                         \
0187   _HEBTREE () : _HUBTREE(new EBTree) {}                                 \
0188   /* Empty constructor */                                               \
0189                                                                         \
0190   /* Access to the methods of EBTree */                                 \
0191                                                                         \
0192   Standard_Boolean Remove (const _OBJTYPE& theObj)                      \
0193         { return ChangeETree().Remove (theObj); }                       \
0194                                                                         \
0195   Standard_Boolean Contains (const _OBJTYPE& theObj) const              \
0196         { return ETree().Contains (theObj); }                           \
0197                                                                         \
0198   const UBTree::TreeNode& FindNode (const _OBJTYPE& theObj) const       \
0199         { return ETree().FindNode (theObj); }                           \
0200                                                                         \
0201   /* Access to the extended tree algorithm */                           \
0202                                                                         \
0203   const EBTree& ETree () const { return (const EBTree&) Tree(); }       \
0204   EBTree&       ChangeETree () { return (EBTree&) ChangeTree(); }       \
0205                                                                         \
0206   DEFINE_STANDARD_RTTI_INLINE(_HEBTREE,_HUBTREE)                                       \
0207   /* Type management */                                                 \
0208 };                                                                      \
0209 DEFINE_STANDARD_HANDLE (_HEBTREE, _HUBTREE)
0210
0211 #define IMPLEMENT_HEBTREE(_HEBTREE, _HUBTREE)
0212
0213
0214
0215 #endif