b311480e |
1 | // Created on: 2002-07-30 |
2 | // Created by: Michael SAZONOV |
3 | // Copyright (c) 2002-2012 OPEN CASCADE SAS |
4 | // |
5 | // The content of this file is subject to the Open CASCADE Technology Public |
6 | // License Version 6.5 (the "License"). You may not use the content of this file |
7 | // except in compliance with the License. Please obtain a copy of the License |
8 | // at http://www.opencascade.org and read it completely before using this file. |
9 | // |
10 | // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its |
11 | // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France. |
12 | // |
13 | // The Original Code and all software distributed under the License is |
14 | // distributed on an "AS IS" basis, without warranty of any kind, and the |
15 | // Initial Developer hereby disclaims all such warranties, including without |
16 | // limitation, any warranties of merchantability, fitness for a particular |
17 | // purpose or non-infringement. Please see the License for the specific terms |
18 | // and conditions governing the rights and limitations under the License. |
19 | |
7fd59977 |
20 | |
21 | #ifndef NCollection_EBTree_HeaderFile |
22 | #define NCollection_EBTree_HeaderFile |
23 | |
24 | #include <NCollection_UBTree.hxx> |
25 | #include <Standard_DefineHandle.hxx> |
26 | #include <MMgt_TShared.hxx> |
27 | #include <NCollection_List.hxx> |
28 | #include <TColStd_SequenceOfInteger.hxx> |
29 | #include <NCollection_DataMap.hxx> |
30 | |
31 | /** |
32 | * The algorithm of unbalanced binary tree of overlapped bounding boxes with |
33 | * the possibility of deleting objects from the tree. |
34 | * |
35 | * In addition to the requirements to the object type defined in the parent |
36 | * class this class requires that the object can be hashed and compared to |
37 | * another object (functions HashCode and IsEqual are defined for it), since |
38 | * the class NCollection_DataMap is used where the object plays the role of |
39 | * the key. |
40 | */ |
41 | template <class TheObjType, class TheBndType> class NCollection_EBTree |
42 | : public NCollection_UBTree <TheObjType, TheBndType> |
43 | { |
44 | public: |
45 | typedef NCollection_UBTree <TheObjType, TheBndType> UBTree; |
46 | typedef TYPENAME UBTree::TreeNode TreeNode; |
47 | // ---------- PUBLIC METHODS ---------- |
48 | |
49 | /** |
50 | * Constructor. |
51 | */ |
52 | NCollection_EBTree (const Handle(NCollection_BaseAllocator)& theAllocator=0L) |
53 | : UBTree (theAllocator) {} |
54 | |
55 | /** |
56 | * Extends the functionality of the parent method by maintaining |
57 | * the map myObjNodeMap. Redefined virtual method |
58 | * @return |
59 | * False if the tree already contains theObj. |
60 | */ |
61 | Standard_EXPORT Standard_Boolean Add (const TheObjType& theObj, |
62 | const TheBndType& theBnd); |
63 | |
64 | /** |
65 | * Removes the given object and updates the tree. |
66 | * @return |
67 | * False if the tree does not contain theObj |
68 | */ |
69 | Standard_EXPORT Standard_Boolean Remove (const TheObjType& theObj); |
70 | |
71 | /** |
72 | * @return |
73 | * True if the tree contains the object. |
74 | */ |
75 | Standard_Boolean Contains (const TheObjType& theObj) const |
76 | { return myObjNodeMap.IsBound (theObj); } |
77 | |
78 | /** |
79 | * @return |
80 | * The leaf node containing the object. |
81 | */ |
82 | const TreeNode& FindNode (const TheObjType& theObj) const |
83 | { return *myObjNodeMap.Find (theObj); } |
84 | |
85 | /** |
86 | * Clears the contents of the tree. Redefined virtual method |
87 | */ |
88 | void Clear (const Handle(NCollection_BaseAllocator)& aNewAlloc = 0L) |
89 | { myObjNodeMap.Clear(); UBTree::Clear(aNewAlloc); } |
90 | |
91 | private: |
92 | // ---------- PRIVATE METHODS ---------- |
93 | |
94 | /// Copy constructor (prohibited). |
95 | NCollection_EBTree (const NCollection_EBTree&); |
96 | |
97 | /// Assignment operator (prohibited). |
98 | NCollection_EBTree& operator = (const NCollection_EBTree&); |
99 | |
100 | // ---------- PRIVATE FIELDS ---------- |
101 | |
102 | NCollection_DataMap <TheObjType, TreeNode*> |
103 | myObjNodeMap; ///< map of object to node pointer |
104 | }; |
105 | |
106 | // ================== METHODS TEMPLATES ===================== |
107 | |
108 | //======================================================================= |
109 | //function : Add |
110 | //purpose : Updates the tree with a new object and its bounding box. |
111 | // Returns false if the tree already contains theObj. |
112 | //======================================================================= |
113 | |
114 | template <class TheObjType, class TheBndType> |
115 | Standard_Boolean NCollection_EBTree<TheObjType,TheBndType>::Add |
116 | (const TheObjType& theObj, |
117 | const TheBndType& theBnd) |
118 | { |
119 | Standard_Boolean result = Standard_False; |
120 | if (!Contains (theObj)) { |
121 | // Add object in the tree using parent method |
122 | UBTree::Add (theObj, theBnd); |
123 | |
124 | // Update the map |
125 | TreeNode& aNewNode = ChangeLastNode(); |
126 | myObjNodeMap.Bind (theObj, &aNewNode); |
127 | // If the new node is not the root (has a parent) check the neighbour node |
128 | if (!aNewNode.IsRoot()) { |
129 | TreeNode& aNeiNode = aNewNode.ChangeParent().ChangeChild(0); |
130 | if (aNeiNode.IsLeaf()) { |
131 | myObjNodeMap.UnBind (aNeiNode.Object()); |
132 | myObjNodeMap.Bind (aNeiNode.Object(), &aNeiNode); |
133 | } |
134 | } |
135 | result = Standard_True; |
136 | } |
137 | return result; |
138 | } |
139 | |
140 | //======================================================================= |
141 | //function : Remove |
142 | //purpose : Removes the given object and updates the tree. |
143 | // Returns false if the tree does not contain theObj. |
144 | //======================================================================= |
145 | |
146 | template <class TheObjType, class TheBndType> |
147 | Standard_Boolean NCollection_EBTree<TheObjType,TheBndType>::Remove |
148 | (const TheObjType& theObj) |
149 | { |
150 | Standard_Boolean result = Standard_False; |
151 | if (Contains (theObj)) { |
152 | TreeNode* pNode = myObjNodeMap (theObj); |
153 | if (pNode->IsRoot()) { |
154 | // it is the root, so clear all the tree |
155 | Clear(); |
156 | } |
157 | else { |
158 | // it is a child of some parent, |
159 | // so kill the child that contains theObj |
160 | // and update bounding boxes of all ancestors |
161 | myObjNodeMap.UnBind (theObj); |
162 | TreeNode* pParent = &pNode->ChangeParent(); |
163 | pParent->Kill ((pNode == &pParent->Child(0) ? 0 : 1), |
164 | this->Allocator()); |
165 | if (pParent->IsLeaf()) { |
166 | // the parent node became a leaf, so update the map |
167 | myObjNodeMap.UnBind (pParent->Object()); |
168 | myObjNodeMap.Bind (pParent->Object(), pParent); |
169 | } |
170 | while (!pParent->IsRoot()) { |
171 | pParent = &pParent->ChangeParent(); |
172 | pParent->ChangeBnd() = pParent->Child(0).Bnd(); |
173 | pParent->ChangeBnd().Add (pParent->Child(1).Bnd()); |
174 | } |
175 | } |
176 | result = Standard_True; |
177 | } |
178 | return result; |
179 | } |
180 | |
181 | // ====================================================================== |
182 | // Declaration of handled version of NCollection_EBTree. |
183 | // In the macros below the arguments are: |
184 | // _HEBTREE - the desired name of handled class |
185 | // _OBJTYPE - the name of the object type |
186 | // _BNDTYPE - the name of the bounding box type |
187 | // _HUBTREE - the name of parent class |
188 | // (defined using macro DEFINE_HUBTREE) |
189 | |
190 | #define DEFINE_HEBTREE(_HEBTREE, _OBJTYPE, _BNDTYPE, _HUBTREE) \ |
191 | class _HEBTREE : public _HUBTREE \ |
192 | { \ |
193 | public: \ |
194 | typedef NCollection_UBTree <_OBJTYPE, _BNDTYPE> UBTree; \ |
195 | typedef NCollection_EBTree <_OBJTYPE, _BNDTYPE> EBTree; \ |
196 | \ |
197 | _HEBTREE () : _HUBTREE(new EBTree) {} \ |
198 | /* Empty constructor */ \ |
199 | \ |
200 | /* Access to the methods of EBTree */ \ |
201 | \ |
202 | Standard_Boolean Remove (const _OBJTYPE& theObj) \ |
203 | { return ChangeETree().Remove (theObj); } \ |
204 | \ |
205 | Standard_Boolean Contains (const _OBJTYPE& theObj) const \ |
206 | { return ETree().Contains (theObj); } \ |
207 | \ |
208 | const UBTree::TreeNode& FindNode (const _OBJTYPE& theObj) const \ |
209 | { return ETree().FindNode (theObj); } \ |
210 | \ |
211 | /* Access to the extended tree algorithm */ \ |
212 | \ |
213 | const EBTree& ETree () const { return (const EBTree&) Tree(); } \ |
214 | EBTree& ChangeETree () { return (EBTree&) ChangeTree(); } \ |
215 | \ |
216 | DEFINE_STANDARD_RTTI (_HEBTREE) \ |
217 | /* Type management */ \ |
218 | }; \ |
219 | DEFINE_STANDARD_HANDLE (_HEBTREE, _HUBTREE) |
220 | |
221 | #define IMPLEMENT_HEBTREE(_HEBTREE, _HUBTREE) \ |
222 | IMPLEMENT_STANDARD_HANDLE (_HEBTREE, _HUBTREE) \ |
223 | IMPLEMENT_STANDARD_RTTIEXT(_HEBTREE, _HUBTREE) |
224 | |
225 | #endif |