1 // Created on: 2002-07-30
2 // Created by: Michael SAZONOV
3 // Copyright (c) 2002-2014 OPEN CASCADE SAS
5 // This file is part of Open CASCADE Technology software library.
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
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.
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
16 #ifndef NCollection_EBTree_HeaderFile
17 #define NCollection_EBTree_HeaderFile
19 #include <NCollection_UBTree.hxx>
20 #include <Standard_Type.hxx>
21 #include <Standard_Transient.hxx>
22 #include <NCollection_List.hxx>
23 #include <TColStd_SequenceOfInteger.hxx>
24 #include <NCollection_DataMap.hxx>
27 * The algorithm of unbalanced binary tree of overlapped bounding boxes with
28 * the possibility of deleting objects from the tree.
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
36 template <class TheObjType, class TheBndType> class NCollection_EBTree
37 : public NCollection_UBTree <TheObjType, TheBndType>
40 typedef NCollection_UBTree <TheObjType, TheBndType> UBTree;
41 typedef TYPENAME UBTree::TreeNode TreeNode;
42 // ---------- PUBLIC METHODS ----------
47 NCollection_EBTree (const Handle(NCollection_BaseAllocator)& theAllocator=0L)
48 : UBTree (theAllocator) {}
51 * Updates the tree with a new object and its bounding box.
52 * Extends the functionality of the parent method by maintaining
53 * the map myObjNodeMap. Redefined virtual method.
55 * False if the tree already contains theObj.
57 Standard_Boolean Add (const TheObjType& theObj, const TheBndType& theBnd) Standard_OVERRIDE
59 Standard_Boolean result = Standard_False;
60 if (!Contains (theObj))
62 // Add object in the tree using parent method
63 UBTree::Add (theObj, theBnd);
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 ())
71 TreeNode& aNeiNode = aNewNode.ChangeParent ().ChangeChild (0);
72 if (aNeiNode.IsLeaf ())
74 myObjNodeMap.UnBind (aNeiNode.Object ());
75 myObjNodeMap.Bind (aNeiNode.Object (), &aNeiNode);
78 result = Standard_True;
84 * Removes the given object and updates the tree.
86 * False if the tree does not contain theObj
88 Standard_Boolean Remove (const TheObjType& theObj);
92 * True if the tree contains the object.
94 Standard_Boolean Contains (const TheObjType& theObj) const
95 { return myObjNodeMap.IsBound (theObj); }
99 * The leaf node containing the object.
101 const TreeNode& FindNode (const TheObjType& theObj) const
102 { return *myObjNodeMap.Find (theObj); }
105 * Clears the contents of the tree. Redefined virtual method
107 void Clear (const Handle(NCollection_BaseAllocator)& aNewAlloc = 0L) Standard_OVERRIDE
109 myObjNodeMap.Clear ();
110 UBTree::Clear (aNewAlloc);
114 // ---------- PRIVATE METHODS ----------
116 /// Copy constructor (prohibited).
117 NCollection_EBTree (const NCollection_EBTree&);
119 /// Assignment operator (prohibited).
120 NCollection_EBTree& operator = (const NCollection_EBTree&);
122 // ---------- PRIVATE FIELDS ----------
124 NCollection_DataMap <TheObjType, TreeNode*>
125 myObjNodeMap; ///< map of object to node pointer
128 // ================== METHODS TEMPLATES =====================
130 //=======================================================================
132 //purpose : Removes the given object and updates the tree.
133 // Returns false if the tree does not contain theObj.
134 //=======================================================================
136 template <class TheObjType, class TheBndType>
137 Standard_Boolean NCollection_EBTree<TheObjType,TheBndType>::Remove
138 (const TheObjType& theObj)
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
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),
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);
160 while (!pParent->IsRoot()) {
161 pParent = &pParent->ChangeParent();
162 pParent->ChangeBnd() = pParent->Child(0).Bnd();
163 pParent->ChangeBnd().Add (pParent->Child(1).Bnd());
166 result = Standard_True;
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)
180 #define DEFINE_HEBTREE(_HEBTREE, _OBJTYPE, _BNDTYPE, _HUBTREE) \
181 class _HEBTREE : public _HUBTREE \
184 typedef NCollection_UBTree <_OBJTYPE, _BNDTYPE> UBTree; \
185 typedef NCollection_EBTree <_OBJTYPE, _BNDTYPE> EBTree; \
187 _HEBTREE () : _HUBTREE(new EBTree) {} \
188 /* Empty constructor */ \
190 /* Access to the methods of EBTree */ \
192 Standard_Boolean Remove (const _OBJTYPE& theObj) \
193 { return ChangeETree().Remove (theObj); } \
195 Standard_Boolean Contains (const _OBJTYPE& theObj) const \
196 { return ETree().Contains (theObj); } \
198 const UBTree::TreeNode& FindNode (const _OBJTYPE& theObj) const \
199 { return ETree().FindNode (theObj); } \
201 /* Access to the extended tree algorithm */ \
203 const EBTree& ETree () const { return (const EBTree&) Tree(); } \
204 EBTree& ChangeETree () { return (EBTree&) ChangeTree(); } \
206 DEFINE_STANDARD_RTTI_INLINE(_HEBTREE,_HUBTREE) \
207 /* Type management */ \
209 DEFINE_STANDARD_HANDLE (_HEBTREE, _HUBTREE)
211 #define IMPLEMENT_HEBTREE(_HEBTREE, _HUBTREE)