#ifndef GR_VertTree

#define GR_VertTree 1

#include <vector>

#include "GR_config.h"
#include "GR_VarArrayBase.h"

#define iMaxVertsPerNode 10

///
class VertTree {
  ///
  double adMin[3], adMax[3];
  ///
  int iNVerts, iDim, iNumOct;
  ///
  Vert* apV[iMaxVertsPerNode];
  int aiV[iMaxVertsPerNode];
  ///
  VertTree *apChild[8];
  ///
  // For 2D cases, the lower octants are used.
  enum eOctantID {eLower = 0, eUpper = 4,
		  eSouth = 0, eNorth = 2,
		  eWest = 0, eEast = 1,
		  eSouthWest = eSouth + eWest,
		  eSouthEast = eSouth + eEast,
		  eNorthWest = eNorth + eWest,
		  eNorthEast = eNorth + eEast,
		  eLowerSouthWest = eLower + eSouth + eWest,
		  eLowerSouthEast = eLower + eSouth + eEast,
		  eLowerNorthWest = eLower + eNorth + eWest,
		  eLowerNorthEast = eLower + eNorth + eEast,
		  eUpperSouthWest = eUpper + eSouth + eWest,
		  eUpperSouthEast = eUpper + eSouth + eEast,
		  eUpperNorthWest = eUpper + eNorth + eWest,
		  eUpperNorthEast = eUpper + eNorth + eEast};
  ///
  int iWhichOctant(const double adTest[], const double adMean[]) const;
  void vChildOctantBounds(const int iOct,
			  double adNewMin[], double adNewMax[]) const;
  VertTree(const VertTree&) {assert(0);}
  const VertTree& operator=(const VertTree&) {assert(0); return(*this);}
public:
  ///
  VertTree(const VAVertex& VA);
  ///
  VertTree(const int iNVerts, Vert * const apV[], const int aiV[],
	   const double adMin[], const double adMax[]);
  ///
  ~VertTree();
  ///
  void vAddPoint(const int iV, Vert* const pVNew);
  ///
  std::vector<Vert*> vecpVRangeQuery(const double adLo[],
				     const double adHi[]) const;
  std::vector<int> veciRangeQuery(const double adLo[],
				  const double adHi[]) const;
  std::vector<int> veciBallQuery(const double adCenter[],
				 const double dRad) const;
  std::vector<int> veciHalfSpaceQuery(const double adNorm[],
				      const double dDist,
				      const double adSamplePt[]) const;
  std::vector<int> veciAllChildren() const;
};

#endif
