OCC22540 Regression: Exception during building of patch by GeomPlate
[occt.git] / src / NCollection / NCollection_UBTree.hxx
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
58 template <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    */
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)                                       \
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 IMPLEMENT_STANDARD_HANDLE (_HUBTREE, _HPARENT)                          \
501 IMPLEMENT_STANDARD_RTTIEXT(_HUBTREE, _HPARENT)
502
503 #ifdef WNT
504 #pragma warning (pop)
505 #endif
506
507 #endif