/*
 *  Copyright (c) 2011-2012, Los Alamos National Security, LLC.
 *  All rights Reserved.
 *
 *  Copyright 2011-2012. Los Alamos National Security, LLC. This software was produced 
 *  under U.S. Government contract DE-AC52-06NA25396 for Los Alamos National 
 *  Laboratory (LANL), which is operated by Los Alamos National Security, LLC 
 *  for the U.S. Department of Energy. The U.S. Government has rights to use, 
 *  reproduce, and distribute this software.  NEITHER THE GOVERNMENT NOR LOS 
 *  ALAMOS NATIONAL SECURITY, LLC MAKES ANY WARRANTY, EXPRESS OR IMPLIED, OR 
 *  ASSUMES ANY LIABILITY FOR THE USE OF THIS SOFTWARE.  If software is modified
 *  to produce derivative works, such modified software should be clearly marked,
 *  so as not to confuse it with the version available from LANL.
 *
 *  Additionally, redistribution and use in source and binary forms, with or without
 *  modification, are permitted provided that the following conditions are met:
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the Los Alamos National Security, LLC, Los Alamos 
 *       National Laboratory, LANL, the U.S. Government, nor the names of its 
 *       contributors may be used to endorse or promote products derived from 
 *       this software without specific prior written permission.
 *  
 *  THIS SOFTWARE IS PROVIDED BY THE LOS ALAMOS NATIONAL SECURITY, LLC AND 
 *  CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT 
 *  NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 *  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LOS ALAMOS NATIONAL
 *  SECURITY, LLC OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 *  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 *  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
 *  OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 *  WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 *  ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 *  POSSIBILITY OF SUCH DAMAGE.
 *  
 *  CLAMR -- LA-CC-11-094
 *  This research code is being developed as part of the 
 *  2011 X Division Summer Workshop for the express purpose
 *  of a collaborative code for development of ideas in
 *  the implementation of AMR codes for Exascale platforms
 *  
 *  AMR implementation of the Wave code previously developed
 *  as a demonstration code for regular grids on Exascale platforms
 *  as part of the Supercomputing Challenge and Los Alamos 
 *  National Laboratory
 *  
 *  Authors: Bob Robey       XCP-2   brobey@lanl.gov
 *           Neal Davis              davis68@lanl.gov, davis68@illinois.edu
 *           David Nicholaeff        dnic@lanl.gov, mtrxknight@aol.com
 *           Dennis Trujillo         dptrujillo@lanl.gov, dptru10@gmail.com
 *           Other LANL authors
 * 
 * 
 *  Implements a 2-dimensional k-D tree. One begins to use the k-D tree by
 *  adding the bounding box of geometric "elements" to the tree structure
 *  through a call to "KDTreeAddElement". Every element should be of the same
 *  type, but could be a single point, a line segment, triangles, etc. Once
 *  all the element bounding boxes have been added, the user of the structure
 *  may make queries against the tree. The actual tree is constructed lazily
 *  when an actual query occurs on the structure.
 *
 *  This version only has one query -- intersection of a box with the elements
 *  and a set of "candidate" elements are returned. The candidates are identified
 *  by an index number (0, ...) signifying the order in which the element was
 *  added to the tree. It is up to the calling code to do additional processing
 *  based on the type of element being used to determine "real" intersections.
 *
 *  The process of actually building the tree takes "n log n" time. Queries 
 *  take "log n" time.
 *
 */

#ifndef _KDTree_
#define _KDTree_

#ifdef __cplusplus
extern "C"
{
#endif
  

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include "Globals.h"
#include "Bounds.h"
   
#define LEFT_HALF   0
#define RIGHT_HALF  1
#define BOTTOM_HALF 0
#define TOP_HALF    1   

typedef struct {
   TBounds extent;
   int elements_num, elements_allocated;
   TBounds* elements;
   bool tree_built;
   int tree_size;
   TBounds* tree_safety_boxes;
   int * tree_link;
} TKDTree;

extern void KDTree_Initialize(TKDTree *t);
extern void KDTree_Finalize(TKDTree *t);
extern void KDTree_Destroy(TKDTree* t);
extern void KDTree_AddElement(TKDTree* t, TBounds* add);
extern void KDTree_CreateTree(TKDTree* t);
extern void KDTree_QueryBoxIntersect(TKDTree* t,
                                     int* result_num, int* result_indicies,
                                     TBounds* box);

void KDTree_QueryCircleIntersect_Double(TKDTree* t,
                                 int* result_num, int* result_indicies,
                                 double radius, int ncells, 
                                 double *x, double *dx, double *y, double *dy);
void KDTree_QueryCircleIntersect_Float(TKDTree* t,
                                 int* result_num, int* result_indicies,
                                 double radius, int ncells, 
                                 float *x, float *dx, float *y, float *dy);

void KDTree_QueryCircleIntersectWeighted_Double(TKDTree* t,
                                 int* result_num, int* result_indicies, double *weight,
                                 double circ_radius, int ncells, 
                                 double *x, double *dx, double *y, double *dy);
void KDTree_QueryCircleIntersectWeighted_Float(TKDTree* t,
                                 int* result_num, int* result_indicies, double *weight,
                                 double circ_radius, int ncells, 
                                 float *x, float *dx, float *y, float *dy);

void KDTree_QueryCircleInterior_Double(TKDTree* t,
                                 int* result_num, int* result_indicies,
                                 double circ_radius, int ncells, 
                                 double *x, double *dx, double *y, double *dy);
void KDTree_QueryCircleInterior_Float(TKDTree* t,
                                 int* result_num, int* result_indicies,
                                 double circ_radius, int ncells, 
                                 float *x, float *dx, float *y, float *dy);
   
#ifdef __cplusplus
}
#endif

#endif