Commit | Line | Data |
---|---|---|
b311480e | 1 | // Created on: 2002-07-30 |
2 | // Created by: Michael SAZONOV | |
973c2be1 | 3 | // Copyright (c) 2002-2014 OPEN CASCADE SAS |
b311480e | 4 | // |
973c2be1 | 5 | // This file is part of Open CASCADE Technology software library. |
b311480e | 6 | // |
d5f74e42 | 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 | |
973c2be1 | 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. | |
b311480e | 12 | // |
973c2be1 | 13 | // Alternatively, this file may be used under the terms of Open CASCADE |
14 | // commercial license or contractual agreement. | |
7fd59977 | 15 | |
16 | #ifndef NCollection_UBTree_HeaderFile | |
17 | #define NCollection_UBTree_HeaderFile | |
18 | ||
19 | #include <NCollection_BaseAllocator.hxx> | |
1c35b92f | 20 | #include <NCollection_DefineAlloc.hxx> |
7fd59977 | 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 | { | |
ddf2fe8e | 65 | public: |
66 | //! Memory allocation | |
67 | DEFINE_STANDARD_ALLOC | |
68 | DEFINE_NCOLLECTION_ALLOC | |
69 | ||
70 | public: | |
7fd59977 | 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 | { | |
1c35b92f | 129 | public: |
130 | DEFINE_STANDARD_ALLOC | |
131 | DEFINE_NCOLLECTION_ALLOC | |
132 | ||
7fd59977 | 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 | ||
7fd59977 | 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, | |
1ede545f | 217 | const Handle(NCollection_BaseAllocator)& theAlloc) |
7fd59977 | 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 | ||
b6a0525b | 240 | /** |
241 | * Empty constructor. | |
242 | */ | |
243 | NCollection_UBTree() : myRoot(0L), myLastNode(0L), myAlloc (NCollection_BaseAllocator::CommonBaseAllocator()) {} | |
244 | ||
7fd59977 | 245 | /** |
246 | * Constructor. | |
247 | */ | |
b6a0525b | 248 | explicit NCollection_UBTree (const Handle(NCollection_BaseAllocator)& theAllocator) |
249 | : myRoot(0L), myLastNode(0L), myAlloc (!theAllocator.IsNull() ? theAllocator : NCollection_BaseAllocator::CommonBaseAllocator()) {} | |
7fd59977 | 250 | |
251 | /** | |
252 | * Update the tree with a new object and its bounding box. | |
253 | * @param theObj | |
254 | * added object | |
255 | * @param theBnd | |
256 | * bounding box of the object. | |
257 | * @return | |
258 | * always True | |
259 | */ | |
0f57ab75 | 260 | virtual Standard_Boolean Add (const TheObjType& theObj, const TheBndType& theBnd); |
7fd59977 | 261 | |
262 | /** | |
263 | * Searches in the tree all objects conforming to the given selector. | |
264 | * return | |
265 | * Number of objects accepted | |
266 | */ | |
23be7421 | 267 | virtual Standard_Integer Select (Selector& theSelector) const |
7fd59977 | 268 | { return (IsEmpty() ? 0 : Select (Root(), theSelector)); } |
269 | ||
270 | /** | |
271 | * Clears the contents of the tree. | |
272 | * @param aNewAlloc | |
273 | * Optional: a new allocator that will be used when the tree is rebuilt | |
274 | * anew. This makes sense if the memory allocator needs re-initialisation | |
275 | * (like NCollection_IncAllocator). By default the previous allocator is | |
276 | * kept. | |
277 | */ | |
278 | virtual void Clear (const Handle(NCollection_BaseAllocator)& aNewAlloc = 0L) | |
279 | // { if (myRoot) delete myRoot; myRoot = 0L; } | |
280 | { | |
281 | if (myRoot) { | |
282 | TreeNode::delNode (myRoot, this->myAlloc); | |
283 | this->myAlloc->Free (myRoot); | |
284 | myRoot = 0L; | |
285 | } | |
286 | if (aNewAlloc.IsNull() == Standard_False) | |
287 | myAlloc = aNewAlloc; | |
288 | } | |
289 | ||
290 | Standard_Boolean IsEmpty () const { return !myRoot; } | |
291 | ||
292 | /** | |
293 | * @return | |
294 | * the root node of the tree | |
295 | */ | |
296 | const TreeNode& Root () const { return *myRoot; } | |
297 | ||
298 | /** | |
299 | * Desctructor. | |
300 | */ | |
301 | virtual ~NCollection_UBTree () { Clear(); } | |
302 | ||
303 | /** | |
304 | * Recommended to be used only in sub-classes. | |
305 | * @return | |
306 | * Allocator object used in this instance of UBTree. | |
307 | */ | |
308 | const Handle(NCollection_BaseAllocator)& Allocator () const | |
309 | { return myAlloc; } | |
310 | ||
311 | protected: | |
312 | // ---------- PROTECTED METHODS ---------- | |
313 | ||
314 | /** | |
315 | * @return | |
316 | * the last added node | |
317 | */ | |
318 | TreeNode& ChangeLastNode () { return *myLastNode; } | |
319 | ||
320 | /** | |
321 | * Searches in the branch all objects conforming to the given selector. | |
322 | * @return | |
323 | * the number of objects accepted | |
324 | */ | |
0f57ab75 | 325 | Standard_Integer Select (const TreeNode& theBranch, Selector& theSelector) const; |
7fd59977 | 326 | |
327 | private: | |
328 | // ---------- PRIVATE METHODS ---------- | |
329 | ||
330 | /// Copy constructor (prohibited). | |
331 | NCollection_UBTree (const NCollection_UBTree&); | |
332 | ||
333 | /// Assignment operator (prohibited). | |
334 | NCollection_UBTree& operator = (const NCollection_UBTree&); | |
335 | ||
336 | // ---------- PRIVATE FIELDS ---------- | |
337 | ||
338 | TreeNode *myRoot; ///< root of the tree | |
339 | TreeNode *myLastNode;///< the last added node | |
340 | Handle(NCollection_BaseAllocator) myAlloc; ///< Allocator for TreeNode | |
341 | }; | |
342 | ||
343 | // ================== METHODS TEMPLATES ===================== | |
344 | //======================================================================= | |
345 | //function : Add | |
346 | //purpose : Updates the tree with a new object and its bounding box | |
347 | //======================================================================= | |
348 | ||
349 | template <class TheObjType, class TheBndType> | |
350 | Standard_Boolean NCollection_UBTree<TheObjType,TheBndType>::Add | |
351 | (const TheObjType& theObj, | |
352 | const TheBndType& theBnd) | |
353 | { | |
354 | if (IsEmpty()) { | |
355 | // Accepting first object | |
356 | myRoot = new (this->myAlloc) TreeNode (theObj, theBnd); | |
357 | myLastNode = myRoot; | |
358 | return Standard_True; | |
359 | } | |
360 | ||
361 | TreeNode *pBranch = myRoot; | |
362 | Standard_Boolean isOutOfBranch = pBranch->Bnd().IsOut (theBnd); | |
363 | ||
364 | for(;;) { | |
365 | // condition of stopping the search | |
366 | if (isOutOfBranch || pBranch->IsLeaf()) { | |
367 | TheBndType aNewBnd = theBnd; | |
368 | aNewBnd.Add (pBranch->Bnd()); | |
369 | // put the new leaf aside on the level of pBranch | |
370 | pBranch->Gemmate (aNewBnd, theObj, theBnd, this->myAlloc); | |
371 | myLastNode = &pBranch->ChangeChild(1); | |
372 | break; | |
373 | } | |
374 | ||
375 | // Update the bounding box of the branch | |
376 | pBranch->ChangeBnd().Add (theBnd); | |
377 | ||
378 | // Select the best child branch to accept the object: | |
379 | // 1. First check if one branch is out and another one is not. | |
380 | // 2. Else select the child having the least union with theBnd | |
381 | Standard_Integer iBest = 0; | |
382 | Standard_Boolean isOut[] = { pBranch->Child(0).Bnd().IsOut (theBnd), | |
383 | pBranch->Child(1).Bnd().IsOut (theBnd) }; | |
384 | if (isOut[0] != isOut[1]) | |
385 | iBest = (isOut[0] ? 1 : 0); | |
386 | else { | |
387 | TheBndType aUnion[] = { theBnd, theBnd }; | |
388 | aUnion[0].Add (pBranch->Child(0).Bnd()); | |
389 | aUnion[1].Add (pBranch->Child(1).Bnd()); | |
390 | const Standard_Real d1 = aUnion[0].SquareExtent(); | |
391 | const Standard_Real d2 = aUnion[1].SquareExtent(); | |
392 | if (d1 > d2) | |
393 | iBest = 1; | |
394 | } | |
395 | ||
396 | // Continue with the selected branch | |
397 | isOutOfBranch = isOut[iBest]; | |
398 | pBranch = &pBranch->ChangeChild(iBest); | |
399 | } | |
400 | return Standard_True; | |
401 | } | |
402 | ||
403 | //======================================================================= | |
404 | //function : Select | |
405 | //purpose : Recursively searches in the branch all objects conforming | |
406 | // to the given selector. | |
407 | // Returns the number of objects found. | |
408 | //======================================================================= | |
409 | ||
410 | template <class TheObjType, class TheBndType> | |
411 | Standard_Integer NCollection_UBTree<TheObjType,TheBndType>::Select | |
412 | (const TreeNode& theBranch, | |
413 | Selector& theSelector) const | |
414 | { | |
415 | // Try to reject the branch by bounding box | |
416 | if (theSelector.Reject (theBranch.Bnd())) | |
417 | return 0; | |
418 | ||
419 | Standard_Integer nSel = 0; | |
420 | ||
421 | if (theBranch.IsLeaf()) { | |
422 | // It is a leaf => try to accept the object | |
423 | if (theSelector.Accept (theBranch.Object())) | |
424 | nSel++; | |
425 | } | |
426 | else { | |
427 | // It is a branch => select from its children | |
428 | nSel += Select (theBranch.Child(0), theSelector); | |
429 | if (!theSelector.Stop()) | |
430 | nSel += Select (theBranch.Child(1), theSelector); | |
431 | } | |
432 | ||
433 | return nSel; | |
434 | } | |
435 | ||
436 | // ====================================================================== | |
437 | /** | |
438 | * Declaration of handled version of NCollection_UBTree. | |
439 | * In the macros below the arguments are: | |
440 | * _HUBTREE - the desired name of handled class | |
441 | * _OBJTYPE - the name of the object type | |
442 | * _BNDTYPE - the name of the bounding box type | |
25e59720 | 443 | * _HPARENT - the name of parent class (usually Standard_Transient) |
7fd59977 | 444 | */ |
445 | #define DEFINE_HUBTREE(_HUBTREE, _OBJTYPE, _BNDTYPE, _HPARENT) \ | |
446 | class _HUBTREE : public _HPARENT \ | |
447 | { \ | |
448 | public: \ | |
449 | typedef NCollection_UBTree <_OBJTYPE, _BNDTYPE> UBTree; \ | |
450 | \ | |
451 | _HUBTREE () : myTree(new UBTree) {} \ | |
452 | /* Empty constructor */ \ | |
857ffd5e | 453 | _HUBTREE (const Handle(NCollection_BaseAllocator)& theAlloc) \ |
23be7421 M |
454 | : myTree(new UBTree(theAlloc)) {} \ |
455 | /* Constructor */ \ | |
7fd59977 | 456 | \ |
457 | /* Access to the methods of UBTree */ \ | |
458 | \ | |
459 | Standard_Boolean Add (const _OBJTYPE& theObj, \ | |
460 | const _BNDTYPE& theBnd) \ | |
461 | { return ChangeTree().Add (theObj, theBnd); } \ | |
462 | \ | |
463 | Standard_Integer Select (UBTree::Selector& theSelector) const \ | |
464 | { return Tree().Select (theSelector); } \ | |
465 | \ | |
466 | void Clear () { ChangeTree().Clear (); } \ | |
467 | \ | |
468 | Standard_Boolean IsEmpty () const { return Tree().IsEmpty(); } \ | |
469 | \ | |
470 | const UBTree::TreeNode& Root () const { return Tree().Root(); } \ | |
471 | \ | |
472 | \ | |
473 | /* Access to the tree algorithm */ \ | |
474 | \ | |
475 | const UBTree& Tree () const { return *myTree; } \ | |
476 | UBTree& ChangeTree () { return *myTree; } \ | |
477 | \ | |
478 | ~_HUBTREE () { delete myTree; } \ | |
479 | /* Destructor */ \ | |
480 | \ | |
92efcf78 | 481 | DEFINE_STANDARD_RTTI_INLINE(_HUBTREE,_HPARENT) \ |
7fd59977 | 482 | /* Type management */ \ |
483 | \ | |
82469411 A |
484 | private: \ |
485 | /* Copying and assignment are prohibited */ \ | |
486 | _HUBTREE (UBTree*); \ | |
487 | _HUBTREE (const _HUBTREE&); \ | |
488 | void operator = (const _HUBTREE&); \ | |
7fd59977 | 489 | \ |
490 | private: \ | |
491 | UBTree *myTree; /* pointer to the tree algorithm */ \ | |
492 | }; \ | |
493 | DEFINE_STANDARD_HANDLE (_HUBTREE, _HPARENT) | |
494 | ||
ec357c5c | 495 | #define IMPLEMENT_HUBTREE(_HUBTREE, _HPARENT) |
496 | ||
497 | ||
7fd59977 | 498 | |
7fd59977 | 499 | #endif |