0027960: Configuration - fix compilation of OSD_Directory with MinGW-w64
[occt.git] / src / NCollection / NCollection_EBTree.hxx
CommitLineData
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>
7fd59977 21#include <MMgt_TShared.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 */
36template <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
109template <class TheObjType, class TheBndType>
110Standard_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
01a6e62b 120 TreeNode& aNewNode = this->ChangeLastNode();
7fd59977 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
141template <class TheObjType, class TheBndType>
142Standard_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) \
186class _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 \
92efcf78 211 DEFINE_STANDARD_RTTI_INLINE(_HEBTREE,_HUBTREE) \
7fd59977 212 /* Type management */ \
213}; \
214DEFINE_STANDARD_HANDLE (_HEBTREE, _HUBTREE)
215
ec357c5c 216#define IMPLEMENT_HEBTREE(_HEBTREE, _HUBTREE)
217
218
7fd59977 219
220#endif