// Keep track of a list of DistancedObjects, return shortest
// David Eppstein, UC Irvine, 18 May 1997
//
// interface:
//		new FastPair():			  make empty list
//		new FastPair(Vector):	  make vector of DistancedObjects into new list
//		elements():				  return Enumeration of objects in list
//		update(DistancedObject):  object has changed, recompute its distances
//		restart():				  all objects changed, recompute all distances
//		add(DistancedObject):	  add another object to the list
//		remove(DistancedObject):  remove object from list
//		closestPair():			  closest pair is returned obj and its neighbor
//		isEmpty():				  true if no objs, false otherwise

import java.util.*;
import java.lang.*;

public class FastPair
{
	private Vector objs;
	public Enumeration elements() { return objs.elements(); }
	public boolean isEmpty() { return objs.isEmpty(); }
	
	// all objects changed, compute new neighbors for everyone
	public void restart() {
		// First, set all objects' neighbors to themselves
		// so we'll know which objects have actual neighbors already
		Enumeration enum = elements();
		if (!enum.hasMoreElements()) return;	// nothing to do
		while (enum.hasMoreElements()) {
			DistancedObject d = (DistancedObject) enum.nextElement();
			d.distanceToNeighbor = Double.POSITIVE_INFINITY;
			d.neighbor = d;
		}
		
		// Start with the first object, and form a chain in which each
		// successive point chooses a neighbor among the so-far-unchosen points;
		// that neighbor then becomes the next to choose, etc,
		// until everyone has a neighbor
		DistancedObject o = (DistancedObject) objs.firstElement();
		while (true) {
			enum = elements();
			while (enum.hasMoreElements()) {
				DistancedObject d = (DistancedObject) enum.nextElement();
				if (d.neighbor == d && d != o) {	// eligible to be neighbor?
					double distToD = o.distanceTo(d);
					if (distToD < o.distanceToNeighbor || o.neighbor == o)
					{									  // better than old nbr?
						o.distanceToNeighbor = distToD;   // yes, remember it
						o.neighbor = d;
					}
				}
			}
			if (o.neighbor == o) return; // didn't find any nbrs, end of line
			o = o.neighbor;				 // else go on to nbrs of new nbr
		}
	}
	
	// constructors
	public FastPair(Vector distancedObjects) {
		objs = distancedObjects;
		restart();
	}
	public FastPair() { objs = new Vector(); }
	
	// Find closest pair, return one of them.
	// Caller beware, may crash if objs is empty.
	public DistancedObject closestPair()
	{
		DistancedObject bestObject = (DistancedObject) objs.firstElement();
		double minDistance = Double.POSITIVE_INFINITY;
		Enumeration enum = elements();
		while (enum.hasMoreElements()) {
			DistancedObject d = (DistancedObject) enum.nextElement();
			if (minDistance > d.distanceToNeighbor) {
				bestObject = d;
				minDistance = d.distanceToNeighbor;
			}
		}
		return bestObject;
	}
	
	// compute new neighbor
	private void findNeighbor(DistancedObject x) {
		Enumeration enum = elements();
		x.distanceToNeighbor = Double.POSITIVE_INFINITY;
		while (enum.hasMoreElements()) {
			DistancedObject d = (DistancedObject) enum.nextElement();
			if (d != x) {
				double dx = x.distanceTo(d);
				if (dx < x.distanceToNeighbor) {
					x.distanceToNeighbor = dx;
					x.neighbor = d;
				}
			}
		}
	}
	
	// add new object
	public void add(DistancedObject x) {
		findNeighbor(x);
		objs.addElement(x);
	}
	
	// delete object
	public void remove(DistancedObject x) {
		objs.removeElement(x);
		Enumeration enum = elements();
		while (enum.hasMoreElements()) {
			DistancedObject d = (DistancedObject) enum.nextElement();
			if (d.neighbor == x) findNeighbor(d);
		}
	}
	
	// change set of distances associated with object already in data structure
	public void update(DistancedObject x) {
		Enumeration enum = elements();
		while (enum.hasMoreElements()) {
			DistancedObject d = (DistancedObject) enum.nextElement();
			if (d.neighbor == x) {
				double dx = d.distanceTo(x);
				if (dx <= d.distanceToNeighbor) d.distanceToNeighbor = dx;
				else findNeighbor(d);
			}
		}
		findNeighbor(x);
	}
}