#ifndef GR_ADT

#define GR_ADT 1

#include "GR_config.h"

#include <vector>
#include "GR_VarArrayBase.h"
#include "GR_Vertex.h"

struct sADTSort {
public:
  double dKey, *pdData;
  int iInd;
  sADTSort() : dKey(0), pdData(NULL), iInd(0) {}
  sADTSort(const int iDataSize, const double dKeyIn,
	   const double adDataIn[], const int iIndIn) :
    dKey(dKeyIn), pdData(0), iInd(iIndIn)
  {
    assert(iDataSize >= 0);
    assert(iInd >= 0);
    pdData = new double[iDataSize];
    for (int i = 0; i < iDataSize; i++) {
      pdData[i] = adDataIn[i];
    }
  }
  void vSetData(const int iDataSize, const double dKeyIn,
		const double adDataIn[], const int iIndIn) {
    assert(iDataSize >= 0);
    assert(iIndIn >= 0);
    dKey = dKeyIn;
    iInd = iIndIn;
    if (pdData != NULL) delete [] pdData;
    pdData = new double[iDataSize];
    for (int i = 0; i < iDataSize; i++) {
      pdData[i] = adDataIn[i];
    }
  }
  void vSetKey(const double dKeyIn) {dKey = dKeyIn;}
  bool operator<(const sADTSort& sADTS) const {
    int iFC = iFuzzyComp(dKey, sADTS.dKey);
    return (iFC == -1 || 
	    (iFC == 0 && iInd < sADTS.iInd));
  }
};


class ADTiterator;

class ADT {
public:
  enum eDataT {ePoints = 1, eBBoxes = 2};
private:
  // Pointers to children and parent.
  ADT *pADT_Left, *pADT_Right, *pADT_Parent;
  // Level within the tree, original index of the data in the input array.
  int iLevel, iDataInd;
  // Number of spatial dimensions of the data
  int iNDim;
  // Data is points or bounding boxes?
  eDataT eDT;
  // A dynamic array storing the data associated with this node.
  double *pdData;
  void vCloneTree(const ADT* const pADTIn);
  void vBuildADT(sADTSort asADTS[], const int iNumObj);
public:
  ADT(ADT * const pADT_ParentIn = NULL, const int iLevIn = -1,
      const int iDataIndIn = -1, const int iNDimIn = 0,
      const eDataT eDTIn = ePoints, const double * const pdDataIn = NULL) :
    pADT_Left(NULL), pADT_Right(NULL),
    pADT_Parent(pADT_ParentIn), iLevel(iLevIn), iDataInd(iDataIndIn),
    iNDim(iNDimIn), eDT(eDTIn), pdData(NULL)
  {
    if (pdDataIn && iNumVars() != 0) {
      pdData = new double[iNumVars()];
      for (int i = iNumVars() - 1; i >= 0; i--) {
	pdData[i] = pdDataIn[i];
      }
    }
  }
  ///
  ADT(const int iNumObj, const int iNumDim, const eDataT eDType,
      const double* const pdData);
  ///
  ADT(const VAVertex* const VAVerts);
  ADT(const ADT&);
  const ADT& operator=(const ADT&);
  ///
  ~ADT()
    {
      if (pdData) {
	delete [] pdData;
	pdData = NULL;
      }
      if (pADT_Left) delete pADT_Left;
      if (pADT_Right) delete pADT_Right;
    }
  ///
  int iDataIndex() const {return (iDataInd);}
  ///
  int iNumVars() const {return (eDT == ePoints) ? iNDim : iNDim*2;}
  ///
  int iDataKey() const {return iLevel % iNumVars();}
  ///
  int iDataKey(const int iLev) const {return iLev % iNumVars();}
  ///
  void vSetDataType(const eDataT eDTIn) {eDT = eDTIn;}
  ///
  void vSetDimensions(const int iNumDim)
  { assert(iNumDim >= 1 && iNumDim <= 3); iNDim = iNumDim; }
  ///
  void vCopyData(const ADT& ADT_In) {
    assert(eDT == ADT_In.eDT);
    assert(iNDim == ADT_In.iNDim);
    assert(pdData != NULL);
    assert(ADT_In.pdData != NULL);
    iLevel = ADT_In.iLevel;
    iDataInd = ADT_In.iDataInd;
    for (int i = iNumVars() - 1; i >= 0; i--) {
      pdData[i] = ADT_In.pdData[i];
    }
  }
  int iTreeLevel() const {return iLevel;}
  ///
  ADT* pADTLeftChild () const {return pADT_Left;}
  ///
  ADT* pADTRightChild() const {return pADT_Right;}
  ///
  ADT* pADTParent() const {return pADT_Parent;}
  ///
  void vSetNodeData(const int iIndex, const double adData[]);
  ///
  int iNumDimensions() const {return iNDim;}
  ///
  void vAddNode(const double adNewData[], const int iInd);
  ///
  std::vector<int> veciRangeQuery(double adRange[]) const;
private:
  void vPointQuery(const double adRange[], std::vector<int>& LiResult) const;
  void vBBoxQuery(const double adRange[], std::vector<int>& LiResult) const;
  void vPointExhaust(const double adRange[], std::vector<int>& LiResult) const;
  void vBBoxExhaust(const double adRange[], std::vector<int>& LiResult) const;
public:
  ///
  const ADT* pADTFindNode(const double adData[], const int iIndSearch) const;
  ///
  const ADT* pADTFindNodeWithMaxValue(const int iKey) const;
  ///
  const ADT* pADTFindNodeWithMinValue(const int iKey) const;
  ///
  void vRemoveNode(const double adData[], const int iInd);
  ///
  void vBalancingPromotion();
  ///
  int iTreeSize() const;
  ///
  int iMaxTreeDepth() const;
  ///
  int iMinTreeDepth() const;
  /// Needed for iterators to work properly.
  typedef ADTiterator iterator;
  iterator begin();
  iterator end();
  const iterator begin() const;
  const iterator end() const;
  void vSpew() const;
  bool qValid() const;
}; // End of ADT declaration

class ADTiterator {
private:
  ADT *pADT;
public:
  ADTiterator(ADT * const pADTIn = NULL) : pADT(pADTIn) {}
  ADTiterator(const ADTiterator& Ai) : pADT(Ai.pADT) {}
  ~ADTiterator() {}

  ADTiterator& operator=(const ADTiterator& Ai)
  {
    pADT = Ai.pADT;
    return (*this);
  }
  ADT& operator*() const {return *pADT;}
  ADT* operator->() const {return pADT;}
  ADTiterator operator++(int)
    {
      if (pADT->pADTRightChild()) {
	*this = pADT->pADTRightChild()->begin();
      }
      else {
	while (pADT->pADTParent() != NULL &&
	       pADT->pADTParent()->pADTRightChild() == pADT) {
	  pADT = pADT->pADTParent();
	}
	pADT = pADT->pADTParent();
      }
      return *this;
    }
  ADTiterator& operator++()
    {
      if (pADT->pADTRightChild()) {
	*this = pADT->pADTRightChild()->begin();
      }
      else {
	while (pADT->pADTParent() != NULL &&
	       pADT->pADTParent()->pADTRightChild() == pADT) {
	  pADT = pADT->pADTParent();
	}
	pADT = pADT->pADTParent();
      }
      return *this;
    }
  friend bool operator==(const ADTiterator& ADTi0, const ADTiterator& ADTi1)
    {
      return ADTi0.pADT == ADTi1.pADT;
    }
  friend bool operator!=(const ADTiterator& ADTi0, const ADTiterator& ADTi1)
    {
      return ADTi0.pADT != ADTi1.pADT;
    }
};

#endif
