| 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 | const 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 Standard_Transient) |
| 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_INLINE(_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 |