//	Physical model of landscape and objects.
//
//	Author	Matthew Caryl
//	Created 13.12.96
//
//  Although under copywrite to the author (Matthew Caryl) this code can be copied and modified for non-commercial
//  purposes as long as any derivatives contain this condition.

package ADT;

public final class Model {
	//
	//	Private interface of Model
	//
	
	//	Maths routines
	private static final float	PI				= (float) (Math.PI);
	private static final float	TWOPI			= (float) (2.0 * Math.PI);
	private static final float	sqr(float n)		{return n * n;}
	private static final int	max(int x, int y)	{return Math.max(x, y);}
	
	private static Physical[]	physicalStore = new Physical[0];
	private static boolean		collision;
	
	private static void swap(int x, int y) {
		Physical swap = physicalStore[x];
		physicalStore[x] = physicalStore[y];
		physicalStore[y] = swap;
		}
	
	private static void quickSort(int left, int right) {
		if (left < right) {
			int h = (int) ((right - left) / 2) + left;
			int	l, r;
			int	x = physicalStore[left].x();
			
			for (l = left + 1, r = right; l <= r;)
				if (physicalStore[l].x() < x)
					l++;
				else if (physicalStore[r].x() >= x)
					r--;
				else {
					swap(l, r);
					l++;
					r--;
					}
			swap(left, l - 1);
			quickSort(left, l - 2);
			quickSort(l, right);
			}
		}
	
	// search back in area of physicalStore for all physicals >= x
	// if none are found return right + 1
	private static int searchLeft(int left, int right, int x) {
		if (left <= right) {
			int h = (int) ((right - left) / 2) + left;
			
			if (physicalStore[h].x() >= x)
				return searchLeft(left, h - 1, x);
			else
				return searchLeft(h + 1, right, x);
			}
		else
			return right + 1;
		}
	
	// search forward in area of physicalStore for all physicals <= x
	// if none are found return left - 1
	private static int searchRight(int left, int right, int x) {
		if (left <= right) {
			int h = right - (int) ((right - left) / 2);
			
			if (physicalStore[h].x() <= x)
				return searchRight(h + 1, right, x);
			else
				return searchRight(left, h - 1, x);
			}
		else
			return left - 1;
		}
		
	// physical - physical collisions within physicalStore
	// return maximum physical radius within check
	private static int collision(int left, int right, boolean first) {
		if (left < right) {
			int h = (int) ((right - left) / 2) + left;
			int	radius = collision(left, h, first) + collision(h + 1, right, first);
			int	l = searchLeft(left, h, physicalStore[h + 1].x() - radius);
			int	r = searchRight(h + 1, right, physicalStore[h].x() + radius);

			for (int i = h + 1; i <= r; i++) {
				Physical p = physicalStore[i];
				
				for (int j = l; j <= h; j++) {
					Physical q = physicalStore[j];
					
					if (sqr(p.x() - q.x()) + sqr(p.y() - q.y()) < sqr(p.radius() + q.radius())) {
						p.collision(q, first);
						q.collision(p, first);
						collision = true;
						}
					}
				}
			
			return radius;
			}
		else
			return (int) physicalStore[left].radius() + 1;
		}
	
	//
	//	Public interface of Model
	//

	public static synchronized boolean collision(Queue physicals, boolean first) {
		if (physicals.size() > physicalStore.length)
			physicalStore = new Physical[(int) (1.5 * physicals.size())];
		
		int storeEnd = physicals.size() - 1;
		
		if (storeEnd <= 0)
			return false;
			
		try {
			for (int i = storeEnd; i >= 0; i--)
				physicalStore[i] = (Physical) physicals.requeue();
			}
		catch (QueueEmpty e) {
			}
		
		collision = false;
		quickSort(0, storeEnd);
		collision(0, storeEnd, first);
		
		return collision;
		}
	
	public static synchronized boolean collision(Physical[] physicals, int length, boolean first) {
		if (length > physicalStore.length)
			physicalStore = new Physical[(int) (1.5 * physicals.length)];
		
		int storeEnd = length - 1;
		
		if (storeEnd <= 0)
			return false;
		
		for (int i = storeEnd; i >= 0; i--)
			physicalStore[i] = physicals[i];
		
		collision = false;
		quickSort(0, storeEnd);
		collision(0, storeEnd, first);
		
		return collision;
		}
	
	public static synchronized boolean collision(Queue physicals, Physical physical) {
		if (physicals.size() > physicalStore.length)
			physicalStore = new Physical[(int) (1.5 * physicals.size())];
		
		try {
			for (int i = physicals.size() - 1; i >= 0; i--)
				physicalStore[i] = (Physical) physicals.requeue();
			}
		catch (QueueEmpty e) {
			}
		
		int	x = physical.x();
		int	y = physical.y();
		float r = physical.radius();
		
		for (int i = physicals.size() - 1; i >= 0; i--) {
			Physical p = physicalStore[i];
				
			if (physical == p)
				continue;
			
			if (sqr(x - p.x()) + sqr(y - p.y()) < sqr(r + p.radius()))
				return true;
			}
		
		return false;
		}
	
	public static synchronized boolean collision(Physical[] physicals, int length, Physical physical) {
		if (length > physicalStore.length)
			physicalStore = new Physical[(int) (1.5 * length)];
		
		for (int i = length - 1; i >= 0; i--)
			physicalStore[i] = physicals[i];
		
		int	x = physical.x();
		int	y = physical.y();
		float r = physical.radius();
		
		for (int i = length - 1; i >= 0; i--) {
			Physical p = physicalStore[i];
			
			if (physical == p)
				continue;
			if (sqr(x - p.x()) + sqr(y - p.y()) < sqr(r + p.radius()))
				return true;
			}
		
		return false;
		}
	}