import java.util.Vector;

import cas.Point;
/**
 * Implementation of a naive nearest neighbor search. This is an O(n) 
 * operation per search. For the L2 norm standard optimization was used (i.e.
 * partial distance computation and use of the squared distance).
 *
 * @author Ziv Yaniv
 */
public class NaiveNearestNeighbor implements NearestNeighbor {
    private Vector points; //hold the data which will be searched

    private int searchNorm;

    /**
     * Create a new object with the given points.
     * @param points This vector of points will be queried for the nearest
     *               neighbor of a given point.
     * @param dataIsMutable If set to 'true' the data will be copied by
     *                      the constructor otherwise we will only
     *                      have a reference to the original data (which
     *                      should not be changed during the life-time of
     *                      the NaiveNearestNeighbor object.
     * @param searchNorm Norm to use for distance computation. Can only be
     *                   one of the constants L1, L2, Linf.
     * @see cas.Point
     */
    public NaiveNearestNeighbor(Vector points, boolean dataIsMutable, 
                                int searchNorm) {
                	//check that all points have the same dimensionality
	int i, n = points.size();
	int dim = ((Point)points.elementAt(0)).getDimension();
	for(i=1; i<n ; i++) {
	    if(((Point)points.elementAt(i)).getDimension() != dim)
		throw new IllegalArgumentException("All points in vector "+
						   "must have same " +
						   "dimensions.");
	}
	if(!dataIsMutable) 
            this.points = points;
        else { //copy the points 
            this.points = new Vector();
            for(i=0; i<n; i++)
                this.points.add(new Point((Point)points.elementAt(i)));
        }
        this.searchNorm = searchNorm;
     }
    /**
     * Create a new object with the given points. Distance computations
     * use the L2 norm as a default.
     * @param points This vector of points will be queried for the nearest
     *               neighbor of a given point.
     * @param dataIsMutable If set to 'true' the data will be copied by
     *                      the constructor otherwise we will only
     *                      have a reference to the original data (which
     *                      should not be changed during the life-time of
     *                      the NaiveNearestNeighbor object.
     * @see cas.Point
     */
    public NaiveNearestNeighbor(Vector points, boolean dataIsMutable) {
                	//check that all points have the same dimensionality
	int i, n = points.size();
	int dim = ((Point)points.elementAt(0)).getDimension();
	for(i=1; i<n ; i++) {
	    if(((Point)points.elementAt(i)).getDimension() != dim)
		throw new IllegalArgumentException("All points in vector "+
						   "must have same " +
						   "dimensions.");
	}
	if(!dataIsMutable) 
            this.points = points;
        else { //copy the points 
            this.points = new Vector();
            for(i=0; i<n; i++)
                this.points.add(new Point((Point)points.elementAt(i)));
        }
                  //set the default search norm to L2
	searchNorm = NearestNeighbor.L2;
    }

    /**
     * Set the search norm to the specified norm.
     * @param searchNorm Norm used to find the nearest neighbor. Must be
     *                   one of the constants L1, L2, Linf .
     */
    public void setSearchNorm(int searchNorm) {
	if((searchNorm!=NearestNeighbor.L1) &&
	   (searchNorm!=NearestNeighbor.L2) &&
	   (searchNorm!=NearestNeighbor.Linf))
	    throw new IllegalArgumentException("Specified norm (" +
					       searchNorm +
					       ") is does not exist.");
	this.searchNorm = searchNorm;
    }

    /**
     * Find the nearest point in the data set to the given point use the
     * norm set with setSearchNorm.
     * The default search norm is L2.
     * @param p Find the nearest point in the data to this point.
     * @return Returns a <b>reference</b> to the nearest point.
     * @see cas.Point
     */
    public Point find(Point p) {
	int i,j, n = points.size();
	double minDist, curDist;
	Point minPnt, curPnt;

	minPnt = null; //pacify the java compiler 

	switch(searchNorm) {
	case L1:
	    minPnt = (Point)(points.elementAt(0)); 
	    minDist = p.distanceL1(minPnt);
	    for(i=1; i<n; i++) {
		curPnt = (Point)(points.elementAt(i));
		curDist = p.distanceL1(curPnt);
		if(curDist < minDist) {
		    minDist = curDist;
		    minPnt = curPnt;
		}
	    }
	    break;
	case L2:         //use partial distance computation to accelerate
	                //the search
	    minPnt = (Point)(points.elementAt(0)); 
	    minDist = p.distanceL2Squared(minPnt);
	    int dim = minPnt.getDimension();
	    double tmp;
	    for(i=1; i<n; i++) {
		curPnt = (Point)(points.elementAt(i));
		curDist = 0.0;
		for(j=0; j<dim && curDist<minDist; j++) {
		    tmp = p.data[j] - curPnt.data[j];
		    curDist+= tmp*tmp;
		}
		if(curDist < minDist) {
		    minDist = curDist;
		    minPnt = curPnt;
		}
	    }
	    break;
	case Linf:
	    minPnt = (Point)(points.elementAt(0)); 
	    minDist = p.distanceLinf(minPnt);
	    for(i=1; i<n; i++) {
		curPnt = (Point)(points.elementAt(i));
		curDist = p.distanceLinf(curPnt);
		if(curDist < minDist) {
		    minDist = curDist;
		    minPnt = curPnt;
		}
	    }
	    break;
	}
	return minPnt;
    }
}