/*
	Netwar
	Copyright (C) 2002  Daniel Grund, Kyle Kakligian, Jason Komutrattananon, & Brian Hibler.

	This file is part of Netwar.

	Netwar is free software; you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation; either version 2 of the License, or
	(at your option) any later version.

	Netwar is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with Netwar; if not, write to the Free Software
	Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

package netwar.game;
import netwar.utils.*;
import netwar.utils.vectorgraphics.*;

/** This class provides a high-RAM, low computation way to find a listing of all
 * other GameObjects, sorted from closest to farthest. This also provides
 * pre-calculated distance squared values. These are faster to calculate than distances,
 * but can be compared as if they were distances to find longer or shorter.
 */
public class SelfSortingMutualDistanceSquared {
	GameObject old;
	GameObject young;
	SelfSortingMutualDistanceSquared nextOld = null;
	SelfSortingMutualDistanceSquared nextYoung = null;
	SelfSortingMutualDistanceSquared prevOld = null;
	SelfSortingMutualDistanceSquared prevYoung = null;
	Point3D oldToYoung;
	Point3D youngToOld;
	float distanceSquared;
	
	/** This calls the constructor for SSMDS to prevent the new object
	 * from being assigned to a reference, which would be improper usage.
	 * The constructor automatically integrates the SSMDS into both
	 * GameObjects' lists.
	 * @param younger the newly made GameObject.
	 * @param older the GameObject already included in the system.
	 */
	public static void newSSMDS(GameObject younger, GameObject older) {
		new SelfSortingMutualDistanceSquared(younger, older);
	}
	private SelfSortingMutualDistanceSquared(GameObject younger, GameObject older) {
		old = older;
		young = younger;
		oldToYoung = new Point3D(young.locate());
		oldToYoung.doDifference(old.locate());
		youngToOld = oldToYoung.getProduct(-1);
		distanceSquared = youngToOld.getLengthSquared();
	
		nextOld = old.firstSSMDS;
		while((nextOld != null) && (nextOld.distanceSquared < distanceSquared)) {
			prevOld = nextOld;
			nextOld = nextOld.getNext(old);
		}
		if(nextOld != null)
			nextOld.setPrev(old, this);
		if(prevOld != null)
			prevOld.setNext(old, this);
		else
			old.firstSSMDS = this;
		
		nextYoung = young.firstSSMDS;
		while((nextYoung != null) && (nextYoung.distanceSquared < distanceSquared)) {
			prevYoung = nextYoung;
			nextYoung = nextYoung.getNext(young);
		}
		if(nextYoung != null)
			nextYoung.setPrev(young,this);
		if(prevYoung != null)
			prevYoung.setNext(young, this);
		else
			young.firstSSMDS = this;
	}
	/** When called on the go.firstSSMDS, it will recursively remove all of the
	 * SSMDSs' which reference go.
	 * @param go The GameObject which is being invalidated.
	 */
	public void remove(GameObject go) {
		if(go == young) {
			if(prevOld == null)
				old.firstSSMDS = nextOld;
			else
				prevOld.setNext(old, nextOld);
			if(nextOld != null)
				nextOld.setPrev(old, prevOld);
			if(nextYoung != null)
				nextYoung.remove(young);
		}else{
			Assert.notFalse(go == old, "Non-owner attempted remove() on SSMDS");
			if(prevYoung == null)
				young.firstSSMDS = nextYoung;
			else
				prevYoung.setNext(young, nextYoung);
			if(nextYoung != null)
				nextYoung.setPrev(young, prevYoung);
			if(nextOld != null)
				nextOld.remove(old);
		}
		//Nullify everything, so garbage collector can work.
		nextYoung = null;
		prevYoung = null;
		nextOld = null;
		prevOld = null;
		young = null;
		old = null;
		oldToYoung = null;
		youngToOld = null;
	}
	
	/** When a GameObject moves, it should call this on each SSMDS in its list.
	 * This is the responsibility of the GameObject, because the order of the
	 * list changes due to each update.
	 * This will adjust the sorting of all the lists.
	 */
	public void update() {
		oldToYoung.set(young.locate());
		oldToYoung.doDifference(old.locate());
		youngToOld.set(oldToYoung);
		youngToOld.doProduct(-1);
		distanceSquared = youngToOld.getLengthSquared();
	
		if((prevOld != null) && (prevOld.distanceSquared > distanceSquared)) {
			prevOld.setNext(old, nextOld);
			if(nextOld != null)
				nextOld.setPrev(old, prevOld);
			while((prevOld != null) && (prevOld.distanceSquared > distanceSquared)) {
				nextOld = prevOld;
				prevOld = prevOld.getPrev(old);
			}
			if(nextOld != null)
				nextOld.setPrev(old, this);
			if(prevOld != null)
				prevOld.setNext(old, this);
			else
				old.firstSSMDS = this;

		}else if((nextOld != null) && (nextOld.distanceSquared < distanceSquared)) {
			if(prevOld != null)
				prevOld.setNext(old, nextOld);
			else
				old.firstSSMDS = nextOld;
			nextOld.setPrev(old, prevOld);
			while((nextOld != null) && (nextOld.distanceSquared < distanceSquared)) {
				prevOld = nextOld;
				nextOld = nextOld.getNext(old);
			}
			if(nextOld != null)
				nextOld.setPrev(old, this);
			if(prevOld != null)
				prevOld.setNext(old, this);
			else
				old.firstSSMDS = this;

		}
		if((prevYoung != null) && (prevYoung.distanceSquared > distanceSquared)) {
			prevYoung.setNext(young, nextYoung);
			if(nextYoung != null)
				nextYoung.setPrev(young, prevYoung);
			while((prevYoung != null) && (prevYoung.distanceSquared > distanceSquared)) {
				nextYoung = prevYoung;
				prevYoung = prevYoung.getPrev(young);
			}
			if(nextYoung != null)
				nextYoung.setPrev(young, this);
			if(prevYoung != null)
				prevYoung.setNext(young, this);
			else
				young.firstSSMDS = this;

		}else if((nextYoung != null) && (nextYoung.distanceSquared < distanceSquared)) {
			if(prevYoung != null)
				prevYoung.setNext(young, nextYoung);
			else
				young.firstSSMDS = nextYoung;
			nextYoung.setPrev(young, prevYoung);
			while((nextYoung != null) && (nextYoung.distanceSquared < distanceSquared)) {
				prevYoung = nextYoung;
				nextYoung = nextYoung.getNext(young);
			}
			if(nextYoung != null)
				nextYoung.setPrev(young, this);
			if(prevYoung != null)
				prevYoung.setNext(young, this);
			else
				young.firstSSMDS = this;

		}

	}

	/** Get a pre-calculated distance squared between the two GameObjects.
	 * @return the distance squared between the two GameObjects.
	 */
	public float getDistanceSquared() {
		return distanceSquared;
	}
	
	/** Get a Point3D which is the vector from the passed GameObject to
	 * the other GameObject.
	 * @param go the GameObject to measure the vector from.
	 * @return the Point3D.
	 */
	public Point3D getVector(GameObject go) {
		if(go == young)
			return youngToOld;
		Assert.notFalse(go == old, "Only an owner may use a SSMDS!");
		return oldToYoung;
	}
	
	/** Get the other GameObject for this SSMDS.
	 * @param go The GameObject which is known.
	 * @return The other GameObject.
	 */
	public GameObject getOther(GameObject go) {
		if(go == young)
			return old;
		Assert.notFalse(go == old, "Only an owner may use a SSMDS!");
		return young;
	}
	
	/** Traverse go's list, and find the SSMDS that matches with target.
	 * @param go - the GameObject which you are searching with.
	 * @param target - the other GameObject for the desired SSMDS.
	 * @return The SSMDS relating go and target.
	 */
	public SelfSortingMutualDistanceSquared getTarget(GameObject go, GameObject target) {
		if(go == young)
		{
			if(target == old)
				return this;
			Assert.notNull(nextYoung, "In getTarget(), the target was invalid.");
			return nextYoung.getTarget(go, target);
		}
		Assert.notFalse(go == old, "Only an owner may use a SSMDS!");
		if(target == young)
			return this;
		Assert.notNull(nextOld, "In getTarget(), the target was invalid.");
		return nextOld.getTarget(go,target);
	}
	
	/** Get the next SSMDS in go's list.
	 * @param go The GameObject whose list you are traversing.
	 * @return The next SSMDS.
	 */
	public SelfSortingMutualDistanceSquared getNext(GameObject go) {
		if(go == young)
			return nextYoung;
		Assert.notFalse(go == old, "Only an owner may use a SSMDS!");
		return nextOld;
	}
	private SelfSortingMutualDistanceSquared getPrev(GameObject go) {
		if(go == young)
			return prevYoung;
		Assert.notFalse(go == old, "Only an owner may use a SSMDS!");
		return prevOld;
	}
	private void setNext(GameObject go, SelfSortingMutualDistanceSquared ssmds) {
		if(go == young) {
			nextYoung = ssmds;
			return;
		}
		Assert.notFalse(go == old, "Only an owner may use a SSMDS!");
		nextOld = ssmds;
	}
	private void setPrev(GameObject go, SelfSortingMutualDistanceSquared ssmds) {
		if(go == young) {
			prevYoung = ssmds;
			return;
		}
		Assert.notFalse(go == old, "Only an owner may use a SSMDS!");
		prevOld = ssmds;
	}
}