// Test of closest pair algorithms
// David Eppstein, UC Irvine, 19 Apr 1997
//
// Fast pair algorithm: hybrid of conga line and nearest neighbors
//
// This is based on the observation that the conga line data structure,
// in practice, does better the more subsets you give to it: even though the
// worst case time for k subsets is O(nk log (n/k)), that worst case
// seems much harder to reach than the nearest neighbor algorithm.
// In the limit of arbitrarily many subsets, each new addition or point moved
// by a deletion will be in a singleton subset, and the algorithm will
// differ from nearest neighbors in only a couple of ways: (1) when we
// create the initial data structure, we use a conga line rather than
// all nearest neighbors, to keep the indegree of each point low, and
// (2) when we insert a point, we don't bother updating other points' neighbors.
//
// Total space: 20n bytes. (Could be reduced to 4n at some cost in update time.)
// Time per insertion or single distance update: O(n)
// Time per deletion or point update: O(n) expected, O(n^2) worst case
// Time per closest pair: O(n)
//
// Note a lot of code overlaps with our other closest pair data structures,
// however I've written this to be self-contained so it can be used
// by itself without including the rest.

#include "ClosestPairs.h"

class FastPair : public ClosestPairs {
 	point * points;					// points currently in set
 	point * where_are_the_points;	// indices into points
 	unsigned long npoints;			// how much of array is actually used?
 	Distance & dist;				// how to compare two points

 	point * neighbors;
 	double * nbr_dist;
 	void FindNeighbor(point);

 public:
  	~FastPair();
 	FastPair(long np, long mp, Distance & d);
 	void operator += (point);
 	void operator -= (point);
 	double operator () (point & a, point & b);
 	void UpdatePoint(point);
 	void UpdateDistance(point,point);
};