/** @file RectangleBinPack.cpp
	@author Jukka Jylänki

	This work is released to Public Domain, do whatever you want with it.

	@brief RectangleBinPack is a data structure for performing online rectangle bin packing.
*/
#include "RectangleBinPack.h"

/** Restarts the packing process, clearing all previously packed rectangles and
	sets up a new bin of a given initial size. These bin dimensions stay fixed during
	the whole packing process, i.e. to change the bin size, the packing must be
	restarted again with a new call to Init(). */
void RectangleBinPack::Init(int width, int height)
{
	binWidth = width;
	binHeight = height;
	root.left = root.right = 0;
	root.x = root.y = 0;
	root.width = width;
	root.height = height;
}

/** @return A value [0, 1] denoting the ratio of total surface area that is in use.
	0.0f - the bin is totally empty, 1.0f - the bin is full. */
float RectangleBinPack::Occupancy() const
{
	unsigned long totalSurfaceArea = binWidth * binHeight;
	unsigned long usedSurfaceArea = UsedSurfaceArea(root);

	return (float)usedSurfaceArea/totalSurfaceArea;
}

/** Recursively calls itself. */
unsigned long RectangleBinPack::UsedSurfaceArea(const Node &node) const
{
	if (node.left || node.right)
	{
		unsigned long usedSurfaceArea = node.width * node.height;
		if (node.left)
			usedSurfaceArea += UsedSurfaceArea(*node.left);
		if (node.right)
			usedSurfaceArea += UsedSurfaceArea(*node.right);

		return usedSurfaceArea;
	}

	// This is a leaf node, it doesn't constitute to the total surface area.
	return 0;
}

/** Running time is linear to the number of rectangles already packed. Recursively calls itself.
	@return 0 If the insertion didn't succeed. */
RectangleBinPack::Node *RectangleBinPack::Insert(RectangleBinPack::Node *node, int width, int height)
{
	// If this node is an internal node, try both leaves for possible space.
	// (The rectangle in an internal node stores used space, the leaves store free space)
	if (node->left || node->right)
	{
		if (node->left)
		{
			Node *newNode = Insert(node->left, width, height);
			if (newNode)
				return newNode;
		}
		if (node->right)
		{
			Node *newNode = Insert(node->right, width, height);
			if (newNode)
				return newNode;
		}
		return 0; // Didn't fit into either subtree!
	}

	// This node is a leaf, but can we fit the new rectangle here?
	if (width > node->width || height > node->height)
		return 0; // Too bad, no space.

	// The new cell will fit, split the remaining space along the shorter axis,
	// that is probably more optimal.
	int w = node->width - width;
	int h = node->height - height;
	node->left = new Node;
	node->right = new Node;
	if (w <= h) // Split the remaining space in horizontal direction.
	{
		node->left->x = node->x + width;
		node->left->y = node->y;
		node->left->width = w;
		node->left->height = height;

		node->right->x = node->x;
		node->right->y = node->y + height;
		node->right->width = node->width;
		node->right->height = h;
	}
	else // Split the remaining space in vertical direction.
	{
		node->left->x = node->x;
		node->left->y = node->y + height;
		node->left->width = width;
		node->left->height = h;

		node->right->x = node->x + width;
		node->right->y = node->y;
		node->right->width = w;
		node->right->height = node->height;
	}
	// Note that as a result of the above, it can happen that node->left or node->right
	// is now a degenerate (zero area) rectangle. No need to do anything about it,
	// like remove the nodes as "unnecessary" since they need to exist as children of
	// this node (this node can't be a leaf anymore).

	// This node is now a non-leaf, so shrink its area - it now denotes
	// *occupied* space instead of free space. Its children spawn the resulting
	// area of free space.
	node->width = width;
	node->height = height;
	return node;
}