src/NCollection/NCollection_UBTree.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_UBTree_HeaderFile
  17 #define NCollection_UBTree_HeaderFile
  18
  19 #include <NCollection_BaseAllocator.hxx>
  20 #include <NCollection_DefineAlloc.hxx>
  21
  22 /**
  23  * The algorithm of unbalanced binary tree of overlapped bounding boxes.
  24  *
  25  * Once the tree of boxes  of geometric objects is constructed, the algorithm
  26  * is capable of fast geometric selection of objects.  The tree can be easily
  27  * updated by adding to it a new object with bounding box.
  28  *
  29  * The time of adding to the tree  of one object is O(log(N)), where N is the
  30  * total number of  objects, so the time  of building a tree of  N objects is
  31  * O(N(log(N)). The search time of one object is O(log(N)).
  32  *
  33  * Defining  various classes  inheriting NCollection_UBTree::Selector  we can
  34  * perform various kinds of selection over the same b-tree object
  35  *
  36  * The object  may be of any  type allowing copying. Among  the best suitable
  37  * solutions there can  be a pointer to an object,  handled object or integer
  38  * index of object inside some  collection.  The bounding object may have any
  39  * dimension  and  geometry. The  minimal  interface  of TheBndType  (besides
  40  * public empty and copy constructor and operator =) used in UBTree algorithm
  41  * is as the following:
  42  * @code
  43  *   class MyBndType
  44  *   {
  45  *    public:
  46  *     inline void                   Add (const MyBndType& other);
  47  *     // Updates me with other bounding
  48  *
  49  *     inline Standard_Boolean       IsOut (const MyBndType& other) const;
  50  *     // Classifies other bounding relatively me
  51  *
  52  *     inline Standard_Real          SquareExtent() const;
  53  *     // Computes the squared maximal linear extent of me.
  54  *     // (For box it is the squared diagonal of box)
  55  *   };
  56  * @endcode
  57  * To select objects you need to define a class derived from UBTree::Selector
  58  * that  should  redefine  the  necessary  virtual methods  to  maintain  the
  59  * selection condition.  The object  of this class  is also used  to retrieve
  60  * selected objects after search.
  61  */
  62
  63 template <class TheObjType, class TheBndType> class NCollection_UBTree
  64 {
  65 public:
  66   //! Memory allocation
  67   DEFINE_STANDARD_ALLOC
  68   DEFINE_NCOLLECTION_ALLOC
  69
  70 public:
  71   // ---------- PUBLIC TYPES ----------
  72
  73   /**
  74    * Class defining the minimal interface of selector.
  75    */
  76   class Selector
  77   {
  78   public:
  79     /**
  80      * Constructor
  81      */
  82     Selector () : myStop(Standard_False) {}
  83
  84     /**
  85      * Rejection base on the bounding type.
  86      * @return
  87      *   True if the bounding box does not conform to some selection conditions
  88      */
  89     virtual Standard_Boolean Reject (const TheBndType&) const = 0;
  90
  91     /**
  92      * Confirm the object while making necessary tests on it. This method is
  93      * called when the bounding box of the object conforms to the conditions
  94      * (see Reject()). It is also supposed to keep record of accepted objects.
  95      * @return
  96      *   True if the object is accepted
  97      */
  98     virtual Standard_Boolean Accept (const TheObjType&) = 0;
  99
 100     /**
 101      * This condition is checked after each call to Accept().
 102      * @return
 103      *   True signals that the selection process is stopped
 104      */
 105     Standard_Boolean Stop () const { return myStop; }
 106
 107     /**
 108      * Destructor
 109      */
 110     virtual ~Selector () {}
 111
 112   protected:
 113     /**
 114      * The method Accept() should set this flag if the selection process
 115      * is to be stopped
 116      */
 117     Standard_Boolean myStop;
 118   };
 119
 120   /**
 121    * Class describing the node of the tree.
 122    * Initially the tree consists of one leaf. A node can grow to a branch
 123    * holding two childs:
 124    * - one correspondent to initial node
 125    * - the new one with a new object and bounding box
 126    */
 127   class TreeNode
 128   {
 129   public:
 130     DEFINE_STANDARD_ALLOC
 131     DEFINE_NCOLLECTION_ALLOC
 132
 133   public:
 134     TreeNode (const TheObjType& theObj, const TheBndType& theBnd)
 135       : myBnd(theBnd), myObject(theObj), myChildren(0), myParent(0) {}
 136
 137     Standard_Boolean       IsLeaf       () const { return !myChildren; }
 138     Standard_Boolean       IsRoot       () const { return !myParent; }
 139     const TheBndType&      Bnd          () const { return myBnd; }
 140     TheBndType&            ChangeBnd    ()       { return myBnd; }
 141     const TheObjType&      Object       () const { return myObject; }
 142     const TreeNode&        Child        (const Standard_Integer i) const
 143                                                  { return myChildren[i]; }
 144     TreeNode&              ChangeChild  (const Standard_Integer i)
 145                                                  { return myChildren[i]; }
 146     const TreeNode&        Parent       () const { return *myParent; }
 147     TreeNode&              ChangeParent ()       { return *myParent; }
 148
 149     /**
 150      * Forces *this node being gemmated such a way that it becomes
 151      * a branch holding the previous content of *this node at the
 152      * first child and theObj at the second child.
 153      * @param TheNewBnd
 154      *   new bounding box comprizing both child nodes.
 155      * @param theObj
 156      *   added object.
 157      * @param theBnd
 158      *   bounding box of theObj.
 159      * @theAlloc
 160      *   allocator providing memory to the new child nodes, provided by the
 161      *   calling Tree instance.
 162      */
 163     void Gemmate            (const TheBndType& theNewBnd,
 164                              const TheObjType& theObj,
 165                              const TheBndType& theBnd,
 166                              const Handle(NCollection_BaseAllocator)& theAlloc)
 167     {
 168       //TreeNode *children = new TreeNode [2];
 169       TreeNode *children = (TreeNode *) theAlloc->Allocate (2*sizeof(TreeNode));
 170       new (&children[0]) TreeNode;
 171       new (&children[1]) TreeNode;
 172       children[0] = *this;
 173       children[1].myObject = theObj;
 174       children[1].myBnd = theBnd;
 175       children[0].myParent = children[1].myParent = this;
 176       if (!IsLeaf()) {
 177         myChildren[0].myParent = children;
 178         myChildren[1].myParent = children;
 179       }
 180       myChildren = children;
 181       myBnd = theNewBnd;
 182       myObject = TheObjType();      // nullify myObject
 183     }
 184
 185     /**
 186      * Kills the i-th child, and *this accepts the content of another child
 187      */
 188     void Kill               (const Standard_Integer i,
 189                              const Handle(NCollection_BaseAllocator)& theAlloc)
 190     {
 191       if (!IsLeaf()) {
 192         TreeNode *oldChildren = myChildren;
 193         const Standard_Integer iopp = 1 - i;
 194         myBnd      = oldChildren[iopp].myBnd;
 195         myObject   = oldChildren[iopp].myObject;
 196         myChildren = oldChildren[iopp].myChildren;
 197         if (!IsLeaf()) {
 198           myChildren[0].myParent = this;
 199           myChildren[1].myParent = this;
 200         }
 201         // oldChildren[0].myChildren = oldChildren[1].myChildren = 0L;
 202         // delete [] oldChildren;
 203         oldChildren[iopp].~TreeNode();
 204         delNode(&oldChildren[i], theAlloc); // remove the whole branch
 205         theAlloc->Free(oldChildren);
 206       }
 207     }
 208
 209 //  ~TreeNode () { if (myChildren) delete [] myChildren; }
 210     ~TreeNode () { myChildren = 0L; }
 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, _HPARENT)                                       \
 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
 501
 502
 503 #endif