// NNInt.java

// Point is a three-dimensional point.

class Point {
   public static int Dimension = 3;
   public double[] Coords; 

// Constructor
   public Point(double x, double y, double z) {
       Coords = new double[3]; 
       Coords[0]=x; Coords[1]=y; Coords[2]=z;
       }
   public String toString() {
       return "[" + Coords[0] + ", " + Coords[1] + ", " + Coords[2]  + "]";
   }
}    

// LabelledPoint is a three-dimensional point plus a boolean label Vote.

class LabelledPoint extends Point {
    public boolean Vote;

// Constructor
    public LabelledPoint(double x, double y, double z, boolean v) {
           super(x,y,z);
           Vote = v;
       }
} 

// DistFun is an interface for a distance function, mapping two points to
// a distance

interface DistFun {
    public double Distance(Point P, Point Q); }

// NNSED implements DistFun as the square of the
// Euclidean distance (the sum of the squares of the differences of the
// coordinates

class NNSED implements DistFun {
  public double SquaredEuclideanDist(Point P, Point Q) {
     double Dist = 0.0;
     for (int i = 0; i < Point.Dimension; i++)
        Dist = Dist + (P.Coords[i]-Q.Coords[i])* (P.Coords[i]-Q.Coords[i]);
     return Dist;
  }
  public double Distance(Point P, Point Q) {
      return SquaredEuclideanDist(P,Q); }
}

// NNMaxDiff implements DistFun as the MaxDiff metric (the maximum difference
// in coordinates).

class NNMaxDiff implements DistFun {
  public double MaxDiff(Point P, Point Q) {
     double Dist = 0.0;
     for (int i = 0; i < Point.Dimension; i++)
        Dist = Math.max(Dist, Math.abs(P.Coords[i]-Q.Coords[i]));
     return Dist;
  }
  public double Distance(Point P, Point Q) {
      return MaxDiff(P,Q); }
}


// NNSubAbs implements DistFun as the SumAbs (the sum of the difference
// in coordinates).
//
class NNSumAbs implements DistFun {
  public double SumAbs(Point P, Point Q) {
     double Dist = 0.0;
     for (int i = 0; i < Point.Dimension; i++)
        Dist = Dist + Math.abs(P.Coords[i]-Q.Coords[i]);
     return Dist;
  }
  public double Distance(Point P, Point Q) {
      return SumAbs(P,Q); }
}


public class NNInt {

// TallyVotes uses the nearest neighbors method to conjecture a label
// for point P.
// DistFun is the distance metric being used
// D is an array of labelled point.
// k is the number of points to use in the nearest neighbors computation
// Find the k points closest to P in D, and take their majority vote to
// label P.
  public static boolean TallyVotes(DistFun Q, Point P, 
                                   LabelledPoint[] D, int k) {
      double[] BestDistances = new double[k+1]; // Distances of k closest point
      boolean[] BestVotes = new boolean[k+1];   // Votes of k closest points
      BestDistances[0] = Q.Distance(P,D[0]);
      BestVotes[0] = D[0].Vote;
      for (int i=1; i<D.length; i++) {
         int t = i;
         if (i > k) t=k;
         double x = Q.Distance(P,D[i]);  // Look at each point in D in sequence
         boolean v = D[i].Vote;
         BestDistances[t]=x;             // Put it at the end of the array
         BestVotes[t]=v;
         for (int j=t;j>0;j--)   // Move it forward to the right place
            if (x < BestDistances[j-1]) { // This is a modified insertion sort
               BestDistances[j]=BestDistances[j-1]; 
               BestDistances[j-1]=x;
               BestVotes[j]= BestVotes[j-1];
               BestVotes[j-1]=v;
            }
       }
      int Yes = 0;                         // Add up the number of Yes votes
      for (int i=0; i < k; i++) 
        if (BestVotes[i]) Yes = Yes+1;
      return Yes > k -Yes;                 // Compare Yes votes to No votes
  }
 
// Simple test case

public static void main(String args[]) {
    LabelledPoint[] Data = 
         { new LabelledPoint(0.0, 0.0, 0.0, true),
           new LabelledPoint(7.0, 3.0, 3.0, true),
           new LabelledPoint(10.0, 3.0, 3.0, false),
           new LabelledPoint(4.0, 8.0, 8.0, true),
           new LabelledPoint(3.0, 5.0, 9.0, false)
         };
    Point NewPt = new Point(3.0, 3.0, 3.0);
    NNSED MyNNSED = new  NNSED();
    System.out.println(TallyVotes(MyNNSED,NewPt,Data,3));
    NNMaxDiff MyNNMaxDiff = new NNMaxDiff();
    System.out.println(TallyVotes(MyNNMaxDiff,NewPt,Data,3));
    NNSumAbs MyNNSumAbs = new NNSumAbs();
    System.out.println(TallyVotes(MyNNSumAbs,NewPt,Data,3));
}
}