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> |
25e59720 |
21 | #include <Standard_Transient.hxx> |
7fd59977 |
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 | /** |
68df8478 |
51 | * Updates the tree with a new object and its bounding box. |
7fd59977 |
52 | * Extends the functionality of the parent method by maintaining |
68df8478 |
53 | * the map myObjNodeMap. Redefined virtual method. |
7fd59977 |
54 | * @return |
55 | * False if the tree already contains theObj. |
56 | */ |
68df8478 |
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 | } |
7fd59977 |
82 | |
83 | /** |
84 | * Removes the given object and updates the tree. |
85 | * @return |
86 | * False if the tree does not contain theObj |
87 | */ |
68df8478 |
88 | Standard_Boolean Remove (const TheObjType& theObj); |
7fd59977 |
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 | */ |
68df8478 |
107 | void Clear (const Handle(NCollection_BaseAllocator)& aNewAlloc = 0L) Standard_OVERRIDE |
108 | { |
109 | myObjNodeMap.Clear (); |
110 | UBTree::Clear (aNewAlloc); |
111 | } |
7fd59977 |
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 | |
7fd59977 |
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 | \ |
92efcf78 |
206 | DEFINE_STANDARD_RTTI_INLINE(_HEBTREE,_HUBTREE) \ |
7fd59977 |
207 | /* Type management */ \ |
208 | }; \ |
209 | DEFINE_STANDARD_HANDLE (_HEBTREE, _HUBTREE) |
210 | |
ec357c5c |
211 | #define IMPLEMENT_HEBTREE(_HEBTREE, _HUBTREE) |
212 | |
213 | |
7fd59977 |
214 | |
215 | #endif |