OCC22540 Regression: Exception during building of patch by GeomPlate
[occt.git] / src / NCollection / NCollection_UBTree.hxx
CommitLineData
7fd59977 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
58template <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 */
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
447 * _HPARENT - the name of parent class (usually MMgt_TShared)
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 */ \
23be7421
M
457 _HUBTREE (const Handle_NCollection_BaseAllocator& theAlloc) \
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 \
485 DEFINE_STANDARD_RTTI (_HUBTREE) \
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
499#define IMPLEMENT_HUBTREE(_HUBTREE, _HPARENT) \
500IMPLEMENT_STANDARD_HANDLE (_HUBTREE, _HPARENT) \
501IMPLEMENT_STANDARD_RTTIEXT(_HUBTREE, _HPARENT)
502
503#ifdef WNT
504#pragma warning (pop)
505#endif
506
507#endif