//----------------------------------------------------------------------
// File:			bd_tree.h
// Programmer:		David Mount
// Description:		Declarations for standard bd-tree routines
// Last modified:	01/04/05 (Version 1.0)
//----------------------------------------------------------------------
// Copyright (c) 1997-2005 University of Maryland and Sunil Arya and
// David Mount.  All Rights Reserved.
// 
// This software and related documentation is part of the Approximate
// Nearest Neighbor Library (ANN).  This software is provided under
// the provisions of the Lesser GNU Public License (LGPL).  See the
// file ../ReadMe.txt for further information.
// 
// The University of Maryland (U.M.) and the authors make no
// representations about the suitability or fitness of this software for
// any purpose.  It is provided "as is" without express or implied
// warranty.
//----------------------------------------------------------------------
// History:
//	Revision 0.1  03/04/98
//		Initial release
//	Revision 1.0  04/01/05
//		Changed IN, OUT to ANN_IN, ANN_OUT
//----------------------------------------------------------------------

#ifndef ANN_bd_tree_H
#define ANN_bd_tree_H

#include "ann_x.hpp"					// all ANN includes
#include "kd_tree.hpp"					// kd-tree includes

//----------------------------------------------------------------------
//	bd-tree shrinking node.
//		The main addition in the bd-tree is the shrinking node, which
//		is declared here.
//
//		Shrinking nodes are defined by list of orthogonal halfspaces.
//		These halfspaces define a (possibly unbounded) orthogonal
//		rectangle.  There are two children, in and out.  Points that
//		lie within this rectangle are stored in the in-child, and the
//		other points are stored in the out-child.
//
//		We use a list of orthogonal halfspaces rather than an
//		orthogonal rectangle object because typically the number of
//		sides of the shrinking box will be much smaller than the
//		worst case bound of 2*dim.
//
//		BEWARE: Note that constructor just copies the pointer to the
//		bounding array, but the destructor deallocates it.  This is
//		rather poor practice, but happens to be convenient.  The list
//		is allocated in the bd-tree building procedure rbd_tree() just
//		prior to construction, and is used for no other purposes.
//
//		WARNING: In the near neighbor searching code it is assumed that
//		the list of bounding halfspaces is irredundant, meaning that there
//		are no two distinct halfspaces in the list with the same outward
//		pointing normals.
//----------------------------------------------------------------------

class ANNbd_shrink : public ANNkd_node	// splitting node of a kd-tree
{
	int					n_bnds;			// number of bounding halfspaces
	ANNorthHSArray		bnds;			// list of bounding halfspaces
	ANNkd_ptr			child[2];		// in and out children
public:
	ANNbd_shrink(						// constructor
		int				nb,				// number of bounding halfspaces
		ANNorthHSArray	bds,			// list of bounding halfspaces
		ANNkd_ptr ic=NULL, ANNkd_ptr oc=NULL)	// children
		{
			n_bnds			= nb;				// cutting dimension
			bnds			= bds;				// assign bounds
			child[ANN_IN]	= ic;				// set children
			child[ANN_OUT]	= oc;
		}

	~ANNbd_shrink()						// destructor
		{
			if (child[ANN_IN]!= NULL && child[ANN_IN]!=  KD_TRIVIAL) 
				delete child[ANN_IN];
			if (child[ANN_OUT]!= NULL&& child[ANN_OUT]!= KD_TRIVIAL) 
				delete child[ANN_OUT];
			if (bnds != NULL)
				delete [] bnds;			// delete bounds
		}

	virtual void getStats(						// get tree statistics
				int dim,						// dimension of space
				ANNkdStats &st,					// statistics
				ANNorthRect &bnd_box);			// bounding box
	virtual void print(int level, ostream &out);// print node
	virtual void dump(ostream &out);			// dump node

	virtual void ann_search(ANNdist);			// standard search routine
	virtual void ann_pri_search(ANNdist);		// priority search routine
};

#endif