/*

	PointSet.java
	by Richard Unger, March 1998
	
	This object is in charge of a collection of points. It is in charge of storing
	them efficiently for the problems I want to solve (spheres of influence), and
	managing the computation on them, keeping the computed results up-to-date as more
	points are added.

	To get a point-set that supports commands and can draw itself I made the 
	InteractivePointSet subclass, which will allow me to create light-weight pointsets
	to just handle calculations if it proves necessary to do some background computation.

	PointSet operates on Spoint objects, not AWT points.
	
*/



import java.util.Vector;


public class PointSet {

// variables
	long nameSeed = 0;
	long colour = 0;
		
// point data-structure
	long numPoints;
	Spoint listHead;
	Spoint treeRoot;

// flags to keep track of what graphs we're drawing...

	boolean nn;
	boolean cc;
	boolean si;

// constructor

	public PointSet(){		
		listHead = null;
		treeRoot = null;
		numPoints = 0;
		nameSeed = 0;
		colour = 0;
		nn = false;
		cc = false;
		si = false;
		}


// adding/removing points	

	public void AddPoint(Spoint where) throws DuplicatePointException{
		where.name = nameSeed++;
		
		if (treeRoot != null){
			treeRoot.Insert(where);
			if (where.prev == null)
				listHead = where;
			}
		else
			listHead = treeRoot = where;
		numPoints++;
		if (nn||cc||si)
			IncrementalNNAdd(where);
		if (si)
			IncrementalSIAdd(where);
		}
		
	
	public void DeletePoint(Spoint which){
		if (which.prev == null)		// if we deleted the head
			listHead = which.next;
		if (which.parent == null)	// if we deleted the root
			treeRoot = which.Delete();
		else
			which.Delete();
		if (nn||cc||si)
			IncrementalNNDelete(which);
		if (si)
			IncrementalSIDelete(which);
		//System.out.println("Deleted: " + which);
		}
	
		
	public void DeleteAllPoints(){
		listHead = treeRoot = null;
		numPoints = 0;
		ResetPointNames();
		}


// setting up graphs


	public void SetNNGraph(boolean on){
		if (on && !nn)
			RecomputeNearestNeighbourGraph();
		nn = on;
		}

	public void SetCCGraph(boolean on){
		if (on && !nn)
			RecomputeNearestNeighbourGraph();
		cc = on;
		}
		
	public void SetSIGraph(boolean on){
		if (on && !nn)
			RecomputeNearestNeighbourGraph();
		if (on && !si)
			RecomputeSpheresGraph();
		si = on;
		}

// algorithmic methods...


	public Spoint FindNeighbour(Spoint toMe){
		// assuming point already in data-structure
		if (numPoints<2)
			return null;
		return toMe.FindClosest();
		}

	
	public Spoint FindClosestPoint(Spoint toMe){
		// does not assume point is data structure
		if (treeRoot == null)
			return null;
		Spoint parent = treeRoot.VirtualInsert(toMe);
		if (parent == null)
			return null;
		toMe.prev = parent;
		toMe.next = parent.next;
		return toMe.FindClosest();
		}


	private long NewColour(){
		return ++colour;
		}


	public void RecomputeNearestNeighbourGraph(){
		// for each node, garbage any existing linkage (use colouring to do this in the same step...
		// then find the closest point.
		// add that closest point to the nn linkage...
		
		if (numPoints < 2)
			return;
				
		long nnColour = NewColour();
		Spoint looper = listHead;
		while (looper != null){
			if (looper.nnColour != nnColour)
				looper.imClosest = null;
			Spoint itsClosest = looper.FindClosest();
			looper.closest = itsClosest;
			itsClosest.AddClosest(looper,nnColour);
			looper = looper.next;
			}
		}


	public void RecomputeSpheresGraph(){
		// for each node, check intersections with all other nodes.
		// if an intersection results, add an edge...
		// bad implementation, could use TONS of extra edges
		// will make better implementation later...
		if (numPoints < 2)
			return;
		long siColour = NewColour();
		for (Spoint a = listHead;a != null;a = a.next){
			if (a.siColour != siColour)
				a.siEdges = null;
			for (Spoint b = a.next;b != null;b = b.next){
				if (b== null)
					continue;
				// check intersection:
				if (a.Distance(a.closest) + b.Distance(b.closest) >= a.Distance(b)){
					a.AddSpheresLink(b,siColour);
					b.AddSpheresLink(a,siColour);
					}
				}
			}
		}

	public void RecomputeSpheresForNewPoint(Spoint which){	// doesn't work fully yet...
		if (numPoints < 2)									// must also recompute points
			return;											// for which a new nn is added...
		for (Spoint b = listHead;b != null;b = b.next){
			// check intersection:
			if (which == b)
				continue;
			if (which.Distance(which.closest) + b.Distance(b.closest) >= which.Distance(b)){
				which.AddSpheresLink(b);
				b.AddSpheresLink(which);
				}
			}
		}

	public void IncrementalNNAdd(Spoint where){
		RecomputeNearestNeighbourGraph();
		}

	public void IncrementalNNDelete(Spoint which){
		which.NNDelete();
		}


	public void IncrementalSIAdd(Spoint where){
		RecomputeSpheresGraph();
		}

	public void IncrementalSIDelete(Spoint which){
		RecomputeSpheresGraph();
		}

// utility functions

	public void ResetPointNames(){
		nameSeed = 0;
		}

}