/*
								+---------------------------------+
								|                                 |
								|   ***   Font tex-atlas   ***    |
								|                                 |
								|  Copyright  © -tHE SWINe- 2007  |
								|                                 |
								|         FontTexture.cpp         |
								|                                 |
								+---------------------------------+
*/

/**
 *	@file gl2/FontTexture.cpp
 *	@author -tHE SWINe-
 *	@date 2007
 *	@brief font texture atlas
 *
 *	@date 2007-06-04
 *
 *	fixed clipped characters artifacts occuring on some fonts with strong character
 *	kerning by rendering glyphs into the center of the bitmap, thus ignoring character metrics
 *
 *	note MSVC compiler has strange error where it incorrectly reports unexpected symbol
 *	CFontTexturePage instead of undefined symbol TBmp in case neither Tga.h or Jpeg.h is included
 *
 *	@date 2007-07-17
 *
 *	added line descent font parameter, ie. CFontTexturePage::m_n_char_descent, new field in
 *	CFontTexturePage constructor and CFontTexturePage::n_Line_descent()
 *	char descent is also added to bitmap info-block so it's not compatible with bitmaps
 *	created by the older versions
 *
 *	@date 2007-12-24
 *
 *	improved linux compatibility by adding posix integer types
 *
 *	@date 2008-03-04
 *
 *	now using Integer.h header
 *
 *	@date 2008-08-08
 *
 *	added \#ifdef for windows 64
 *
 *	@date 2009-01-11
 *
 *	added the geometry padding feature
 *
 *	@date 2009-05-04
 *
 *	fixed mixed windows / linux line endings
 *
 *	@date 2009-05-23
 *
 *	removed all instances of std::vector::reserve and replaced them by stl_ut::Reserve_*
 *
 *	@date 2009-10-11
 *
 *	replaced stl container ::resize() by stl_ut::Resize_*() to avoid unhandled
 *	std::bad_alloc
 *
 *	@date 2009-10-20
 *
 *	fixed some warnings when compiling under VC 2005, implemented "Security
 *	Enhancements in the CRT" for VC 2008. compare against MyProjects_2009-10-19_
 *
 *	@todo this code is now largerly obsolete. while design isn't the worst, implementation is.
 *		need to stop using immediate mode, and 
 *
 */

#include "../NewFix.h"

#include "../CallStack.h"
#if defined(_WIN32) || defined(_WIN64)
#include <windows.h>
#endif // _WIN32 || _WIN64
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <math.h>
#include <algorithm>
#include "../Tga.h"
#include "../Vector.h"
#include "FontTexture.h"
#include "../StlUtils.h"

/*
 *								=== CGDI_Bitmap ===
 */

#ifdef FONT_TEXTURE_CREATE_FONTS

/*
 *	CGDI_Bitmap::CGDI_Bitmap(int n_width, int n_height, int n_plane_num = 1, int n_bit_count = 32)
 *		- default constructor. creates bitmap with size n_width per n_height pixels,
 *		  n_plane_num color planes and n_bit_count bits per pixel
 *		- note uncompressed RGB formats are supported only
 */
CGDI_Bitmap::CGDI_Bitmap(int n_width, int n_height, int n_plane_num, int n_bit_count)
	:m_n_width(n_width), m_n_height(n_height),
	m_n_plane_num(n_plane_num), m_n_bit_count(n_bit_count), m_h_dib(0), m_h_dc(0)
{
	int n_image_size = n_width * n_height * n_plane_num * ((n_bit_count + 7) / 8);

	m_t_info.bmiHeader.biSize = sizeof(BITMAPINFOHEADER);
	m_t_info.bmiHeader.biWidth = n_width;
	m_t_info.bmiHeader.biHeight = n_height;
	m_t_info.bmiHeader.biPlanes = n_plane_num;
	m_t_info.bmiHeader.biBitCount = n_bit_count;
	m_t_info.bmiHeader.biCompression = BI_RGB;
	m_t_info.bmiHeader.biSizeImage = n_image_size;
	m_t_info.bmiHeader.biXPelsPerMeter = 0;
	m_t_info.bmiHeader.biYPelsPerMeter = 0;
	m_t_info.bmiHeader.biClrUsed = 0;
	m_t_info.bmiHeader.biClrImportant = 0;
	// fill bitmap info header

	if(!(m_p_buffer = new(std::nothrow) unsigned char[n_image_size]))
		return;
	// alloc bitmap buffer

	m_h_dib = CreateDIBSection(NULL, &m_t_info, DIB_RGB_COLORS,
		(void**)&m_p_buffer, NULL, 0);
	// create dib
}

/*
 *	CGDI_Bitmap::~CGDI_Bitmap()
 *		- default destructor
 */
CGDI_Bitmap::~CGDI_Bitmap()
{
	if(m_h_dib) {
		ReleaseDC();
		DeleteObject(m_h_dib);
	}
}

/*
 *	HDC CGDI_Bitmap::h_GetDC()
 *		- creates device context and assigns this bitmap to be rendered to
 */
HDC CGDI_Bitmap::h_GetDC()
{
	if(m_h_dc)
		return m_h_dc;
	if(!(m_h_dc = CreateCompatibleDC(0)/*CreateDC("DISPLAY", NULL, NULL, NULL)*/))
		return 0;
	m_h_prev_dc_obj = SelectObject(m_h_dc, m_h_dib);
	return m_h_dc;
}

/*
 *	bool CGDI_Bitmap::ReleaseDC()
 *		- releases device context
 *		- returns true on success or in case no context was created, otherwise false
 */
bool CGDI_Bitmap::ReleaseDC()
{
	if(!m_h_dc)
		return true;
	SelectObject(m_h_dc, m_h_prev_dc_obj);
	bool b_result = DeleteDC(m_h_dc) != FALSE;
	m_h_dc = 0;

	return b_result;
}

/*
 *	void CGDI_Bitmap::Draw(HDC h_dc, int n_x, int n_y, int n_op = SRCCOPY) const
 *		- draws bitmap using device context h_dc on position n_x, n_y
 *		  using operation n_op
 */
void CGDI_Bitmap::Draw(HDC h_dc, int n_x, int n_y, int n_op) const
{
	HDC h_dc_bmp = CreateCompatibleDC(h_dc);
	SelectObject(h_dc_bmp, m_h_dib);
	BitBlt(h_dc, n_x, n_y, m_n_width, m_n_height, h_dc_bmp, 0, 0, n_op);
	DeleteDC(h_dc_bmp);
}

#endif // FONT_TEXTURE_CREATE_FONTS

/*
 *								=== ~CGDI_Bitmap ===
 */

/*
 *								=== TCharacterInfo ===
 */

#ifdef FONT_TEXTURE_CREATE_FONTS

/*
 *	bool TCharacterInfo::Create(unsigned char n_character, CGDI_Bitmap &r_bitmap)
 *		- create character info using font selected in r_bitmap. n_character is requested
 *		  character ascii code and r_bitmap serves as temporal buffer for drawing
 *		  (must have sufficient size)
 *		- returns true on success or false on failure (not enough memory)
 */
bool TCharacterInfo::Create(unsigned char n_character, CGDI_Bitmap &r_bitmap)
{
	HDC h_dc = r_bitmap.h_GetDC();

	char p_s_buffer[2] = {n_character, 0};
	SIZE t_size;
	GetTextExtentPoint32(h_dc, p_s_buffer, 1, &t_size);
	n_caret_shift = t_size.cx;
	// get character size

	TEXTMETRIC t_text_metric;
	GetTextMetrics(h_dc, &t_text_metric);
	int n_y_offset = -t_text_metric.tmDescent + t_text_metric.tmHeight;
	// get character y-offset

	memset(r_bitmap.p_Buffer(), 0, r_bitmap.n_Width() *
		r_bitmap.n_Height() * sizeof(uint32_t));
	// clear

	SetTextColor(h_dc, 0xffffff);
	int n_off_x = r_bitmap.n_Width() / 2;
	int n_off_y = -r_bitmap.n_Height() / 2;
	// hack - windows font system do not specify bounding box
	// have to render glyphs into the middle to determine it without clipping
	TextOut(h_dc, n_off_x, r_bitmap.n_Height() + n_off_y, p_s_buffer, 1);
	// draw character

	const uint32_t *p_buffer = (const uint32_t*)r_bitmap.p_Buffer();
	// get buffer

	int n_min_x = r_bitmap.n_Width();
	int n_max_x = 0;
	for(int n_x = 0; n_x < r_bitmap.n_Width(); ++ n_x) {
		if(!b_Column_Empty(p_buffer + n_x, r_bitmap.n_Height(), r_bitmap.n_Width())) {
			if(n_min_x > n_x)
				n_min_x = n_x;
			if(n_max_x < n_x)
				n_max_x = n_x;
		}
	}
	int n_min_y = r_bitmap.n_Height();
	int n_max_y = 0;
	int n_char_w = n_max_x - n_min_x + 1;
	if(n_char_w > 0) {
		for(int n_y = 0; n_y < r_bitmap.n_Height(); ++ n_y) {
			if(!b_Scanline_Empty(p_buffer + n_min_x + n_y * r_bitmap.n_Width(), n_char_w)) {
				if(n_min_y > n_y)
					n_min_y = n_y;
				if(n_max_y < n_y)
					n_max_y = n_y;
			}
		}
	}
	// get character bitmap dimensions

	/*TBmp t_bmp;
	t_bmp.n_width = r_bitmap.n_Width();
	t_bmp.n_height = r_bitmap.n_Height();
	t_bmp.p_buffer = (uint32_t*)p_buffer;
	Save_Gray_TGA("blah.tga", &t_bmp);*/

	n_bitmap_width = n_max_x - n_min_x + 1;
	n_bitmap_height = n_max_y - n_min_y + 1;
	if(n_bitmap_width < 0 || n_bitmap_height < 0) {
		n_bitmap_width = n_bitmap_height = 0;
		n_min_x = n_min_y = 0;
		n_off_x = n_off_y = 0; // avoid rubbish coords
		// handle undisplayable chars (space, etc)
	}
	v_baseline_offset.x = n_min_x - n_off_x;
	v_baseline_offset.y = n_min_y + n_off_y + n_y_offset;
	// get character metrics

	n_code = n_character;
	// remember code

	return true;
}

/*
 *	void TCharacterInfo::Render(HDC h_dc, int n_raster_height) const
 *		- renders character using device context h_dc of
 *		- n_raster_height is texture page height
 */
void TCharacterInfo::Render(HDC h_dc, int n_raster_height) const
{
	char p_s_str[] = {n_code, 0};

	TEXTMETRIC t_text_metric;
	GetTextMetrics(h_dc, &t_text_metric);
	int n_y_offset = -t_text_metric.tmDescent + t_text_metric.tmHeight;
	// get character y-offset

	TextOut(h_dc, v_bitmap_pos.x - v_baseline_offset.x, n_raster_height -
		v_bitmap_pos.y + v_baseline_offset.y - n_y_offset, p_s_str, 1);
	// render character using GDI
}

/*
 *	bool TCharacterInfo::b_Collide(const TCharacterInfo &r_t_other, int n_padding)
 *		- returns true in case bitmaps of this character and r_t_other
 *		  are colliding in texture space, otherwise false
 */
bool TCharacterInfo::b_Collide(const TCharacterInfo &r_t_other, int n_padding)
{
	return !b_Disjunct(v_bitmap_pos.y, v_Max(n_padding).y,
		r_t_other.v_bitmap_pos.y, r_t_other.v_Max(n_padding).y) &&
		!b_Disjunct(v_bitmap_pos.x, v_Max(n_padding).x,
		r_t_other.v_bitmap_pos.x, r_t_other.v_Max(n_padding).x);
}

bool TCharacterInfo::b_Scanline_Empty(const uint32_t *p_buffer, int n_width)
{
	for(const uint32_t *p_end = p_buffer + n_width;
	   p_buffer != p_end; ++ p_buffer) {
		if(*p_buffer)
			return false;
	}
	return true;
}

bool TCharacterInfo::b_Column_Empty(const uint32_t *p_buffer, int n_height, int n_width)
{
	for(const uint32_t *p_end = p_buffer + ((n_height) * n_width);
	   p_buffer != p_end; p_buffer += n_width) {
		if(*p_buffer)
			return false;
	}
	return true;
}

#endif // FONT_TEXTURE_CREATE_FONTS

/*
 *								=== ~TCharacterInfo ===
 */

/*
 *								=== CFontTexturePage ===
 */

class CFontTexturePage::CGrayBlockReader {
protected:
	const unsigned char *m_p_block;
	const unsigned int m_n_scan_length;
	const unsigned int m_n_block_width;
	unsigned int m_n_scan_pos;

public:
	inline CGrayBlockReader(const void *p_block,
		unsigned int n_scan_length, unsigned int n_block_width)
		:m_p_block((const unsigned char*)p_block), m_n_scan_length(n_scan_length +
		n_block_width), m_n_block_width(n_block_width), m_n_scan_pos(n_block_width)
	{}

	inline void Read(void *p_data, unsigned int n_size)
	{
		unsigned char *p_byte_data = (unsigned char*)p_data;
		while(1) {
			if(n_size < m_n_scan_pos) {
				m_n_scan_pos -= n_size;
				_reverse_copy(p_byte_data, n_size);
				return;
			} else if(n_size == m_n_scan_pos) {
				_reverse_copy(p_byte_data, n_size);
				m_p_block -= (m_n_scan_length) * 4;
				m_n_scan_pos = m_n_block_width;
				return;
			} else /*if(n_size > m_n_scan_pos)*/ {
				_reverse_copy(p_byte_data, m_n_scan_pos);
				p_byte_data += m_n_scan_pos;
				n_size -= m_n_scan_pos;
				m_p_block -= (m_n_scan_length) * 4;
				m_n_scan_pos = m_n_block_width;
			}
		}
	}

protected:
	inline void _reverse_copy(unsigned char *p_gray_dest, unsigned int n_size)
	{
		for(unsigned char *p_end = p_gray_dest + n_size; p_gray_dest != p_end;
		   ++ p_gray_dest, m_p_block += 4)
			*p_gray_dest = *m_p_block;
	}
};

#ifdef FONT_TEXTURE_CREATE_FONTS

class CFontTexturePage::CGDIRenderBitmaps {
protected:
	HDC m_h_dc;
	int m_n_raster_height;

public:
	inline CGDIRenderBitmaps(HDC h_dc, int n_raster_height)
		:m_h_dc(h_dc), m_n_raster_height(n_raster_height)
	{}

	inline void operator ()(const TCharacterInfo *p_info) const
	{
		p_info->Render(m_h_dc, m_n_raster_height);
	}
};

class CFontTexturePage::CSolveCollisions {
protected:
	TCharacterInfo &m_r_t_rect;
	const int m_n_width, m_n_height;
	const int m_n_char_padding;
	const int m_n_geom_padding;
	int &m_r_n_min_max_y;

public:
	CSolveCollisions(TCharacterInfo &r_t_rect, int n_width, int n_height,
		int n_char_padding, int n_geom_padding, int &r_n_temp)
		:m_r_t_rect(r_t_rect), m_n_width(n_width), m_n_height(n_height),
		m_n_char_padding(n_char_padding), m_n_geom_padding(n_geom_padding),
		m_r_n_min_max_y(r_n_temp)
	{}

	inline bool operator ()(const TCharacterInfo *p_other)
	{
		if(m_r_t_rect.b_Collide(*p_other, m_n_char_padding)) {
			if(p_other->v_Max(m_n_char_padding).y < m_r_n_min_max_y)
				m_r_n_min_max_y = p_other->v_Max(m_n_char_padding).y + 1;
			// track minimum of max-y

			m_r_t_rect.Shift_Right(*p_other, m_n_char_padding);
			// shift right

			if(m_r_t_rect.v_Max(m_n_geom_padding).x >= m_n_width) {
				m_r_t_rect.Place(Vector2i(1 + m_n_geom_padding,
					m_r_n_min_max_y + m_n_geom_padding));
				m_r_n_min_max_y = m_n_height;
			}
			// restart position

			return true;
		}
		return false;
	}
};

class CFontTexturePage::CGrayBlockWriter {
protected:
	unsigned char *m_p_block;
	const unsigned int m_n_scan_length;
	const unsigned int m_n_block_width;
	unsigned int m_n_scan_pos;

public:
	inline CGrayBlockWriter(void *p_block, unsigned int n_scan_length, unsigned int n_block_width)
		:m_p_block((unsigned char*)p_block), m_n_scan_length(n_scan_length - n_block_width),
		m_n_block_width(n_block_width), m_n_scan_pos(n_block_width)
	{}

	inline void Write(const void *p_data, unsigned int n_size)
	{
		const unsigned char *p_byte_data = (const unsigned char*)p_data;
		while(1) {
			if(n_size < m_n_scan_pos) {
				m_n_scan_pos -= n_size;
				_copy(p_byte_data, n_size);
				return;
			} else if(n_size == m_n_scan_pos) {
				_copy(p_byte_data, n_size);
				m_p_block += (m_n_scan_length) * 4;
				m_n_scan_pos = m_n_block_width;
				return;
			} else /*if(n_size > m_n_scan_pos)*/ {
				_copy(p_byte_data, m_n_scan_pos);
				p_byte_data += m_n_scan_pos;
				n_size -= m_n_scan_pos;
				m_p_block += (m_n_scan_length) * 4;
				m_n_scan_pos = m_n_block_width;
			}
		}
	}

protected:
	inline void _copy(const unsigned char *p_gray_src, unsigned int n_size)
	{
		for(const unsigned char *p_end = p_gray_src + n_size;
		   p_gray_src != p_end; ++ p_gray_src) {
			*m_p_block ++ = *p_gray_src;
			*m_p_block ++ = *p_gray_src;
			*m_p_block ++ = *p_gray_src;
			++ m_p_block; // don't care about alpha
		}
	}
};

template <class CBlockWriter>
class CFontTexturePage::CWriteIntLayout {
protected:
	CBlockWriter m_writer;

public:
	inline CWriteIntLayout(CBlockWriter writer)
		:m_writer(writer)
	{}

	inline void operator ()(const TCharacterInfo *p_char_info)
	{
		m_writer.Write(p_char_info, sizeof(TCharacterInfo));
	}
};

class CFontTexturePage::CSumArea {
protected:
	int m_n_area;
	int m_n_padding;

public:
	inline CSumArea(int n_padding)
		:m_n_padding(n_padding), m_n_area(0)
	{}

	inline void operator ()(const TCharacterInfo &r_char_info)
	{
		m_n_area += r_char_info.n_Area(m_n_padding);
	}

	inline operator int() const
	{
		return m_n_area;
	}
};

/*
 *	CFontTexturePage::CFontTexturePage(tcharinfo_iterator p_character_begin,
 *		tcharinfo_iterator p_character_end, int n_char_padding, int n_geom_padding,
 *		int n_space_width, int n_newline_height, int n_line_descent,
 *		int n_internal_leading, int n_max_size)
 *		- default constructor; attempts to insert characters p_character_begin till
 *		  p_character_end while keeping maximal texture dimensions below or equal
 *		  to n_max_size while keeping 1 pixel spacing between characters and border and
 *		  n_padding spacing between characters themselves
 *		- n_space_width, n_newline_height, n_line_descent and n_internal_leading
 *		  are font metrics (in pixels)
 *		- note power-of-two texture dimensions are used only
 *		- call n_Character_Num() to see how many of characters were actually added 
 */
CFontTexturePage::CFontTexturePage(tcharinfo_iterator p_character_begin,
	tcharinfo_iterator p_character_end, int n_char_padding, int n_geom_padding,
	int n_space_width, int n_newline_height, int n_line_descent,
	int n_internal_leading, int n_max_size)
	:m_n_char_padding(n_char_padding), m_n_geom_padding(n_geom_padding),
	m_n_width(0), m_n_height(0), m_n_max_char_num(0), m_p_character(0),
	m_n_space_width(n_space_width), m_n_newline_height(n_newline_height),
	m_n_char_descent(n_line_descent), m_n_internal_leading(n_internal_leading)
{
	const int n_character_size = sizeof(TCharacterInfo);
	const int n_header_size = 6 * sizeof(int);
	// char count, padding, info block dimensions, space width, newline height

	const int n_pixel_size = 1; // use grayscale

	int n_info_block_size = (p_character_end - p_character_begin) *
		n_character_size + n_header_size;
	// calculate character block size

	int n_header_pixel_size = (n_header_size + n_pixel_size - 1) / n_pixel_size;
	int n_info_block_pixel_size = (n_info_block_size + n_pixel_size - 1) / n_pixel_size;
	// calculate number of pixels

	int n_best_delta = -1;
	for(int n_width = n_header_pixel_size; n_width <= n_max_size; ++ n_width) {
		int n_height = (n_info_block_pixel_size + n_width - 1) / n_width;
		if(n_height > n_max_size)
			continue;
		// calculate necessary height

		if(abs(n_width - n_height) < n_best_delta || n_best_delta == -1) {
			n_best_delta = abs(n_width - n_height);
			m_t_info_block.n_bitmap_width = n_width;
			m_t_info_block.n_bitmap_height = n_height;
			if(!n_best_delta)
				break;
		}
	}
	if(n_best_delta == -1)
		return;
	m_t_info_block.v_bitmap_pos = Vector2i(0, 0);
	// place info-block

	m_n_max_char_num = ((n_pixel_size * m_t_info_block.n_bitmap_width *
		m_t_info_block.n_bitmap_height) - n_header_size) / n_character_size;
	if(m_n_max_char_num < 0)
		m_n_max_char_num = 0;
	// maximal number of characters

	_ASSERTE(m_character_list.empty());
	stl_ut::Reserve_N(m_character_list, m_n_max_char_num + 1);
	if(m_character_list.capacity() < 1)
		return;
	m_character_list.push_back(&m_t_info_block);
	// insert info-block

	int n_chars_area = std::for_each(p_character_begin,
		p_character_end, CSumArea(m_n_char_padding));
	// sum chars area

	int n_min_size;
	if(n_max_size * n_max_size > n_chars_area) {
		n_min_size = 1 << ((int)(log(sqrt(float(n_chars_area))) / log(2.0f) + .99999f) - 1);
		if(!n_min_size)
			n_min_size = 1;
	} else
		n_min_size = n_max_size;
	// calculate minimal size

	for(int n_width = n_min_size; n_width <= n_max_size; n_width <<= 1) {
		if(n_width < m_t_info_block.n_bitmap_width || n_width < n_space_width)
			continue;
		for(int n_height = n_min_size; n_height <= n_max_size; n_height <<= 1) {
			if(n_height < m_t_info_block.n_bitmap_height || n_height < m_n_newline_height)
				continue;
			m_character_list.erase(m_character_list.begin() + 1, m_character_list.end());
			// erase everything but info-block

			m_n_width = n_width;
			m_n_height = n_height;
			// reset with new dimensions

			if(p_AddCharacters(p_character_begin, p_character_end) == p_character_end)
				return;
			// in case we managed to add all characters, be happy and quit
		}
	}
	// try placeing some characters onto the bitmap
}

/*
 *	tcharinfo_iterator CFontTexturePage::p_AddCharacters(tcharinfo_iterator p_character_begin,
 *		tcharinfo_iterator p_character_end)
 *		- attempts to insert characters p_character_begin till
 *		  p_character_end while keeping texture dimensions set by constructor
 *		- returns next character to be inserted to another texture page
 */
CFontTexturePage::tcharinfo_iterator CFontTexturePage::p_AddCharacters(
	CFontTexturePage::tcharinfo_iterator p_character_begin,
	CFontTexturePage::tcharinfo_iterator p_character_end)
{
	if(p_character_end - p_character_begin > m_n_max_char_num)
		p_character_end = p_character_begin + m_n_max_char_num;
	// don't add more characters than we can hold

	for(tcharinfo_iterator p_rect_iter = p_character_begin;
	   p_rect_iter != p_character_end; ++ p_rect_iter) {
		if(p_rect_iter != p_character_begin &&
		   (*p_rect_iter).n_bitmap_width == (*(p_rect_iter - 1)).n_bitmap_width &&
		   (*p_rect_iter).n_bitmap_height == (*(p_rect_iter - 1)).n_bitmap_height) {
			(*p_rect_iter).Place(Vector2i(1 + m_n_geom_padding,
				(*(p_rect_iter - 1)).v_Min().y + m_n_geom_padding));
		} else
			(*p_rect_iter).Place(Vector2i(1 + m_n_geom_padding, 1 + m_n_geom_padding));
		// shift to origin

		bool b_implacable = false;
		int n_temp = m_n_height;
		while(std::find_if(m_character_list.begin(), m_character_list.end(),
		   CSolveCollisions(*p_rect_iter, m_n_width, m_n_height,
		   m_n_char_padding, m_n_geom_padding, n_temp)) != m_character_list.end()) {
			if((*p_rect_iter).v_Max(m_n_geom_padding).y >= m_n_height) {
				b_implacable = true;
				break;
			}
		}
		// solve collisions

		if(b_implacable)
			return p_rect_iter;
		else {
			if(!stl_ut::Reserve_1More(m_character_list))
				return p_rect_iter;
			m_character_list.push_back(&*p_rect_iter);
		}
		// can't place this one

		if(p_rect_iter + 1 == p_character_end)
			return p_character_end;
		// we've done it!
	}

	return p_character_begin;
}

#endif // FONT_TEXTURE_CREATE_FONTS

/*
 *	CFontTexturePage::CFontTexturePage(const TBmp *p_bitmap)
 *		- loads texture page from bitmap p_bitmap
 *		- assumes grayscale layout info stored in bottom-left corner of bitmap
 *		- in case of success, n_Character_Num() should return positive number of characters
 *		  (font tool should never create empty texture page), otherwise there will be
 *		  no characters
 */
CFontTexturePage::CFontTexturePage(const TBmp *p_bitmap)
	:m_n_width(p_bitmap->n_width), m_n_height(p_bitmap->n_height), m_p_character(0)
{
	_ASSERTE(p_bitmap->b_grayscale && p_bitmap->n_former_bpc == 8);

	uint32_t *p_buffer = p_bitmap->p_buffer +
		(p_bitmap->n_height - 1) * p_bitmap->n_width;
	// pointer to last scanline

	m_t_info_block.n_bitmap_width = ((p_buffer[0] >> 16) & 0xff) |
		(((p_buffer[1] >> 16) & 0xff) << 8) | (((p_buffer[2] >> 16) & 0xff) << 16) |
		(((p_buffer[3] >> 16) & 0xff) << 24);
	if(m_t_info_block.n_bitmap_width > p_bitmap->n_width)
		return; // can't be greater than bitmap width
	// pick info-block width

	CGrayBlockReader reader(p_buffer, p_bitmap->n_width, m_t_info_block.n_bitmap_width);
	int n_temp;
	reader.Read(&n_temp, sizeof(int));
	_ASSERTE(m_t_info_block.n_bitmap_width == n_temp);
	reader.Read(&m_t_info_block.n_bitmap_height, sizeof(int));
	if(m_t_info_block.n_bitmap_height > p_bitmap->n_height)
		return; // can't be greater than bitmap height
	int n_version;
	reader.Read(&n_version, sizeof(int));
	if(n_version <= 100) { // it is unlikely padding would be >= 100px
		m_n_char_padding = n_version;
		n_version = 100;
		m_n_geom_padding = 0;
		// do nothing
	}
	if(n_version < 100 || n_version > 101)
		return; // unknown version
	if(n_version != 100)
		reader.Read(&m_n_char_padding, sizeof(int));
	if(n_version > 100)
		reader.Read(&m_n_geom_padding, sizeof(int));
	reader.Read(&m_n_space_width, sizeof(int));
	reader.Read(&m_n_char_descent, sizeof(int));
	reader.Read(&m_n_newline_height, sizeof(int));
	reader.Read(&m_n_internal_leading, sizeof(int));
	reader.Read(&m_n_max_char_num, sizeof(int)); // don't allow inserting more characters
	// read info-block header

	_ASSERTE(m_character_list.empty());
	if(!stl_ut::Reserve_N(m_character_list, m_n_max_char_num + 1))
		return;
	// alloc list

	if(!(m_p_character = new(std::nothrow) TCharacterInfo[m_n_max_char_num]))
		return;
	// alloc characters

	reader.Read(m_p_character, m_n_max_char_num * sizeof(TCharacterInfo));
	// read all characters

	m_character_list.push_back(&m_t_info_block);
	for(int i = 0; i < m_n_max_char_num; ++ i)
		m_character_list.push_back(m_p_character + i);
	// insert characters
}

#ifdef FONT_TEXTURE_CREATE_FONTS

/*
 *	CGDI_Bitmap *CFontTexturePage::p_Create_Bitmap(HFONT h_font) const
 *		- renders bitmap with glyphs (must be the same font as the one used
 *		  for glyph rendering otherwise glyphs won't fit)
 *		- returns true on success, false on failure
 */
CGDI_Bitmap *CFontTexturePage::p_Create_Bitmap(HFONT h_font) const
{
	if(!m_n_width || !m_n_height || m_character_list.empty())
		return false;
	// don't render empty bitmaps

	CGDI_Bitmap *p_bitmap;
	if(!(p_bitmap = new(std::nothrow) CGDI_Bitmap(m_n_width, m_n_height)))
		return 0;
	HDC h_dc;
	if(!p_bitmap->b_State() || !(h_dc = p_bitmap->h_GetDC())) {
		delete p_bitmap;
		return 0;
	}
	// create bitmap and retrieve it's device context

	memset(p_bitmap->p_Buffer(), 0, p_bitmap->n_Width() *
		p_bitmap->n_Height() * sizeof(uint32_t));
	// clean it's background

	HGDIOBJ h_return = SelectObject(h_dc, h_font);
	SetBkMode(h_dc, TRANSPARENT);
	SetTextColor(h_dc, 0xffffff);
	// select font

	std::for_each(m_character_list.begin() + 1, m_character_list.end(),
		CGDIRenderBitmaps(h_dc, p_bitmap->n_Height()));
	// render characters to bitmap

	SelectObject(h_dc, h_return);
	p_bitmap->ReleaseDC();
	// deselect font, release dc

	CGrayBlockWriter writer(p_bitmap->p_Buffer(), p_bitmap->n_Width(),
		m_t_info_block.n_bitmap_width);

	writer.Write(&m_t_info_block.n_bitmap_width, sizeof(int));
	writer.Write(&m_t_info_block.n_bitmap_height, sizeof(int));
	int n_version = 101; // version
	writer.Write(&n_version, sizeof(int));
	writer.Write(&m_n_char_padding, sizeof(int));
	writer.Write(&m_n_geom_padding, sizeof(int));
	writer.Write(&m_n_space_width, sizeof(int));
	writer.Write(&m_n_char_descent, sizeof(int));
	writer.Write(&m_n_newline_height, sizeof(int));
	writer.Write(&m_n_internal_leading, sizeof(int));
	int n_temp = m_character_list.size() - 1;
	writer.Write(&n_temp, sizeof(int));
	// write info block header

	std::for_each(m_character_list.begin() + 1, m_character_list.end(),
		CWriteIntLayout<CGrayBlockWriter>(writer));
	// write (internal) character layout

	return p_bitmap;
}

#endif // FONT_TEXTURE_CREATE_FONTS

/*
 *								=== ~CFontTexturePage ===
 */

#ifdef FONT_TEXTURE_CREATE_FONTS

/*
 *								=== CFontTexture_Util ===
 */

/*
 *	static bool CFontTexture_Util::Create_CharacterList(nsigned char n_first_char,
 *		unsigned char n_char_num, std::vector<TCharacterInfo> &r_character_list,
 *		CGDI_Bitmap &r_bitmap)
 *		- fills r_character_list with list of characters in range n_first_char trough
 *		  n_first_char + n_char_num
 *		- r_bitmap is used for glyph rendering
 *		- returns true on success, false on failure
 */
bool CFontTexture_Util::Create_CharacterList(unsigned char n_first_char,
	unsigned char n_char_num, std::vector<TCharacterInfo> &r_character_list, CGDI_Bitmap &r_bitmap)
{
	r_character_list.clear();
	if(!stl_ut::Resize_To_N(r_character_list, n_char_num))
		return false;
	// alloc

	for(int i = 0; i < n_char_num; ++ i) {
		if(!r_character_list[i].Create(n_first_char + i, r_bitmap))
			return false;
	}
	// render characters

	return true;
}

/*
 *	static bool CFontTexture_Util::Create_TexturePageList(std::vector<CFontTexturePage*>
 *		&r_texture_list, std::vector<TCharacterInfo> &r_character_list, int n_char_padding,
 *		int n_geom_padding, int n_max_texture_size, int n_space_width, int n_newline_height,
 *		int n_line_descent, int n_internal_leading)
 *		- fills list of texture pages r_texture_list by characters from r_character_list
 *		  while keeping n_char_padding pixels distances between characters and
 *		  having texture pages with dimensions equal or below n_max_texture_size
 *		- n_space_width, n_newline_height, n_line_descent and n_internal_leading
 *		  are font metrics
 *		- n_geom_padding is geometry padding (space between character raster bounding box
 *		  and GL_QUAD texcoords box; default 0)
 *		- returns true on success, false on failure
 */
bool CFontTexture_Util::Create_TexturePageList(std::vector<CFontTexturePage*> &r_texture_list,
	std::vector<TCharacterInfo> &r_character_list, int n_char_padding, int n_geom_padding,
	int n_max_texture_size, int n_space_width, int n_newline_height, int n_line_descent,
	int n_internal_leading)
{
	n_char_padding += 2 * n_geom_padding;

	r_texture_list.clear();
	for(std::vector<TCharacterInfo>::iterator p_character_begin =
	   r_character_list.begin(); p_character_begin != r_character_list.end();) {
		if(!stl_ut::Reserve_1More(r_texture_list))
			return false;
		CFontTexturePage *p_texture_page;
		if(!(p_texture_page = new(std::nothrow) CFontTexturePage(p_character_begin,
		   r_character_list.end(), n_char_padding, n_geom_padding, n_space_width,
		   n_newline_height, n_line_descent, n_internal_leading, n_max_texture_size)))
			return false;
		r_texture_list.push_back(p_texture_page);
		// create a new texture page and add it to the list

		if(!p_texture_page->n_Character_Num())
			return false;
		p_character_begin += p_texture_page->n_Character_Num();
		// add all characters we can

		for(int i = 0, n = r_texture_list.size(); i < n &&
		   p_character_begin != r_character_list.end(); ++ i) {
			std::vector<TCharacterInfo>::iterator p_last_char;
			if((p_last_char = r_texture_list[i]->p_AddCharacters(p_character_begin,
			   r_character_list.end())) > p_character_begin && i)
				i = -1; // restart the loop in case we added something
			p_character_begin = p_last_char;
			// add all characters we can
		}
		// add smaller characters to existing texture pages
		// (which contain large characters at the beginning)
	}

	return true;
}

/*
 *								=== ~CFontTexture_Util ===
 */

#endif // FONT_TEXTURE_CREATE_FONTS
