KdTree.java使用了未经检查或不安全的操作

algorithm princeton coursera

命令行编译报错：
错误：BST.Node可以在BST中访问private
import edu.princeton.cs.algs4.BST.Node
注：KdTree.java使用了未经检查或不安全的操作。
注：有关详细信息，请使用-Xlint:unchecked 重新编译

Then,

`Exception in thread "main" java.lang.NullPointerException

main方法出现了空指针异常

1、NullPointerException是java应用程序中最常见的一种异常，空指针异常
2、空指针异常是一种运行时异常，发生在调用对象的方法或者属性的时候。
3、当对象为null时，调用其任何方法均会报NullPointerException
4、最好的解决办法是在调用一个对象或者集合类时，先判断当前对象是否为null，为null进入其他的业务处理流程。
示例：

Then,
Exception in thread "main" 0.765625 0.515625 java.lang.StackOverflowError

How to solve StackOverflowError

solution:
I changed code line 88

Now there's no Exception, but I don't know why this works.
What is the difference between return new Node(); and t = new Node()
Isn't it true that they both creat an object and takes the same memory? Still confused. And still there's something wrong with the program.

I got result like this:

Next day, I plan to modify the most parts of my codes, using other people's codes as refrences, because my score was too low(41/100) which shows that I might lack background knowledge to actually finish the assignment. I don't want to continue without a clue, so...

I met plenty of problems:
When I wrote

private int cmp(Point2D a, Point2D b, int depth){
      if(depth % 2 == 0){
          int cmp = (a.x()).compareTo((b.x()));

It doesn't work, has to change to:

private int cmp(Point2D a, Point2D b, int depth){
      if(depth % 2 == 0){
          int cmp = new Double(a.x()).compareTo(new Double(b.x()));

Why?

After modify(nearly rewrite) insert() method, the output seems correct as the photo shows:

But when I submitted, I still got a low score(54/100)
let's see the feedback:

I checked line 60, which turned out to be an endless recursion.

So, I declaredprivate int size;in KdTree.class,and changed line 60 to:

public int size(){                                        
    return this.size;
  }

but it doesn't work still, until I added size = 0 in the KdTree constructor.

 public KdTree(){                                               
    root = null;
    size = 0;
  }

Don't know why and how size actually know the size of KdTree at all.

Then, I passed corectness tests about insert() method, but still got a low score(66/100) because I failed in almost all contains() method tests. Let's take a look.

As insert(), I changed the comparator which pissed me off(likely read from a pdf named hw5 from Delaware university, it sucked) to a simpler one, but I still am a little bit confused about how to use the recursion. And I passed the contains() related tests.So, now I got 81/100, which is the passing score for the assignment.

My range() method worked fine, but I've got plenty of problems in nearest() method, let's take a look.

I modified my codes according to someone's (tested 95/100) like this:

 public Point2D nearest(Point2D p){                       
    if(isEmpty()) {
        return null;
    }else{
        Point2D closestPoint = null;
        closestPoint = nearest(root,closestPoint,p);
        return closestPoint;
     }
  }
  //what is this Node t, guess it's the starting node when searching for the nearest to the query
  //or look it as the current Node
  private Point2D nearest(Node t, Point2D closestSofar, Point2D queryPoint){
// because I only have this one point, it has to be the nearest to the query point
    if(t != null ){
      if( closestSofar == null){
        closestSofar = t.p;
      } 
//closestDistance >= t.rect.distanceSquaredTo(queryPoint) has been mentioned in the video
//it's not very intuitive
    if(closestSofar.distanceSquaredTo(queryPoint) >= t.rect.distanceSquaredTo(queryPoint)) {
      if(t.p.distanceSquaredTo(queryPoint) < closestSofar.distanceSquaredTo(queryPoint)) {
        closestSofar = t.p;
      }
    }
    //determining first search the left or right?
    if(t.rt != null && t.rt.rect.contains(queryPoint)){
        closestSofar = nearest(t.rt, closestSofar, queryPoint);
        closestSofar = nearest(t.lb, closestSofar, queryPoint);  
    }else{
        closestSofar = nearest(t.lb, closestSofar, queryPoint);
        closestSofar = nearest(t.rt, closestSofar, queryPoint);  
     }
    }
      return closestSofar;
  }

This is the original codes i refrenced:

public Point2D nearest(Point2D point) {
        if (isEmpty()) {
            return null;
        } else {
            Point2D result = null;
            result = nearest(root, point, result);
            return result;
        }
    }
    private Point2D nearest(Node x, Point2D point, Point2D min) {
        if (x != null) {
            if (min == null) {
                min = x.p;
            }
            // If the current min point is closer to query than the current point
            if (min.distanceSquaredTo(point)
                    >= x.rect.distanceSquaredTo(point)) {
                if (x.p.distanceSquaredTo(point) < min.distanceSquaredTo(point)) {
                    min = x.p;
                }
                // Check in which order should we iterate
                if (x.right != null && x.right.rect.contains(point)) {
                    min = nearest(x.right, point, min);
                    min = nearest(x.left, point, min);
                } else {
                    min = nearest(x.left, point, min);
                    min = nearest(x.right, point, min);
                }
            }
        }
        return min;
    }

I'm trying to figure out what went wrong in my codes, it says things like:

Test 6a: Insert n non-degenerate points and call nearest() with random query points
* 50000 random non-degenerate points in a 100000-by-100000 grid

    ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
    OperationCountLimitExceededException
    Number of calls to methods in Point2D exceeds limit: 1000000000
    ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

• 5000 random non-degenerate points in a 10000-by-10000 grid

    ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
    OperationCountLimitExceededException
    Number of calls to methods in Point2D exceeds limit: 1000000000
    ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

• 500 random non-degenerate points in a 1000-by-1000 grid

    ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
    OperationCountLimitExceededException
    Number of calls to methods in Point2D exceeds limit: 1000000000
    ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

This is annoying, I nearly copied this guy's codes, but mine still got 84/100. let's take a look.

Guess what? I figured out where went wrong in my code, I had placed a "}" in a wrong place. Briefly speaking, as you can see in the above codes, there's three "}" above return closestSofar;, while in my codes there's only two. That's what went wrong. But i haven't thoroughly understand why yet.

btw, I got errors in nearest() method in PointSET.java as well, I modified my codes learning from the same person's codes.
mine that didnt work were like :

 public Point2D nearest (Point2D p){             // a nearest neighbor in the set to point p; null if the set is empty 
    if(isEmpty()) {
      return null;
    }
    Point2D nearestPoint = null;
    for(Point2D point : set){
      if(point.distanceTo(p)< nearestPoint.distanceTo(p)){
        nearestPoint = point;
      }
    }
      return nearestPoint;
  }

I changed to:

 public Point2D nearest (Point2D p){             // a nearest neighbor in the set to point p; null if the set is empty 
    if(isEmpty()) {
      return null;
    }else{
      Point2D nearestPoint = null;
        for(Point2D point : set){
          if(nearestPoint == null || point.distanceTo(p)< nearestPoint.distanceTo(p)){
            nearestPoint = point;
          }
        }
      return nearestPoint;
  }
 }

It worked, now I got 100/100. But I actually still have a lot of problems that I didn't understand need investigations.