/*

	class Spoint.java
	by Richard Unger, March 1998

	The data structure that holds one point for our problem.
	Maintains data structure of points that is both a sorted
	linked list (on x value) and a BST (on x value)

*/


import java.util.Vector;



final public class Spoint {

	// point information
	
	public double x;		// x coordinate in euclidean space
	public double y;		// y coordinate in euclidean space
	
	public long name;		// for now use integer names...
	
	public boolean selected;// true if the point is selected in the UI
	
	// linkage information
	
	public Spoint next;
	public Spoint prev;
	public Spoint left;
	public Spoint right;
	public Spoint parent;
	
	public Spoint selNext;
	public Spoint selPrev;
	
	// nearest neighbour graph...
	
	public Spoint closest;
	public Vector imClosest;
	public long nnColour;
	public Vector siEdges;
	public long siColour;

	// constructor
	
	public Spoint(double inx,double iny){
		x = inx;
		y = iny;
		selected = false;
		next = prev = left = right = parent = selNext = selPrev = null;
		name = 0;
		imClosest = null;
		siEdges = null;
		nnColour = 0;
		siColour = 0;
		closest = null;
		}


	public Spoint(double inx,double iny,long inName){
		this(inx,iny);
		name = inName;
		}


	// linkage control

	public void Insert(Spoint who) throws DuplicatePointException{
		// inserts the point who into the tree rooted at this node
		// a process of binary search...
		// data structure and point are modified by this operation!
		
		if (x==who.x && y==who.y)
			throw new DuplicatePointException(this);
		
		if (who.x<x){	// insert left
			if (left == null){
				// found location for point
				left = who;
				who.parent = this;
				who.prev = prev;
				who.next = this;	// won't permit insert of sub-trees
				prev = who;
				if (who.prev != null)
					who.prev.next = who;
				}
			else
				left.Insert(who);
			}
		else{
			if (right == null){
				right = who;
				who.parent = this;
				who.prev = this;		// won't let us insert sub-trees
				who.next = next;
				next = who;
				if (who.next != null)
					who.next.prev = who;
				}
			else
				right.Insert(who);
			}
		}

	
	public Spoint VirtualInsert(Spoint who){
		// gives the parent of the node 'who', were it to be inserted into the tree.
		
/*		if (who.x<x)
			return (left==null)?this:left.VirtualInsert(who);
		else
			return (right==null)?this:right.VirtualInsert(who);
*/
	// iterative solution is faster...				
		Spoint p = this;
		Spoint c = this;
		while (c!=null){
			p = c;
			if (who.x<c.x)
				c = c.left;
			else
				c = c.right;
			}
		return p;
		}
	
	
	
	public Spoint Delete(){
		// deletes a node from the data structure...
		Spoint replacement;
		
		// delete from binary tree
		if ( (left == null) && (right == null)){	// deleting a leaf
			if (parent != null){
				if (parent.left == this)	// unlink from tree
					parent.left = null;
				else
					parent.right = null;
				}
			replacement = null;
			}
		else{
			if ( (left != null) && (right != null) ){ // we have 2 kids - must move a node
				replacement = (x>y)?next:prev;	// some randomness
				if (parent != null){
					if (parent.left == this)	// unlink from tree
						parent.left = replacement;
					else
						parent.right = replacement;
					}
				if (replacement.parent.left == replacement)
					replacement.parent.left = null;
				else
					replacement.parent.right = null;
				if (left != null)
					left.parent = replacement;
				if (right != null)
					right.parent = replacement;
				replacement.parent = parent;
				replacement.left = left;
				replacement.right = right;
				}
			else{		// we have 1 child, move it up...
				replacement = (right == null)?left:right;
				if (parent != null){
					if (parent.left == this)	// unlink from tree
						parent.left = replacement;
					else
						parent.right = replacement;
					}
				replacement.parent = parent;
				}
			}
						
		// fix up linked list...		
		if (prev != null)
			prev.next = next;
		if (next != null)
			next.prev = prev;
			
		next = prev = parent = left = right = null;
		UnselectPoint(this);
			
		return replacement;
		}


	// updating nearest neighbour.
	
	
	public void AddClosest(Spoint who,long col){
		if ( (imClosest == null) || (nnColour != col) ){	// erase old closest point info...
			imClosest = new Vector(6);
			nnColour = col;
			}
		imClosest.addElement(who);
		}


	public void AddClosest(Spoint who){
		if ( (imClosest == null))	// erase old closest point info...
			imClosest = new Vector(6);
		imClosest.addElement(who);
		}



	public void NNUpdate(){
		if (closest != null)		// remove old linkage
			closest.imClosest.removeElement(this);
		closest = FindClosest();
		if (closest != null)
			closest.AddClosest(this);
		}


	public void NNDelete(){			// must be called after point is removed from data structure
		if (closest != null)
			closest.imClosest.removeElement(this);
		if (imClosest != null){
			while (imClosest.size() > 0){
				Spoint upd = (Spoint)imClosest.firstElement();
				upd.NNUpdate();
				}
			}
		closest = null;
		imClosest = null;
		nnColour = 0;
		}
	
	
	public void AddSpheresLink(Spoint who,long col){
		if ((siEdges == null) || (siColour != col)){
			siEdges = new Vector(10,10);
			siColour = col;
			}
		siEdges.addElement(who);
		}
	

	public void AddSpheresLink(Spoint who){
		if ((siEdges == null))
			siEdges = new Vector(10,10);
		siEdges.addElement(who);
		}

	
	
	// utility


	public Spoint ToggleSelection(Spoint selHead){
		if (selected)
			return UnselectPoint(selHead);
		else
			return SelectPoint(selHead);
		}

	public Spoint UnselectPoint(Spoint selHead){
		if (selPrev != null)
			selPrev.selNext = selNext;
		if (selNext != null)
			selNext.selPrev = selPrev;
		selected = false;
		Spoint temp = ((this==selHead)?selNext:selHead);
		selNext = selPrev = null;
		return temp;
		}

	public Spoint SelectPoint(Spoint selHead){
		selected = true;
		selNext = selHead;
		selPrev = null;
		if (selHead != null)
			selHead.selPrev = this;
		return this;	
		}


	public Spoint FindClosest(){
		Spoint prox = (prev==null)?next:prev;
		if (prox == null)
			return null;
		Spoint l=prev;
		Spoint r=next;
		double bound = SquareDistance(prox);
		double distFound;
		
		while ( (l!=null) || (r!=null)){
			// check whether left guy is closer
			if (l != null){
				distFound = SquareDistance(l);
				if (distFound < bound){
					bound = distFound;
					prox = l;
					}
				l = ((x-l.x)*(x-l.x) >= bound)?null:l.prev;
				}
			if (r != null){
				distFound = SquareDistance(r);
				if (distFound < bound){
					bound = distFound;
					prox = r;
					}
				r = ((x-r.x)*(x-r.x) >= bound)?null:r.next;
				}			
			}
		
		return prox;
		}


	public double SquareDistance(Spoint other){
		return (other.x-x)*(other.x-x) + (other.y-y)*(other.y-y);
		}
		
	public double Distance(Spoint other){
		return Math.sqrt(SquareDistance(other));
		}

	public Spoint Add(Spoint other){
		return new Spoint(x+other.x,y+other.y);
		}
	public Spoint Subtract(Spoint other){
		return new Spoint(x-other.x,y-other.y);
		}

	public String toString(){
		return new String(Double.toString(x)+","+Double.toString(y));
		}


}