// Copyright (C) 2012-2013 ChaosForge / Kornel Kisielewicz
// http://chaosforge.org/
//
// This file is part of NV Libraries.
// For conditions of distribution and use, see copyright notice in nv.hh

#include "nv/gfx/texture_atlas.hh"

#include "nv/logging.hh"
#include <iostream>

using namespace nv;

texture_atlas::texture_atlas( glm::ivec2 size, size_t depth, size_t border /*= 1*/ )
	: image( size, depth ), m_used( 0 ), m_border( border )
{
	m_nodes.push_back( glm::ivec3( m_border, m_border, m_size.x - 2 * m_border ) );
	fill( 0 );
}

region texture_atlas::get_region( glm::ivec2 size )
{
	region r ( glm::ivec2(0,0), size );

	int best_height = INT_MAX;
	int best_index  = -1;
	int best_width  = INT_MAX;

	for( size_t i=0; i < m_nodes.size(); ++i )
	{
		int y = fit( i, size );
		if ( y >= 0 )
		{
			glm::ivec3 node = m_nodes[ i ];
			if ( ( (y + size.y) < best_height ) ||
				( ((y + size.y) == best_height) && (node.z < best_width)) )
			{
				best_height = y + size.y;
				best_index = static_cast<int>( i );
				best_width = node.z;
				r.pos.x = node.x;
				r.pos.y = y;
			}
		}
	}
   
	if ( best_index == -1 )
	{
		return region( glm::ivec2( -1, -1 ), glm::ivec2( 0, 0 ) );
	}

	m_nodes.insert( m_nodes.begin() + best_index, glm::ivec3( r.pos.x, r.pos.y + size.y, size.x ) );

	for( size_t i = static_cast<size_t>( best_index )+1; i < m_nodes.size(); ++i )
	{
		glm::ivec3 node = m_nodes[ i ];
		glm::ivec3 prev = m_nodes[ i-1 ];

		if ( node.x < prev.x + prev.z )
		{
			int shrink = prev.x + prev.z - node.x;
			m_nodes[ i ].x += shrink;
			m_nodes[ i ].z -= shrink;

			if ( m_nodes[ i ].z <= 0 )
			{
				m_nodes.erase( m_nodes.begin() + static_cast<int>(i) );
				--i;
			}
			else
			{
				break;
			}
		}
		else
		{
			break;
		}
	}
	merge();
	m_used += static_cast<uint32>(size.x * size.y);
	return r;
}

int texture_atlas::fit( size_t index, glm::ivec2 size )
{
	glm::ivec3 node = m_nodes[ index ];

	if ( node.x + size.x > m_size.x - static_cast<int>( m_border ) ) 
	{
		return -1;
	}

	int y     = node.y;
	int wleft = size.x;

	while ( wleft > 0 )
	{
		node = m_nodes[ index ];
		if ( node.y > y )
		{
			y = node.y;
		}
		if ( y + size.y > m_size.y - static_cast<int>( m_border ) )
		{
			return -1;
		}
		wleft -= node.z;
		++index;
	}
	return y;
}

void texture_atlas::merge()
{
	for ( size_t i=0; i < m_nodes.size()-1; ++i )
    {
		if ( m_nodes[ i ].y == m_nodes[ i+1 ].y )
		{
			m_nodes[ i ].z += m_nodes[ i+1 ].z;
            m_nodes.erase( m_nodes.begin()+static_cast<int>(i+1) );
			--i;
		}
    }
}

void texture_atlas::clear()
{
	m_nodes.clear();
	m_used = 0;
	m_nodes.push_back( glm::ivec3( 1, 1, m_size.x - 2 ) );
	fill( 0 );
}