/********************************************************
** Copyright 1999 Earth Resource Mapping Ltd.
** This document contains proprietary source code of
** Earth Resource Mapping Ltd, and can only be used under
** one of the three licenses as described in the 
** license.txt file supplied with this distribution. 
** See separate license.txt file for license details 
** and conditions.
**
** This software is covered by US patent #6,442,298,
** #6,102,897 and #6,633,688.  Rights to use these patents 
** is included in the license agreements.
**
** FILE:    NCSQTree.h
** CREATED: Thu Feb 25 09:19:00 WST 1999
** AUTHOR:  Mark Sheridan
** PURPOSE: Generic Quad tree class for NCS. User should
**			inherit directly from this class and supply
**			the required virtual functions
** EDITS:
 *******************************************************/

#ifndef NCSQUADTREE_H
#define NCSQUADTREE_H

#include "NCSTypes.h"
#include "NCSErrors.h"
#include "NCSDefs.h"
#include "NCSMalloc.h"
#include "NCSMutex.h"
#include <math.h>
#if (defined(WIN32) && !defined(_WIN32_WCE))
#include <crtdbg.h>
#endif

#define NCSQTreeGetNodeQuad1(pNode) (pNode->nw)
#define NCSQTreeGetNodeQuad2(pNode) (pNode->ne)
#define NCSQTreeGetNodeQuad3(pNode) (pNode->se)
#define NCSQTreeGetNodeQuad4(pNode) (pNode->sw)
#define NCSQTreeGetNodeData(pNode)  (pNode->pData)
#define NCSQTreeSetNodeData(pNode, pData)  \
	 pNode->pData = (void *)pData

typedef struct NCSQTreeNode {
	void   *pData;				// Pointer to generic data pointer
	UINT32 nID;					// Unique ID of this node
	IEEE8  dWorldX;				// World X coordinate of node
	IEEE8  dWorldY;				// World Y coordinate of node
	struct NCSQTreeNode *nw;	// Pointer to Node in North West
	struct NCSQTreeNode *ne;	// Pointer to Node in North East
	struct NCSQTreeNode *sw;	// Pointer to Node in South West
	struct NCSQTreeNode *se;	// Pointer to Node in South East
} NCSQTreeNode;

typedef enum NCSQTreeAlg{		// The algorithm used to construct the Quad Tree
	NCSQTALG_PRKD,				// PRKD tree algorithm - NOT YET IMPLEMENTED
	NCSQTALG_PR,				// PR tree algorithm
	NCSQTALG_POINT,				// Simple point algorithm
	NCSQTALG_KD,				// KD tree algorithm - NOT YET IMPLEMENTED
	NCSQTALG_MX,				// MX tree algorithm - NOT YET IMPLEMENTED
	NCSQTALG_PMR,				// PMR tree algorithm - NOT YET IMPLEMENTED
	NCSQTALG_SIMPLE_EDGES,		// Edge algorithm - NOT YET IMPLEMENTED
	NCSQTALG_SIMPLE_GRID		// Grid algorithm - NOT YET IMPLEMENTED
} NCSQTreeAlg;

typedef NCSError (*NCSQTreeNodeFunc)(NCSQTreeNode *pNode, void *pInfo);

class __declspec( dllexport ) CNCSQTree  
{

public:
	// Initialisation
	CNCSQTree();
	virtual ~CNCSQTree();
	NCSError InitExtents(NCSCoordSys CSysType, IEEE8 tlx, IEEE8 tly, IEEE8 brx, IEEE8 bry );

	// Node functions
	NCSError	Print( void );
	NCSError	Draw(void *pDrawInfo);
	void		*GetNodeData( NCSQTreeNode *pNode);
	void		SetNodeData (NCSQTreeNode *pNode, void *pData);
	NCSQTreeNode *FindNode( IEEE8 dWorldX, IEEE8 dWorldY, IEEE8 dRadiusX, IEEE8 dRadiusY );

	// Virtual functions
	virtual	NCSError DrawNode(void *pDrawInfo) = 0;
	virtual NCSError PrintNode(NCSQTreeNode *pNode) = 0;
	virtual void FreeNodeData( void *pData );

	// Node creation-free
	NCSQTreeNode * FreeNode(NCSQTreeNode *pNode);
	NCSQTreeNode * AddNode( void *pNodeData , IEEE8 dWorldX, IEEE8 dWorldY );	

	// Algorithm functions
	NCSError SetAlgorithm(NCSQTreeAlg nAlg);
	NCSQTreeAlg GetAlgorithm();

	// Tree traversal - use custom traverse function "pFunction".
	NCSError Traverse(NCSQTreeNodeFunc pFunction, void *pData);

	// Miscellaneous routines
	NCSError Balance(void);

private:
	NCSQTreeNode * DrawInternal( void *pDrawInfo, NCSQTreeNode *pRoot);
	NCSQTreeNode * FindNodeInternal (NCSQTreeNode *pRoot, IEEE8 latitude, IEEE8 longitude);
	NCSQTreeNode * AddNodeInternalPR( NCSQTreeNode *pRootNode, void *pData, IEEE8 latitude, IEEE8 longitude, IEEE8 tlx, IEEE8 tly, IEEE8 brx, IEEE8 bry);
	NCSQTreeNode * AddNodeInternalPOINT( NCSQTreeNode *pRootNode, void *pData, IEEE8 latitude, IEEE8 longitude);
	NCSQTreeNode * PrintInternal(NCSQTreeNode *pRoot);
	NCSQTreeNode * TraverseNode(NCSQTreeNode *pNode, NCSQTreeNodeFunc pFunction, void *pData);
	NCSQTreeNode * CreateNode(IEEE8 dWorldX, IEEE8 dWorldY, void *pData);

	static NCSError NCSQTreeCalcExtentsFn(NCSQTreeNode *pNode, void *pInfo);
	static NCSError NCSQTreeCopyFn(NCSQTreeNode *pNode, void *pInfo);
	
	IEEE8	m_WorldTLX;
	IEEE8	m_WorldTLY;
	IEEE8	m_WorldBRX;
	IEEE8	m_WorldBRY;
	INT32	m_NrNodes;
	UINT16	m_CurrDrawLevel;
	IEEE8	m_RadiusDistanceX;
	IEEE8	m_RadiusDistanceY;

	NCSQTreeAlg		m_nAlgorithm;
	NCSQTreeNode	* m_pRootNode;
	NCSCoordSys		m_CoordSys;
	NCSQTreeNode	*m_pFindNodeResult;
	NCSMutex		m_TraverseMutex;
};

#endif