/*
								+--------------------------------+
								|                                |
								|  ***  Bin packing solver  ***  |
								|                                |
								|  Copyright © -tHE SWINe- 2011  |
								|                                |
								|          BinPacking.h          |
								|                                |
								+--------------------------------+
*/

#pragma once
#ifndef __BIN_PACKING_INCLUDED
#define __BIN_PACKING_INCLUDED

/**
 *	@file BinPacking.h
 *	@author -tHE SWINe-
 *	@brief A simple implementation of the bin packing algorithm (in two dimensions).
 *	@date 2011-03-13
 *
 *	Some benchmark:
 *
 *	es ec ug | time     | ug speedup | ec speedup | es slowdown
 *	---------+----------+------------+------------+------------
 *	 0  0  0 | 0.088621 |            |            | 
 *	 0  0  1 | 0.014827 | 5.977001 x |            | 
 *	 0  1  0 | 0.074816 |            | 1.184519 x | 
 *	 0  1  1 | 0.012443 | 6.012698 x | 1.191593 x | 
 *	 1  0  0 | 0.211866 |            |            | 2.390697 x
 *	 1  0  1 | 0.023947 | 8.847288 x |            | 1.615094 x
 *	 1  1  0 | 0.148871 |            | 1.423151 x | 1.989828 x
 *	 1  1  1 | 0.018273 | 8.147048 x | 1.310512 x | 1.468536 x
 *
 *	es stands for __BIN_PACKER_EXHAUSTIVE_SEED_SEARCH
 *	ec stands for __BIN_PACKER_EDGE_CULLING
 *	ug stands for __BIN_PACKER_USE_UNIFORM_GRID
 *
 *	meassured on random tiles 5x5 to 21x21 pixels, packed to area 256x256 pixels
 *	on unloaded AMD Opteron 2360 SE
 *
 *	@date 2014-03-12
 *
 *	Improved documentation of the template types.
 *
 */

#include <vector>
#include <list>
#include <map>
#include <algorithm>
#include "Vector.h"
#include "MinMax.h"

#if defined(_MSC_VER) && !defined(__MWERKS__) && !defined(for) && _MSC_VER <= 1200
#define for if(0) {} else for
#endif // _MSC_VER && !__MWERKS__ && !for && _MSC_VER <= 1200
// msvc 'for' scoping hack

/**
 *	@def __BIN_PACKER_EXHAUSTIVE_SEED_SEARCH
 *	@brief enables exhaustive search of box position in a bin
 *		(this is only about twice slower, but increases packing efficiency about 5 - 10%)
 */
#define __BIN_PACKER_EXHAUSTIVE_SEED_SEARCH

/**
 *	@def __BIN_PACKER_EDGE_CULLING
 *	@brief enables edge culling (a speed optimization, the algorithm
 *		ran about 1.5 times faster on the random tile dataset)
 *	@note This has no effect on packing efficiency.
 */
#define __BIN_PACKER_EDGE_CULLING

/**
 *	@def __BIN_PACKER_USE_UNIFORM_GRID
 *	@brief enables uniform grid sptaial subdivision structure (a speed optimization,
 *		the algorithm ran almost 10 times faster on the random tile dataset)
 *	@note This has no effect on packing efficiency.
 */
#define __BIN_PACKER_USE_UNIFORM_GRID

/**
 *	@def __BIN_PACKER_WANT_DEBUG_RASTER
 *	@brief enables function CPage::Debug_Raster()
 */
#define __BIN_PACKER_WANT_DEBUG_RASTER

/**
 *	@def __BIN_PACKER_NO_DEBUG_RASTER
 *	@brief disables function CPage::Debug_Raster(), even in debug builds
 *	@note This overrides __BIN_PACKER_WANT_DEBUG_RASTER.
 */
//#define __BIN_PACKER_NO_DEBUG_RASTER

#if (defined(_DEBUG) || defined(__BIN_PACKER_WANT_DEBUG_RASTER)) && !defined(__BIN_PACKER_NO_DEBUG_RASTER)
#include "Tga.h"
#endif // (_DEBUG || __BIN_PACKER_WANT_DEBUG_RASTER) && !__BIN_PACKER_NO_DEBUG_RASTER

/**
 *	@brief a simple 2D "box" class which can be used for bin packing
 *	@tparam _TySize is type in which item dimensions are represented (such as int, float or size_t)
 */
template <class _TySize>
struct TBinPackingItem {
	_TySize n_x; /**< @brief horizontal position */
	_TySize n_y; /**< @brief vertical position */
	_TySize n_width; /**< @brief width of the box */
	_TySize n_height; /**< @brief height of the box */
	bool b_orientation; /**< @brief rotation flag */

	/**
	 *	@brief default constructor; has no effect
	 */
	TBinPackingItem()
	{}

	/**
	 *	@brief constructor
	 *
	 *	@param[in] n_x is horizontal position of the item
	 *	@param[in] n_y is vertical position of the item
	 *	@param[in] n_width is width of the item
	 *	@param[in] n_height is height of the item
	 */
	TBinPackingItem(_TySize _n_x, _TySize _n_y, _TySize n_width, _TySize n_height)
		:n_x(_n_x), n_y(_n_y), n_width(n_width),
		n_height(n_height), b_orientation(false)
	{}

	/**
	 *	@brief copy-constructor
	 *	@param[in] r_item is item being copied
	 */
	TBinPackingItem(const TBinPackingItem &r_item)
		:n_x(r_item.n_x), n_y(r_item.n_y), n_width(r_item.n_width),
		n_height(r_item.n_height), b_orientation(r_item.b_orientation)
	{}

	/**
	 *	@brief positionless constructor
	 *
	 *	@param[in] n_width is width of the item
	 *	@param[in] n_height is height of the item
	 */
	TBinPackingItem(_TySize _n_width, _TySize _n_height)
		:n_x(0), n_y(0), n_width(_n_width), n_height(_n_height), b_orientation(false)
	{}
};

/**
 *	@brief item manipulator interface template
 *
 *	@tparam _TySize is size type
 *	@tparam _TyBinPackingItem is type of the item to be packed
 */
template <class _TySize, class _TyBinPackingItem>
class CBinPackingItemManipulator {
public:
	/**
	 *	@brief gets item width
	 *	@param[in] r_t_item is bin packing item
	 *	@return Returns the horizontal size.
	 */
	static inline _TySize n_Width(const _TyBinPackingItem &r_t_item)
	{
		return r_t_item.n_width;
	}

	/**
	 *	@brief gets item height
	 *	@param[in] r_t_item is bin packing item
	 *	@return Returns the vertical size.
	 */
	static inline _TySize n_Height(const _TyBinPackingItem &r_t_item)
	{
		return r_t_item.n_height;
	}

	/**
	 *	@brief gets item orientation
	 *	@param[in] r_t_item is bin packing item
	 *	@return Returns orientation of the box, false means original, true means rotated.
	 */
	static inline bool b_Orientation(const _TyBinPackingItem &r_t_item)
	{
		return r_t_item.b_orientation;
	}

	/**
	 *	@brief sets position of the item
	 *
	 *	@param[in,out] r_t_item is bin packing item
	 *	@param[in] n_x is a new horizontal position
	 *	@param[in] n_y is a new vertical position
	 */
	static inline void Set_Position(_TyBinPackingItem &r_t_item, _TySize _n_x, _TySize _n_y)
	{
		r_t_item.n_x = _n_x;
		r_t_item.n_y = _n_y;
	}

	/**
	 *	@brief gets horizontal position
	 *	@param[in] r_t_item is bin packing item
	 *	@return Returns the horizontal position.
	 */
	static inline _TySize n_X(const _TyBinPackingItem &r_t_item)
	{
		return r_t_item.n_x;
	}

	/**
	 *	@brief gets vertical position
	 *	@param[in] r_t_item is bin packing item
	 *	@return Returns the vertical position.
	 */
	static inline _TySize n_Y(const _TyBinPackingItem &r_t_item)
	{
		return r_t_item.n_y;
	}

	/**
	 *	@brief determines whether the box supports rotation
	 *	@param[in] r_t_item is bin packing item
	 *	@return Returns whether the box supports rotation.
	 */
	static inline bool b_CanTurn(const _TyBinPackingItem &UNUSED(r_t_item))
	{
		return true;
	}

	/**
	 *	@brief turns the item (swaps width and height)
	 *	@param[in,out] r_t_item is bin packing item
	 */
	static inline void Turn(_TyBinPackingItem &r_t_item)
	{
		_ASSERTE(b_CanTurn(r_t_item));
		std::swap(r_t_item.n_height, r_t_item.n_width);
		r_t_item.b_orientation = !r_t_item.b_orientation;
	}
};

/**
 *	@brief bin packing page, a container which allocates positions for the added items ("boxes")
 *
 *	@tparam _TySize is type in which item dimensions are represented (such as int, float or size_t)
 *	@tparam _TyItem is item type
 *	@tparam _TyItemManipulator is an interface for operations on the item type
 */
template <class _TySize, class _TyItem, class _TyItemManipulator>
class CBinPackingPage {
public:
	typedef _TySize TSizeType;
	typedef _TyItem TItemType;
	typedef _TyItemManipulator TMan;
	typedef _TyItem *TItemRefType;

protected:
	struct TEdge {
		_TySize n_org; /**< @brief origin of the edge (the first intersection, or the edge of the area) */
		_TySize n_begin; /**< @brief the beginning of the edge (a vertex of the box) */
		_TySize n_end; /**< @brief the end of the edge (a vertex of the box) */

		inline TEdge(_TySize _n_begin, _TySize _n_end)
			:n_org(0), n_begin(_n_begin), n_end(_n_end)
		{}

		inline TEdge(_TySize _n_org, _TySize _n_begin, _TySize _n_end)
			:n_org(_n_org), n_begin(_n_begin), n_end(_n_end)
		{}
	};

	typedef std::multimap<_TySize, TEdge> edge_map; /**< @brief edges, ordered by their position */

	_TySize m_n_width; /**< @brief width of the page */
	_TySize m_n_height; /**< @brief height of the page */
	std::list<_TyItem> m_off_area_list; /**< @brief list of off-areas */ // this needs to be list so the pointers are fixed
	std::vector<_TyItem*> m_box_list; /**< @brief list of boxes, placed in the page */

	std::vector<Vector2<_TySize> > m_seed_list; /**< @brief list of possible seed points */

	edge_map m_upper_edge_list; /**< @brief list of upper edges */
	edge_map m_right_edge_list; /**< @brief list of right edges */

	_TySize m_n_bounding_box_width; /**< @brief width of the bounding box */
	_TySize m_n_bounding_box_height; /**< @brief height of the bounding box */
	double m_f_occupied_area; /**< @brief sum of areas of all the boxes inside */

#ifdef __BIN_PACKER_USE_UNIFORM_GRID
	const _TySize m_n_uniform_grid_cell_size; /**< @brief size of a single uniform grid cell @note this is probably best to be set arround average box size (width or height) */
	const size_t m_n_uniform_grid_width; /**< @brief number of uniform grid cells accross */
	const size_t m_n_uniform_grid_height; /**< @brief number of uniform grid cells down */
	std::vector<std::vector<const _TyItem*> > m_box_map; /**< @brief the uniform grid */
#endif // __BIN_PACKER_USE_UNIFORM_GRID

	class CFindPointCollision {
	protected:
		Vector2<_TySize> m_v_point;

	public:
		inline CFindPointCollision(Vector2<_TySize> v_point)
			:m_v_point(v_point)
		{}

		inline bool operator ()(const _TyItem &r_item) const
		{
			return m_v_point.x >= TMan::n_X(r_item) && m_v_point.x < TMan::n_X(r_item) + TMan::n_Width(r_item) &&
				m_v_point.y >= TMan::n_Y(r_item) && m_v_point.y < TMan::n_Y(r_item) + TMan::n_Height(r_item);
		}

		inline bool operator ()(const _TyItem *p_box) const
		{
			return (*this)(*p_box);
		}
	};

	class CFindBoxCollision {
	protected:
		const _TyItem &m_r_box;

	public:
		inline CFindBoxCollision(const _TyItem &r_item)
			:m_r_box(r_item)
		{}

		inline bool operator ()(const _TyItem &r_item) const
		{
			return (TMan::n_X(m_r_box) + TMan::n_Width(m_r_box) > TMan::n_X(r_item)) &&
				(TMan::n_X(m_r_box) < TMan::n_X(r_item) + TMan::n_Width(r_item)) &&
				(TMan::n_Y(m_r_box) + TMan::n_Height(m_r_box) > TMan::n_Y(r_item)) &&
				(TMan::n_Y(m_r_box) < TMan::n_Y(r_item) + TMan::n_Height(r_item));
		}

		inline bool operator ()(const _TyItem *p_box) const
		{
			return (*this)(*p_box);
		}
	};

public:
	/**
	 *	@brief default constructor
	 *
	 *	@param[in] n_width is page width
	 *	@param[in] n_height is page height
	 *	@param[in] n_uniform_grid_cell_size is size of uniform grid cell
	 *		(only used if __BIN_PACKER_USE_UNIFORM_GRID is defined)
	 *
	 *	@note This throws std::bad_alloc.
	 */
	CBinPackingPage(_TySize n_width, _TySize n_height, _TySize n_uniform_grid_cell_size = 32) // throws(std::bad_alloc)
		:m_n_width(n_width), m_n_height(n_height), m_n_bounding_box_width(0),
		m_n_bounding_box_height(0), m_f_occupied_area(0)
#ifdef __BIN_PACKER_USE_UNIFORM_GRID
		, m_n_uniform_grid_cell_size(n_uniform_grid_cell_size),
		m_n_uniform_grid_width((n_width + n_uniform_grid_cell_size - 1) / n_uniform_grid_cell_size),
		m_n_uniform_grid_height((n_height + n_uniform_grid_cell_size - 1) / n_uniform_grid_cell_size)
#endif // __BIN_PACKER_USE_UNIFORM_GRID
	{
		m_seed_list.push_back(Vector2<_TySize>(0, 0));
		// add a single seed at the origin

		m_upper_edge_list.insert(typename edge_map::value_type(0, TEdge(0, 0, n_width)));
		m_right_edge_list.insert(typename edge_map::value_type(0, TEdge(0, 0, n_height)));
		// add left and bottom edges of the area

#ifdef __BIN_PACKER_USE_UNIFORM_GRID
		_ASSERTE(m_n_uniform_grid_width > 0 && m_n_uniform_grid_height > 0 &&
			m_n_uniform_grid_width < SIZE_MAX / m_n_uniform_grid_height); // got some errors like that
		m_box_map.resize(m_n_uniform_grid_width * m_n_uniform_grid_height);
		// alloc the box map
#endif // __BIN_PACKER_USE_UNIFORM_GRID
	}

	/**
	 *	@brief copy-constructor
	 *	@param[in] r_page is page to copy
	 *	@note This throws std::bad_alloc.
	 */
	CBinPackingPage(const CBinPackingPage &r_page) // throws(std::bad_alloc)
		:m_n_width(r_page.m_n_width), m_n_height(r_page.m_n_height),
		m_off_area_list(r_page.m_off_area_list), m_box_list(r_page.m_box_list),
		m_seed_list(r_page.m_seed_list), m_upper_edge_list(r_page.m_upper_edge_list),
		m_right_edge_list(r_page.m_right_edge_list),
		m_n_bounding_box_width(r_page.m_n_bounding_box_width),
		m_n_bounding_box_height(r_page.m_n_bounding_box_height),
		m_f_occupied_area(r_page.m_f_occupied_area)
#ifdef __BIN_PACKER_USE_UNIFORM_GRID
		, m_n_uniform_grid_cell_size(r_page.m_n_uniform_grid_cell_size),
		m_n_uniform_grid_width(r_page.m_n_uniform_grid_width),
		m_n_uniform_grid_height(r_page.m_n_uniform_grid_height), m_box_map(r_page.m_box_map)
#endif // __BIN_PACKER_USE_UNIFORM_GRID
	{}

	/**
	 *	@brief gets asymptotic efficiency
	 *	@return Returns the asymptiotic efficiency (ratio of the occupied space to the area of the bounding box).
	 */
	double f_Asymptotic_Efficiency() const
	{
		return m_f_occupied_area / (double(m_n_bounding_box_width) * m_n_bounding_box_height);
	}

	/**
	 *	@brief gets efficiency
	 *	@return Returns the efficiency (ratio of the occupied space to the area of the page).
	 */
	double f_Efficiency() const
	{
		return m_f_occupied_area / (double(m_n_width) * m_n_height);
	}

	/**
	 *	@brief gets free space in the page
	 *	@return Returns the total unused area in the page.
	 */
	double f_Free_Space() const
	{
		return double(m_n_width) * m_n_height - m_f_occupied_area;
	}

	/**
	 *	@brief gets used space in the page
	 *	@return Returns the total used area in the page.
	 */
	double f_Used_Space() const
	{
		return m_f_occupied_area;
	}

	/**
	 *	@brief gets page width
	 *	@return Returns page width (the value specified in constructor, or set by Set_Size()).
	 *	@note To get actual size of the contents, use n_BoundingBox_Width().
	 */
	inline _TySize n_Width() const
	{
		return m_n_width;
	}

	/**
	 *	@brief gets page height
	 *	@return Returns page height (the value specified in constructor, or set by Set_Size()).
	 *	@note To get actual size of the contents, use n_BoundingBox_Height().
	 */
	inline _TySize n_Height() const
	{
		return m_n_height;
	}

	/**
	 *	@brief sets a new page size
	 *
	 *	@param[in] n_width is a new page width
	 *	@param[in] n_height is a new page height
	 *
	 *	@note This doesn't check page size against the page contents; use with caution.
	 */
	void Set_Size(_TySize n_width, _TySize n_height)
	{
		m_n_width = n_width;
		m_n_height = n_height;
	}

	/**
	 *	@brief gets bounding box width
	 *	@return Returns bounding box width.
	 *	@note One of bounding box corners lies at the origin.
	 */
	_TySize n_BoundingBox_Width() const
	{
		return m_n_bounding_box_width;
	}

	/**
	 *	@brief gets bounding box height
	 *	@return Returns bounding box height.
	 *	@note One of bounding box corners lies at the origin.
	 */
	_TySize n_BoundingBox_Height() const
	{
		return m_n_bounding_box_height;
	}

	/**
	 *	@brief gets page items
	 *	@return Returns list of page items.
	 */
	const std::vector<_TyItem*> &r_ItemList() const
	{
		return m_box_list;
	}

	/**
	 *	@brief sets off-limits area
	 *	@param[in] t_off_area is a positioned box, which is completely
	 *		inside the area and is not intersecting anything
	 *	@return Returns true on success, false on failure.
	 *	@note The off-areas must be specified before adding the boxes, otherwise
	 *		it can't be guaranteed there will be no collisions.
	 */
	bool Set_OffArea(_TyItem t_off_area)
	{
		_ASSERTE(m_box_list.empty()); // make sure there are no boxes when adding off-areas
		_ASSERTE(TMan::n_X(t_off_area) >= 0 && TMan::n_Y(t_off_area) >= 0 &&
			TMan::n_X(t_off_area) + TMan::n_Width(t_off_area) <= m_n_width &&
			TMan::n_Y(t_off_area) + TMan::n_Height(t_off_area) <= m_n_height); // make sure the off areas do not collide with anything
		// make some simple assumptions

		try {
			m_off_area_list.push_back(t_off_area);
		} catch(std::bad_alloc&) {
			return false;
		}
		const _TyItem &r_item = m_off_area_list.back();
		// add the off-area to the list

		//m_n_bounding_box_width = max(m_n_bounding_box_width, TMan::n_X(t_off_area) + TMan::n_Width(r_item));
		//m_n_bounding_box_height = max(m_n_bounding_box_height, TMan::n_Y(t_off_area) + TMan::n_Height(r_item));
		m_f_occupied_area += double(TMan::n_Width(r_item)) * TMan::n_Height(r_item); // this is for efficiency / etc, this is not the bounding box area
		// update occupied area

		return Update_SeedsEdges(r_item);
		// update the seeds and edges
	}

	/**
	 *	@brief tests if an item fits in the page
	 *	@param[in,out] r_item is reference to the item being tested
	 *	@param[in] b_allow_rotation is rotation enable flag (if the total number of objects
	 *		is known, it's good to enable rotation only for the part of objects which are packed last)
	 *	@return Returns true if the box fits, otherwise returns false.
	 */
	bool b_Item_Fits(_TyItem &r_item, bool b_allow_rotation = true)
	{
		for(int n_rotation = 0;; ++ n_rotation) {
			for(size_t i = 0, n = m_seed_list.size(); i < n; ++ i) {
				TMan::Set_Position(r_item, m_seed_list[i].x, m_seed_list[i].y);
				// assume a new position

				if(!b_Collision(r_item))
					return true; // found non-colliding situation
				// detect collisions
			}

			if(!b_allow_rotation || !TMan::b_CanTurn(r_item))
				break;
			TMan::Turn(r_item);
			if(n_rotation == 1)
				break;
			// handle rotations
		}
		// finds the seed to position the box at

		return false;
	}

	/**
	 *	@brief allocates a new item in the page
	 *	@param[out] r_b_box_added is set to true if the item fit and was added
	 *	@param[in,out] r_item is reference to the item being added (it's address
	 *		must not change in the lifetime of this CPage and it must not be deallocated)
	 *	@param[in] b_allow_rotation is rotation enable flag (if the total number of objects
	 *		is known, it's good to enable rotation only for the part of objects which are packed last)
	 *	@return Returns true on success, false on failure.
	 *	@note This fails if there is not enough memory. The condition where the item was not
	 *		added is considered success (the function returns true) and is marked by cleared r_b_box_added.
	 */
	bool Add_Item(bool &r_b_box_added, _TyItem &r_item, bool b_allow_rotation = true)
	{
		size_t n_best_seed = -1;
		bool b_best_while_turned = false;
		{
			double f_best_area = 0;
			_TySize n_best_off = m_n_width + m_n_height; // distance from the origin (a secondary metric)
			for(int n_rotation = 0;; ++ n_rotation) {
				for(size_t i = 0, n = m_seed_list.size(); i < n; ++ i) {
					TMan::Set_Position(r_item, m_seed_list[i].x, m_seed_list[i].y);
					// assume a new position

					if(b_Collision(r_item))
						continue;
					// detect collisions

#ifdef __BIN_PACKER_EXHAUSTIVE_SEED_SEARCH
					_TySize n_new_bbox_width = max(m_n_bounding_box_width, _TySize(TMan::n_X(r_item) + TMan::n_Width(r_item)));
					_TySize n_new_bbox_height = max(m_n_bounding_box_height, _TySize(TMan::n_Y(r_item) + TMan::n_Height(r_item)));
					double f_new_area = double(n_new_bbox_width) /** n_new_bbox_height*/; // this is slightly better than the area
					_TySize n_off = m_seed_list[i].x + m_seed_list[i].y;
					if(f_best_area > f_new_area || n_best_seed == -1 ||
					   (f_best_area == f_new_area && n_best_off > n_off)) {
						n_best_off = n_off;
						f_best_area = f_new_area;
						n_best_seed = i;
						b_best_while_turned = n_rotation != 0;
					}
					// try to find the best poition that keeps the most compact arrangement
#else // __BIN_PACKER_EXHAUSTIVE_SEED_SEARCH
					n_best_seed = i;
					b_best_while_turned = n_rotation != 0; // !!
					break; // be happy with the first one that fits
#endif // __BIN_PACKER_EXHAUSTIVE_SEED_SEARCH
				}

#ifndef __BIN_PACKER_EXHAUSTIVE_SEED_SEARCH
				if(!n_rotation && n_best_seed != -1)
					break;
				// in case it found a good position without rotation, keep it that way
#endif // __BIN_PACKER_EXHAUSTIVE_SEED_SEARCH

				if(!b_allow_rotation || !TMan::b_CanTurn(r_item))
					break;
				TMan::Turn(r_item);
				if(n_rotation == 1)
					break;
			}
		}
		// finds the seed to position the box at

		if(b_best_while_turned)
			TMan::Turn(r_item);
		// return to the favorable rotation

		if(n_best_seed == -1) {
			r_b_box_added = false;
			return true;
		}
		// in case there was no good seed, the box was not added

		TMan::Set_Position(r_item, m_seed_list[n_best_seed].x, m_seed_list[n_best_seed].y);
		// assume a new position

		m_n_bounding_box_width = max(m_n_bounding_box_width, _TySize(TMan::n_X(r_item) + TMan::n_Width(r_item)));
		m_n_bounding_box_height = max(m_n_bounding_box_height, _TySize(TMan::n_Y(r_item) + TMan::n_Height(r_item)));
		m_f_occupied_area += double(TMan::n_Width(r_item)) * TMan::n_Height(r_item); // this is for efficiency / etc, this is not the bounding box area
		// update the bounding box

		m_seed_list.erase(m_seed_list.begin() + n_best_seed);
		// remove the seed that has just been used

		try {
			m_box_list.push_back(&r_item);
			// add the box
		} catch(std::bad_alloc&) {
			return false;
		}
		// add the box to the list

		if(!Update_SeedsEdges(r_item))
			return false;
		// update seeds and edges

		r_b_box_added = true;
		// the box was added

		return true;
	}

#if (defined(_DEBUG) || defined(__BIN_PACKER_WANT_DEBUG_RASTER)) && !defined(__BIN_PACKER_NO_DEBUG_RASTER)

	/**
	 *	@brief rasterizes the page and saves it in TGA format
	 *	@param[in] p_s_filename is output file name
	 *	@return Returns true on success, false on failure.
	 *	@note This is only compiled in debug builds,
	 *		or if __BIN_PACKER_WANT_DEBUG_RASTER is defined.
	 *		This can be disabled by defining __BIN_PACKER_NO_DEBUG_RASTER.
	 */
	bool Debug_Raster(const char *p_s_filename) const
	{
		TBmp t_bmp;
		if(!(t_bmp.p_buffer = new uint32_t[m_n_width * m_n_height]))
			return false;
		t_bmp.b_alpha = false;
		t_bmp.b_grayscale = false;
		t_bmp.n_former_bpp = 8;
		t_bmp.n_width = m_n_width;
		t_bmp.n_height = m_n_height;
		memset(t_bmp.p_buffer, 0xff, m_n_width * m_n_height * sizeof(uint32_t));
		// alloc bitmap

		// @todo - fix the size_t conversion mayhem

		for(size_t i = 0, n = m_box_list.size(); i < n; ++ i) {
			const _TyItem &r_item = *m_box_list[i];
			const _TySize x0 = TMan::n_X(r_item), y0 = TMan::n_Y(r_item),
				x1 = TMan::n_X(r_item) + TMan::n_Width(r_item),
				y1 = TMan::n_Y(r_item) + TMan::n_Height(r_item);
			// get box and it's extents

			uint32_t n_border_color = (i + 1 == n)? 0xffa0410d : 0xff0000ff;
			for(size_t _y0 = size_t(y0); _y0 < size_t(y1); ++ _y0) {
				t_bmp.p_buffer[size_t(x0) + _y0 * t_bmp.n_width] = n_border_color;
				t_bmp.p_buffer[size_t(x1 - 1) + _y0 * t_bmp.n_width] = n_border_color;
			}
			for(size_t _x0 = x0; _x0 < size_t(x1); ++ _x0) {
				t_bmp.p_buffer[_x0 + size_t(y0) * t_bmp.n_width] = n_border_color;
				t_bmp.p_buffer[_x0 + size_t(y1 - 1) * t_bmp.n_width] = n_border_color;
			}
			// draw wireframe box

			uint32_t n_fill_color = (i + 1 == n)? 0xfff26522 : 0xff24aeff;
			for(size_t _y0 = size_t(y0+1); _y0 < size_t(y1-1); ++ _y0) {
				for(size_t _x0 = size_t(x0+1); _x0 < size_t(x1-1); ++ _x0)
					t_bmp.p_buffer[_x0 + _y0 * t_bmp.n_width] = n_fill_color;
			}
			// fill the inside of the box
		}
		// rasterize boxes

		for(typename std::list<_TyItem>::const_iterator p_it = m_off_area_list.begin(),
		   p_end_it = m_off_area_list.end(); p_it != p_end_it; ++ p_it) {
			const _TyItem &r_item = (*p_it);
			const _TySize x0 = TMan::n_X(r_item), y0 = TMan::n_Y(r_item),
				x1 = TMan::n_X(r_item) + TMan::n_Width(r_item),
				y1 = TMan::n_Y(r_item) + TMan::n_Height(r_item);
			// get box and it's extents

			uint32_t n_border_color = 0xff808000;
			for(size_t _y0 = size_t(y0); _y0 < size_t(y1); ++ _y0) {
				t_bmp.p_buffer[size_t(x0) + _y0 * t_bmp.n_width] = n_border_color;
				t_bmp.p_buffer[size_t(x1 - 1) + _y0 * t_bmp.n_width] = n_border_color;
			}
			for(size_t _x0 = x0; _x0 < size_t(x1); ++ _x0) {
				t_bmp.p_buffer[_x0 + size_t(y0) * t_bmp.n_width] = n_border_color;
				t_bmp.p_buffer[_x0 + size_t(y1 - 1) * t_bmp.n_width] = n_border_color;
			}
			// draw wireframe box

			uint32_t n_fill_color = 0xffffff00;
			for(size_t _y0 = size_t(y0+1); _y0 < size_t(y1-1); ++ _y0) {
				for(size_t _x0 = size_t(x0+1); _x0 < size_t(x1-1); ++ _x0)
					t_bmp.p_buffer[_x0 + _y0 * t_bmp.n_width] = n_fill_color;
			}
			// fill the inside of the box
		}
		// rasterize off-areas

		for(typename edge_map::const_iterator p_it = m_upper_edge_list.begin(),
		   p_end = m_upper_edge_list.end(); p_it != p_end; ++ p_it) {
			_TySize y = (*p_it).first;
			if(y >= m_n_height) { // can happen
				//_ASSERTE(y == m_n_height); // that's the way it should happen
				// this won't hold if the user applied some padding and changed page size using Set_Size()
				continue;
			}
			TEdge t_edge = (*p_it).second;
			for(size_t x = size_t(t_edge.n_org); x < size_t(t_edge.n_begin); ++ x)
				t_bmp.p_buffer[x + size_t(y) * t_bmp.n_width] = 0xff8dc63f;
		}
		for(typename edge_map::const_iterator p_it = m_right_edge_list.begin(),
		   p_end = m_right_edge_list.end(); p_it != p_end; ++ p_it) {
			_TySize x = (*p_it).first;
			if(x >= m_n_width) { // can happen
				//_ASSERTE(x == m_n_width); // that's the way it should happen
				// this won't hold if the user applied some padding and changed page size using Set_Size()
				continue;
			}
			TEdge t_edge = (*p_it).second;
			for(size_t y = size_t(t_edge.n_org); y < size_t(t_edge.n_begin); ++ y)
				t_bmp.p_buffer[size_t(x) + y * t_bmp.n_width] = 0xff8dc63f;
		}
		// rasterize edge extents

		for(size_t i = 0, n = m_seed_list.size(); i < n; ++ i) {
			Vector2<_TySize> v_seed = m_seed_list[i];
			for(int j = -2; j <= 2; ++ j) {
				if(int(v_seed.x) + j >= 0 && int(v_seed.x) + j < t_bmp.n_width) {
					if(int(v_seed.y) + j >= 0 && int(v_seed.y) + j < t_bmp.n_height)
						t_bmp.p_buffer[size_t(v_seed.x + j) + size_t(v_seed.y + j) * t_bmp.n_width] = 0xff000000;
					if(int(v_seed.y) - j >= 0 && int(v_seed.y) - j < t_bmp.n_height)
						t_bmp.p_buffer[size_t(v_seed.x + j) + size_t(v_seed.y - j) * t_bmp.n_width] = 0xff000000;
				}
			}
		}
		// rasterize seeds

		bool b_result = CTgaCodec::Save_TGA(p_s_filename, t_bmp, false);

		delete[] t_bmp.p_buffer;
		// cleanup

		return b_result;
	}

#endif // (_DEBUG || __BIN_PACKER_WANT_DEBUG_RASTER) && !__BIN_PACKER_NO_DEBUG_RASTER

protected:
	bool Update_SeedsEdges(const _TyItem &r_item)
	{
		try {
#ifdef __BIN_PACKER_USE_UNIFORM_GRID
			Hash_Box(r_item); // throws(std::bad_alloc)
#endif // __BIN_PACKER_USE_UNIFORM_GRID

			Vector2<_TySize> v_seed_top(TMan::n_X(r_item), TMan::n_Y(r_item) + TMan::n_Height(r_item));
			Vector2<_TySize> v_seed_right(TMan::n_X(r_item) + TMan::n_Width(r_item), TMan::n_Y(r_item));
			if(!b_Collision(v_seed_right))
				m_seed_list.insert(m_seed_list.begin(), v_seed_right); // add it to the beginning so it's used first
			if(!b_Collision(v_seed_top))
				m_seed_list.push_back(v_seed_top);
			// each box adds a single seed point at it's upper left and bottom right corner

			_TySize n_upper_edge_org = 0;
			_TySize n_right_edge_org = 0;
			{
				_TySize n_top_edge_y = TMan::n_Y(r_item) + TMan::n_Height(r_item);
				typename edge_map::/*const_*/iterator p_last_right = m_right_edge_list.upper_bound(TMan::n_X(r_item) + TMan::n_Width(r_item) - 1);
				if(p_last_right != m_right_edge_list.begin()) {
					for(-- p_last_right; p_last_right != m_right_edge_list.begin(); -- p_last_right) {
						_TySize n_edge_x = (*p_last_right).first;
						_TySize n_edge_y_org = (*p_last_right).second.n_org;
						_TySize n_edge_y0 = (*p_last_right).second.n_begin;
						_TySize n_edge_y1 = (*p_last_right).second.n_end;
						// start and end of the edge

						if(n_edge_y_org > n_top_edge_y || n_edge_y1 <= n_top_edge_y)
							continue;
						// this edge is below, there is little sense in adding another seed here

						Vector2<_TySize> v_intersection(n_edge_x, n_top_edge_y);
						if(!b_Collision(v_intersection))
							m_seed_list.push_back(v_intersection);
						// add a new seed point

						if(n_top_edge_y >= n_edge_y0 && n_top_edge_y < n_edge_y1) {
							n_upper_edge_org = n_edge_x;
							break;
						}
						// this edge collided with the top edge
					}
				}
				if(p_last_right == m_right_edge_list.begin()) {
					_ASSERTE((*p_last_right).first == 0 && (*p_last_right).second.n_begin == 0 &&
						(*p_last_right).second.n_end == m_n_height);
					// make sure the area edge is the first

					Vector2<_TySize> v_intersection(0, n_top_edge_y);
					if(!b_Collision(v_intersection)) // there are almost no collisions
						m_seed_list.push_back(v_intersection);
					// there was no collision, add a new seed point at the leftmost position
				}
			}
			// each box adds a single seed point at all the left intersections
			// of it's upper edge with all the right edges !above! it

			{
				_TySize n_right_edge_x = TMan::n_X(r_item) + TMan::n_Width(r_item);
				typename edge_map::/*const_*/iterator p_last_upper = m_upper_edge_list.upper_bound(TMan::n_Y(r_item) + TMan::n_Height(r_item) - 1);
				if(p_last_upper != m_upper_edge_list.begin()) {
					for(-- p_last_upper; p_last_upper != m_upper_edge_list.begin(); -- p_last_upper) {
						_TySize n_edge_y = (*p_last_upper).first;
						_TySize n_edge_x_org = (*p_last_upper).second.n_org;
						_TySize n_edge_x0 = (*p_last_upper).second.n_begin;
						_TySize n_edge_x1 = (*p_last_upper).second.n_end;
						// start and end of the edge

						if(n_edge_x_org > n_right_edge_x || n_edge_x1 <= n_right_edge_x)
							continue;
						// this edge is left, there is little sense in adding another seed here

						Vector2<_TySize> v_intersection(n_right_edge_x, n_edge_y);
						if(!b_Collision(v_intersection))
							m_seed_list.push_back(v_intersection);
						// add a new seed point

						if(n_right_edge_x >= n_edge_x0 && n_right_edge_x < n_edge_x1) {
							n_right_edge_org = n_edge_y;
							break;
						}
						// this edge collided with the right edge
					}
				}
				if(p_last_upper == m_upper_edge_list.begin()) {
					_ASSERTE((*p_last_upper).first == 0 && (*p_last_upper).second.n_begin == 0 &&
						(*p_last_upper).second.n_end == m_n_width);
					// make sure the area edge is the first

					Vector2<_TySize> v_intersection(n_right_edge_x, 0);
					if(!b_Collision(v_intersection)) // there are almost no collisions
						m_seed_list.push_back(v_intersection);
					// there was no collision, add a new seed point at the bottom
				}
			}
			// each box adds a single seed point at all the bottom intersections
			// of it's right edge with all the upper edges !right! to it

			
#ifdef __BIN_PACKER_EDGE_CULLING
			{
				const _TySize n_upper_edge_x0 = TMan::n_X(r_item);
				const _TySize n_upper_edge_x1 = TMan::n_X(r_item) + TMan::n_Width(r_item);
				const _TySize n_lower_edge_y = TMan::n_Y(r_item); // even more aggresive culling
				const _TySize n_upper_edge_y = TMan::n_Y(r_item) + TMan::n_Height(r_item);
				for(typename edge_map::iterator p_right_it = m_right_edge_list.lower_bound(n_upper_edge_x0);
				   p_right_it != m_right_edge_list.end(); ++ p_right_it) {
					const _TySize n_edge_x = (*p_right_it).first;
					const _TySize n_edge_y_org = (*p_right_it).second.n_org;
					const _TySize n_edge_y0 = (*p_right_it).second.n_begin;
					const _TySize n_edge_y1 = (*p_right_it).second.n_end;
					// start and end of the edge

					_ASSERTE(n_edge_x >= n_upper_edge_x0);
					if(n_edge_x >= n_upper_edge_x1)
						break;
					// the edge is not intersecting

					if(n_edge_y0 < n_lower_edge_y || n_edge_y_org > n_upper_edge_y)
						continue;
					// this edge is below / above

					_ASSERTE(n_edge_y_org <= n_upper_edge_y);
					(*p_right_it).second.n_org = min(n_edge_y0, n_upper_edge_y);
					// set a new origin
				}
			}
			{
				const _TySize n_left_edge_x = TMan::n_X(r_item); // even more aggresive culling
				const _TySize n_right_edge_x = TMan::n_X(r_item) + TMan::n_Width(r_item);
				const _TySize n_right_edge_y0 = TMan::n_Y(r_item);
				const _TySize n_right_edge_y1 = TMan::n_Y(r_item) + TMan::n_Height(r_item);
				for(typename edge_map::iterator p_upper_it = m_upper_edge_list.lower_bound(n_right_edge_y0);
				   p_upper_it != m_upper_edge_list.end(); ++ p_upper_it) {
					const _TySize n_edge_y = (*p_upper_it).first;
					const _TySize n_edge_x_org = (*p_upper_it).second.n_org;
					const _TySize n_edge_x0 = (*p_upper_it).second.n_begin;
					const _TySize n_edge_x1 = (*p_upper_it).second.n_end;
					// start and end of the edge

					_ASSERTE(n_edge_y >= n_right_edge_y0);
					if(n_edge_y >= n_right_edge_y1)
						break;
					// the edge is not intersecting

					if(n_edge_x0 < n_left_edge_x || n_edge_x_org > n_right_edge_x)
						continue;
					// this edge is below / above

					_ASSERTE(n_edge_x_org <= n_right_edge_x);
					(*p_upper_it).second.n_org = min(n_edge_x0, n_right_edge_x);
					// set a new origin
				}
			}
#endif // __BIN_PACKER_EDGE_CULLING
			// cull edges, blocked by this box

			m_upper_edge_list.insert(typename edge_map::value_type(TMan::n_Y(r_item) + TMan::n_Height(r_item),
				TEdge(n_upper_edge_org, TMan::n_X(r_item), TMan::n_X(r_item) + TMan::n_Width(r_item))));
			m_right_edge_list.insert(typename edge_map::value_type(TMan::n_X(r_item) + TMan::n_Width(r_item),
				TEdge(n_right_edge_org, TMan::n_Y(r_item), TMan::n_Y(r_item) + TMan::n_Height(r_item))));
			// add edges to the lists

			if(!m_seed_list.empty()) {
				_TySize x0 = TMan::n_X(r_item);
				_TySize y0 = TMan::n_Y(r_item);
				_TySize x1 = TMan::n_X(r_item) + TMan::n_Width(r_item);
				_TySize y1 = TMan::n_Y(r_item) + TMan::n_Height(r_item);
				for(size_t i = m_seed_list.size() - 1; i != SIZE_MAX; -- i) {
					Vector2<_TySize> v_seed = m_seed_list[i];
					if(v_seed.x >= x0 && v_seed.x < x1 &&
					   v_seed.y >= y0 && v_seed.y < y1) {
						m_seed_list.erase(m_seed_list.begin() + i);
						//++ i; // !!
					}
				}
			}
			// erase collided seeds (the naive way)
		} catch(std::bad_alloc&) {
			return false;
		}
		// add the new seeds, calculate and cull edges, etc.

		return true;
	}

#ifdef __BIN_PACKER_USE_UNIFORM_GRID

	void Hash_Box(const _TyItem &r_item) // throws(std::bad_alloc)
	{
		_TySize _n_x0 = TMan::n_X(r_item);
		_TySize _n_x1 = _n_x0 + TMan::n_Width(r_item);
		_TySize _n_y0 = TMan::n_Y(r_item);
		_TySize _n_y1 = _n_y0 + TMan::n_Height(r_item);
		// get box coords

		size_t n_x0 = _n_x0 / m_n_uniform_grid_cell_size;
		size_t n_y0 = _n_y0 / m_n_uniform_grid_cell_size;
		size_t n_x1 = (_n_x1 + m_n_uniform_grid_cell_size - 1) / m_n_uniform_grid_cell_size;
		size_t n_y1 = (_n_y1 + m_n_uniform_grid_cell_size - 1) / m_n_uniform_grid_cell_size;
		_ASSERTE(n_x0 < m_n_uniform_grid_width && n_y0 < m_n_uniform_grid_height);
		_ASSERTE(n_x1 <= m_n_uniform_grid_width && n_y1 <= m_n_uniform_grid_height);
		// get box coords in the uniform grid

		for(size_t y = n_y0; y < n_y1; ++ y) {
			for(size_t x = n_x0; x < n_x1; ++ x) {
				size_t n_cell_index = x + m_n_uniform_grid_width * y;
				// get cell to put the box to

				m_box_map[n_cell_index].push_back(&r_item);
				// store the pointer to the box in the map
			}
		}
		// add the box to all the cells it intersects
	}

	bool b_BoxCollision_Hash(const _TyItem &r_item) const
	{
		_TySize _n_x0 = TMan::n_X(r_item);
		_TySize _n_x1 = _n_x0 + TMan::n_Width(r_item);
		_TySize _n_y0 = TMan::n_Y(r_item);
		_TySize _n_y1 = _n_y0 + TMan::n_Height(r_item);
		// get box coords

		size_t n_x0 = size_t(_n_x0 / m_n_uniform_grid_cell_size);
		size_t n_y0 = size_t(_n_y0 / m_n_uniform_grid_cell_size);
		size_t n_x1 = size_t((_n_x1 + m_n_uniform_grid_cell_size - 1) / m_n_uniform_grid_cell_size);
		size_t n_y1 = size_t((_n_y1 + m_n_uniform_grid_cell_size - 1) / m_n_uniform_grid_cell_size);
		_ASSERTE(n_x0 < m_n_uniform_grid_width && n_y0 < m_n_uniform_grid_height);
		_ASSERTE(n_x1 <= m_n_uniform_grid_width && n_y1 <= m_n_uniform_grid_height);
		// get box coords in the uniform grid

		CFindBoxCollision collision(r_item);

		for(size_t y = n_y0; y < n_y1; ++ y) {
			for(size_t x = n_x0; x < n_x1; ++ x) {
				size_t n_cell_index = x + m_n_uniform_grid_width * y;
				// get cell to put the box to

				typename std::vector<const _TyItem*>::const_iterator p_end_it = m_box_map[n_cell_index].end();
				if(std::find_if(m_box_map[n_cell_index].begin(), p_end_it, collision) != p_end_it)
					return true;
				// check for collisions
			}
		}
		// check the box against all the boxes in all the cells it intersects


		return false;
	}

	bool b_PointCollision_Hash(Vector2<_TySize> v_point) const
	{
		size_t n_x = size_t(v_point.x / m_n_uniform_grid_cell_size);
		size_t n_y = size_t(v_point.y / m_n_uniform_grid_cell_size);
		// get coords in the uniform grid

		_ASSERTE(n_x < m_n_uniform_grid_width && n_y < m_n_uniform_grid_height);

		CFindPointCollision collision(v_point);
		{
			size_t n_cell_index = n_x + m_n_uniform_grid_width * n_y;
			// get cell to put the box to

			typename std::vector<const _TyItem*>::const_iterator p_end_it = m_box_map[n_cell_index].end();
			if(std::find_if(m_box_map[n_cell_index].begin(), p_end_it, collision) != p_end_it)
				return true;
			// check for collisions
		}
		// check the point against all the boxes in the cell it lies in

		return false;
	}

#endif // __BIN_PACKER_USE_UNIFORM_GRID

	bool b_Collision(Vector2<_TySize> v_point) const
	{
		if(v_point.x < 0 || v_point.y < 0 || v_point.x >= m_n_width || v_point.y >= m_n_height)
			return true;
		// the point is outside the area (is colliding with area boundaries)

#ifdef __BIN_PACKER_USE_UNIFORM_GRID
		bool b_result = b_PointCollision_Hash(v_point);
#ifdef _DEBUG
		bool b_result_dbg = std::find_if(m_off_area_list.begin(), m_off_area_list.end(),
			CFindPointCollision(v_point)) != m_off_area_list.end() ||
			std::find_if(m_box_list.begin(), m_box_list.end(),
			CFindPointCollision(v_point)) != m_box_list.end();
		_ASSERTE(b_result_dbg == b_result);
#endif // _DEBUG
		return b_result;
#else // __BIN_PACKER_USE_UNIFORM_GRID
		return std::find_if(m_off_area_list.begin(), m_off_area_list.end(),
			CFindPointCollision(v_point)) != m_off_area_list.end() ||
			std::find_if(m_box_list.begin(), m_box_list.end(),
			CFindPointCollision(v_point)) != m_box_list.end();
		// find collision with one of off-areas or boxes
#endif // __BIN_PACKER_USE_UNIFORM_GRID
	}

	bool b_Collision(const _TyItem &r_item) const
	{
		if(TMan::n_X(r_item) < 0 || TMan::n_Y(r_item) < 0 ||
		   TMan::n_X(r_item) + TMan::n_Width(r_item) > m_n_width ||
		   TMan::n_Y(r_item) + TMan::n_Height(r_item) > m_n_height)
			return true;
		// the box is outside the area (is colliding with area boundaries)

#ifdef __BIN_PACKER_USE_UNIFORM_GRID
		bool b_result = b_BoxCollision_Hash(r_item);
#ifdef _DEBUG
		bool b_result_dbg = std::find_if(m_off_area_list.begin(), m_off_area_list.end(),
			CFindBoxCollision(r_item)) != m_off_area_list.end() ||
			std::find_if(m_box_list.begin(), m_box_list.end(),
			CFindBoxCollision(r_item)) != m_box_list.end();
		_ASSERTE(b_result_dbg == b_result);
#endif // _DEBUG
		return b_result;
#else // __BIN_PACKER_USE_UNIFORM_GRID
		return std::find_if(m_off_area_list.begin(), m_off_area_list.end(),
			CFindBoxCollision(r_item)) != m_off_area_list.end() ||
			std::find_if(m_box_list.begin(), m_box_list.end(),
			CFindBoxCollision(r_item)) != m_box_list.end();
		// find collision with one of off-areas or the other boxes
#endif // __BIN_PACKER_USE_UNIFORM_GRID
	}
};

/**
 *	@brief a simple box packing problem solver
 *
 *	@tparam _TySize is type in which item dimensions are represented (such as int, float or size_t)
 *	@tparam _TyItem is item type
 *	@tparam _TyItemManipulator is item manipulator interface
 */
template <class _TySize, class _TyItem, class _TyItemManipulator>
class CBinPackingSolver {
public:
	typedef CBinPackingPage<_TySize, _TyItem, _TyItemManipulator> CPage;
	typedef _TyItemManipulator TMan;

	class CBasicPageFactory {
	protected:
		_TySize m_n_page_width, m_n_page_height;

	public:
		inline CBasicPageFactory(size_t n_page_width, size_t n_page_height)
			:m_n_page_width(n_page_width), m_n_page_height(n_page_height)
		{}

		inline CPage operator ()() const
		{
			return CPage(m_n_page_width, m_n_page_height);
		}
	};

public:
	/**
	 *	@brief prepares items to be packed
	 *
	 *	@tparam _ItemContainer is item container type, this might be std::vector<_TyItem>
	 *
	 *	@param[in,out] r_item_list list of items to be packed
	 *	@param[in] b_sort_items enables sorting intems by size
	 *	@param[in] b_directional_align enables rotating items so that they
	 *		are all rotated in the same direction (given by the longer edge)
	 *	@param[in] b_rotate_to_landscape 
	 */
	template <class _ItemContainer>
	static void Prepare_Items(_ItemContainer &r_item_list,
		bool b_sort_items = true, bool b_directional_align = true, bool b_rotate_to_landscape = true)
	{
		if(b_sort_items)
			std::sort(r_item_list.begin(), r_item_list.end(), b_HasLergerArea);
		// sort items by size (improves packing efficiency)

		if(b_directional_align) {
			if(b_rotate_to_landscape)
				std::for_each(r_item_list.begin(), r_item_list.end(), MakeLandscape);
			else
				std::for_each(r_item_list.begin(), r_item_list.end(), MakeStanding);
		}
		// orient items so they are width-oriented ("lanscape")
	}

	/**
	 *	@brief performs bin packing using the first fit algorithm
	 *
	 *	@tparam _ItemContainer is item container type, this might be std::vector<_TyItem>
	 *	@tparam _PageFactory is type of functor used to generate a new pages
	 *
	 *	@param[in,out] r_page_list is list of pages to be filled with given items
	 *		(may contain pre-generated pages)
	 *	@param[in,out] r_item_list is list of items to be packed
	 *	@param[in] page_factory is functor used to generate a new pages
	 *		(CBasicPageFactory can be used for this)
	 *	@param[in] b_allow_rotation is rotation enable flag
	 *	@param[in] f_rotation_thresh is rotation threshold (relative to item number;
	 *		0 means all items will be rotated, 1 means no items will be rotated)
	 *
	 *	@return Returns true on success, false on failure.
	 *
	 *	@note This always fails, may there be an item larger than a generated page.
	 */
	template <class _ItemContainer, class _PageFactory>
	static bool First_Fit(std::list<CPage> &r_page_list,
		_ItemContainer &r_item_list, _PageFactory page_factory,
		bool b_allow_rotation = true, float f_rotation_thresh = .75f)
	{
		_ASSERTE(f_rotation_thresh >= 0 && f_rotation_thresh <= 1);
		size_t n_rot_thresh = (b_allow_rotation)? size_t(r_item_list.size() * f_rotation_thresh) : r_item_list.size();
		size_t n_item_index = 0;
		for(typename _ItemContainer::iterator p_it = r_item_list.begin(),
		   p_end_it = r_item_list.end(); p_it != p_end_it; ++ p_it, ++ n_item_index) {
			_TyItem &r_item = *p_it;

			bool b_placed = false;
			for(typename std::list<CPage>::iterator p_pg_it = r_page_list.begin(),
			   p_pg_end_it = r_page_list.end(); p_pg_it != p_pg_end_it; ++ p_pg_it) {
				if(!(*p_pg_it).Add_Item(b_placed, r_item, n_item_index >= n_rot_thresh))
					return false;
				if(b_placed)
					break;
			}
			// attempts to place the item to any page available

			if(b_placed)
				continue;
			// if placed, move onto another item

			try {
				r_page_list.push_back(page_factory());
			} catch(std::bad_alloc&) {
				return false;
			}
			CPage &r_page = r_page_list.back();
			if(!r_page.Add_Item(b_placed, r_item, n_item_index >= n_rot_thresh))
				return false;
			if(!b_placed)
				return false; // the item would not fit in such page
			// attempts to place the item in a new page
		}

		return true;
	}

	/**
	 *	@brief performs bin packing using the best fit algorithm
	 *
	 *	@tparam _ItemContainer is item container type, this might be std::vector<_TyItem>
	 *	@tparam _PageFactory is type of functor used to generate a new pages
	 *
	 *	@param[in,out] r_page_list is list of pages to be filled with given items
	 *		(may contain pre-generated pages)
	 *	@param[in,out] r_item_list is list of items to be packed
	 *	@param[in] page_factory is functor used to generate a new pages
	 *		(CBasicPageFactory can be used for this)
	 *	@param[in] b_allow_rotation is rotation enable flag
	 *	@param[in] f_rotation_thresh is rotation threshold (relative to item number;
	 *		0 means all items will be rotated, 1 means no items will be rotated)
	 *
	 *	@return Returns true on success, false on failure.
	 *
	 *	@note This always fails, may there be an item larger than a generated page.
	 */
	template <class _ItemContainer, class _PageFactory>
	static bool Best_Fit(std::list<CPage> &r_page_list,
		_ItemContainer &r_item_list, _PageFactory page_factory,
		bool b_allow_rotation = true, float f_rotation_thresh = .75f)
	{
		std::vector<std::pair<double, CPage*> > page_order; // this is not very nice // @todo - improve this, then implement (second) worst fit
		try {
			for(typename std::list<CPage>::iterator p_pg_it = r_page_list.begin(),
			   p_pg_end_it = r_page_list.end(); p_pg_it != p_pg_end_it; ++ p_pg_it) {
				page_order.push_back(std::make_pair((*p_pg_it).f_Free_Space(), &(*p_pg_it)));
			}
		} catch(std::bad_alloc&) {
			return false;
		}
		std::sort(page_order.begin(), page_order.end(), b_SmallerFreeSpace);
		// create page order

		_ASSERTE(f_rotation_thresh >= 0 && f_rotation_thresh <= 1);
		size_t n_rot_thresh = (b_allow_rotation)? size_t(r_item_list.size() * f_rotation_thresh) : r_item_list.size();
		size_t n_item_index = 0;
		for(typename _ItemContainer::iterator p_it = r_item_list.begin(),
		   p_end_it = r_item_list.end(); p_it != p_end_it; ++ p_it, ++ n_item_index) {
			_TyItem &r_item = *p_it;

			bool b_placed = false;
			for(typename std::vector<std::pair<double, CPage*> >::iterator p_pg_it = page_order.begin(),
			   p_pg_end_it = page_order.end(); p_pg_it != p_pg_end_it; ++ p_pg_it) {
				if(!(*p_pg_it).second->Add_Item(b_placed, r_item, n_item_index >= n_rot_thresh))
					return false;
				if(b_placed) {
					(*p_pg_it).first = (*p_pg_it).second->f_Free_Space(); // update free space
					std::stable_sort(page_order.begin(), page_order.end(),
						b_SmallerFreeSpace); // keep page order sorted
					break;
				}
			}
			// attempts to place the item to any page available

			if(b_placed)
				continue;
			// if placed, move onto another item

			try {
				r_page_list.push_back(page_factory());
				page_order.push_back(std::make_pair(r_page_list.back().f_Free_Space(), &r_page_list.back()));
			} catch(std::bad_alloc&) {
				return false;
			}
			std::pair<double, CPage*> &r_page_space = page_order.back();
			if(!r_page_space.second->Add_Item(b_placed, r_item, n_item_index >= n_rot_thresh))
				return false;
			if(!b_placed)
				return false; // the item would not fit in such page
			r_page_space.first = r_page_space.second->f_Free_Space();
			std::stable_sort(page_order.begin(),
				page_order.end(), b_SmallerFreeSpace); // keep page order sorted
			// attempts to place the item in a new page
		}

		return true;
	}

protected:
	static inline bool b_SmallerFreeSpace(const std::pair<double, CPage*> &a,
		const std::pair<double, CPage*> &b)
	{
		return a.first < b.first;
	}

	static inline void MakeLandscape(_TyItem &r_item)
	{
		if(TMan::b_CanTurn(r_item) && TMan::n_Height(r_item) > TMan::n_Width(r_item))
			TMan::Turn(r_item);
	}

	static inline void MakeStanding(_TyItem &r_item)
	{
		if(TMan::b_CanTurn(r_item) && TMan::n_Height(r_item) < TMan::n_Width(r_item))
			TMan::Turn(r_item);
	}

	static inline bool b_HasLergerArea(const _TyItem &r_b1, const _TyItem &r_b2)
	{
		return double(TMan::n_Width(r_b1)) * TMan::n_Height(r_b1) >
			double(TMan::n_Width(r_b2)) * TMan::n_Height(r_b2);
	}
};

#endif // !__BIN_PACKING_INCLUDED
