// Test of closest pair algorithms
// David Eppstein, UC Irvine, 19 Apr 1997
//
// Brute force closest pair algorithm
// Keeps two arrays: one listing points in the current point set,
// another listing locations of points in the first array.
// For each closest pair computation, tries all pairs of points in set.
// Does not check e.g. if too many points added or some point added twice;
// caller is responsible for making sure this doesn't happen.
//
// Total space: 8n bytes. (Could be reduced to n/8 at some cost in update time.)
// Time per insertion or deletion: O(1).
// Time per closest pair: O(Dn^2) where D=time per distance eval

#ifndef BRUTE_FORCE_H
#define BRUTE_FORCE_H

#include "ClosestPairs.h"

class BruteForceCP : public ClosestPairs {
 protected:
 	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

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

#endif