
#include "Core/Asura.h"

#include "TextureTiler/Tools_TextureTiler_Algorithm.h"

// Core
#include "Core/Asura_TextureFlags.h"
#include "Core/Asura_TextureManagement.h"
#include "Core/Asura_TiledTextureManagement.h"

// Tools
#include "Misc/Tools_Timed_Messages.h"
#include "Texturing/Tools_Texture_Management.h"
#include "TextureTiler/Tools_TextureTiler_Export.h"
#include "TextureTiler/Tools_TextureTiler_Render.h"

// <-- class Tools_TT_Tile -->

Tools_TT_Tile::Tools_TT_Tile( const int iTextureID /* = ASURA_TEXTURE_NONE*/ )
:m_xTextureName()
,m_xUVRectangle()
,m_xImageUV()
,m_xPosition()
,m_xImageDimensions()
,m_xTextureDimensions()
,m_iTextureID(ASURA_TEXTURE_NONE)
,m_bTiled(false)
,m_bValid(false)
{
	SetTexture( iTextureID );
}

Tools_TT_Tile::Tools_TT_Tile( const Tools_TT_Tile& xTile )
:m_xTextureName( xTile.m_xTextureName )
,m_xUVRectangle( xTile.m_xUVRectangle )
,m_xImageUV( xTile.m_xImageUV )
,m_xPosition( xTile.m_xPosition )
,m_xImageDimensions( xTile.m_xImageDimensions )
,m_xTextureDimensions( xTile.m_xTextureDimensions )
,m_iTextureID( xTile.m_iTextureID )
,m_bTiled( xTile.m_bTiled )
,m_bValid( xTile.m_bValid )
{}

Tools_TT_Tile::Tools_TT_Tile( const Asura_TiledTextureInfo& xTileInfo, const int iTextureID )
:m_xUVRectangle( xTileInfo.m_fu1, xTileInfo.m_fv1, xTileInfo.m_fu2, xTileInfo.m_fv2 )
,m_xPosition( static_cast<int>(xTileInfo.m_fu1 * xTileInfo.m_TiledToWidth), static_cast<int>(xTileInfo.m_fv1 * xTileInfo.m_TiledToHeight) )
,m_iTextureID( ASURA_TEXTURE_NONE )
,m_bTiled( true )
,m_bValid( false )
{
	SetTexture( iTextureID );	
}

const bool Tools_TT_Tile::SetTexture( const int iTextureID )
{
	if( iTextureID == ASURA_TEXTURE_NONE )
	{
		return false;
	}

	const Asura_String* pxTextureName( Asura_Texture_Management::GetTextureName( iTextureID ) );

	bool bSuccess(true);

	if( pxTextureName == NULL )
	{
		bSuccess = false;
		Asura_Assert( bSuccess,"Failed to find texture name" );	
	}

	Tools_TT_Vector_2i xTextureDimensions;
	Tools_TT_Vector_2i xImageDimensions;
	
	if( bSuccess )
	{
		bSuccess = Tools_TT_Export_FindTextureAndImageSize( pxTextureName->GetString(),xTextureDimensions.x(),xTextureDimensions.y(),xImageDimensions.x(),xImageDimensions.y() );

		Asura_Assert( bSuccess,"Failed to find texture and image dimensions" );
	}

	if( bSuccess )
	{
		m_iTextureID   = iTextureID;
		m_xTextureName = *pxTextureName;

		m_xTextureDimensions = xTextureDimensions;
		m_xImageDimensions   = xImageDimensions;
		
		m_xImageUV.MinX = 0.0f;
		m_xImageUV.MinY = 0.0f;

		m_xImageUV.MaxX = static_cast<float>(xImageDimensions.x()) / static_cast<float>(xTextureDimensions.x());
		m_xImageUV.MaxY = static_cast<float>(xImageDimensions.y()) / static_cast<float>(xTextureDimensions.y());
		m_bValid = true;
	}

	return bSuccess;
}

void Tools_TT_Tile::Render( const Asura_Bounding_Rectangle& xRectangle,const int iBackgroundColour = Tools_TT_Colour::Null,const ASURA_TRANSLUCENCY_MODE eTranslucency = ASURA_TRANSLUCENCY_OFF ) const
{	
	if( IsTiled() )
	{
		Asura_Bounding_Rectangle xScreenRectangle;

		// calculate screen space coordinates for tile
		xScreenRectangle = GetUVRectangle();
			
		xScreenRectangle.MinX *= xRectangle.GetWidth();
		xScreenRectangle.MinX += xRectangle.MinX;  
		
		xScreenRectangle.MinY *= xRectangle.GetHeight();
		xScreenRectangle.MinY += xRectangle.MinY;

		xScreenRectangle.MaxX *= xRectangle.GetWidth();
		xScreenRectangle.MaxX += xRectangle.MinX;

		xScreenRectangle.MaxY *= xRectangle.GetHeight();
		xScreenRectangle.MaxY += xRectangle.MinY;

		Tools_TT_RenderTexture( xScreenRectangle,m_xImageUV,GetTextureID(),iBackgroundColour,eTranslucency );
	}
}

void Tools_TT_Tile::UpdateUV( const int iTileToWidth, const int iTileToHeight )
{
	if( IsTiled() )
	{	
		// find absolute position and size (in pixels) and scale to screen position and size
		m_xUVRectangle.MinX = static_cast<float>( GetPosition().x() ) / static_cast<float>( iTileToWidth ); 
		m_xUVRectangle.MinY = static_cast<float>( GetPosition().y() ) / static_cast<float>( iTileToHeight );
		m_xUVRectangle.MaxX = static_cast<float>( GetPosition().x() + GetWidth() ) / static_cast<float>( iTileToWidth ); 
		m_xUVRectangle.MaxY = static_cast<float>( GetPosition().y() + GetHeight() ) / static_cast<float>( iTileToHeight );
	}
	else
	{
		m_xUVRectangle.Set( 0.0f,0.0f,0.0f,0.0f );
	}
}

// <-- class rect tree node -->
Tools_TT_RectTreeNode::Tools_TT_RectTreeNode( const Tools_TT_Rectangle_2i& xRect )
{
	m_apxChild[0] = 0;
	m_apxChild[1] = 0;
	m_xRect   = xRect;
	m_bFilled = false;
}

Tools_TT_RectTreeNode::~Tools_TT_RectTreeNode()
{
	if( m_apxChild[0] )
	{
		delete m_apxChild[0];
	}
	if( m_apxChild[1] )
	{
		delete m_apxChild[1];
	}
}
    
const Tools_TT_RectTreeNode* Tools_TT_RectTreeNode::Insert(Tools_TT_Rectangle_2i& xRect)
{
	//is tile too large?
	if(xRect.GetWidth() > m_xRect.GetWidth()) return 0;
	if(xRect.GetHeight() > m_xRect.GetHeight()) return 0;
	
	if(m_apxChild[0])
	{
		//not a leaf , so try inserting a child nodes
		const Tools_TT_RectTreeNode* pxNode = 0;
		pxNode = m_apxChild[0]->Insert(xRect);
		if(!pxNode) pxNode = m_apxChild[1]->Insert(xRect);

		return pxNode;
	}
	else
	{
		//is a tile already inserted here?
		if(m_bFilled) return 0;

		//is space exactly the right size?
		if(xRect.GetWidth() == m_xRect.GetWidth() && xRect.GetHeight() == m_xRect.GetHeight())
		{
			//tile goes here then
			m_bFilled = true;
			return this;
		}

		//need to split need then
		//decide which way to split
		const int iDeltaWidth( m_xRect.GetWidth()-xRect.GetWidth() );
		const int iDeltaHeight( m_xRect.GetHeight()-xRect.GetHeight() );

		Tools_TT_Rectangle_2i xChildRect[2];
		xChildRect[0] = m_xRect;
		xChildRect[1] = m_xRect;

		if( iDeltaWidth > iDeltaHeight )
		{
			//horizontal split
			xChildRect[0].Max().x() = m_xRect.Min().x() + xRect.GetWidth();
			xChildRect[1].Min().x() = m_xRect.Min().x() + xRect.GetWidth();
		}
		else
		{
			//vertical split
			xChildRect[0].Max().y() = m_xRect.Min().y() + xRect.GetHeight();
			xChildRect[1].Min().y() = m_xRect.Min().y() + xRect.GetHeight();
		}

		//create the child nodes
		m_apxChild[0] = new Tools_TT_RectTreeNode(xChildRect[0]);
		m_apxChild[1] = new Tools_TT_RectTreeNode(xChildRect[1]);

		//insert the tile into the first node
		return m_apxChild[0]->Insert(xRect);
	}
}


// <-- tiling algorithms -->
const u_int Tools_TT_DoTiling( Tools_TT_Tile* pxTextureInfo, const u_int uTextureInfoSize, const Tools_TT_Vector_2i& xTextureDimensions, const TOOLS_TT_ALGORITHM_TYPE eAlgorithmType )
{
	// Sort	the	list on	the	height then	the	width of the bitmaps
	Tools_TT_Sort( pxTextureInfo,pxTextureInfo+uTextureInfoSize,OrderForTiling());

	u_int uRetVal(0);

	switch (eAlgorithmType)
	{
		default	: 
		case TOOLS_TT_ALGORITHM_CLASSIC :
			uRetVal = Tools_TT_DoTiling_Classic( pxTextureInfo,uTextureInfoSize,xTextureDimensions );
			break;

		case TOOLS_TT_ALGORITHM_FIRSTAVAILABLESPACE :
			uRetVal	= Tools_TT_DoTiling_FirstAvailableSpace( pxTextureInfo,uTextureInfoSize,xTextureDimensions );
			break;

		case TOOLS_TT_ALGORITHM_RECTTREE :
			uRetVal	= Tools_TT_DoTiling_RectTree( pxTextureInfo,uTextureInfoSize,xTextureDimensions );
			break;

	}

	return uRetVal;

}

const u_int Tools_TT_DoTiling_Classic( Tools_TT_Tile* pxTextureInfo, const u_int uTextureInfoSize, const Tools_TT_Vector_2i& xTextureDimensions )
{
	// array to store all as yet unocupied areas in the TTL
	Tools_TT_Rectangle_2i* pxPotentialArea( new Tools_TT_Rectangle_2i[uTextureInfoSize+1] );
	
	u_int uFirstUnmatchedTile(0);
	u_int uPotentialAreaEnd(0);

	float fCurrentFitness(0.0f);
	float fCurrentBestFitness(0.0f);
	u_int uCurrentBestTile(0);
	u_int uCurrentBestArea(0);
	bool  bAtLeastOneFits(false);
	bool  bNoMatchFoundLastTime(true);

	// create first potential area. This is equal to the size of the TTL as no space has been assigned as yet
	pxPotentialArea[0].Set( Tools_TT_Vector_2i(0,0),xTextureDimensions );
	++uPotentialAreaEnd;

	while( uFirstUnmatchedTile<uTextureInfoSize )
	{
		bAtLeastOneFits = false;

		// iterate over unmatched tiles
		for( u_int uUnmatchedTile(uFirstUnmatchedTile);uUnmatchedTile<uTextureInfoSize;++uUnmatchedTile )
		{
			// reset best fitness for this tile
			fCurrentBestFitness = 0.0f;

			// iterate over remaining unused areas
			for( u_int uPotentialArea(0);uPotentialArea<uPotentialAreaEnd;++uPotentialArea )
			{
				if( Tools_TT_TextureFits( pxPotentialArea[uPotentialArea],pxTextureInfo[uUnmatchedTile] ) )
				{
					bAtLeastOneFits	= true;
					fCurrentFitness	= Tools_TT_AssessTextureFitness( pxPotentialArea[uPotentialArea],pxTextureInfo[uUnmatchedTile]);

					if(fCurrentFitness > fCurrentBestFitness)
					{
						// If this is the best one then	make it	the	one	to add
						fCurrentBestFitness	= fCurrentFitness;
						uCurrentBestTile	= uUnmatchedTile;
						uCurrentBestArea    = uPotentialArea;
					}
				}

			}
		}

		// if a match has been found
		if( bAtLeastOneFits )
		{	
			bNoMatchFoundLastTime = false;

			// set matched tile's position and tiled flag
			pxTextureInfo[uCurrentBestTile].SetPosition( pxPotentialArea[uCurrentBestArea].Min() );
			pxTextureInfo[uCurrentBestTile].SetTiled(true);

			// move matched tile towards begining of tile info array
			Tools_TT_Swap( pxTextureInfo[uCurrentBestTile],pxTextureInfo[uFirstUnmatchedTile] );

			// update current best match index so that it still points to the matched tile
			uCurrentBestTile = uFirstUnmatchedTile;

			// increment first unmatched tile so that this tile will not be scanned next time around
			++uFirstUnmatchedTile;
			
			// create two new areas representing the parts of the matched area which are not 
			// occupied by the matched tile. One of these will replace the matched area and the 
			// other will be added to the potential area array just after the last potential 
			// area stored there.
			
			// create new area below (y) matched tile with width (x) equal to matched tile
			pxPotentialArea[uPotentialAreaEnd].Min().x() = pxPotentialArea[uCurrentBestArea].Min().x();
			pxPotentialArea[uPotentialAreaEnd].Min().y() = pxPotentialArea[uCurrentBestArea].Min().y() + pxTextureInfo[uCurrentBestTile].GetHeight();
			pxPotentialArea[uPotentialAreaEnd].Max().x() = pxPotentialArea[uCurrentBestArea].Min().x() + pxTextureInfo[uCurrentBestTile].GetWidth();
			pxPotentialArea[uPotentialAreaEnd].Max().y() = pxPotentialArea[uCurrentBestArea].Max().y();
			++uPotentialAreaEnd;

			// change matched area to represent area to the right (x direction) of matched tile but with hight (y direction) remaining unchanged
			pxPotentialArea[uCurrentBestArea].Min().x() += pxTextureInfo[uCurrentBestTile].GetWidth();
		}
		else
		{
			// if this is the second cosecutive time that no matches have been found then break;
			if( bNoMatchFoundLastTime ) break;

			// find the largest free rectangle in the TTL
			Tools_TT_Rectangle_2i xNewArea;
			Tools_TT_FindLargestFreeRectangle( pxTextureInfo,uFirstUnmatchedTile,xNewArea,xTextureDimensions );

			// set first potential area equal to the new rectangle and ignore the rest of the potential areas
			pxPotentialArea[0] = xNewArea;
			uPotentialAreaEnd  = 1;

			bNoMatchFoundLastTime = true;
		}
	}

	delete [] pxPotentialArea;

	// return the number of bitmaps that were tiled
	return uFirstUnmatchedTile;
}

const u_int Tools_TT_DoTiling_FirstAvailableSpace( Tools_TT_Tile* pxTextureInfo, const u_int uTextureInfoSize, const Tools_TT_Vector_2i& xTextureDimensions )
{
	// create array to hold all unocupied rectangles in the TTL
	Tools_TT_Rectangle_2i* pxPotentialArea( new Tools_TT_Rectangle_2i[uTextureInfoSize+1] );
	
	u_int uUntiledTexuteCount(0);
	u_int uPotentialAreaEnd(0);
	u_int uArea(0);
	
	// create first potential area. This is equal to the size of the TTL as no space has been assigned as yet
	pxPotentialArea[0].Set( Tools_TT_Vector_2i(0,0),xTextureDimensions );
	++uPotentialAreaEnd;

	for( u_int uTexture(0);uTexture<uTextureInfoSize;++uTexture )
	{
		//try this bitmap in each area until a free one is found
		for( uArea = 0;uArea<uPotentialAreaEnd;++uArea )
		{
			if( !Tools_TT_TextureFits( pxPotentialArea[uArea],pxTextureInfo[uTexture] ) )
				continue;	// Next area 

			// Set the position of the bitmap
			pxTextureInfo[uTexture].SetPosition( pxPotentialArea[uArea].Min() );
			pxTextureInfo[uTexture].SetTiled( true );
			
			// create two new areas representing the parts of the matched area which are not 
			// occupied by the matched tile. One of these will replace the matched area and the 
			// other will be added to the potential area array just after the last potential 
			// area stored there.
			
			// create new area below (y) matched tile and with width (x) equal to matched tile
			pxPotentialArea[uPotentialAreaEnd].Min().x() = pxPotentialArea[uArea].Min().x();
			pxPotentialArea[uPotentialAreaEnd].Min().y() = pxPotentialArea[uArea].Min().y() + pxTextureInfo[uTexture].GetHeight();
			pxPotentialArea[uPotentialAreaEnd].Max().x() = pxPotentialArea[uArea].Min().x() + pxTextureInfo[uTexture].GetWidth();
			pxPotentialArea[uPotentialAreaEnd].Max().y() = pxPotentialArea[uArea].Max().y();
			++uPotentialAreaEnd;

			// change matched area to represent area to the right (x) of matched tile but with hight (y) remaining unchanged
			pxPotentialArea[uArea].Min().x() += pxTextureInfo[uTexture].GetWidth();

			break;
		}

		if( uArea == uPotentialAreaEnd )
		{
			++uUntiledTexuteCount;
			pxTextureInfo[uTexture].SetTiled( false );
		}
	}

	delete [] pxPotentialArea;

	// shift all untiled textures to the end of the collection
	Tools_TT_ShiftElementsToEnd( pxTextureInfo,pxTextureInfo+uTextureInfoSize,IsTiled(),false );

	// return the number of textures successfully tiled
	return uTextureInfoSize - uUntiledTexuteCount;
}


const u_int Tools_TT_DoTiling_RectTree( Tools_TT_Tile* pxTextureInfo, const u_int uTextureInfoSize, const Tools_TT_Vector_2i& xTTLDelta )
{
	//create node for entire texture
	Tools_TT_RectTreeNode* m_pxRootNode( new Tools_TT_RectTreeNode( Tools_TT_Rectangle_2i(0,0,xTTLDelta.x(),xTTLDelta.y()) ) );

	u_int uTiledTextureCount(0);

	//iterate over bitmaps , inserting into tree
	for( u_int u(0);u<uTextureInfoSize;++u )
	{
		//get tiles rectangle
		Tools_TT_Rectangle_2i xTextureRect( 0,0,pxTextureInfo[u].GetWidth(),pxTextureInfo[u].GetHeight() );

		//try inserting
		const Tools_TT_RectTreeNode* pxNode( m_pxRootNode->Insert(xTextureRect) );

		if( pxNode )
		{
			//success
			pxTextureInfo[u].SetTiled( true );
			pxTextureInfo[u].SetPosition( pxNode->GetRect().Min() );
			++uTiledTextureCount;
		}
	}

	//finished with tree
	delete m_pxRootNode;

	// shift all untiled textures to the end of the collection
	Tools_TT_ShiftElementsToEnd( pxTextureInfo,pxTextureInfo+uTextureInfoSize,IsTiled(),false );

	// return the number of textures successfully tiled
	return uTiledTextureCount;
}

const float Tools_TT_AssessTextureFitness( const Tools_TT_Rectangle_2i& xAreaFitInto, const	Tools_TT_Tile& xTools_TT_Tile )
{
	// Use heuristics to determine whether the Tools_TT_Tile will be a	"good fit" into	the	area
	// Heuristics are (in preference:)
	// 1. Fill greatest	% of an	area
	// 2. Fills	greatest % of the width
	// 3. Fills	greatest % of the height
	// 4. Fills	up the least % of an area (worst case if all other heuristics fail)

	//// replaced implicit cast from float to int with explit use of _Chop casting function varient - NDB
	//int	iAreaWidth( Asura_Maths::FloatToInt_Chop( xAreaFitInto.MaxX - xAreaFitInto.MinX ) );
	//int	iAreaHeight( Asura_Maths::FloatToInt_Chop( xAreaFitInto.MaxY - xAreaFitInto.MinY ) );
	//int	iAreaArea( iAreaWidth * iAreaHeight );

	// Assess heuristic	1:
//	float fHeuristic, fTempHeuristic;
//	fHeuristic = 100.0f	* (float)(xTools_TT_Tile.iWidth * xTools_TT_Tile.iHeight)	/ iAreaArea;
	
	// heuristic 2:
//	fTempHeuristic = 1.f * float(xTools_TT_Tile.iHeight) /	iAreaWidth;
//	fHeuristic = fTempHeuristic	> fHeuristic ? fTempHeuristic :	fHeuristic;

	// heuristic 3:
//	fTempHeuristic = 100.f * float(xTools_TT_Tile.iWidth) / iAreaWidth;
//	fHeuristic = fTempHeuristic	> fHeuristic ? fTempHeuristic :	fHeuristic;

	float fHeuristic = 100.0f *	static_cast<float>(xTools_TT_Tile.GetWidth() );

	return fHeuristic;
}

const bool Tools_TT_TextureInRegion( const Tools_TT_Tile* const pxTextureInfo,const u_int uTextureInfoSize,const Tools_TT_Rectangle_2i& xRegion )
{
	bool bInBitmaps(false);
	Tools_TT_Rectangle_2i xBitmapDims;
	
	for( u_int uBitmap(0);uBitmap<uTextureInfoSize;++uBitmap )
	{
		// Build rectangle of bitmap dimensions
		xBitmapDims.Min() = pxTextureInfo[uBitmap].GetPosition();
		xBitmapDims.Max() = Tools_TT_Vector_2i( pxTextureInfo[uBitmap].GetPosition().x() + pxTextureInfo[uBitmap].GetWidth() - 1,
												pxTextureInfo[uBitmap].GetPosition().y() + pxTextureInfo[uBitmap].GetHeight() - 1);
		
		if( Tools_TT_PointInRectangle( xBitmapDims.Min(),xRegion )	||
			Tools_TT_PointInRectangle( xBitmapDims.Max(),xRegion ))
		{
			bInBitmaps = true;
			break;
		}
	}
	return bInBitmaps;
}

const bool Tools_TT_FindLargestFreeRectangle( const Tools_TT_Tile* const pxTextureInfo, const u_int uTextureInfoSize, Tools_TT_Rectangle_2i& xRegion, const Tools_TT_Vector_2i& xTextureDimensions )
{
	// Try and construct new areas from	the	Tools_TT_Tile's already added
	bool bAreaFound(false);
	int	iCurrentMaxArea(0);

	Tools_TT_Rectangle_2i xCurrentMaxArea;
	Tools_TT_Rectangle_2i xNewArea;
	
	xNewArea.Max() = xTextureDimensions;

	for( u_int uBitmap(0);uBitmap<uTextureInfoSize;++uBitmap )
	{
		xNewArea.Min() = Tools_TT_Vector_2i( pxTextureInfo[uBitmap].GetPosition().x() + pxTextureInfo[uBitmap].GetWidth(),
											 pxTextureInfo[uBitmap].GetPosition().y() + pxTextureInfo[uBitmap].GetHeight() );

		if( iCurrentMaxArea < xNewArea.GetWidth() *	xNewArea.GetHeight() && !Tools_TT_TextureInRegion( pxTextureInfo,uTextureInfoSize,xNewArea ))
		{
			xCurrentMaxArea	= xNewArea;
			iCurrentMaxArea	= xNewArea.GetWidth() * xNewArea.GetHeight();
			bAreaFound = true;
		}
	}

	if(bAreaFound)
	{
		xRegion = xCurrentMaxArea;
	}

	return bAreaFound;
}

const bool Tools_TT_TextureFits( const Tools_TT_Rectangle_2i& xAreaFitInto, const Tools_TT_Tile& xTools_TT_Tile )
{
	// Check whether the texture will fit into the rectangle xAreaFitInto if place at
	// point xPointToFitAt
	return (xTools_TT_Tile.GetWidth()  <= xAreaFitInto.GetWidth() &&
			xTools_TT_Tile.GetHeight() <= xAreaFitInto.GetHeight() );
}

