0022815: Missing delete operator for placement new
[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 #include <NCollection_DefineAlloc.hxx>
11
12 /**
13  * The algorithm of unbalanced binary tree of overlapped bounding boxes.
14  *
15  * Once the tree of boxes  of geometric objects is constructed, the algorithm
16  * is capable of fast geometric selection of objects.  The tree can be easily
17  * updated by adding to it a new object with bounding box.
18  * 
19  * The time of adding to the tree  of one object is O(log(N)), where N is the
20  * total number of  objects, so the time  of building a tree of  N objects is
21  * O(N(log(N)). The search time of one object is O(log(N)).
22  * 
23  * Defining  various classes  inheriting NCollection_UBTree::Selector  we can
24  * perform various kinds of selection over the same b-tree object
25  * 
26  * The object  may be of any  type allowing copying. Among  the best suitable
27  * solutions there can  be a pointer to an object,  handled object or integer
28  * index of object inside some  collection.  The bounding object may have any
29  * dimension  and  geometry. The  minimal  interface  of TheBndType  (besides
30  * public empty and copy constructor and operator =) used in UBTree algorithm
31  * is as the following:
32  * @code
33  *   class MyBndType
34  *   {
35  *    public:
36  *     inline void                   Add (const MyBndType& other);
37  *     // Updates me with other bounding
38  * 
39  *     inline Standard_Boolean       IsOut (const MyBndType& other) const;
40  *     // Classifies other bounding relatively me
41  * 
42  *     inline Standard_Real          SquareExtent() const;
43  *     // Computes the squared maximal linear extent of me.
44  *     // (For box it is the squared diagonal of box)
45  *   };
46  * @endcode
47  * To select objects you need to define a class derived from UBTree::Selector
48  * that  should  redefine  the  necessary  virtual methods  to  maintain  the
49  * selection condition.  The object  of this class  is also used  to retrieve
50  * selected objects after search.
51  */
52
53 template <class TheObjType, class TheBndType> class NCollection_UBTree
54 {
55  public:
56   // ---------- PUBLIC TYPES ----------
57
58   /**
59    * Class defining the minimal interface of selector.
60    */
61   class Selector
62   {
63   public:
64     /**
65      * Constructor
66      */
67     Selector () : myStop(Standard_False) {}
68
69     /**
70      * Rejection base on the bounding type.
71      * @return
72      *   True if the bounding box does not conform to some selection conditions
73      */
74     virtual Standard_Boolean Reject (const TheBndType&) const = 0;
75
76     /**
77      * Confirm the object while making necessary tests on it. This method is
78      * called when the bounding box of the object conforms to the conditions
79      * (see Reject()). It is also supposed to keep record of accepted objects.
80      * @return
81      *   True if the object is accepted
82      */
83     virtual Standard_Boolean Accept (const TheObjType&) = 0;
84
85     /**
86      * This condition is checked after each call to Accept().
87      * @return
88      *   True signals that the selection process is stopped
89      */
90     Standard_Boolean Stop () const { return myStop; }
91
92     /**
93      * Destructor
94      */
95     virtual ~Selector () {}
96
97   protected:
98     /**
99      * The method Accept() should set this flag if the selection process
100      * is to be stopped
101      */
102     Standard_Boolean myStop;
103   };
104
105   /**
106    * Class describing the node of the tree.
107    * Initially the tree consists of one leaf. A node can grow to a branch
108    * holding two childs:
109    * - one correspondent to initial node
110    * - the new one with a new object and bounding box
111    */
112   class TreeNode
113   {
114   public:
115     DEFINE_STANDARD_ALLOC
116     DEFINE_NCOLLECTION_ALLOC
117
118   public:
119     TreeNode (const TheObjType& theObj, const TheBndType& theBnd)
120       : myBnd(theBnd), myObject(theObj), myChildren(0), myParent(0) {}
121
122     Standard_Boolean       IsLeaf       () const { return !myChildren; }
123     Standard_Boolean       IsRoot       () const { return !myParent; }
124     const TheBndType&      Bnd          () const { return myBnd; }
125     TheBndType&            ChangeBnd    ()       { return myBnd; }
126     const TheObjType&      Object       () const { return myObject; }
127     const TreeNode&        Child        (const Standard_Integer i) const
128                                                  { return myChildren[i]; }
129     TreeNode&              ChangeChild  (const Standard_Integer i)
130                                                  { return myChildren[i]; }
131     const TreeNode&        Parent       () const { return *myParent; }
132     TreeNode&              ChangeParent ()       { return *myParent; }
133
134     /**
135      * Forces *this node being gemmated such a way that it becomes
136      * a branch holding the previous content of *this node at the 
137      * first child and theObj at the second child.
138      * @param TheNewBnd
139      *   new bounding box comprizing both child nodes.
140      * @param theObj
141      *   added object.
142      * @param theBnd
143      *   bounding box of theObj.
144      * @theAlloc
145      *   allocator providing memory to the new child nodes, provided by the
146      *   calling Tree instance.
147      */
148     void Gemmate            (const TheBndType& theNewBnd,
149                              const TheObjType& theObj,
150                              const TheBndType& theBnd,
151                              const Handle(NCollection_BaseAllocator)& theAlloc)
152     {
153       //TreeNode *children = new TreeNode [2];
154       TreeNode *children = (TreeNode *) theAlloc->Allocate (2*sizeof(TreeNode));
155       new (&children[0]) TreeNode;
156       new (&children[1]) TreeNode;
157       children[0] = *this;
158       children[1].myObject = theObj;
159       children[1].myBnd = theBnd;
160       children[0].myParent = children[1].myParent = this;
161       if (!IsLeaf()) {
162         myChildren[0].myParent = children;
163         myChildren[1].myParent = children;
164       }
165       myChildren = children;
166       myBnd = theNewBnd;
167       myObject = TheObjType();      // nullify myObject
168     }
169
170     /**
171      * Kills the i-th child, and *this accepts the content of another child
172      */
173     void Kill               (const Standard_Integer i,
174                              const Handle(NCollection_BaseAllocator)& theAlloc)
175     {
176       if (!IsLeaf()) {
177         TreeNode *oldChildren = myChildren;
178         const Standard_Integer iopp = 1 - i;
179         myBnd      = oldChildren[iopp].myBnd;
180         myObject   = oldChildren[iopp].myObject;
181         myChildren = oldChildren[iopp].myChildren;
182         if (!IsLeaf()) {
183           myChildren[0].myParent = this;
184           myChildren[1].myParent = this;
185         }
186         // oldChildren[0].myChildren = oldChildren[1].myChildren = 0L;
187         // delete [] oldChildren;
188         oldChildren[iopp].~TreeNode();
189         delNode(&oldChildren[i], theAlloc); // remove the whole branch
190         theAlloc->Free(oldChildren);
191       }
192     }
193
194 //  ~TreeNode () { if (myChildren) delete [] myChildren; }
195     ~TreeNode () { myChildren = 0L; }
196
197     /**
198      * Deleter of tree node. The whole hierarchy of its children also deleted.
199      * This method should be used instead of operator delete.
200      */ 
201     static void delNode (TreeNode * theNode,
202                          Handle(NCollection_BaseAllocator)& theAlloc)
203     {
204       if (theNode) {
205         if (theNode -> myChildren) {
206           delNode (&theNode -> myChildren[0], theAlloc);
207           delNode (&theNode -> myChildren[1], theAlloc);
208           theAlloc->Free(theNode -> myChildren);
209         }
210         theNode->~TreeNode();
211       }
212     }
213
214   private:
215     TreeNode () : myChildren(0L), myParent(0L) {}
216
217     TheBndType  myBnd;          ///< bounding geometry
218     TheObjType  myObject;       ///< the object
219     TreeNode   *myChildren;     ///< 2 children forming a b-tree
220     TreeNode   *myParent;       ///< the pointer to a parent node
221   };
222
223   // ---------- PUBLIC METHODS ----------
224
225   /**
226    * Constructor.
227    */
228   NCollection_UBTree
229     (const Handle(NCollection_BaseAllocator)& theAllocator=0L)
230       : myRoot(0L), myLastNode(0L)
231   {
232     if (theAllocator.IsNull())
233       myAlloc = NCollection_BaseAllocator::CommonBaseAllocator();
234     else
235       myAlloc = theAllocator;
236   }
237
238   /**
239    * Update the tree with a new object and its bounding box.
240    * @param theObj
241    *   added object
242    * @param theBnd
243    *   bounding box of the object.
244    * @return
245    *   always True
246    */
247   Standard_EXPORT virtual Standard_Boolean Add (const TheObjType& theObj,
248                                                 const TheBndType& theBnd);
249
250   /**
251    * Searches in the tree all objects conforming to the given selector.
252    * return
253    *   Number of objects accepted
254    */
255   virtual Standard_Integer Select (Selector& theSelector) const
256         { return (IsEmpty() ? 0 : Select (Root(), theSelector)); }
257
258   /**
259    * Clears the contents of the tree.
260    * @param aNewAlloc
261    *   Optional:   a new allocator that will be used when the tree is rebuilt
262    *   anew. This makes sense if the memory allocator needs re-initialisation
263    *   (like NCollection_IncAllocator).  By default the previous allocator is
264    *   kept.
265    */
266   virtual void Clear (const Handle(NCollection_BaseAllocator)& aNewAlloc = 0L)
267 //      { if (myRoot) delete myRoot; myRoot = 0L; }
268   {
269     if (myRoot) {
270       TreeNode::delNode (myRoot, this->myAlloc);
271       this->myAlloc->Free (myRoot);
272       myRoot = 0L;
273     }
274     if (aNewAlloc.IsNull() == Standard_False)
275       myAlloc = aNewAlloc;
276   }
277
278   Standard_Boolean IsEmpty () const { return !myRoot; }
279
280   /**
281    * @return
282    *   the root node of the tree
283    */
284   const TreeNode& Root () const { return *myRoot; }
285
286   /**
287    * Desctructor.
288    */
289   virtual ~NCollection_UBTree () { Clear(); }
290
291   /**
292    * Recommended to be used only in sub-classes.
293    * @return
294    *   Allocator object used in this instance of UBTree.
295    */
296   const Handle(NCollection_BaseAllocator)& Allocator () const
297   { return myAlloc; }
298
299  protected:
300   // ---------- PROTECTED METHODS ----------
301
302   /**
303    * @return
304    *   the last added node
305    */
306   TreeNode& ChangeLastNode () { return *myLastNode; }
307
308   /**
309    * Searches in the branch all objects conforming to the given selector.
310    * @return
311    *   the number of objects accepted
312    */
313   Standard_EXPORT Standard_Integer Select (const TreeNode& theBranch,
314                                            Selector& theSelector) const;
315
316  private:
317   // ---------- PRIVATE METHODS ----------
318
319   /// Copy constructor (prohibited).
320   NCollection_UBTree (const NCollection_UBTree&);
321
322   /// Assignment operator (prohibited).
323   NCollection_UBTree& operator = (const NCollection_UBTree&);
324
325   // ---------- PRIVATE FIELDS ----------
326
327   TreeNode                            *myRoot;    ///< root of the tree
328   TreeNode                            *myLastNode;///< the last added node
329   Handle(NCollection_BaseAllocator)    myAlloc;   ///< Allocator for TreeNode
330 };
331
332 // ================== METHODS TEMPLATES =====================
333 //=======================================================================
334 //function : Add
335 //purpose  : Updates the tree with a new object and its bounding box
336 //=======================================================================
337
338 template <class TheObjType, class TheBndType>
339 Standard_Boolean NCollection_UBTree<TheObjType,TheBndType>::Add
340                         (const TheObjType& theObj,
341                          const TheBndType& theBnd)
342 {
343   if (IsEmpty()) {
344     // Accepting first object
345     myRoot = new (this->myAlloc) TreeNode (theObj, theBnd);
346     myLastNode = myRoot;
347     return Standard_True;
348   }
349
350   TreeNode *pBranch = myRoot;
351   Standard_Boolean isOutOfBranch = pBranch->Bnd().IsOut (theBnd);
352
353   for(;;) {
354     // condition of stopping the search
355     if (isOutOfBranch || pBranch->IsLeaf()) {
356       TheBndType aNewBnd = theBnd;
357       aNewBnd.Add (pBranch->Bnd());
358       // put the new leaf aside on the level of pBranch
359       pBranch->Gemmate (aNewBnd, theObj, theBnd, this->myAlloc);
360       myLastNode = &pBranch->ChangeChild(1);
361       break;
362     }
363
364     // Update the bounding box of the branch
365     pBranch->ChangeBnd().Add (theBnd);
366
367     // Select the best child branch to accept the object:
368     // 1. First check if one branch is out and another one is not.
369     // 2. Else select the child having the least union with theBnd
370     Standard_Integer iBest = 0;
371     Standard_Boolean isOut[] = { pBranch->Child(0).Bnd().IsOut (theBnd),
372                                  pBranch->Child(1).Bnd().IsOut (theBnd) };
373     if (isOut[0] != isOut[1])
374       iBest = (isOut[0] ? 1 : 0);
375     else {
376       TheBndType aUnion[] = { theBnd, theBnd };
377       aUnion[0].Add (pBranch->Child(0).Bnd());
378       aUnion[1].Add (pBranch->Child(1).Bnd());
379       const Standard_Real d1 = aUnion[0].SquareExtent();
380       const Standard_Real d2 = aUnion[1].SquareExtent();
381       if (d1 > d2)
382         iBest = 1;
383     }
384
385     // Continue with the selected branch
386     isOutOfBranch = isOut[iBest];
387     pBranch = &pBranch->ChangeChild(iBest);
388   }
389   return Standard_True;
390 }
391
392 //=======================================================================
393 //function : Select
394 //purpose  : Recursively searches in the branch all objects conforming 
395 //           to the given selector.
396 //           Returns the number of objects found.
397 //=======================================================================
398
399 template <class TheObjType, class TheBndType>
400 Standard_Integer NCollection_UBTree<TheObjType,TheBndType>::Select
401                                  (const TreeNode& theBranch,
402                                   Selector&       theSelector) const
403 {
404   // Try to reject the branch by bounding box
405   if (theSelector.Reject (theBranch.Bnd()))
406     return 0;
407
408   Standard_Integer nSel = 0;
409
410   if (theBranch.IsLeaf()) {
411     // It is a leaf => try to accept the object
412     if (theSelector.Accept (theBranch.Object()))
413       nSel++;
414   }
415   else {
416     // It is a branch => select from its children
417     nSel += Select (theBranch.Child(0), theSelector);
418     if (!theSelector.Stop())
419       nSel += Select (theBranch.Child(1), theSelector);
420   }
421
422   return nSel;
423 }
424
425 // ======================================================================
426 /**
427  * Declaration of handled version of NCollection_UBTree.
428  * In the macros below the arguments are:
429  * _HUBTREE      - the desired name of handled class
430  * _OBJTYPE      - the name of the object type
431  * _BNDTYPE      - the name of the bounding box type
432  * _HPARENT      - the name of parent class (usually MMgt_TShared)
433  */
434 #define DEFINE_HUBTREE(_HUBTREE, _OBJTYPE, _BNDTYPE, _HPARENT)          \
435 class _HUBTREE : public _HPARENT                                        \
436 {                                                                       \
437  public:                                                                \
438   typedef NCollection_UBTree <_OBJTYPE, _BNDTYPE> UBTree;               \
439                                                                         \
440   _HUBTREE () : myTree(new UBTree) {}                                   \
441   /* Empty constructor */                                               \
442   _HUBTREE (const Handle_NCollection_BaseAllocator& theAlloc)           \
443      : myTree(new UBTree(theAlloc)) {}                                  \
444   /* Constructor */                                                     \
445                                                                         \
446   /* Access to the methods of UBTree */                                 \
447                                                                         \
448   Standard_Boolean Add (const _OBJTYPE& theObj,                         \
449                         const _BNDTYPE& theBnd)                         \
450         { return ChangeTree().Add (theObj, theBnd); }                   \
451                                                                         \
452   Standard_Integer Select (UBTree::Selector& theSelector) const         \
453         { return Tree().Select (theSelector); }                         \
454                                                                         \
455   void Clear () { ChangeTree().Clear (); }                              \
456                                                                         \
457   Standard_Boolean IsEmpty () const { return Tree().IsEmpty(); }        \
458                                                                         \
459   const UBTree::TreeNode& Root () const { return Tree().Root(); }       \
460                                                                         \
461                                                                         \
462   /* Access to the tree algorithm */                                    \
463                                                                         \
464   const UBTree& Tree () const { return *myTree; }                       \
465   UBTree&       ChangeTree () { return *myTree; }                       \
466                                                                         \
467   ~_HUBTREE () { delete myTree; }                                       \
468   /* Destructor */                                                      \
469                                                                         \
470   DEFINE_STANDARD_RTTI (_HUBTREE)                                       \
471   /* Type management */                                                 \
472                                                                         \
473  private:                                                               \
474   /* Copying and assignment are prohibited  */                          \
475   _HUBTREE (UBTree*);                                                   \
476   _HUBTREE (const _HUBTREE&);                                           \
477   void operator = (const _HUBTREE&);                                    \
478                                                                         \
479  private:                                                               \
480   UBTree       *myTree;        /* pointer to the tree algorithm */      \
481 };                                                                      \
482 DEFINE_STANDARD_HANDLE (_HUBTREE, _HPARENT)
483
484 #define IMPLEMENT_HUBTREE(_HUBTREE, _HPARENT)                           \
485 IMPLEMENT_STANDARD_HANDLE (_HUBTREE, _HPARENT)                          \
486 IMPLEMENT_STANDARD_RTTIEXT(_HUBTREE, _HPARENT)
487
488 #endif