/*
 * Faculty of Applied Science and Engineering, University of Toronto
 * CSC181: Introduction to Computer Programming, Fall 2000
 *
 * Assignment: 2
 * File: a2.c
 * Author: Ray Ortigas (rayo@dgp.toronto.edu)
 * Contains: Function definitions for A2.
 */

#include <stdio.h>
#include <math.h>
#include <assert.h>
#include "a2.h"

double max(double a, double b) { return a > b ? a : b; }
double min(double a, double b) { return a < b ? a : b; }

Point pointInit(const double x, const double y) {
	Point result;
	result.x = x;
	result.y = y;
	return result;
}

double pointX(const Point p) { return p.x; }

double pointY(const Point p) { return p.y; }

double pointDistanceBetween(const Point p1, const Point p2) {
	double dx = p1.x-p2.x;
	double dy = p1.y-p2.y;
	return sqrt(dx*dx + dy*dy);
}

boolean pointAreEqual(const Point p1, const Point p2) {
	return p1.x == p2.x && p1.y == p2.y;
}

Rectangle rectangleInit(const Point c, const double w, const double h) {
	Rectangle result;
	result.c = c;
	result.w = w;
	result.h = h;
	return result;
}

Point rectangleCentre(const Rectangle r) { return r.c; }

double rectangleWidth(const Rectangle r) { return r.w; }

double rectangleHeight(const Rectangle r) { return r.h; }

boolean	rectangleAreEqual(const Rectangle r1, const Rectangle r2) {
	return pointAreEqual(r1.c, r2.c) && r1.w == r2.w && r1.h == r2.h;
}

Rectangle rectangleUnion(const Rectangle r1, const Rectangle r2) {
	Rectangle result;
	double rr1 = r1.c.x + r1.w/2.0;
	double rr2 = r2.c.x + r2.w/2.0;
	double lr1 = r1.c.x - r1.w/2.0;
	double lr2 = r2.c.x - r2.w/2.0;
	double tr1 = r1.c.y + r1.h/2.0;
	double tr2 = r2.c.y + r2.h/2.0;
	double br1 = r1.c.y - r1.h/2.0;
	double br2 = r2.c.y - r2.h/2.0;

	result.c.x = (max(rr1, rr2) + min(lr1, lr2))/2.0;
	result.c.y = (max(tr1, tr2) + min(br1, br2))/2.0;
	result.w = max(rr1, rr2) - min(lr1, lr2);
	result.h = max(tr1, tr2) - min(br1, br2);
	return result;
}

boolean isBetween(double x, double a, double b) {
	return (a <= x && x <= b) || (b <= x && x <= a);
}

Rectangle rectangleIntersection(const Rectangle r1, const Rectangle r2) {
	Rectangle result = rectangleInit(pointInit(0, 0), 0, 0);
	double rr1 = r1.c.x + r1.w/2.0;
	double rr2 = r2.c.x + r2.w/2.0;
	double lr1 = r1.c.x - r1.w/2.0;
	double lr2 = r2.c.x - r2.w/2.0;
	double tr1 = r1.c.y + r1.h/2.0;
	double tr2 = r2.c.y + r2.h/2.0;
	double br1 = r1.c.y - r1.h/2.0;
	double br2 = r2.c.y - r2.h/2.0;

	if ((isBetween(rr1, lr2, rr2) || isBetween(rr2, lr1, rr1))
		&& (isBetween(tr1, br2, tr2) || isBetween(tr2, br1, tr1))) {
		
		result.c.x = (min(rr1, rr2) + max(lr1, lr2))/2.0;
		result.c.y = (min(tr1, tr2) + max(br1, br2))/2.0;
		result.w = min(rr1, rr2) - max(lr1, lr2);
		result.h = min(tr1, tr2) - max(br1, br2);
	}

	return result;
}

double rectangleArea(const Rectangle r) { return r.w * r.h; }

RectangleList rectangleListInit(void) {
	RectangleList result;
	result.rectanglesSize = 0;
	return result;
}

int rectangleListSize(const RectangleList rl) {
	return rl.rectanglesSize;
}

Rectangle rectangleListGet(const RectangleList rl, const int i) {
	assert(i >= 0 && i < rl.rectanglesSize);
	return rl.rectangles[i];
}

RectangleList rectangleListAdd(const RectangleList rl, const Rectangle r) {
	RectangleList result = rl;
	result.rectangles[result.rectanglesSize] = r;
	result.rectanglesSize++;
	return result;
}

RectangleList rectangleListSet
(const RectangleList rl, const Rectangle r, const int i) {
	RectangleList result;
	assert(i >= 0 && i < rl.rectanglesSize);

	result = rl;
	result.rectangles[i] = r;
	return result;
}

RectangleList rectangleListSubList
(const RectangleList rl, const int a, const int b) {
	RectangleList result;
	int i;
	
	assert(0 <= a && a <= b && b <= rl.rectanglesSize);

	for (i = 0; i <= b-a; i++) {
		result.rectangles[i] = rl.rectangles[a+i];
	}
	result.rectanglesSize = b-a;
	return result;
}

Rectangle rectangleListUnion(const RectangleList rl) {
	Rectangle result = rectangleInit(pointInit(0, 0), 0, 0);

	if (rl.rectanglesSize > 0) {
		int i = 1;
		result = rl.rectangles[0];
		while (i != rl.rectanglesSize) {
			result = rectangleUnion(result, rl.rectangles[i]);
			i++;
		}
	}

	return result;
}

Rectangle rectangleListIntersection(const RectangleList rl) {
	Rectangle result = rectangleInit(pointInit(0, 0), 0, 0);

	if (rl.rectanglesSize > 0) {
		int i = 1;
		result = rl.rectangles[0];
		while (i != rl.rectanglesSize) {
			result = rectangleIntersection(result, rl.rectangles[i]);
			i++;
		}
	}

	return result;
}

double rectangleListArea
(const RectangleList rl, const boolean discountOverlap) {
	double result = 0.0;

	if (!discountOverlap) {
		int i;
		for (i = 0; i != rl.rectanglesSize; i++) {
			result += rectangleArea(rl.rectangles[i]);
		}
	}
	else {
		/*
		 * n - the number of rectangles
		 * j - number of possible subsets of rectangles
		 */
		int n = rl.rectanglesSize;
		int j;
		for (j = 0; j != pow(2, n); j++) {
			/*
			 * k - number of rectangles in subset j
			 * x - starts out as j, used as binary representation
			 *     to determine which rectangles are included
			 * i - the index of the rectangle we are considering
			 *     for inclusion in the subset
			 */
			int k, x, i;
			Rectangle intersection = rectangleInit(pointInit(0, 0), 0, 0);
			for (k = 0, x = j, i = 0; x != 0; x /= 2, i++) {
				if (x % 2 == 1) {
					intersection = (k == 0)
						? rl.rectangles[i]
						: rectangleIntersection
							(intersection, rl.rectangles[i]);
					k++;
				}
			}

			result += (k % 2 == 0)
				? -rectangleArea(intersection)
				: rectangleArea(intersection);
		}
	}

	return result;
}