src/NCollection/NCollection_EBTree.hxx

   1 // Created on: 2002-07-30
   2 // Created by: Michael SAZONOV
   3 // Copyright (c) 2002-2014 OPEN CASCADE SAS
   4 //
   5 // This file is part of Open CASCADE Technology software library.
   6 //
   7 // This library is free software; you can redistribute it and/or modify it under
   8 // the terms of the GNU Lesser General Public License version 2.1 as published
   9 // by the Free Software Foundation, with special exception defined in the file
  10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  11 // distribution for complete text of the license and disclaimer of any warranty.
  12 //
  13 // Alternatively, this file may be used under the terms of Open CASCADE
  14 // commercial license or contractual agreement.
  15
  16 #ifndef NCollection_EBTree_HeaderFile
  17 #define NCollection_EBTree_HeaderFile
  18
  19 #include <NCollection_UBTree.hxx>
  20 #include <Standard_DefineHandle.hxx>
  21 #include <MMgt_TShared.hxx>
  22 #include <NCollection_List.hxx>
  23 #include <TColStd_SequenceOfInteger.hxx>
  24 #include <NCollection_DataMap.hxx>
  25
  26 /**
  27  * The algorithm of unbalanced binary  tree of overlapped bounding boxes with
  28  * the possibility of deleting objects from the tree.
  29  *
  30  * In addition to  the requirements to the object type  defined in the parent
  31  * class this  class requires that the  object can be hashed  and compared to
  32  * another object (functions HashCode and  IsEqual are defined for it), since
  33  * the class NCollection_DataMap  is used where the object  plays the role of
  34  * the key.
  35  */
  36 template <class TheObjType, class TheBndType> class NCollection_EBTree
  37   : public NCollection_UBTree <TheObjType, TheBndType>
  38 {
  39  public:
  40   typedef NCollection_UBTree <TheObjType, TheBndType> UBTree;
  41   typedef TYPENAME UBTree::TreeNode TreeNode;
  42   // ---------- PUBLIC METHODS ----------
  43
  44   /**
  45    * Constructor.
  46    */
  47   NCollection_EBTree (const Handle(NCollection_BaseAllocator)& theAllocator=0L)
  48     : UBTree (theAllocator) {}
  49
  50   /**
  51    * Extends the functionality of the parent method by maintaining
  52    * the map myObjNodeMap. Redefined virtual method
  53    * @return
  54    *   False if the tree already contains theObj.
  55    */
  56   Standard_EXPORT Standard_Boolean Add    (const TheObjType& theObj,
  57                                            const TheBndType& theBnd);
  58
  59   /**
  60    * Removes the given object and updates the tree.
  61    * @return
  62    *   False if the tree does not contain theObj
  63    */
  64   Standard_EXPORT Standard_Boolean Remove (const TheObjType& theObj);
  65
  66   /**
  67    * @return
  68    *   True if the tree contains the object.
  69    */
  70   Standard_Boolean Contains (const TheObjType& theObj) const
  71         { return myObjNodeMap.IsBound (theObj); }
  72
  73   /**
  74    * @return
  75    *   The leaf node containing the object.
  76    */
  77   const TreeNode& FindNode (const TheObjType& theObj) const
  78         { return *myObjNodeMap.Find (theObj); }
  79
  80   /**
  81    * Clears the contents of the tree. Redefined virtual method
  82    */
  83   void Clear (const Handle(NCollection_BaseAllocator)& aNewAlloc = 0L)
  84         { myObjNodeMap.Clear(); UBTree::Clear(aNewAlloc); }
  85
  86  private:
  87   // ---------- PRIVATE METHODS ----------
  88
  89   /// Copy constructor (prohibited).
  90   NCollection_EBTree (const NCollection_EBTree&);
  91
  92   /// Assignment operator (prohibited).
  93   NCollection_EBTree& operator = (const NCollection_EBTree&);
  94
  95   // ---------- PRIVATE FIELDS ----------
  96
  97   NCollection_DataMap <TheObjType, TreeNode*>
  98                             myObjNodeMap;   ///< map of object to node pointer
  99 };
 100
 101 // ================== METHODS TEMPLATES =====================
 102
 103 //=======================================================================
 104 //function : Add
 105 //purpose  : Updates the tree with a new object and its bounding box.
 106 //           Returns false if the tree already contains theObj.
 107 //=======================================================================
 108
 109 template <class TheObjType, class TheBndType>
 110 Standard_Boolean NCollection_EBTree<TheObjType,TheBndType>::Add
 111                         (const TheObjType& theObj,
 112                          const TheBndType& theBnd)
 113 {
 114   Standard_Boolean result = Standard_False;
 115   if (!Contains (theObj)) {
 116     // Add object in the tree using parent method
 117     UBTree::Add (theObj, theBnd);
 118
 119     // Update the map
 120     TreeNode& aNewNode = ChangeLastNode();
 121     myObjNodeMap.Bind (theObj, &aNewNode);
 122     // If the new node is not the root (has a parent) check the neighbour node
 123     if (!aNewNode.IsRoot()) {
 124       TreeNode& aNeiNode = aNewNode.ChangeParent().ChangeChild(0);
 125       if (aNeiNode.IsLeaf()) {
 126         myObjNodeMap.UnBind (aNeiNode.Object());
 127         myObjNodeMap.Bind (aNeiNode.Object(), &aNeiNode);
 128       }
 129     }
 130     result = Standard_True;
 131   }
 132   return result;
 133 }
 134
 135 //=======================================================================
 136 //function : Remove
 137 //purpose  : Removes the given object and updates the tree.
 138 //           Returns false if the tree does not contain theObj.
 139 //=======================================================================
 140
 141 template <class TheObjType, class TheBndType>
 142 Standard_Boolean NCollection_EBTree<TheObjType,TheBndType>::Remove
 143                                 (const TheObjType& theObj)
 144 {
 145   Standard_Boolean result = Standard_False;
 146   if (Contains (theObj)) {
 147     TreeNode* pNode = myObjNodeMap (theObj);
 148     if (pNode->IsRoot()) {
 149       // it is the root, so clear all the tree
 150       Clear();
 151     }
 152     else {
 153       // it is a child of some parent,
 154       // so kill the child that contains theObj
 155       // and update bounding boxes of all ancestors
 156       myObjNodeMap.UnBind (theObj);
 157       TreeNode* pParent = &pNode->ChangeParent();
 158       pParent->Kill ((pNode == &pParent->Child(0) ? 0 : 1),
 159                      this->Allocator());
 160       if (pParent->IsLeaf()) {
 161         // the parent node became a leaf, so update the map
 162         myObjNodeMap.UnBind (pParent->Object());
 163         myObjNodeMap.Bind (pParent->Object(), pParent);
 164       }
 165       while (!pParent->IsRoot()) {
 166         pParent = &pParent->ChangeParent();
 167         pParent->ChangeBnd() = pParent->Child(0).Bnd();
 168         pParent->ChangeBnd().Add (pParent->Child(1).Bnd());
 169       }
 170     }
 171     result = Standard_True;
 172   }
 173   return result;
 174 }
 175
 176 // ======================================================================
 177 // Declaration of handled version of NCollection_EBTree.
 178 // In the macros below the arguments are:
 179 // _HEBTREE      - the desired name of handled class
 180 // _OBJTYPE      - the name of the object type
 181 // _BNDTYPE      - the name of the bounding box type
 182 // _HUBTREE      - the name of parent class
 183 //                 (defined using macro DEFINE_HUBTREE)
 184
 185 #define DEFINE_HEBTREE(_HEBTREE, _OBJTYPE, _BNDTYPE, _HUBTREE)          \
 186 class _HEBTREE : public _HUBTREE                                        \
 187 {                                                                       \
 188  public:                                                                \
 189   typedef NCollection_UBTree <_OBJTYPE, _BNDTYPE> UBTree;               \
 190   typedef NCollection_EBTree <_OBJTYPE, _BNDTYPE> EBTree;               \
 191                                                                         \
 192   _HEBTREE () : _HUBTREE(new EBTree) {}                                 \
 193   /* Empty constructor */                                               \
 194                                                                         \
 195   /* Access to the methods of EBTree */                                 \
 196                                                                         \
 197   Standard_Boolean Remove (const _OBJTYPE& theObj)                      \
 198         { return ChangeETree().Remove (theObj); }                       \
 199                                                                         \
 200   Standard_Boolean Contains (const _OBJTYPE& theObj) const              \
 201         { return ETree().Contains (theObj); }                           \
 202                                                                         \
 203   const UBTree::TreeNode& FindNode (const _OBJTYPE& theObj) const       \
 204         { return ETree().FindNode (theObj); }                           \
 205                                                                         \
 206   /* Access to the extended tree algorithm */                           \
 207                                                                         \
 208   const EBTree& ETree () const { return (const EBTree&) Tree(); }       \
 209   EBTree&       ChangeETree () { return (EBTree&) ChangeTree(); }       \
 210                                                                         \
 211   DEFINE_STANDARD_RTTI (_HEBTREE)                                       \
 212   /* Type management */                                                 \
 213 };                                                                      \
 214 DEFINE_STANDARD_HANDLE (_HEBTREE, _HUBTREE)
 215
 216 #define IMPLEMENT_HEBTREE(_HEBTREE, _HUBTREE)                           \
 217 IMPLEMENT_STANDARD_HANDLE (_HEBTREE, _HUBTREE)                          \
 218 IMPLEMENT_STANDARD_RTTIEXT(_HEBTREE, _HUBTREE)
 219
 220 #endif