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