0022651: Impossible to build OCC as static library due to using Standard_EXPORT inste...
[occt.git] / src / NCollection / NCollection_EBTree.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_EBTree_HeaderFile
17 #define NCollection_EBTree_HeaderFile
18
19 #include <NCollection_UBTree.hxx>
20 #include <Standard_Type.hxx>
21 #include <Standard_Transient.hxx>
22 #include <NCollection_List.hxx>
23 #include <TColStd_SequenceOfInteger.hxx>
24 #include <NCollection_DataMap.hxx>
25
26 /**
27  * The algorithm of unbalanced binary  tree of overlapped bounding boxes with
28  * the possibility of deleting objects from the tree.
29  *
30  * In addition to  the requirements to the object type  defined in the parent
31  * class this  class requires that the  object can be hashed  and compared to
32  * another object (functions HashCode and  IsEqual are defined for it), since
33  * the class NCollection_DataMap  is used where the object  plays the role of
34  * the key.
35  */
36 template <class TheObjType, class TheBndType> class NCollection_EBTree
37   : public NCollection_UBTree <TheObjType, TheBndType>
38 {
39  public:
40   typedef NCollection_UBTree <TheObjType, TheBndType> UBTree;
41   typedef TYPENAME UBTree::TreeNode TreeNode;
42   // ---------- PUBLIC METHODS ----------
43
44   /**
45    * Constructor.
46    */
47   NCollection_EBTree (const Handle(NCollection_BaseAllocator)& theAllocator=0L)
48     : UBTree (theAllocator) {}
49
50   /**
51    * Updates the tree with a new object and its bounding box.
52    * Extends the functionality of the parent method by maintaining
53    * the map myObjNodeMap. Redefined virtual method.
54    * @return
55    *   False if the tree already contains theObj.
56    */ 
57   Standard_Boolean Add (const TheObjType& theObj, const TheBndType& theBnd) Standard_OVERRIDE
58   {
59     Standard_Boolean result = Standard_False;
60     if (!Contains (theObj))
61     {
62       // Add object in the tree using parent method
63       UBTree::Add (theObj, theBnd);
64
65       // Update the map
66       TreeNode& aNewNode = this->ChangeLastNode ();
67       myObjNodeMap.Bind (theObj, &aNewNode);
68       // If the new node is not the root (has a parent) check the neighbour node
69       if (!aNewNode.IsRoot ())
70       {
71         TreeNode& aNeiNode = aNewNode.ChangeParent ().ChangeChild (0);
72         if (aNeiNode.IsLeaf ())
73         {
74           myObjNodeMap.UnBind (aNeiNode.Object ());
75           myObjNodeMap.Bind (aNeiNode.Object (), &aNeiNode);
76         }
77       }
78       result = Standard_True;
79     }
80     return result;
81   }
82
83   /**
84    * Removes the given object and updates the tree.
85    * @return
86    *   False if the tree does not contain theObj
87    */
88   Standard_Boolean Remove (const TheObjType& theObj);
89
90   /**
91    * @return
92    *   True if the tree contains the object.
93    */
94   Standard_Boolean Contains (const TheObjType& theObj) const
95         { return myObjNodeMap.IsBound (theObj); }
96
97   /**
98    * @return
99    *   The leaf node containing the object.
100    */
101   const TreeNode& FindNode (const TheObjType& theObj) const
102         { return *myObjNodeMap.Find (theObj); }
103
104   /**
105    * Clears the contents of the tree. Redefined virtual method
106    */
107   void Clear (const Handle(NCollection_BaseAllocator)& aNewAlloc = 0L) Standard_OVERRIDE
108   {
109     myObjNodeMap.Clear ();
110     UBTree::Clear (aNewAlloc);
111   }
112
113  private:
114   // ---------- PRIVATE METHODS ----------
115
116   /// Copy constructor (prohibited).
117   NCollection_EBTree (const NCollection_EBTree&);
118
119   /// Assignment operator (prohibited).
120   NCollection_EBTree& operator = (const NCollection_EBTree&);
121
122   // ---------- PRIVATE FIELDS ----------
123
124   NCollection_DataMap <TheObjType, TreeNode*>
125                             myObjNodeMap;   ///< map of object to node pointer
126 };
127
128 // ================== METHODS TEMPLATES =====================
129
130 //=======================================================================
131 //function : Remove
132 //purpose  : Removes the given object and updates the tree.
133 //           Returns false if the tree does not contain theObj.
134 //=======================================================================
135
136 template <class TheObjType, class TheBndType>
137 Standard_Boolean NCollection_EBTree<TheObjType,TheBndType>::Remove
138                                 (const TheObjType& theObj)
139 {
140   Standard_Boolean result = Standard_False;
141   if (Contains (theObj)) {
142     TreeNode* pNode = myObjNodeMap (theObj);
143     if (pNode->IsRoot()) {
144       // it is the root, so clear all the tree
145       Clear();
146     }
147     else {
148       // it is a child of some parent,
149       // so kill the child that contains theObj
150       // and update bounding boxes of all ancestors
151       myObjNodeMap.UnBind (theObj);
152       TreeNode* pParent = &pNode->ChangeParent();
153       pParent->Kill ((pNode == &pParent->Child(0) ? 0 : 1),
154                      this->Allocator());
155       if (pParent->IsLeaf()) {
156         // the parent node became a leaf, so update the map
157         myObjNodeMap.UnBind (pParent->Object());
158         myObjNodeMap.Bind (pParent->Object(), pParent);
159       }
160       while (!pParent->IsRoot()) {
161         pParent = &pParent->ChangeParent();
162         pParent->ChangeBnd() = pParent->Child(0).Bnd();
163         pParent->ChangeBnd().Add (pParent->Child(1).Bnd());
164       }
165     }
166     result = Standard_True;
167   }
168   return result;
169 }
170
171 // ======================================================================
172 // Declaration of handled version of NCollection_EBTree.
173 // In the macros below the arguments are:
174 // _HEBTREE      - the desired name of handled class
175 // _OBJTYPE      - the name of the object type
176 // _BNDTYPE      - the name of the bounding box type
177 // _HUBTREE      - the name of parent class
178 //                 (defined using macro DEFINE_HUBTREE)
179
180 #define DEFINE_HEBTREE(_HEBTREE, _OBJTYPE, _BNDTYPE, _HUBTREE)          \
181 class _HEBTREE : public _HUBTREE                                        \
182 {                                                                       \
183  public:                                                                \
184   typedef NCollection_UBTree <_OBJTYPE, _BNDTYPE> UBTree;               \
185   typedef NCollection_EBTree <_OBJTYPE, _BNDTYPE> EBTree;               \
186                                                                         \
187   _HEBTREE () : _HUBTREE(new EBTree) {}                                 \
188   /* Empty constructor */                                               \
189                                                                         \
190   /* Access to the methods of EBTree */                                 \
191                                                                         \
192   Standard_Boolean Remove (const _OBJTYPE& theObj)                      \
193         { return ChangeETree().Remove (theObj); }                       \
194                                                                         \
195   Standard_Boolean Contains (const _OBJTYPE& theObj) const              \
196         { return ETree().Contains (theObj); }                           \
197                                                                         \
198   const UBTree::TreeNode& FindNode (const _OBJTYPE& theObj) const       \
199         { return ETree().FindNode (theObj); }                           \
200                                                                         \
201   /* Access to the extended tree algorithm */                           \
202                                                                         \
203   const EBTree& ETree () const { return (const EBTree&) Tree(); }       \
204   EBTree&       ChangeETree () { return (EBTree&) ChangeTree(); }       \
205                                                                         \
206   DEFINE_STANDARD_RTTI_INLINE(_HEBTREE,_HUBTREE)                                       \
207   /* Type management */                                                 \
208 };                                                                      \
209 DEFINE_STANDARD_HANDLE (_HEBTREE, _HUBTREE)
210
211 #define IMPLEMENT_HEBTREE(_HEBTREE, _HUBTREE)                           
212
213
214
215 #endif