Overture  Version 25
GeometricADT3dInt.h
Go to the documentation of this file.
1 //
2 // GeometricADT3dInt : this version templated on both the data-type and the 6.
3 //
4 // Authors: Kyle Chand and Bill Henshaw.
5 //
6 #ifndef __GEOMETRIC_ADT_3D_INT_H__
7 #define __GEOMETRIC_ADT_3D_INT_H__
8 
9 #define processedWithDT
10 
11 #ifndef processedWithDT
12 #define GeomADTTuple3dInt GeomADTTuple3dInt
13 #define GeometricADT3dInt GeometricADT3dInt
14 #define GeometricADTTraversor3dInt __GeometricADTtraversor2
15 #define GeometricADTIterator3dInt __GeometricADTiterator2
16 
17 
18 #define debug_GeometricADT3dInt debug_GeometricADT2
19 
20 
21 #define 12 (6*2)
22 
23 #endif
24 
25 //kkc 040415 #include <iostream.h>
26 #include "OvertureDefine.h"
27 #include OV_STD_INCLUDE(iostream)
28 using namespace std;
29 #include "GeometricADTExceptions.h"
31 #ifndef OV_USE_OLD_STL_HEADERS
32 #include <list>
33 using namespace std;
34 #else
35 #include <list.h>
36 #endif
37 
38 #include "GeomADTTuple3dInt.h"
39 
40 #undef __ADTType
41 #define __ADTType NTreeNode2GeomADTTuple3dInt
42 
43 
44 
45 // forward declare this guy
46  class GeometricADT3dInt;
47 
48 // GeometricADT3dInt iterator class
49 
51 {
52  public:
54  {
55  ADT_LEFT = 0,
57  };
58 
59  GeometricADTIterator3dInt(const GeometricADT3dInt &gADT, const real *target_);
62 
65  GeometricADTIterator3dInt & operator++(); // decend to the next node in the tree
66  GeometricADTIterator3dInt operator++(int); // decend to the next node in the tree
67 
68  inline GeomADTTuple3dInt & operator*(); // dereference the iterator
69 
70  inline bool isTerminal(); // is this iterator at an end of the tree ?
71  inline int getDepth();
72 
73  friend class GeometricADT3dInt;
74 
75  protected:
76  // these constructors make no sense
77  GeometricADTIterator3dInt();// { } // what does this do ?
78  GeometricADTIterator3dInt(GeometricADT3dInt &x);// { } // should probably be a standard tree iteration (eg preorder or postorder...)
79 
80  private:
81  GeometricADT3dInt *thisADT;
82  __ADTType *current;
83  real target[6];
84  int depth;
85 };
86 
87 
88 // GeometricADT3dInt traversor class
89 
90 class GeometricADTTraversor3dInt // this class should probably have a superclass in NTreeNode2GeomADTTuple3dInt
91 {
92  public:
94  {
95  ADT_LEFT = 0,
97  };
98 
99  GeometricADTTraversor3dInt(const GeometricADT3dInt &gADT, const real *target_);
103 
106  GeometricADTTraversor3dInt & operator++(); // decend to the next node in the tree
107  GeometricADTTraversor3dInt operator++(int); // decend to the next node in the tree
108 
109  inline GeomADTTuple3dInt & operator*(); // dereference the traversor
110 
111  void setTarget(const real *target_);
112 
113  inline bool isFinished() const; // is this traversor finished traversing the tree ?
114 
115  inline int getDepth();
116 
117  friend class GeometricADT3dInt;
118 
119  protected:
120  // these constructors make no sense
121  GeometricADTTraversor3dInt() { } // what does this do ?
122  // GeometricADTTraversor3dInt(GeometricADT3dInt &x) { } // should probably be a standard tree iteration (eg preorder or postorder...)
123  inline bool isOverlapping(int depth, const real *bBox);
124  inline bool isCandidate(const real *candidate);
125 
126  private:
127  int depth;
128  bool traversalFinished;
129 
130  list<bool> leftSubTreeFinished; // keeps a stack of the traversal
131 
132  GeometricADT3dInt *thisADT;
133  __ADTType *current;
134  real target[6];
135  real a[6];
136  real b[6];
137 };
138 
139 // Actual GeometricADT3dInt class
140 
142 {
143  public:
144 
146  {
147  ADT_LEFT = 0,
149  };
150 
151  GeometricADT3dInt(int rangeDimension_=2);
152  GeometricADT3dInt(int rangeDimension_, const real *boundingBox_);
153 
155 
157 
160 
161  void initTree();
162  void initTree(int rangeDimension_, const real *boundingBox_);
163 
164  int addElement(const real *bBox, int &data);
165  int delElement(GeometricADT3dInt::iterator & delItem);
166  void verifyTree();
167 
168 
171 
172  protected:
173  inline int getSplitAxis(int depth) const;
174  inline Real getSplitLocation(int axis, const real *box) const;
175  void shiftTreeUp(GeometricADT3dInt::ADTType *node, int depth); // used to rebuild the search tree
176  void verifyNode(GeometricADT3dInt::ADTType &node, int depth);
177  int insert(GeometricADT3dInt::iterator &insParent, int leaf, GeomADTTuple3dInt &data);
178  int insert(GeometricADT3dInt::iterator &insParent, int leaf);
179 
180  private:
181 
182  int rangeDimension;
183  int ADTDimension;
184  int ADTdepth;
185  int numberOfItems;
186 
187  real boundingBox[12];
188 
190 
191 };
192 
193 
194 //
195 // implementation of inlined GeometricADT3dInt methods
196 //
197 
198 
199 
200 inline
201 int
203 getSplitAxis(int depth) const
204 {
205  //AssertException<GeometricADT3dInt::InvalidDepth> (depth<=ADTdepth);
206 #if 0
207  assert(depth<=ADTdepth);
208 #endif
209  return depth%ADTDimension;
210 }
211 
212 
213 inline
214 real
216 getSplitLocation(int axis, const real *box) const
217 {
218  //AssertException<InvalidADTDimension> (axis<ADTDimension && box.getLength(0)==2*ADTDimension);
219  // assert(axis<ADTDimension && box.getLength(0)==2*ADTDimension);
220  // assert(axis<ADTDimension && box.getLength(0)==2*ADTDimension);
221  return (box[2*axis+1] + box[2*axis])/2.0;
222 }
223 
224 // include "../GridGenerator/GeometricADT3dInt.C"
225 // include "../GridGenerator/GeometricADTIterator.C"
226 // include "../GridGenerator/GeometricADTTraversor.C"
227 
228 //\begin{GeometricADTIterator.tex}{\subsection{Dereference operator*()}}
229 
230 inline
234 // /Purpose : returns the data at the current node of the iterators {\tt GeometricADT3dInt}
235 //\end{GeometricADT3dInt.tex}
236 {
237  return current->getData();
238 }
239 
240 //\begin{GeometricADTIterator.tex}{\subsection{getDepth}}
241 
242 inline
243 int
246 // /Purpose : returns the iterators depth in it's {\tt GeometricADT3dInt}
247 //\end{GeometricADT3dInt.tex}
248 {
249  return depth;
250 }
251 
252 
253 inline
254 bool
256 isFinished() const
257 {
258 
259  return traversalFinished;
260 
261 }
262 
263 
264 inline
268 {
269  return current->getData();
270 }
271 
272 
273 inline
274 int
277 {
278  return depth;
279 }
280 
281 
282 
283 inline
284 bool
286 isOverlapping(int theDepth, const real *bBox)
287 {
288 
289  // this may need to be reworked to make it more general...
290  //bBox.display("bBox");
291  int axis = thisADT->getSplitAxis(theDepth);
292  return (a[axis]<=bBox[2*axis+1] && bBox[2*axis]<=b[axis]);
293 
294 }
295 
296 
297 inline
298 bool
300 isCandidate(const real *candidate)
301 {
302  for (int axis=0; axis<thisADT->ADTDimension; axis++)
303  {
304  // res = res && (a[axis]<=candidate[axis] && candidate[axis]<=b[axis]);
305  if( a[axis]>candidate[axis] || candidate[axis]>b[axis] )
306  return false;
307  //cout << " axis "<<axis<<" a "<<a(axis)<<" xk "<<candidate(axis)<<" b "<<b(axis)<<endl;
308  }
309  return true;
310 }
311 
312 //\begin{>>GeometricADTIterator.tex}{\subsection{isTerminal}}
313 
314 inline
315 bool
318 // /Purpose : return true if the iterator is a terminal leaf (ie it cannot descend any further)
319 //\end{GeometricADTIterator.tex}
320 {
321 
322  if (current==NULL) return true;
323 
324  int splitAxis = thisADT->getSplitAxis(depth);
325  Real splitLoc = thisADT->getSplitLocation(splitAxis, (current->getData()).boundingBox);
326 
327  if ((current->querry(ADT_LEFT) &&
328  current->querry(ADT_RIGHT)) ||
329  (current->querry(ADT_LEFT) && target[splitAxis]<=splitLoc) ||
330  (current->querry(ADT_RIGHT) && target[splitAxis]>splitLoc))
331  return false;
332  else
333  return true;
334 
335 }
336 
337 
338 #ifndef processedWithDT
339 
340 #include "GeometricADT3dInt.C"
341 
342 #undef GeomADTTuple3dInt
343 #undef GeometricADT3dInt
344 #undef GeometricADTTraversor3dInt
345 #undef GeometricADTIterator3dInt
346 #undef GeometricADTError
347 #undef GeometricADTIteratorError
348 #undef GeometricADTTraversorError
349 #undef debug_GeometricADT3dInt
350 #undef 12
351 
352 #endif
353 
354 #endif