src/NCollection/NCollection_UBTree.hxx

   1 // File:      NCollection_UBTree.hxx
   2 // Created:   30.07.02 09:51:33
   3 // Author:    Michael SAZONOV
   4 // Copyright: Open CASCADE 2002
   5
   6 #ifndef NCollection_UBTree_HeaderFile
   7 #define NCollection_UBTree_HeaderFile
   8
   9 #include <NCollection_BaseAllocator.hxx>
  10
  11 #ifdef WNT
  12 // Disable the warning: "operator new unmatched by delete"
  13 #pragma warning (push)
  14 #pragma warning (disable:4291)
  15 #endif
  16
  17 /**
  18  * The algorithm of unbalanced binary tree of overlapped bounding boxes.
  19  *
  20  * Once the tree of boxes  of geometric objects is constructed, the algorithm
  21  * is capable of fast geometric selection of objects.  The tree can be easily
  22  * updated by adding to it a new object with bounding box.
  23  *
  24  * The time of adding to the tree  of one object is O(log(N)), where N is the
  25  * total number of  objects, so the time  of building a tree of  N objects is
  26  * O(N(log(N)). The search time of one object is O(log(N)).
  27  *
  28  * Defining  various classes  inheriting NCollection_UBTree::Selector  we can
  29  * perform various kinds of selection over the same b-tree object
  30  *
  31  * The object  may be of any  type allowing copying. Among  the best suitable
  32  * solutions there can  be a pointer to an object,  handled object or integer
  33  * index of object inside some  collection.  The bounding object may have any
  34  * dimension  and  geometry. The  minimal  interface  of TheBndType  (besides
  35  * public empty and copy constructor and operator =) used in UBTree algorithm
  36  * is as the following:
  37  * @code
  38  *   class MyBndType
  39  *   {
  40  *    public:
  41  *     inline void                   Add (const MyBndType& other);
  42  *     // Updates me with other bounding
  43  *
  44  *     inline Standard_Boolean       IsOut (const MyBndType& other) const;
  45  *     // Classifies other bounding relatively me
  46  *
  47  *     inline Standard_Real          SquareExtent() const;
  48  *     // Computes the squared maximal linear extent of me.
  49  *     // (For box it is the squared diagonal of box)
  50  *   };
  51  * @endcode
  52  * To select objects you need to define a class derived from UBTree::Selector
  53  * that  should  redefine  the  necessary  virtual methods  to  maintain  the
  54  * selection condition.  The object  of this class  is also used  to retrieve
  55  * selected objects after search.
  56  */
  57
  58 template <class TheObjType, class TheBndType> class NCollection_UBTree
  59 {
  60  public:
  61   // ---------- PUBLIC TYPES ----------
  62
  63   /**
  64    * Class defining the minimal interface of selector.
  65    */
  66   class Selector
  67   {
  68   public:
  69     /**
  70      * Constructor
  71      */
  72     Selector () : myStop(Standard_False) {}
  73
  74     /**
  75      * Rejection base on the bounding type.
  76      * @return
  77      *   True if the bounding box does not conform to some selection conditions
  78      */
  79     virtual Standard_Boolean Reject (const TheBndType&) const = 0;
  80
  81     /**
  82      * Confirm the object while making necessary tests on it. This method is
  83      * called when the bounding box of the object conforms to the conditions
  84      * (see Reject()). It is also supposed to keep record of accepted objects.
  85      * @return
  86      *   True if the object is accepted
  87      */
  88     virtual Standard_Boolean Accept (const TheObjType&) = 0;
  89
  90     /**
  91      * This condition is checked after each call to Accept().
  92      * @return
  93      *   True signals that the selection process is stopped
  94      */
  95     Standard_Boolean Stop () const { return myStop; }
  96
  97     /**
  98      * Destructor
  99      */
 100     virtual ~Selector () {}
 101
 102   protected:
 103     /**
 104      * The method Accept() should set this flag if the selection process
 105      * is to be stopped
 106      */
 107     Standard_Boolean myStop;
 108   };
 109
 110   /**
 111    * Class describing the node of the tree.
 112    * Initially the tree consists of one leaf. A node can grow to a branch
 113    * holding two childs:
 114    * - one correspondent to initial node
 115    * - the new one with a new object and bounding box
 116    */
 117   class TreeNode
 118   {
 119   public:
 120     TreeNode (const TheObjType& theObj, const TheBndType& theBnd)
 121       : myBnd(theBnd), myObject(theObj), myChildren(0), myParent(0) {}
 122
 123     Standard_Boolean       IsLeaf       () const { return !myChildren; }
 124     Standard_Boolean       IsRoot       () const { return !myParent; }
 125     const TheBndType&      Bnd          () const { return myBnd; }
 126     TheBndType&            ChangeBnd    ()       { return myBnd; }
 127     const TheObjType&      Object       () const { return myObject; }
 128     const TreeNode&        Child        (const Standard_Integer i) const
 129                                                  { return myChildren[i]; }
 130     TreeNode&              ChangeChild  (const Standard_Integer i)
 131                                                  { return myChildren[i]; }
 132     const TreeNode&        Parent       () const { return *myParent; }
 133     TreeNode&              ChangeParent ()       { return *myParent; }
 134
 135     /**
 136      * Forces *this node being gemmated such a way that it becomes
 137      * a branch holding the previous content of *this node at the
 138      * first child and theObj at the second child.
 139      * @param TheNewBnd
 140      *   new bounding box comprizing both child nodes.
 141      * @param theObj
 142      *   added object.
 143      * @param theBnd
 144      *   bounding box of theObj.
 145      * @theAlloc
 146      *   allocator providing memory to the new child nodes, provided by the
 147      *   calling Tree instance.
 148      */
 149     void Gemmate            (const TheBndType& theNewBnd,
 150                              const TheObjType& theObj,
 151                              const TheBndType& theBnd,
 152                              const Handle(NCollection_BaseAllocator)& theAlloc)
 153     {
 154       //TreeNode *children = new TreeNode [2];
 155       TreeNode *children = (TreeNode *) theAlloc->Allocate (2*sizeof(TreeNode));
 156       new (&children[0]) TreeNode;
 157       new (&children[1]) TreeNode;
 158       children[0] = *this;
 159       children[1].myObject = theObj;
 160       children[1].myBnd = theBnd;
 161       children[0].myParent = children[1].myParent = this;
 162       if (!IsLeaf()) {
 163         myChildren[0].myParent = children;
 164         myChildren[1].myParent = children;
 165       }
 166       myChildren = children;
 167       myBnd = theNewBnd;
 168       myObject = TheObjType();      // nullify myObject
 169     }
 170
 171     /**
 172      * Kills the i-th child, and *this accepts the content of another child
 173      */
 174     void Kill               (const Standard_Integer i,
 175                              const Handle(NCollection_BaseAllocator)& theAlloc)
 176     {
 177       if (!IsLeaf()) {
 178         TreeNode *oldChildren = myChildren;
 179         const Standard_Integer iopp = 1 - i;
 180         myBnd      = oldChildren[iopp].myBnd;
 181         myObject   = oldChildren[iopp].myObject;
 182         myChildren = oldChildren[iopp].myChildren;
 183         if (!IsLeaf()) {
 184           myChildren[0].myParent = this;
 185           myChildren[1].myParent = this;
 186         }
 187         // oldChildren[0].myChildren = oldChildren[1].myChildren = 0L;
 188         // delete [] oldChildren;
 189         oldChildren[iopp].~TreeNode();
 190         delNode(&oldChildren[i], theAlloc); // remove the whole branch
 191         theAlloc->Free(oldChildren);
 192       }
 193     }
 194
 195 //  ~TreeNode () { if (myChildren) delete [] myChildren; }
 196     ~TreeNode () { myChildren = 0L; }
 197
 198     /**
 199      * Allocator of a tree node.
 200      */
 201     void * operator new (size_t theSize,
 202                          const Handle(NCollection_BaseAllocator)& theAllocator)
 203     { return theAllocator->Allocate(theSize); }
 204
 205     /**
 206      * Allocator of a tree node.
 207      */
 208     void * operator new (size_t,
 209                          void * theMem)
 210     { return theMem; }
 211
 212     /**
 213      * Deleter of tree node. The whole hierarchy of its children also deleted.
 214      * This method should be used instead of operator delete.
 215      */
 216     static void delNode (TreeNode * theNode,
 217                          Handle(NCollection_BaseAllocator)& theAlloc)
 218     {
 219       if (theNode) {
 220         if (theNode -> myChildren) {
 221           delNode (&theNode -> myChildren[0], theAlloc);
 222           delNode (&theNode -> myChildren[1], theAlloc);
 223           theAlloc->Free(theNode -> myChildren);
 224         }
 225         theNode->~TreeNode();
 226       }
 227     }
 228
 229   private:
 230     TreeNode () : myChildren(0L), myParent(0L) {}
 231
 232     TheBndType  myBnd;          ///< bounding geometry
 233     TheObjType  myObject;       ///< the object
 234     TreeNode   *myChildren;     ///< 2 children forming a b-tree
 235     TreeNode   *myParent;       ///< the pointer to a parent node
 236   };
 237
 238   // ---------- PUBLIC METHODS ----------
 239
 240   /**
 241    * Constructor.
 242    */
 243   NCollection_UBTree
 244     (const Handle(NCollection_BaseAllocator)& theAllocator=0L)
 245       : myRoot(0L), myLastNode(0L)
 246   {
 247     if (theAllocator.IsNull())
 248       myAlloc = NCollection_BaseAllocator::CommonBaseAllocator();
 249     else
 250       myAlloc = theAllocator;
 251   }
 252
 253   /**
 254    * Update the tree with a new object and its bounding box.
 255    * @param theObj
 256    *   added object
 257    * @param theBnd
 258    *   bounding box of the object.
 259    * @return
 260    *   always True
 261    */
 262   Standard_EXPORT virtual Standard_Boolean Add (const TheObjType& theObj,
 263                                                 const TheBndType& theBnd);
 264
 265   /**
 266    * Searches in the tree all objects conforming to the given selector.
 267    * return
 268    *   Number of objects accepted
 269    */
 270   virtual Standard_Integer Select (Selector& theSelector) const
 271         { return (IsEmpty() ? 0 : Select (Root(), theSelector)); }
 272
 273   /**
 274    * Clears the contents of the tree.
 275    * @param aNewAlloc
 276    *   Optional:   a new allocator that will be used when the tree is rebuilt
 277    *   anew. This makes sense if the memory allocator needs re-initialisation
 278    *   (like NCollection_IncAllocator).  By default the previous allocator is
 279    *   kept.
 280    */
 281   virtual void Clear (const Handle(NCollection_BaseAllocator)& aNewAlloc = 0L)
 282 //      { if (myRoot) delete myRoot; myRoot = 0L; }
 283   {
 284     if (myRoot) {
 285       TreeNode::delNode (myRoot, this->myAlloc);
 286       this->myAlloc->Free (myRoot);
 287       myRoot = 0L;
 288     }
 289     if (aNewAlloc.IsNull() == Standard_False)
 290       myAlloc = aNewAlloc;
 291   }
 292
 293   Standard_Boolean IsEmpty () const { return !myRoot; }
 294
 295   /**
 296    * @return
 297    *   the root node of the tree
 298    */
 299   const TreeNode& Root () const { return *myRoot; }
 300
 301   /**
 302    * Desctructor.
 303    */
 304   virtual ~NCollection_UBTree () { Clear(); }
 305
 306   /**
 307    * Recommended to be used only in sub-classes.
 308    * @return
 309    *   Allocator object used in this instance of UBTree.
 310    */
 311   const Handle(NCollection_BaseAllocator)& Allocator () const
 312   { return myAlloc; }
 313
 314  protected:
 315   // ---------- PROTECTED METHODS ----------
 316
 317   /**
 318    * @return
 319    *   the last added node
 320    */
 321   TreeNode& ChangeLastNode () { return *myLastNode; }
 322
 323   /**
 324    * Searches in the branch all objects conforming to the given selector.
 325    * @return
 326    *   the number of objects accepted
 327    */
 328   Standard_EXPORT Standard_Integer Select (const TreeNode& theBranch,
 329                                            Selector& theSelector) const;
 330
 331  private:
 332   // ---------- PRIVATE METHODS ----------
 333
 334   /// Copy constructor (prohibited).
 335   NCollection_UBTree (const NCollection_UBTree&);
 336
 337   /// Assignment operator (prohibited).
 338   NCollection_UBTree& operator = (const NCollection_UBTree&);
 339
 340   // ---------- PRIVATE FIELDS ----------
 341
 342   TreeNode                            *myRoot;    ///< root of the tree
 343   TreeNode                            *myLastNode;///< the last added node
 344   Handle(NCollection_BaseAllocator)    myAlloc;   ///< Allocator for TreeNode
 345 };
 346
 347 // ================== METHODS TEMPLATES =====================
 348 //=======================================================================
 349 //function : Add
 350 //purpose  : Updates the tree with a new object and its bounding box
 351 //=======================================================================
 352
 353 template <class TheObjType, class TheBndType>
 354 Standard_Boolean NCollection_UBTree<TheObjType,TheBndType>::Add
 355                         (const TheObjType& theObj,
 356                          const TheBndType& theBnd)
 357 {
 358   if (IsEmpty()) {
 359     // Accepting first object
 360     myRoot = new (this->myAlloc) TreeNode (theObj, theBnd);
 361     myLastNode = myRoot;
 362     return Standard_True;
 363   }
 364
 365   TreeNode *pBranch = myRoot;
 366   Standard_Boolean isOutOfBranch = pBranch->Bnd().IsOut (theBnd);
 367
 368   for(;;) {
 369     // condition of stopping the search
 370     if (isOutOfBranch || pBranch->IsLeaf()) {
 371       TheBndType aNewBnd = theBnd;
 372       aNewBnd.Add (pBranch->Bnd());
 373       // put the new leaf aside on the level of pBranch
 374       pBranch->Gemmate (aNewBnd, theObj, theBnd, this->myAlloc);
 375       myLastNode = &pBranch->ChangeChild(1);
 376       break;
 377     }
 378
 379     // Update the bounding box of the branch
 380     pBranch->ChangeBnd().Add (theBnd);
 381
 382     // Select the best child branch to accept the object:
 383     // 1. First check if one branch is out and another one is not.
 384     // 2. Else select the child having the least union with theBnd
 385     Standard_Integer iBest = 0;
 386     Standard_Boolean isOut[] = { pBranch->Child(0).Bnd().IsOut (theBnd),
 387                                  pBranch->Child(1).Bnd().IsOut (theBnd) };
 388     if (isOut[0] != isOut[1])
 389       iBest = (isOut[0] ? 1 : 0);
 390     else {
 391       TheBndType aUnion[] = { theBnd, theBnd };
 392       aUnion[0].Add (pBranch->Child(0).Bnd());
 393       aUnion[1].Add (pBranch->Child(1).Bnd());
 394       const Standard_Real d1 = aUnion[0].SquareExtent();
 395       const Standard_Real d2 = aUnion[1].SquareExtent();
 396       if (d1 > d2)
 397         iBest = 1;
 398     }
 399
 400     // Continue with the selected branch
 401     isOutOfBranch = isOut[iBest];
 402     pBranch = &pBranch->ChangeChild(iBest);
 403   }
 404   return Standard_True;
 405 }
 406
 407 //=======================================================================
 408 //function : Select
 409 //purpose  : Recursively searches in the branch all objects conforming
 410 //           to the given selector.
 411 //           Returns the number of objects found.
 412 //=======================================================================
 413
 414 template <class TheObjType, class TheBndType>
 415 Standard_Integer NCollection_UBTree<TheObjType,TheBndType>::Select
 416                                  (const TreeNode& theBranch,
 417                                   Selector&       theSelector) const
 418 {
 419   // Try to reject the branch by bounding box
 420   if (theSelector.Reject (theBranch.Bnd()))
 421     return 0;
 422
 423   Standard_Integer nSel = 0;
 424
 425   if (theBranch.IsLeaf()) {
 426     // It is a leaf => try to accept the object
 427     if (theSelector.Accept (theBranch.Object()))
 428       nSel++;
 429   }
 430   else {
 431     // It is a branch => select from its children
 432     nSel += Select (theBranch.Child(0), theSelector);
 433     if (!theSelector.Stop())
 434       nSel += Select (theBranch.Child(1), theSelector);
 435   }
 436
 437   return nSel;
 438 }
 439
 440 // ======================================================================
 441 /**
 442  * Declaration of handled version of NCollection_UBTree.
 443  * In the macros below the arguments are:
 444  * _HUBTREE      - the desired name of handled class
 445  * _OBJTYPE      - the name of the object type
 446  * _BNDTYPE      - the name of the bounding box type
 447  * _HPARENT      - the name of parent class (usually MMgt_TShared)
 448  */
 449 #define DEFINE_HUBTREE(_HUBTREE, _OBJTYPE, _BNDTYPE, _HPARENT)          \
 450 class _HUBTREE : public _HPARENT                                        \
 451 {                                                                       \
 452  public:                                                                \
 453   typedef NCollection_UBTree <_OBJTYPE, _BNDTYPE> UBTree;               \
 454                                                                         \
 455   _HUBTREE () : myTree(new UBTree) {}                                   \
 456   /* Empty constructor */                                               \
 457   _HUBTREE (const Handle_NCollection_BaseAllocator& theAlloc)           \
 458      : myTree(new UBTree(theAlloc)) {}                                  \
 459   /* Constructor */                                                     \
 460                                                                         \
 461   /* Access to the methods of UBTree */                                 \
 462                                                                         \
 463   Standard_Boolean Add (const _OBJTYPE& theObj,                         \
 464                         const _BNDTYPE& theBnd)                         \
 465         { return ChangeTree().Add (theObj, theBnd); }                   \
 466                                                                         \
 467   Standard_Integer Select (UBTree::Selector& theSelector) const         \
 468         { return Tree().Select (theSelector); }                         \
 469                                                                         \
 470   void Clear () { ChangeTree().Clear (); }                              \
 471                                                                         \
 472   Standard_Boolean IsEmpty () const { return Tree().IsEmpty(); }        \
 473                                                                         \
 474   const UBTree::TreeNode& Root () const { return Tree().Root(); }       \
 475                                                                         \
 476                                                                         \
 477   /* Access to the tree algorithm */                                    \
 478                                                                         \
 479   const UBTree& Tree () const { return *myTree; }                       \
 480   UBTree&       ChangeTree () { return *myTree; }                       \
 481                                                                         \
 482   ~_HUBTREE () { delete myTree; }                                       \
 483   /* Destructor */                                                      \
 484                                                                         \
 485   DEFINE_STANDARD_RTTI (_HUBTREE)                                       \
 486   /* Type management */                                                 \
 487                                                                         \
 488  private:                                                               \
 489   /* Copying and assignment are prohibited  */                          \
 490   _HUBTREE (UBTree*);                                                   \
 491   _HUBTREE (const _HUBTREE&);                                           \
 492   void operator = (const _HUBTREE&);                                    \
 493                                                                         \
 494  private:                                                               \
 495   UBTree       *myTree;        /* pointer to the tree algorithm */      \
 496 };                                                                      \
 497 DEFINE_STANDARD_HANDLE (_HUBTREE, _HPARENT)
 498
 499 #define IMPLEMENT_HUBTREE(_HUBTREE, _HPARENT)                           \
 500 IMPLEMENT_STANDARD_HANDLE (_HUBTREE, _HPARENT)                          \
 501 IMPLEMENT_STANDARD_RTTIEXT(_HUBTREE, _HPARENT)
 502
 503 #ifdef WNT
 504 #pragma warning (pop)
 505 #endif
 506
 507 #endif