f790f20169d9698c87d45e1aea1f552f7864b124
[occt.git] / src / NCollection / NCollection_EBTree.hxx
1 // Created on: 2002-07-30
2 // Created by: Michael SAZONOV
3 // Copyright (c) 2002-2014 OPEN CASCADE SAS
4 //
5 // This file is part of Open CASCADE Technology software library.
6 //
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.
12 //
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
15
16 #ifndef NCollection_EBTree_HeaderFile
17 #define NCollection_EBTree_HeaderFile
18
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>
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
120     TreeNode& aNewNode = this->ChangeLastNode();
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                                                                         \
211   DEFINE_STANDARD_RTTI_INLINE(_HEBTREE,_HUBTREE)                                       \
212   /* Type management */                                                 \
213 };                                                                      \
214 DEFINE_STANDARD_HANDLE (_HEBTREE, _HUBTREE)
215
216 #define IMPLEMENT_HEBTREE(_HEBTREE, _HUBTREE)                           
217
218
219
220 #endif