00001 /* 00002 00003 LICENSE NOTICE 00004 00005 This source code is a part of the Project X software library. Project X 00006 solves partial differential equations 00007 in multiple dimensions using an adaptive, discontinuous Galerkin finite 00008 element method, and has been 00009 specifically designed to solve the compressible Euler and Navier-Stokes 00010 equations. 00011 00012 Copyright © 2003-2007 Massachusetts Institute of Technology 00013 00014 00015 00016 This library is free software; you can redistribute it and/or modify it 00017 under the terms of the GNU Lesser 00018 General Public License as published by the Free Software Foundation; 00019 either version 2.1 of the License, 00020 or (at your option) any later version. 00021 00022 00023 00024 This library is distributed in the hope that it will be useful, but 00025 WITHOUT ANY WARRANTY; without even the 00026 implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 00027 See the GNU Lesser 00028 General Public License in lgpl.txt for more details. 00029 00030 00031 00032 You should have received a copy of the GNU Lesser General Public License 00033 along with this library; if not, write 00034 to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, 00035 Boston, MA 02111-1307 USA. 00036 00037 This software was developed with the assistance of Government 00038 sponsorship related to Government Contract 00039 Number F33615-03-D-3306. The Government retains certain rights to this 00040 software under that Contract. 00041 00042 00043 For more information about Project X, please contact: 00044 00045 00046 David L. Darmofal 00047 Department of Aeronautics & Astronautics 00048 Massachusetts Institute of Technology 00049 77 Massachusetts Ave, Room 37-401 00050 Cambridge, MA 02139 00051 00052 Phone: (617) 258-0743 00053 FAX: (617) 258-5143 00054 00055 E-MAIL: [email protected] 00056 URL: http://raphael.mit.edu 00057 00058 */ 00059 00060 /* 00061 This file is part of ``kdtree'', a library for working with kd-trees. 00062 Copyright (C) 2007-2009 John Tsiombikas <[email protected]> 00063 00064 Redistribution and use in source and binary forms, with or without 00065 modification, are permitted provided that the following conditions are met: 00066 00067 1. Redistributions of source code must retain the above copyright notice, this 00068 list of conditions and the following disclaimer. 00069 2. Redistributions in binary form must reproduce the above copyright notice, 00070 this list of conditions and the following disclaimer in the documentation 00071 and/or other materials provided with the distribution. 00072 3. The name of the author may not be used to endorse or promote products 00073 derived from this software without specific prior written permission. 00074 00075 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED 00076 WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 00077 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO 00078 EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 00079 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT 00080 OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 00081 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 00082 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 00083 IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY 00084 OF SUCH DAMAGE. 00085 */ 00086 00087 #ifdef CH_LANG_CC 00088 /* 00089 * _______ __ 00090 * / ___/ / ___ __ _ / / ___ 00091 * / /__/ _ \/ _ \/ V \/ _ \/ _ \ 00092 * \___/_//_/\___/_/_/_/_.__/\___/ 00093 * Please refer to Copyright.txt, in Chombo's root directory. 00094 */ 00095 #endif 00096 00097 #ifndef _KDTREE_H_ 00098 #define _KDTREE_H_ 00099 00100 #ifndef USE_LIST_NODE_ALLOCATOR 00101 #define USE_LIST_NODE_ALLOCATOR 1 00102 #endif 00103 00104 #define RESTRICT __restrict__ 00105 00106 #include <string> 00107 using std::string; 00108 00109 #include "KDStruct.H" 00110 00111 #include "REAL.H" 00112 #include "NamespaceHeader.H" // for Chombo 00113 00114 00115 /****************************************************************/ 00116 /****************************************************************/ 00117 /****************************************************************/ 00118 /*******************KDTree GENERAL INFORMATION*******************/ 00119 /****************************************************************/ 00120 /****************************************************************/ 00121 /****************************************************************/ 00122 /****************************************************************/ 00123 /* PLEASE be familiar with binary trees, KDTrees, 00124 and Linked Lists before using these functions. 00125 (See Wikipedia for more info) */ 00126 00127 /* This file defines functions for interacting with KDTree and ListHead */ 00128 /* (which is a LinkedList) data structures defined in KDStruct.h */ 00129 00130 /* This library follows an abstract, object-oriented design methodology. */ 00131 00132 /* KDTree and ListHead allow for each node to reference any type of data, */ 00133 /* as long as every node stores the same type. That is, each node */ 00134 /* has a field: void *data; */ 00135 /* If you want KDTree/ListHead to free their data when destroyed, */ 00136 /* you MUST call DataDestructor with a function pointer toan appropriate */ 00137 /* free() method for the data. */ 00138 00139 /* KDTrees provide a fast way of searching N k-dimensional data (points).*/ 00140 /* This library allows the user to find the closest data point to a given */ 00141 /* query point in log^k(N) time. This library also supports searching for */ 00142 /* all data points within a given distance of query point. */ 00143 00144 /* To use KDTree: */ 00145 /* 1) KDCreate to make a KDTree for k-dimensional data */ 00146 /* 1a) KDDataDestructor to set the data destructor, if needed. */ 00147 /* 2) KDInsert the data points (must be done one at a time) */ 00148 /* NOTE: KDInsert creates a COPY of the input data points */ 00149 /* 2a) KDInsert2d and KDInsert3d are special cases for 2d and 3d data. */ 00150 /* 3a) KDNearestNeighbor to search for the nearest data point to a query point */ 00151 /* 3b) KDNearestRange to search for all data points within some distance of a query */ 00152 /* Note that NearestRange creates and returns a KDResult list, which must 00153 be RELEASED when useage is complete! */ 00154 /* 4) Call KDFree */ 00155 00156 /* NOTE: a KDTree with dim<<1 is the same as a Binary Tree. */ 00157 /* Feel free to use KDTree for this purpose, but remember that a delete */ 00158 /* function DOES NOT currently exist! */ 00159 00160 /* FUTURE: KDResult will be removed, and KDTree will use ListHead objects 00161 to return the results of KDNearestRange. */ 00162 00163 /****************************************************************/ 00164 /****************************************************************/ 00165 /****************************************************************/ 00166 /*******************ListHead GENERAL INFORMATION*****************/ 00167 /****************************************************************/ 00168 /****************************************************************/ 00169 /****************************************************************/ 00170 /****************************************************************/ 00171 00172 /* ListHead objects "own" LinkedLists (LList). For maximum abstraction, the */ 00173 /* user CANNOT interact with ListNodes directly. Instead they must */ 00174 /* use the LList.* functions (described below). ListHead objects provide */ 00175 /* way to iterate over ListNodes and insert/delete nodes. */ 00176 00177 /* As with KDTree, LinkedLists allow for arbitrary data to be stored at */ 00178 /* each ListNode. Again, LListDataDestructor MUST be called if you want */ 00179 /* LList to free these data when the LList is destroyed */ 00180 00181 /* To use Linked Lists: */ 00182 /* 1) LListCreate to create a ListHead. The linked list owned by */ 00183 /* the ListHead can be ordered by a Real key or unordered. */ 00184 /* 1a) LListDataDestructor if needed (see KDTree for more details) */ 00185 /* INSERT: */ 00186 /* 2) LListInsert to insert nodes with optional data. LListInsert will 00187 insert in order if the associated ListHead is ordered. Otherwise 00188 it will insert at the current iterator position. */ 00189 /* 2a) LListInsertFirst inserts a node at the front of the list. If the 00190 list is ordered, the node will be inserted in order. */ 00191 /* ITERATORS: */ 00192 /* Since users CANNOT interact with the LinkedList directly, an iterator is*/ 00193 /* provided (as in Java) to allow users to navigate the list. */ 00194 /* 3a) LListRewind sets the iterator to the first node (or to NULL if list is empty) */ 00195 /* 3b) LListNext increments the iterator. */ 00196 /* 3c) LListIterIsNull determines if the iterator is pointing to a LList node or not. */ 00197 /* 3d) LListAtLast determines if the iterator is pointing to the LAST node. */ 00198 /* 3e) LListItem returns the data stored at the node currently pointed to by the list iterator */ 00199 /* 3f) LListKey returns the key at the current node. */ 00200 /* NOTE: the list iterator in ListHead starts off NULL */ 00201 00202 /* 4) Call LListFree to clear the entire LinkedList and destroy the 00203 ListHead object. */ 00204 00205 /****************************************************************/ 00206 /****************************************************************/ 00207 /****************************************************************/ 00208 /****************************************************************/ 00209 00210 00211 00212 00213 00214 /*********************************************************************/ 00215 /*********************************************************************/ 00216 /*********************************************************************/ 00217 /************************KDTree FUNCTIONS ****************************/ 00218 /*********************************************************************/ 00219 /*********************************************************************/ 00220 /*********************************************************************/ 00221 00222 00223 00224 00225 00226 00227 /* 00228 typedef struct _kdtree KDTree; 00229 struct _kdtree; 00230 typedef struct _kdres KDResult; 00231 struct _kdres; 00232 typedef struct _linkedlisthead ListHead; 00233 struct _linkedlisthead; 00234 */ 00235 00236 /******************************************************************/ 00237 KDTree *KDCreate(int const k, int *ierr); 00238 /* create a kd-tree for "k"-dimensional data */ 00239 00240 /******************************************************************/ 00241 int KDFree(KDTree *tree); 00242 /* free the KDTree (calls KDClear, then destroys the head) */ 00243 00244 /******************************************************************/ 00245 int KDClear(KDTree *tree); 00246 /* remove all the elements from the tree */ 00247 /* this does not destroy the head, so the KDTree can be re-filled with */ 00248 /* new information */ 00249 00250 00251 /******************************************************************/ 00252 void KDSetGlobalData(KDTree *tree, void *data); 00253 /* if called with non-null 2nd argument, tree's globalData pointer 00254 will be set. This functionality is usually used in conjunction 00255 with KDSetGlobalDataDestructor, but that is not required. 00256 00257 Does not check that tree->globalData is NULL; i.e., this will 00258 overwrite any existing pointer 00259 */ 00260 00261 /******************************************************************/ 00262 int KDSetGlobalDataDestructor(KDTree *tree, void (*destr)(void*)); 00263 /* if called with non-null 2nd argument, then KDTree 00264 guarantees that destr(tree->globalData) will be called by KDFree(). 00265 00266 tree->globalDestrFlag must be -1 before this call. 00267 tree->globalDestrFlag will be set to 1. 00268 */ 00269 00270 void KDGetGlobalData(KDTree *tree, void** data); 00271 00272 /******************************************************************/ 00273 int KDSetDataDestructor(KDTree *tree, void (*destr)(void*)); 00274 /* if called with non-null 2nd argument, the function provided 00275 * will be called on data pointers (see KDinsert) when nodes 00276 * are to be removed from the tree. 00277 00278 tree->globalDestrFlag must be -1 before this call. 00279 tree->globalDestrFlag will be set to 0. 00280 */ 00281 00282 /******************************************************************/ 00283 int KDInsert(KDTree *tree, Real const *pos, void *data); 00284 /* insert a node, specifying its position, and optional data */ 00285 00286 /******************************************************************/ 00287 int KDTreeStatistics(KDTree const *tree); 00288 /* 00289 Prints statistics about the structure of the tree: 00290 <>max/min/avg depth printed to stdout 00291 <>depth of each leaf printed to "leafDepths.txt" 00292 */ 00293 00294 int KDTreePrint(KDTree const *tree); 00295 00296 int KDNodePrint(KDNode const *node, 00297 const string &prefix); 00298 00299 /******************************************************************/ 00300 int KDSearch(KDTree const *tree, Real const *pos, int *foundFlag); 00301 /* Searches *tree to determine whether a KDNode with coordinate *pos 00302 has already been inserted. 00303 *foundflag is set to 1 if *pos is pre-existing and 0 otherwise. 00304 */ 00305 00306 /******************************************************************/ 00307 int KDExhaustiveSearch(KDTree const *tree, Real const *pos, int *numFound); 00308 /* Searches the entire KDTree exhaustively for KDNodes holding position pos. 00309 FOR UNIT TESTING ONLY. DO NOT USE THIS FUNCTION. 00310 */ 00311 00312 00313 /******************************************************************/ 00314 int KDNearestNeighbor(KDTree const *tree, Real const* const queryPoint, 00315 Real *resultPoint, void **resultData, 00316 Real *bestDistSquared, int const approx); 00317 00318 00319 /******************************************************************/ 00320 extern int 00321 KDBBoxSearch(KDTree const *tree, Real const * RESTRICT xbb, 00322 int *pnData, void ***resultData); 00323 /* 00324 PURPOSE: returns all tree data items within a bounding box 00325 00326 INPUT: 00327 tree : tree on which to perform search 00328 xbb : bounding box ( xmin, xmax, ymin, ymax .... ) 00329 00330 OUTPUT: 00331 nData : number of tree items inside bounding box 00332 resultData : array of data items corresponding to bounding box (reallocated) 00333 00334 RETURN: error code 00335 */ 00336 00337 00338 /******************************************************************/ 00339 KDResult *KDNearestRange(KDTree *kd, 00340 Real const *query, 00341 Real const range, int *ierr); 00342 /* Find any nearest nodes from the specified point within a range. 00343 * 00344 * This function returns a pointer to a result set, which can be manipulated 00345 * by the KDResult_* functions. 00346 * The returned pointer can be null as an indication of an error. Otherwise 00347 * a valid result set is always returned which may contain 0 or more elements. 00348 * The result set must be deallocated with KDResultFree, after use. 00349 */ 00350 00351 00352 /******************************************************************/ 00353 void KDResultFree(KDResult *set); 00354 /* frees a result set returned by KDnearest_range() */ 00355 00356 /******************************************************************/ 00357 int KDResultSize(KDResult const *set); 00358 /* returns the size of the result set (in elements) */ 00359 00360 /******************************************************************/ 00361 void KDResultRewind(KDResult *set); 00362 /* rewinds the result set iterator */ 00363 00364 /******************************************************************/ 00365 int KDResultEnd(KDResult const *set); 00366 /* returns non-zero if the set iterator reached the end after the last element */ 00367 00368 /******************************************************************/ 00369 int KDResultNext(KDResult *set); 00370 /* advances the result set iterator, returns non-zero on success, zero if 00371 * there are no more elements in the result set. 00372 */ 00373 00374 /******************************************************************/ 00375 void *KDResultItem(KDResult const *set, Real *pos); 00376 /* returns the data pointer (can be null) of the current result set item 00377 * and optionally sets its position to the pointers(s) if not null. 00378 */ 00379 00380 00381 /******************************************************************/ 00382 void *KDResultItemData(KDResult const *set); 00383 /* equivalent to KDResultItem(set, 0) */ 00384 00385 00386 00387 00388 /*********************************************************************/ 00389 /*********************************************************************/ 00390 /*********************************************************************/ 00391 /************************LinkedList FUNCTIONS ************************/ 00392 /*********************************************************************/ 00393 /*********************************************************************/ 00394 /*********************************************************************/ 00395 00396 00397 00398 00399 /******************************************************************/ 00400 int LListInsert(ListHead *head, void *data, 00401 Real const key, int const useListIter); 00402 /* 00403 Inserts a node with data and key. If head->ordered is 0, then 00404 the node will be inserted in order by key (increasing order). 00405 00406 If useListIter is 0, behavior is the same as LListInsertFirst. 00407 00408 If useListIter is nonzero, unordered insertion places the node AFTER 00409 the node that list->listIter points to. Returns -1 if listIter == NULL. 00410 Ordered insertion attempts to insert AFTER listIter; if it can't (b/c such 00411 an insertion is out of order OR listIter == NULL), then it will search 00412 and insert at the correct location. 00413 */ 00414 00415 /******************************************************************/ 00416 int LListInsertFirst(ListHead *head, void *data, 00417 Real const key); 00418 /* 00419 unordered: Inserts a node with data and key at the head of head->llist. 00420 ordered: Begins at the head and searches forward until the correct position 00421 for this key is found. 00422 */ 00423 00424 /******************************************************************/ 00425 ListHead *LListCreate(int const ordered, int *ierr); 00426 /* create a linked list object. if ordered == 1, the list will ensure 00427 that LListNodes are inserted in order. Else no ordering is guaranteed.*/ 00428 00429 /******************************************************************/ 00430 void LListFree(ListHead *head); 00431 /*Frees the linked list associated with this ListHead. */ 00432 00433 /*****************************************************************/ 00434 /* int LListIndexOf(ListHead *head, void (*isEqual)(void*,void*), void* data1, int goThereFlag, int indexOf);*/ 00435 /* Using the comparator isEqual(void* data1, void* data2), where *data1 00436 is input and *data2 corresponds to the data in some LListNode, 00437 IndexOf returns the first occurence of data1 in the list. 00438 00439 If there are no occurences, IndexOf = -1. 00440 00441 If goThereFlag = 1, the list iterator will point to the node at position 00442 indexOf when LListIndexOf completes. If indexOf = -1, the list iterator will 00443 be returned to the first node. 00444 If goThereFlag = 0, the list iterator will not be changed. 00445 */ 00446 00447 /******************************************************************/ 00448 int LListSize(ListHead const *head); 00449 /*Returns the size of the LinkedList */ 00450 00451 /******************************************************************/ 00452 void LListRewind(ListHead *head); 00453 /*Rewinds the iterator one step.*/ 00454 00455 /******************************************************************/ 00456 int LListIterIsNull(ListHead const *head); 00457 /*Returns non-zero if the LinkedList iterator has reached the end of the list.*/ 00458 00459 /******************************************************************/ 00460 int LListAtLast(ListHead const *head); 00461 /*Returns non-zero if the LinkedList iterator is at the last node of the list.*/ 00462 00463 00464 /******************************************************************/ 00465 int LListNext(ListHead *head); 00466 /* 00467 Advances the LinkedList iterator. Returns non-zero on success; returns zero if there 00468 are no more elements (i.e. if LListEnd would return nonzero). 00469 */ 00470 00471 /******************************************************************/ 00472 void *LListItem(ListHead const *head); 00473 /* 00474 Returns the data pointer of the LListNode pointed to by head->listIter. 00475 Returns NULL if listIter points to nothing. 00476 */ 00477 00478 /******************************************************************/ 00479 Real LListKey(ListHead const *head); 00480 /* Returns the value of the key for the node pointed to by listIter. */ 00481 00482 /******************************************************************/ 00483 void LListDataDestructor(ListHead *head, void (*destr)(void*)); 00484 /* if called with non-null 2nd argument, the function provided 00485 * will be called on data pointers (see KDInsert) when nodes 00486 * are to be removed from the tree. 00487 */ 00488 00489 #ifdef USE_LIST_NODE_ALLOCATOR 00490 void LListFinalize( void ); 00491 void KDTreeFinalize( void ); 00492 #endif 00493 00494 /*********************************************************************/ 00495 /*********************************************************************/ 00496 /*********************************************************************/ 00497 /************************Stack FUNCTIONS *****************************/ 00498 /*********************************************************************/ 00499 /*********************************************************************/ 00500 /*********************************************************************/ 00501 00502 void *StackPop(ListHead *head, int *ierr); 00503 /* Pop the first node off of the stack. 00504 Throws an error if the stack is empty. */ 00505 00506 /*******************************************************************/ 00507 int StackPush(ListHead *head, void *data); 00508 /* Push a node onto the stack. 00509 The node key is NOT set, so it could take any value. */ 00510 00511 /*******************************************************************/ 00512 void *StackPopWithKey(ListHead *head, Real *key, int *ierr); 00513 /* Pop the first node off of the stack, also returning the key. 00514 Throws an error if the stack is empty. 00515 00516 WARNING: it is NOT SAFE to call this function with a stack 00517 built with StackPush b/c the key is NOT set! */ 00518 00519 /*******************************************************************/ 00520 int StackPushWithKey(ListHead *head, void *data, Real const key); 00521 /* Push a node onto the stack with a specified key. */ 00522 00523 /*******************************************************************/ 00524 ListHead *StackCreate(int *ierr, int const prealloc); 00525 /* Create a Stack object. */ 00526 00527 /*******************************************************************/ 00528 void StackFree(ListHead *head); 00529 /* Free the Stack object, even if the stack is non-empty. 00530 This will free all stack members with a warning. */ 00531 00532 00533 #include "NamespaceFooter.H" // for Chombo 00534 00535 #endif /* _KDTREE_H_ */
1.5.5