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