// NNAbsHonors.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;
    public LabelledPoint(double x, double y, double z, boolean v) {
           super(x,y,z);
           Vote = v;
    }
} 

// NN is an abstract class with an abstract Distance method,
// an abstract Weight method 
// a concrete TallyVotes method that uses the Distance and Weight
// to apply the nearest neighbors method

abstract class NN {
   public abstract double Distance(Point P1, Point P2);

   public abstract double Weight(double Dist);
   
  
// 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 boolean TallyVotes(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] = 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 = 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;
            }
      }
      double YesSum = 0.0;  // Sum of weights on yes votes
      double NoSum = 0.0;   // Sum of weights on no votes
      for (int i=0; i < k; i++)
        if (BestVotes[i]) YesSum = YesSum+Weight(BestDistances[i]); 
          else NoSum = NoSum+Weight(BestDistances[i]); 
      return YesSum > NoSum;
 }           
}

// NNSED is a concrete class that instantiates the Distance function to
// be the squared Euclidean distance and the Weight function to be 
// the function that is 1/Dist^{2}
//
class NNSED extends NN {
  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);
   }

  public double Weight(double Dist) { return 1.0/(Dist*Dist); } 

}

// NNMaxDiff is a concrete class that instantiates the Distance function to
// be the maximum difference between coordinates, and the Weight function
// to be 1/Distance.

class NNMaxDiff extends NN {
  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);
   }

  public double Weight(double Dist) { return 1.0/Dist; } 

}

// NNSumAbs is a concrete class that instantiates the Distance function to
// be the sum of the differences between coordinates, and the Weight function
// to be the constant 1 function

class NNSumAbs extends NN {
  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 double Weight(double Dist) { return 1.0; } 
}

// Simple test case

public class NNAbsHonors {
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(MyNNSED.TallyVotes(NewPt,Data,3));
    NNMaxDiff MyNNMaxDiff = new NNMaxDiff();
    System.out.println(MyNNMaxDiff.TallyVotes(NewPt,Data,3));
    NNSumAbs MyNNSumAbs = new NNSumAbs();
    System.out.println(MyNNSumAbs.TallyVotes(NewPt,Data,3));
}
}