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