0029151: GCC 7.1 warnings "this statement may fall through" [-Wimplicit-fallthrough=]
[occt.git] / src / NCollection / NCollection_UBTree.hxx
CommitLineData
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
63template <class TheObjType, class TheBndType> class NCollection_UBTree
64{
ddf2fe8e 65public:
66 //! Memory allocation
67 DEFINE_STANDARD_ALLOC
68 DEFINE_NCOLLECTION_ALLOC
69
70public:
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 {
129 public:
1c35b92f 130 DEFINE_STANDARD_ALLOC
131 DEFINE_NCOLLECTION_ALLOC
132
133 public:
7fd59977 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 /**
7fd59977 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
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 */
23be7421 270 virtual Standard_Integer Select (Selector& theSelector) const
7fd59977 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
353template <class TheObjType, class TheBndType>
354Standard_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
414template <class TheObjType, class TheBndType>
415Standard_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
25e59720 447 * _HPARENT - the name of parent class (usually Standard_Transient)
7fd59977 448 */
449#define DEFINE_HUBTREE(_HUBTREE, _OBJTYPE, _BNDTYPE, _HPARENT) \
450class _HUBTREE : public _HPARENT \
451{ \
452 public: \
453 typedef NCollection_UBTree <_OBJTYPE, _BNDTYPE> UBTree; \
454 \
455 _HUBTREE () : myTree(new UBTree) {} \
456 /* Empty constructor */ \
857ffd5e 457 _HUBTREE (const Handle(NCollection_BaseAllocator)& theAlloc) \
23be7421
M
458 : myTree(new UBTree(theAlloc)) {} \
459 /* Constructor */ \
7fd59977 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 \
92efcf78 485 DEFINE_STANDARD_RTTI_INLINE(_HUBTREE,_HPARENT) \
7fd59977 486 /* Type management */ \
487 \
82469411
A
488 private: \
489 /* Copying and assignment are prohibited */ \
490 _HUBTREE (UBTree*); \
491 _HUBTREE (const _HUBTREE&); \
492 void operator = (const _HUBTREE&); \
7fd59977 493 \
494 private: \
495 UBTree *myTree; /* pointer to the tree algorithm */ \
496}; \
497DEFINE_STANDARD_HANDLE (_HUBTREE, _HPARENT)
498
ec357c5c 499#define IMPLEMENT_HUBTREE(_HUBTREE, _HPARENT)
500
501
7fd59977 502
7fd59977 503#endif