/*
 * IMPLEMENTATION NOTES.
 * 
 * The rectangular area is split into a grid of slots of fixed size. Each slot
 * is initially empty, that is its value is zero. By marking some zone as "used"
 * the corresponding involved slots are set to 1.
 */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>
#include <string.h>

#include "../../src/util/memory.h"
#include "../../src/util/error.h"

#define ratnest_IMPORT
#include "ratnest.h"

/** Granularity. */
#define ratnest_N (60)

struct ratnest_Type {
	/** Rectangular region to monitor. */
	ratnest_Rect bounds;
	/** Size of a slot. */
	double dx, dy;
	/** Each slot value is either 0 (not occupied) or 1 (occupied). */
	char slots[ratnest_N][ratnest_N];
};


char *ratnest_RectToString(ratnest_Rect *r)
{
	static char s[99];
	snprintf(s, sizeof(s), "[%g, %g, %g, %g]", r->x1, r->y1, r->x2, r->y2);
	return s;
}


/**
 * This module assumes each rectangle be not empty and (x1,y1) be the bottom-
 * left corner. Fatal error if it is not.
 * @param r
 */
static void ratnest_checkRect(ratnest_Rect *r)
{
	if( !(r->x1 < r->x2 && r->y1 < r->y2) )
		error_internal("invalid rectangle: %s", ratnest_RectToString(r));
}

/*
static void ratnest_destruct(void *p)
{
	ratnest_Type *o = (ratnest_Type *) p;
}
*/

ratnest_Type * ratnest_new(ratnest_Rect *bounds)
{
	ratnest_checkRect(bounds);
	ratnest_Type * this = memory_allocate(sizeof(ratnest_Type), NULL);
	this->bounds = *bounds;
	this->dx = (bounds->x2 - bounds->x1) / ratnest_N;
	this->dy = (bounds->y2 - bounds->y1) / ratnest_N;
	memory_zero(&this->slots);
	return this;
}


void ratnest_markSegment(ratnest_Type *this, double x1, double y1, double x2, double y2)
{
	// FIXME: do clipping; hopefully not necessary.
	double deltax = x2 - x1;
	double deltay = y2 - y1;
	int nsteps_h = fabs(deltax) / this->dx;
	int nsteps_v = fabs(deltay) / this->dy;
	int nsteps = (nsteps_h < nsteps_v)? nsteps_v : nsteps_h;
	
	// This algo is simple but it does not cover all the slots the segment
	// pass over. Doubling the number of steps mitigates this issue giving
	// a result good enough.
	// Moreover, add 1 to force at least 1 slot be occupied by very short
	// segments.
	nsteps = 2*nsteps + 1;
	
	int i;
	for(i = 0; i <= nsteps; i++){
		int h = (x1 + i * deltax /nsteps - this->bounds.x1) / this->dx;
		if( !(0 <= h && h < ratnest_N) )
			continue;
		int v = (y1 + i * deltay /nsteps - this->bounds.y1) / this->dy;
		if( !(0 <= v && v < ratnest_N) )
			continue;
		this->slots[v][h] = 1;
	}
}


/**
 * Clip the rectangle to the boundary.
 * @param this
 * @param r Modified in place with the clipped rectangle!
 * @return True if the resulting rectangle is not-empty.
 */
static int ratnest_clipRectToBounds(ratnest_Type *this, ratnest_Rect *r)
{
	// left bound:
	if( r->x2 <= this->bounds.x1 )
		return 0;
	if( r->x1 < this->bounds.x1 )
		r->x1 = this->bounds.x1;
	
	// right bound:
	if( this->bounds.x2 <= r->x1 )
		return 0;
	if( this->bounds.x2 < r->x2 )
		r->x2 = this->bounds.x2;
	
	// bottom bound:
	if( r->y2 <= this->bounds.y1 )
		return 0;
	if( r->y1 < this->bounds.y1 )
		r->y1 = this->bounds.y1;
	
	// top bound:
	if( this->bounds.y2 <= r->y1 )
		return 0;
	if( this->bounds.y2 < r->y2 )
		r->y2 = this->bounds.y2;
	
	if( (r->x2 - r->x1) * (r->y2 - r->y1) <= 0 )
		return 0;
	
	return 1;
}


void ratnest_markRect(ratnest_Type *this, ratnest_Rect *r)
{
	ratnest_checkRect(r);
	ratnest_Rect r1 = *r;
	if( ! ratnest_clipRectToBounds(this, &r1) )
		return;
	int h1 = (r1.x1 - this->bounds.x1) / this->dx;
	if( h1 >= ratnest_N )
		h1 = ratnest_N - 1;
	int h2 = (r1.x2 - this->bounds.x1) / this->dx;
	if( h2 >= ratnest_N )
		h2 = ratnest_N - 1;
	
	int v1 = (r1.y1 - this->bounds.y1) / this->dy;
	if( v1 >= ratnest_N )
		v1 = ratnest_N - 1;
	int v2 = (r1.y2 - this->bounds.y1) / this->dy;
	if( v2 >= ratnest_N )
		v2 = ratnest_N - 1;
	int h, v;
	for(v = v1; v <= v2; v++)
		for(h = h1; h <= h2; h++)
			this->slots[v][h] = 1;
}


int  ratnest_place(ratnest_Type *this, ratnest_Rect *r, ratnest_Rect *found)
{
	ratnest_checkRect(r);
	double req_width = r->x2 - r->x1;
	double req_height = r->y2 - r->y1;
	if( !(req_width <= this->bounds.x2 - this->bounds.x1
		&& req_height <= this->bounds.y2 - this->bounds.y1) )
		error_internal("rectangle too big to place: %s", ratnest_RectToString(r));
	
	// No. of slot required (width and height):
	int width = ceil(req_width / this->dx);
	int height = ceil(req_height / this->dy);
	
	// Limits of the search area among slots:
	int hmax = ratnest_N - width;
	int vmax = ratnest_N - height;
	
	// Initial search area [h1,v1,h2,v2] among slots is the slot where the
	// given rectangle is located; if occupied, widens the search area by
	// one slot and tray again with the slots added on the border of that
	// larger area.
	int h1 = (r->x1 - this->bounds.x1)/this->dx;
	if( h1 < 0 )  h1 = 0;
	else if( h1 > hmax )  h1 = hmax;
	int v1 = (r->y1 - this->bounds.y1)/this->dy;
	if( v1 < 0 )  v1 = 0;
	else if( v1 > vmax )  v1 = vmax;
	int h2 = h1;
	int v2 = v1;
	
	while(1){
		
		// Search place along the border of [h1,v1,h2,v2]:
		int v, h;
		for(v = v2; v >= v1; v--){
			for(h = h2; h >= h1; h--){
				
				if( !(v == v1 || v == v2 || h == h1 || h == h2) )
					// Not a slot on the border of [h1,v1,h2,v2].
					continue;
				
				// Check if the slots are free:
				int occupied = 0;
				int v1, h1;
				for(v1 = v; v1 < v + height; v1++){
					for(h1 = h; h1 < h + width; h1++){
						if( this->slots[v1][h1] != 0 ){
							occupied = 1;
							break;
						}
					}
					if( occupied )
						break;
				}
				
				if( ! occupied ){
					// Put the requested rectangle at the center of the available
					// free slots area, so we also have a bit of margin added.
					double avail_width = width * this->dx;
					double avail_height = height * this->dy;
					found->x1 = this->bounds.x1 + h * this->dx + (avail_width - req_width)/2;
					found->y1 = this->bounds.y1 + v * this->dy + (avail_height - req_height)/2;
					found->x2 = found->x1 + req_width;
					found->y2 = found->y1 + req_height;
					return 1;
				}
			}
		}
		
		// Widens search area [h1,v1,h2,v2] by one slot and retry on the border.
		int wider = 0;
		if( v1 > 0 ){
			v1--;
			wider = 1;
		}
		if( v2 < vmax ){
			v2++;
			wider = 1;
		}
		if( h1 > 0 ){
			h1--;
			wider = 1;
		}
		if( h2 < hmax ){
			h2++;
			wider = 1;
		}
		if( ! wider ){
			// Cannot enlarge search area any further -- give up.
			return 0;
		}
	}
}


/**
 * Draws a circle on each occupied slot.
 * @param this
 * @param ps
 */
/*
void ratnest_debug(ratnest_Type *this, ps_Type *ps)
{
	ps_setLineWidth(ps, 0.2);
	int h, v;
	for(h = 0; h < ratnest_N; h++){
		double x = this->bounds.x1 + h*this->dx;
		for(v = 0; v < ratnest_N; v++){
			if( this->slots[v][h] == 0 )
				continue;
			double y = this->bounds.y1 + v*this->dy;
			ps_drawRect(ps, x, y, this->dx, this->dy);
		}
	}
}
*/