1 // File: NCollection_EBTree.hxx
2 // Created: 30.07.02 09:51:33
3 // Author: Michael SAZONOV
4 // Copyright: Open CASCADE 2002
6 #ifndef NCollection_EBTree_HeaderFile
7 #define NCollection_EBTree_HeaderFile
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>
17 * The algorithm of unbalanced binary tree of overlapped bounding boxes with
18 * the possibility of deleting objects from the tree.
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
26 template <class TheObjType, class TheBndType> class NCollection_EBTree
27 : public NCollection_UBTree <TheObjType, TheBndType>
30 typedef NCollection_UBTree <TheObjType, TheBndType> UBTree;
31 typedef TYPENAME UBTree::TreeNode TreeNode;
32 // ---------- PUBLIC METHODS ----------
37 NCollection_EBTree (const Handle(NCollection_BaseAllocator)& theAllocator=0L)
38 : UBTree (theAllocator) {}
41 * Extends the functionality of the parent method by maintaining
42 * the map myObjNodeMap. Redefined virtual method
44 * False if the tree already contains theObj.
46 Standard_EXPORT Standard_Boolean Add (const TheObjType& theObj,
47 const TheBndType& theBnd);
50 * Removes the given object and updates the tree.
52 * False if the tree does not contain theObj
54 Standard_EXPORT Standard_Boolean Remove (const TheObjType& theObj);
58 * True if the tree contains the object.
60 Standard_Boolean Contains (const TheObjType& theObj) const
61 { return myObjNodeMap.IsBound (theObj); }
65 * The leaf node containing the object.
67 const TreeNode& FindNode (const TheObjType& theObj) const
68 { return *myObjNodeMap.Find (theObj); }
71 * Clears the contents of the tree. Redefined virtual method
73 void Clear (const Handle(NCollection_BaseAllocator)& aNewAlloc = 0L)
74 { myObjNodeMap.Clear(); UBTree::Clear(aNewAlloc); }
77 // ---------- PRIVATE METHODS ----------
79 /// Copy constructor (prohibited).
80 NCollection_EBTree (const NCollection_EBTree&);
82 /// Assignment operator (prohibited).
83 NCollection_EBTree& operator = (const NCollection_EBTree&);
85 // ---------- PRIVATE FIELDS ----------
87 NCollection_DataMap <TheObjType, TreeNode*>
88 myObjNodeMap; ///< map of object to node pointer
91 // ================== METHODS TEMPLATES =====================
93 //=======================================================================
95 //purpose : Updates the tree with a new object and its bounding box.
96 // Returns false if the tree already contains theObj.
97 //=======================================================================
99 template <class TheObjType, class TheBndType>
100 Standard_Boolean NCollection_EBTree<TheObjType,TheBndType>::Add
101 (const TheObjType& theObj,
102 const TheBndType& theBnd)
104 Standard_Boolean result = Standard_False;
105 if (!Contains (theObj)) {
106 // Add object in the tree using parent method
107 UBTree::Add (theObj, theBnd);
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);
120 result = Standard_True;
125 //=======================================================================
127 //purpose : Removes the given object and updates the tree.
128 // Returns false if the tree does not contain theObj.
129 //=======================================================================
131 template <class TheObjType, class TheBndType>
132 Standard_Boolean NCollection_EBTree<TheObjType,TheBndType>::Remove
133 (const TheObjType& theObj)
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
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),
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);
155 while (!pParent->IsRoot()) {
156 pParent = &pParent->ChangeParent();
157 pParent->ChangeBnd() = pParent->Child(0).Bnd();
158 pParent->ChangeBnd().Add (pParent->Child(1).Bnd());
161 result = Standard_True;
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)
175 #define DEFINE_HEBTREE(_HEBTREE, _OBJTYPE, _BNDTYPE, _HUBTREE) \
176 class _HEBTREE : public _HUBTREE \
179 typedef NCollection_UBTree <_OBJTYPE, _BNDTYPE> UBTree; \
180 typedef NCollection_EBTree <_OBJTYPE, _BNDTYPE> EBTree; \
182 _HEBTREE () : _HUBTREE(new EBTree) {} \
183 /* Empty constructor */ \
185 /* Access to the methods of EBTree */ \
187 Standard_Boolean Remove (const _OBJTYPE& theObj) \
188 { return ChangeETree().Remove (theObj); } \
190 Standard_Boolean Contains (const _OBJTYPE& theObj) const \
191 { return ETree().Contains (theObj); } \
193 const UBTree::TreeNode& FindNode (const _OBJTYPE& theObj) const \
194 { return ETree().FindNode (theObj); } \
196 /* Access to the extended tree algorithm */ \
198 const EBTree& ETree () const { return (const EBTree&) Tree(); } \
199 EBTree& ChangeETree () { return (EBTree&) ChangeTree(); } \
201 DEFINE_STANDARD_RTTI (_HEBTREE) \
202 /* Type management */ \
204 DEFINE_STANDARD_HANDLE (_HEBTREE, _HUBTREE)
206 #define IMPLEMENT_HEBTREE(_HEBTREE, _HUBTREE) \
207 IMPLEMENT_STANDARD_HANDLE (_HEBTREE, _HUBTREE) \
208 IMPLEMENT_STANDARD_RTTIEXT(_HEBTREE, _HUBTREE)