b311480e |
1 | // Created on: 2002-07-30 |
2 | // Created by: Michael SAZONOV |
973c2be1 |
3 | // Copyright (c) 2002-2014 OPEN CASCADE SAS |
b311480e |
4 | // |
973c2be1 |
5 | // This file is part of Open CASCADE Technology software library. |
b311480e |
6 | // |
d5f74e42 |
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 |
973c2be1 |
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. |
b311480e |
12 | // |
973c2be1 |
13 | // Alternatively, this file may be used under the terms of Open CASCADE |
14 | // commercial license or contractual agreement. |
7fd59977 |
15 | |
16 | #ifndef NCollection_EBTree_HeaderFile |
17 | #define NCollection_EBTree_HeaderFile |
18 | |
19 | #include <NCollection_UBTree.hxx> |
ec357c5c |
20 | #include <Standard_Type.hxx> |
7fd59977 |
21 | #include <MMgt_TShared.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 | * Extends the functionality of the parent method by maintaining |
52 | * the map myObjNodeMap. Redefined virtual method |
53 | * @return |
54 | * False if the tree already contains theObj. |
55 | */ |
56 | Standard_EXPORT Standard_Boolean Add (const TheObjType& theObj, |
57 | const TheBndType& theBnd); |
58 | |
59 | /** |
60 | * Removes the given object and updates the tree. |
61 | * @return |
62 | * False if the tree does not contain theObj |
63 | */ |
64 | Standard_EXPORT Standard_Boolean Remove (const TheObjType& theObj); |
65 | |
66 | /** |
67 | * @return |
68 | * True if the tree contains the object. |
69 | */ |
70 | Standard_Boolean Contains (const TheObjType& theObj) const |
71 | { return myObjNodeMap.IsBound (theObj); } |
72 | |
73 | /** |
74 | * @return |
75 | * The leaf node containing the object. |
76 | */ |
77 | const TreeNode& FindNode (const TheObjType& theObj) const |
78 | { return *myObjNodeMap.Find (theObj); } |
79 | |
80 | /** |
81 | * Clears the contents of the tree. Redefined virtual method |
82 | */ |
83 | void Clear (const Handle(NCollection_BaseAllocator)& aNewAlloc = 0L) |
84 | { myObjNodeMap.Clear(); UBTree::Clear(aNewAlloc); } |
85 | |
86 | private: |
87 | // ---------- PRIVATE METHODS ---------- |
88 | |
89 | /// Copy constructor (prohibited). |
90 | NCollection_EBTree (const NCollection_EBTree&); |
91 | |
92 | /// Assignment operator (prohibited). |
93 | NCollection_EBTree& operator = (const NCollection_EBTree&); |
94 | |
95 | // ---------- PRIVATE FIELDS ---------- |
96 | |
97 | NCollection_DataMap <TheObjType, TreeNode*> |
98 | myObjNodeMap; ///< map of object to node pointer |
99 | }; |
100 | |
101 | // ================== METHODS TEMPLATES ===================== |
102 | |
103 | //======================================================================= |
104 | //function : Add |
105 | //purpose : Updates the tree with a new object and its bounding box. |
106 | // Returns false if the tree already contains theObj. |
107 | //======================================================================= |
108 | |
109 | template <class TheObjType, class TheBndType> |
110 | Standard_Boolean NCollection_EBTree<TheObjType,TheBndType>::Add |
111 | (const TheObjType& theObj, |
112 | const TheBndType& theBnd) |
113 | { |
114 | Standard_Boolean result = Standard_False; |
115 | if (!Contains (theObj)) { |
116 | // Add object in the tree using parent method |
117 | UBTree::Add (theObj, theBnd); |
118 | |
119 | // Update the map |
01a6e62b |
120 | TreeNode& aNewNode = this->ChangeLastNode(); |
7fd59977 |
121 | myObjNodeMap.Bind (theObj, &aNewNode); |
122 | // If the new node is not the root (has a parent) check the neighbour node |
123 | if (!aNewNode.IsRoot()) { |
124 | TreeNode& aNeiNode = aNewNode.ChangeParent().ChangeChild(0); |
125 | if (aNeiNode.IsLeaf()) { |
126 | myObjNodeMap.UnBind (aNeiNode.Object()); |
127 | myObjNodeMap.Bind (aNeiNode.Object(), &aNeiNode); |
128 | } |
129 | } |
130 | result = Standard_True; |
131 | } |
132 | return result; |
133 | } |
134 | |
135 | //======================================================================= |
136 | //function : Remove |
137 | //purpose : Removes the given object and updates the tree. |
138 | // Returns false if the tree does not contain theObj. |
139 | //======================================================================= |
140 | |
141 | template <class TheObjType, class TheBndType> |
142 | Standard_Boolean NCollection_EBTree<TheObjType,TheBndType>::Remove |
143 | (const TheObjType& theObj) |
144 | { |
145 | Standard_Boolean result = Standard_False; |
146 | if (Contains (theObj)) { |
147 | TreeNode* pNode = myObjNodeMap (theObj); |
148 | if (pNode->IsRoot()) { |
149 | // it is the root, so clear all the tree |
150 | Clear(); |
151 | } |
152 | else { |
153 | // it is a child of some parent, |
154 | // so kill the child that contains theObj |
155 | // and update bounding boxes of all ancestors |
156 | myObjNodeMap.UnBind (theObj); |
157 | TreeNode* pParent = &pNode->ChangeParent(); |
158 | pParent->Kill ((pNode == &pParent->Child(0) ? 0 : 1), |
159 | this->Allocator()); |
160 | if (pParent->IsLeaf()) { |
161 | // the parent node became a leaf, so update the map |
162 | myObjNodeMap.UnBind (pParent->Object()); |
163 | myObjNodeMap.Bind (pParent->Object(), pParent); |
164 | } |
165 | while (!pParent->IsRoot()) { |
166 | pParent = &pParent->ChangeParent(); |
167 | pParent->ChangeBnd() = pParent->Child(0).Bnd(); |
168 | pParent->ChangeBnd().Add (pParent->Child(1).Bnd()); |
169 | } |
170 | } |
171 | result = Standard_True; |
172 | } |
173 | return result; |
174 | } |
175 | |
176 | // ====================================================================== |
177 | // Declaration of handled version of NCollection_EBTree. |
178 | // In the macros below the arguments are: |
179 | // _HEBTREE - the desired name of handled class |
180 | // _OBJTYPE - the name of the object type |
181 | // _BNDTYPE - the name of the bounding box type |
182 | // _HUBTREE - the name of parent class |
183 | // (defined using macro DEFINE_HUBTREE) |
184 | |
185 | #define DEFINE_HEBTREE(_HEBTREE, _OBJTYPE, _BNDTYPE, _HUBTREE) \ |
186 | class _HEBTREE : public _HUBTREE \ |
187 | { \ |
188 | public: \ |
189 | typedef NCollection_UBTree <_OBJTYPE, _BNDTYPE> UBTree; \ |
190 | typedef NCollection_EBTree <_OBJTYPE, _BNDTYPE> EBTree; \ |
191 | \ |
192 | _HEBTREE () : _HUBTREE(new EBTree) {} \ |
193 | /* Empty constructor */ \ |
194 | \ |
195 | /* Access to the methods of EBTree */ \ |
196 | \ |
197 | Standard_Boolean Remove (const _OBJTYPE& theObj) \ |
198 | { return ChangeETree().Remove (theObj); } \ |
199 | \ |
200 | Standard_Boolean Contains (const _OBJTYPE& theObj) const \ |
201 | { return ETree().Contains (theObj); } \ |
202 | \ |
203 | const UBTree::TreeNode& FindNode (const _OBJTYPE& theObj) const \ |
204 | { return ETree().FindNode (theObj); } \ |
205 | \ |
206 | /* Access to the extended tree algorithm */ \ |
207 | \ |
208 | const EBTree& ETree () const { return (const EBTree&) Tree(); } \ |
209 | EBTree& ChangeETree () { return (EBTree&) ChangeTree(); } \ |
210 | \ |
ec357c5c |
211 | DEFINE_STANDARD_RTTI (_HEBTREE, _HUBTREE) \ |
7fd59977 |
212 | /* Type management */ \ |
213 | }; \ |
214 | DEFINE_STANDARD_HANDLE (_HEBTREE, _HUBTREE) |
215 | |
ec357c5c |
216 | #define IMPLEMENT_HEBTREE(_HEBTREE, _HUBTREE) |
217 | |
218 | |
7fd59977 |
219 | |
220 | #endif |