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