/*Original code from Frederic Hecht <hecht@ann.jussieu.fr> (BAMG v1.01, QuadTree.h)*/
#ifndef _QUADTREE_H
#define _QUADTREE_H

#include "./include.h"

namespace bamg {

	const int  MaxDeep  = 30;
	const long MaxISize = ( 1L << MaxDeep);  // = 2^30 : 010000000000..000 (bitwise operation)

	class BamgVertex;

	class QuadTree{

		private:

			/*A quadtree box contains a maximum of 4 vertices. 4 other quadtree boxes are
			 * created if a fifth vertex is added to the same box. A Quadtree box is therefore
			 * composed of EITHER:
			 * - up to 4 vertices
			 * - 4 "sub" quadtree boxes*/
			class QuadTreeBox: public Object{ 
				public:
					int nbitems; // number of current vertices in the box
					union{
						QuadTreeBox* b[4];
						BamgVertex*  v[4];
					};
					/*Object functions*/
					void  Echo(){_error_("not implemented yet");};
					void  DeepEcho(){_error_("not implemented yet");};
					int   Id(){_error_("not implemented yet");};
					int   MyRank(){_error_("not implemented yet");};
					int   ObjectEnum(){_error_("not implemented yet");};
					Object* copy(){_error_("not implemented yet");};
			};

			/*QuadTree private Fields*/
			DataSet* boxcontainer;

		public:

			/*QuadTree public Fields*/
			QuadTreeBox* root;
			long         NbQuadTreeBox;
			long         NbVertices;

			QuadTree();
			QuadTree(Mesh *t,long nbv=-1);
			~QuadTree();

			BamgVertex*  NearestVertex(Icoor1 i,Icoor1 j);
			BamgVertex*  NearestVertexWithNormal(Icoor1 i,Icoor1 j);
			QuadTreeBox* NewQuadTreeBox(void);
			BamgVertex*  ToClose(BamgVertex & ,double ,Icoor1,Icoor1);
			void         Add( BamgVertex & w);

	};
}
#endif
