Chombo + EB  3.2
KDTree.H
Go to the documentation of this file.
1 /*
2 
3 LICENSE NOTICE
4 
5 This source code is a part of the Project X software library. Project X
6 solves partial differential equations
7 in multiple dimensions using an adaptive, discontinuous Galerkin finite
8 element method, and has been
9 specifically designed to solve the compressible Euler and Navier-Stokes
10 equations.
11 
12 Copyright © 2003-2007 Massachusetts Institute of Technology
13 
14 
15 
16 This library is free software; you can redistribute it and/or modify it
17 under the terms of the GNU Lesser
18 General Public License as published by the Free Software Foundation;
19 either version 2.1 of the License,
20 or (at your option) any later version.
21 
22 
23 
24 This library is distributed in the hope that it will be useful, but
25 WITHOUT ANY WARRANTY; without even the
26 implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
27 See the GNU Lesser
28 General Public License in lgpl.txt for more details.
29 
30 
31 
32 You should have received a copy of the GNU Lesser General Public License
33 along with this library; if not, write
34 to the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
35 Boston, MA 02111-1307 USA.
36 
37 This software was developed with the assistance of Government
38 sponsorship related to Government Contract
39 Number F33615-03-D-3306. The Government retains certain rights to this
40 software under that Contract.
41 
42 
43 For more information about Project X, please contact:
44 
45 
46 David L. Darmofal
47 Department of Aeronautics & Astronautics
48 Massachusetts Institute of Technology
49 77 Massachusetts Ave, Room 37-401
50 Cambridge, MA 02139
51 
52 Phone: (617) 258-0743
53 FAX: (617) 258-5143
54 
55 E-MAIL: [email protected]
56 URL: http://raphael.mit.edu
57 
58 */
59 
60 /*
61 This file is part of ``kdtree'', a library for working with kd-trees.
62 Copyright (C) 2007-2009 John Tsiombikas <[email protected]>
63 
64 Redistribution and use in source and binary forms, with or without
65 modification, are permitted provided that the following conditions are met:
66 
67 1. Redistributions of source code must retain the above copyright notice, this
68  list of conditions and the following disclaimer.
69 2. Redistributions in binary form must reproduce the above copyright notice,
70  this list of conditions and the following disclaimer in the documentation
71  and/or other materials provided with the distribution.
72 3. The name of the author may not be used to endorse or promote products
73  derived from this software without specific prior written permission.
74 
75 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
76 WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
77 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
78 EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
79 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
80 OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
81 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
82 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
83 IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
84 OF SUCH DAMAGE.
85 */
86 
87 #ifdef CH_LANG_CC
88 /*
89  * _______ __
90  * / ___/ / ___ __ _ / / ___
91  * / /__/ _ \/ _ \/ V \/ _ \/ _ \
92  * \___/_//_/\___/_/_/_/_.__/\___/
93  * Please refer to Copyright.txt, in Chombo's root directory.
94  */
95 #endif
96 
97 #ifndef _KDTREE_H_
98 #define _KDTREE_H_
99 
100 #ifndef USE_LIST_NODE_ALLOCATOR
101 #define USE_LIST_NODE_ALLOCATOR 1
102 #endif
103 
104 #define RESTRICT __restrict__
105 
106 #include <string>
107 using std::string;
108 
109 #include "KDStruct.H"
110 
111 #include "REAL.H"
112 #include "NamespaceHeader.H" // for Chombo
113 
114 
115  /****************************************************************/
116  /****************************************************************/
117  /****************************************************************/
118  /*******************KDTree GENERAL INFORMATION*******************/
119  /****************************************************************/
120  /****************************************************************/
121  /****************************************************************/
122  /****************************************************************/
123  /* PLEASE be familiar with binary trees, KDTrees,
124  and Linked Lists before using these functions.
125  (See Wikipedia for more info) */
126 
127  /* This file defines functions for interacting with KDTree and ListHead */
128  /* (which is a LinkedList) data structures defined in KDStruct.h */
129 
130  /* This library follows an abstract, object-oriented design methodology. */
131 
132  /* KDTree and ListHead allow for each node to reference any type of data, */
133  /* as long as every node stores the same type. That is, each node */
134  /* has a field: void *data; */
135  /* If you want KDTree/ListHead to free their data when destroyed, */
136  /* you MUST call DataDestructor with a function pointer toan appropriate */
137  /* free() method for the data. */
138 
139  /* KDTrees provide a fast way of searching N k-dimensional data (points).*/
140  /* This library allows the user to find the closest data point to a given */
141  /* query point in log^k(N) time. This library also supports searching for */
142  /* all data points within a given distance of query point. */
143 
144  /* To use KDTree: */
145  /* 1) KDCreate to make a KDTree for k-dimensional data */
146  /* 1a) KDDataDestructor to set the data destructor, if needed. */
147  /* 2) KDInsert the data points (must be done one at a time) */
148  /* NOTE: KDInsert creates a COPY of the input data points */
149  /* 2a) KDInsert2d and KDInsert3d are special cases for 2d and 3d data. */
150  /* 3a) KDNearestNeighbor to search for the nearest data point to a query point */
151  /* 3b) KDNearestRange to search for all data points within some distance of a query */
152  /* Note that NearestRange creates and returns a KDResult list, which must
153  be RELEASED when useage is complete! */
154  /* 4) Call KDFree */
155 
156  /* NOTE: a KDTree with dim<<1 is the same as a Binary Tree. */
157  /* Feel free to use KDTree for this purpose, but remember that a delete */
158  /* function DOES NOT currently exist! */
159 
160  /* FUTURE: KDResult will be removed, and KDTree will use ListHead objects
161  to return the results of KDNearestRange. */
162 
163  /****************************************************************/
164  /****************************************************************/
165  /****************************************************************/
166  /*******************ListHead GENERAL INFORMATION*****************/
167  /****************************************************************/
168  /****************************************************************/
169  /****************************************************************/
170  /****************************************************************/
171 
172  /* ListHead objects "own" LinkedLists (LList). For maximum abstraction, the */
173  /* user CANNOT interact with ListNodes directly. Instead they must */
174  /* use the LList.* functions (described below). ListHead objects provide */
175  /* way to iterate over ListNodes and insert/delete nodes. */
176 
177  /* As with KDTree, LinkedLists allow for arbitrary data to be stored at */
178  /* each ListNode. Again, LListDataDestructor MUST be called if you want */
179  /* LList to free these data when the LList is destroyed */
180 
181  /* To use Linked Lists: */
182  /* 1) LListCreate to create a ListHead. The linked list owned by */
183  /* the ListHead can be ordered by a Real key or unordered. */
184  /* 1a) LListDataDestructor if needed (see KDTree for more details) */
185  /* INSERT: */
186  /* 2) LListInsert to insert nodes with optional data. LListInsert will
187  insert in order if the associated ListHead is ordered. Otherwise
188  it will insert at the current iterator position. */
189  /* 2a) LListInsertFirst inserts a node at the front of the list. If the
190  list is ordered, the node will be inserted in order. */
191  /* ITERATORS: */
192  /* Since users CANNOT interact with the LinkedList directly, an iterator is*/
193  /* provided (as in Java) to allow users to navigate the list. */
194  /* 3a) LListRewind sets the iterator to the first node (or to NULL if list is empty) */
195  /* 3b) LListNext increments the iterator. */
196  /* 3c) LListIterIsNull determines if the iterator is pointing to a LList node or not. */
197  /* 3d) LListAtLast determines if the iterator is pointing to the LAST node. */
198  /* 3e) LListItem returns the data stored at the node currently pointed to by the list iterator */
199  /* 3f) LListKey returns the key at the current node. */
200  /* NOTE: the list iterator in ListHead starts off NULL */
201 
202  /* 4) Call LListFree to clear the entire LinkedList and destroy the
203  ListHead object. */
204 
205  /****************************************************************/
206  /****************************************************************/
207  /****************************************************************/
208  /****************************************************************/
209 
210 
211 
212 
213 
214 /*********************************************************************/
215 /*********************************************************************/
216 /*********************************************************************/
217 /************************KDTree FUNCTIONS ****************************/
218 /*********************************************************************/
219 /*********************************************************************/
220 /*********************************************************************/
221 
222 
223 
224 
225 
226 
227  /*
228 typedef struct _kdtree KDTree;
229 struct _kdtree;
230 typedef struct _kdres KDResult;
231 struct _kdres;
232 typedef struct _linkedlisthead ListHead;
233 struct _linkedlisthead;
234  */
235 
236 /******************************************************************/
237  KDTree *KDCreate(int const k, int *ierr);
238 /* create a kd-tree for "k"-dimensional data */
239 
240 /******************************************************************/
241 int KDFree(KDTree *tree);
242 /* free the KDTree (calls KDClear, then destroys the head) */
243 
244 /******************************************************************/
245 int KDClear(KDTree *tree);
246 /* remove all the elements from the tree */
247 /* this does not destroy the head, so the KDTree can be re-filled with */
248 /* new information */
249 
250 
251 /******************************************************************/
252  void KDSetGlobalData(KDTree *tree, void *data);
253 /* if called with non-null 2nd argument, tree's globalData pointer
254  will be set. This functionality is usually used in conjunction
255  with KDSetGlobalDataDestructor, but that is not required.
256 
257  Does not check that tree->globalData is NULL; i.e., this will
258  overwrite any existing pointer
259  */
260 
261 /******************************************************************/
262  int KDSetGlobalDataDestructor(KDTree *tree, void (*destr)(void*));
263 /* if called with non-null 2nd argument, then KDTree
264  guarantees that destr(tree->globalData) will be called by KDFree().
265 
266  tree->globalDestrFlag must be -1 before this call.
267  tree->globalDestrFlag will be set to 1.
268  */
269 
270  void KDGetGlobalData(KDTree *tree, void** data);
271 
272 /******************************************************************/
273 int KDSetDataDestructor(KDTree *tree, void (*destr)(void*));
274 /* if called with non-null 2nd argument, the function provided
275  * will be called on data pointers (see KDinsert) when nodes
276  * are to be removed from the tree.
277 
278  tree->globalDestrFlag must be -1 before this call.
279  tree->globalDestrFlag will be set to 0.
280  */
281 
282 /******************************************************************/
283  int KDInsert(KDTree *tree, Real const *pos, void *data);
284 /* insert a node, specifying its position, and optional data */
285 
286 /******************************************************************/
287  int KDTreeStatistics(KDTree const *tree);
288  /*
289  Prints statistics about the structure of the tree:
290  <>max/min/avg depth printed to stdout
291  <>depth of each leaf printed to "leafDepths.txt"
292  */
293 
294  int KDTreePrint(KDTree const *tree);
295 
296  int KDNodePrint(KDNode const *node,
297  const string &prefix);
298 
299 /******************************************************************/
300  int KDSearch(KDTree const *tree, Real const *pos, int *foundFlag);
301  /* Searches *tree to determine whether a KDNode with coordinate *pos
302  has already been inserted.
303  *foundflag is set to 1 if *pos is pre-existing and 0 otherwise.
304  */
305 
306 /******************************************************************/
307  int KDExhaustiveSearch(KDTree const *tree, Real const *pos, int *numFound);
308  /* Searches the entire KDTree exhaustively for KDNodes holding position pos.
309  FOR UNIT TESTING ONLY. DO NOT USE THIS FUNCTION.
310  */
311 
312 
313 /******************************************************************/
314 int KDNearestNeighbor(KDTree const *tree, Real const* const queryPoint,
315  Real *resultPoint, void **resultData,
316  Real *bestDistSquared, int const approx);
317 
318 
319 /******************************************************************/
320 extern int
321 KDBBoxSearch(KDTree const *tree, Real const * RESTRICT xbb,
322  int *pnData, void ***resultData);
323 /*
324  PURPOSE: returns all tree data items within a bounding box
325 
326  INPUT:
327  tree : tree on which to perform search
328  xbb : bounding box ( xmin, xmax, ymin, ymax .... )
329 
330  OUTPUT:
331  nData : number of tree items inside bounding box
332  resultData : array of data items corresponding to bounding box (reallocated)
333 
334  RETURN: error code
335 */
336 
337 
338 /******************************************************************/
340  Real const *query,
341  Real const range, int *ierr);
342 /* Find any nearest nodes from the specified point within a range.
343  *
344  * This function returns a pointer to a result set, which can be manipulated
345  * by the KDResult_* functions.
346  * The returned pointer can be null as an indication of an error. Otherwise
347  * a valid result set is always returned which may contain 0 or more elements.
348  * The result set must be deallocated with KDResultFree, after use.
349  */
350 
351 
352 /******************************************************************/
353 void KDResultFree(KDResult *set);
354 /* frees a result set returned by KDnearest_range() */
355 
356 /******************************************************************/
357 int KDResultSize(KDResult const *set);
358 /* returns the size of the result set (in elements) */
359 
360 /******************************************************************/
361 void KDResultRewind(KDResult *set);
362 /* rewinds the result set iterator */
363 
364 /******************************************************************/
365 int KDResultEnd(KDResult const *set);
366 /* returns non-zero if the set iterator reached the end after the last element */
367 
368 /******************************************************************/
369 int KDResultNext(KDResult *set);
370 /* advances the result set iterator, returns non-zero on success, zero if
371  * there are no more elements in the result set.
372  */
373 
374 /******************************************************************/
375 void *KDResultItem(KDResult const *set, Real *pos);
376 /* returns the data pointer (can be null) of the current result set item
377  * and optionally sets its position to the pointers(s) if not null.
378  */
379 
380 
381 /******************************************************************/
382 void *KDResultItemData(KDResult const *set);
383 /* equivalent to KDResultItem(set, 0) */
384 
385 
386 
387 
388 /*********************************************************************/
389 /*********************************************************************/
390 /*********************************************************************/
391 /************************LinkedList FUNCTIONS ************************/
392 /*********************************************************************/
393 /*********************************************************************/
394 /*********************************************************************/
395 
396 
397 
398 
399 /******************************************************************/
400  int LListInsert(ListHead *head, void *data,
401  Real const key, int const useListIter);
402 /*
403 Inserts a node with data and key. If head->ordered is 0, then
404 the node will be inserted in order by key (increasing order).
405 
406 If useListIter is 0, behavior is the same as LListInsertFirst.
407 
408 If useListIter is nonzero, unordered insertion places the node AFTER
409 the node that list->listIter points to. Returns -1 if listIter == NULL.
410 Ordered insertion attempts to insert AFTER listIter; if it can't (b/c such
411 an insertion is out of order OR listIter == NULL), then it will search
412 and insert at the correct location.
413 */
414 
415 /******************************************************************/
416  int LListInsertFirst(ListHead *head, void *data,
417  Real const key);
418 /*
419 unordered: Inserts a node with data and key at the head of head->llist.
420 ordered: Begins at the head and searches forward until the correct position
421  for this key is found.
422  */
423 
424 /******************************************************************/
425  ListHead *LListCreate(int const ordered, int *ierr);
426 /* create a linked list object. if ordered == 1, the list will ensure
427  that LListNodes are inserted in order. Else no ordering is guaranteed.*/
428 
429 /******************************************************************/
430  void LListFree(ListHead *head);
431  /*Frees the linked list associated with this ListHead. */
432 
433  /*****************************************************************/
434  /* int LListIndexOf(ListHead *head, void (*isEqual)(void*,void*), void* data1, int goThereFlag, int indexOf);*/
435  /* Using the comparator isEqual(void* data1, void* data2), where *data1
436  is input and *data2 corresponds to the data in some LListNode,
437  IndexOf returns the first occurence of data1 in the list.
438 
439  If there are no occurences, IndexOf = -1.
440 
441  If goThereFlag = 1, the list iterator will point to the node at position
442  indexOf when LListIndexOf completes. If indexOf = -1, the list iterator will
443  be returned to the first node.
444  If goThereFlag = 0, the list iterator will not be changed.
445  */
446 
447 /******************************************************************/
448  int LListSize(ListHead const *head);
449  /*Returns the size of the LinkedList */
450 
451 /******************************************************************/
452  void LListRewind(ListHead *head);
453  /*Rewinds the iterator one step.*/
454 
455 /******************************************************************/
456  int LListIterIsNull(ListHead const *head);
457  /*Returns non-zero if the LinkedList iterator has reached the end of the list.*/
458 
459 /******************************************************************/
460  int LListAtLast(ListHead const *head);
461  /*Returns non-zero if the LinkedList iterator is at the last node of the list.*/
462 
463 
464 /******************************************************************/
465  int LListNext(ListHead *head);
466  /*
467  Advances the LinkedList iterator. Returns non-zero on success; returns zero if there
468  are no more elements (i.e. if LListEnd would return nonzero).
469  */
470 
471 /******************************************************************/
472  void *LListItem(ListHead const *head);
473  /*
474  Returns the data pointer of the LListNode pointed to by head->listIter.
475  Returns NULL if listIter points to nothing.
476  */
477 
478 /******************************************************************/
479  Real LListKey(ListHead const *head);
480  /* Returns the value of the key for the node pointed to by listIter. */
481 
482 /******************************************************************/
483 void LListDataDestructor(ListHead *head, void (*destr)(void*));
484 /* if called with non-null 2nd argument, the function provided
485  * will be called on data pointers (see KDInsert) when nodes
486  * are to be removed from the tree.
487  */
488 
489 #ifdef USE_LIST_NODE_ALLOCATOR
490  void LListFinalize( void );
491  void KDTreeFinalize( void );
492 #endif
493 
494 /*********************************************************************/
495 /*********************************************************************/
496 /*********************************************************************/
497 /************************Stack FUNCTIONS *****************************/
498 /*********************************************************************/
499 /*********************************************************************/
500 /*********************************************************************/
501 
502  void *StackPop(ListHead *head, int *ierr);
503  /* Pop the first node off of the stack.
504  Throws an error if the stack is empty. */
505 
506  /*******************************************************************/
507  int StackPush(ListHead *head, void *data);
508  /* Push a node onto the stack.
509  The node key is NOT set, so it could take any value. */
510 
511  /*******************************************************************/
512  void *StackPopWithKey(ListHead *head, Real *key, int *ierr);
513  /* Pop the first node off of the stack, also returning the key.
514  Throws an error if the stack is empty.
515 
516  WARNING: it is NOT SAFE to call this function with a stack
517  built with StackPush b/c the key is NOT set! */
518 
519  /*******************************************************************/
520  int StackPushWithKey(ListHead *head, void *data, Real const key);
521  /* Push a node onto the stack with a specified key. */
522 
523  /*******************************************************************/
524  ListHead *StackCreate(int *ierr, int const prealloc);
525  /* Create a Stack object. */
526 
527  /*******************************************************************/
528  void StackFree(ListHead *head);
529  /* Free the Stack object, even if the stack is non-empty.
530  This will free all stack members with a warning. */
531 
532 
533 #include "NamespaceFooter.H" // for Chombo
534 
535 #endif /* _KDTREE_H_ */
int KDSetDataDestructor(KDTree *tree, void(*destr)(void *))
KDTree * KDCreate(int const k, int *ierr)
int LListIterIsNull(ListHead const *head)
Definition: KDStruct.H:78
ListHead * LListCreate(int const ordered, int *ierr)
int KDResultEnd(KDResult const *set)
int KDResultSize(KDResult const *set)
void LListDataDestructor(ListHead *head, void(*destr)(void *))
int StackPushWithKey(ListHead *head, void *data, Real const key)
void LListFinalize(void)
Real LListKey(ListHead const *head)
int KDTreePrint(KDTree const *tree)
int LListSize(ListHead const *head)
int LListInsertFirst(ListHead *head, void *data, Real const key)
ListHead * StackCreate(int *ierr, int const prealloc)
void * StackPopWithKey(ListHead *head, Real *key, int *ierr)
int LListNext(ListHead *head)
void LListRewind(ListHead *head)
int LListAtLast(ListHead const *head)
void LListFree(ListHead *head)
int KDFree(KDTree *tree)
KDResult * KDNearestRange(KDTree *kd, Real const *query, Real const range, int *ierr)
int KDClear(KDTree *tree)
int KDBBoxSearch(KDTree const *tree, Real const *RESTRICT xbb, int *pnData, void ***resultData)
int KDNearestNeighbor(KDTree const *tree, Real const *const queryPoint, Real *resultPoint, void **resultData, Real *bestDistSquared, int const approx)
Definition: KDStruct.H:98
int KDNodePrint(KDNode const *node, const string &prefix)
void KDResultRewind(KDResult *set)
void KDGetGlobalData(KDTree *tree, void **data)
double Real
Definition: REAL.H:33
void KDSetGlobalData(KDTree *tree, void *data)
int KDSearch(KDTree const *tree, Real const *pos, int *foundFlag)
Definition: KDStruct.H:111
int KDSetGlobalDataDestructor(KDTree *tree, void(*destr)(void *))
void * KDResultItem(KDResult const *set, Real *pos)
int LListInsert(ListHead *head, void *data, Real const key, int const useListIter)
int KDResultNext(KDResult *set)
void KDTreeFinalize(void)
int StackPush(ListHead *head, void *data)
#define RESTRICT
Definition: KDTree.H:104
void * LListItem(ListHead const *head)
int KDInsert(KDTree *tree, Real const *pos, void *data)
void KDResultFree(KDResult *set)
void * StackPop(ListHead *head, int *ierr)
void * KDResultItemData(KDResult const *set)
Definition: KDStruct.H:125
int KDExhaustiveSearch(KDTree const *tree, Real const *pos, int *numFound)
int KDTreeStatistics(KDTree const *tree)
void StackFree(ListHead *head)