Improve knn() in QuadTree.java

manjikian commented 3 years ago

Description

The function will find the k nearest points in a Cartesian plane to a point specified by its two coordinates x and y. The function is complex for two reasons. First, because the algorithm is hard coded for the 4 quadrants of the Cartesian plain. Second, because of repetition which duplicates the cyclomatic complexity.

Refactoring

The obvious and easy refactoring step in this case is to eliminate the code duplication. Especially, that this part of code has an obvious purpose, which is finding closer points when we already found k candidate points. The other step would be to rewrite the algorithm so that it is not hard-coded to 4 regions, but instead have an iterative algorithm that will iterate over all the regions.

The first refactoring was done and the result was reducing the cyclomatic complexity form 97 to 43.

[x] CC count
[x] DIY test
[x] Write four tests
[x] Refactor

Data from Lizard tool:

Path to function: ./src/main/java/com/williamfiset/algorithms/datastructures/quadtree/QuadTree.java
Lines of code (NLOC): 113
Cyclomatic complexity (CCN): 91
Data JaCoCo:
Branch coverage: 0%

manjikian commented 3 years ago

Cyclomatic complexity calculation:

Cyclometric complexity = 90 - 1 + 2 = 91

Number of decisions: 90
- Line 168: for
- Line 172: ternary
- Line 178: if
- Line 180: if
- Line 190: if, &&
- Line 193: if, &&
- Line 196: if, &&
- Line 199: if, &&
- Line 204: if
- Line 210: ternary
- Line 223: &&
- Line 226: if
- Line 228: if
- Line 229: if
- Line 230: if, if
- Line 231: if, if
- Line 232: if, if
- Line 234: if, if
- Line 235: if, if
- Line 236: if, if
- Line 239: if
- Line 240: if, if
- Line 241: if, if
- Line 242: if, if
- Line 244: if, if
- Line 245: if, if
- Line 246: if, if
- Line 256: for
- Line 258: if
- Line 259: ternary
- Line 262: &&
- Line 265: if
- Line 266: if
- Line 267: if
- Line 268: if
- Line 269: if
- Line 270: if
- Line 272: if
- Line 273: if
- Line 274: if
- Line 277: if
- Line 278: if
- Line 279: if
- Line 280: if
- Line 282: if
- Line 283: if
- Line 284: if
- Line 291: if
- Line 292: if
- Line 293: if, if
- Line 294: if, if
- Line 295: if, if
- Line 297: if, if
- Line 298: if, if
- Line 299: if, if
- Line 302: if
- Line 303: if, if
- Line 304: if, if
- Line 305: if, if
- Line 307: if, if
- Line 308: if, if
- Line 309: if, if
number of exit points: 1

Autonymic commented 3 years ago

Cyclomatic complexity = PI - S + 2 = 88 - 1 + 2 = 89

private void knn(int k, long x, long y, PriorityQueue<SortedPt> heap) {

      for (int i = 0; i < ptCount; i++) {                       //PI = 1
        long xx = X[i], yy = Y[i];

        // Get largest radius.
        double radius = heap.isEmpty() ? POSITIVE_INFINITY : heap.peek().dist;      //PI = 2

        // Get distance from point to this point.
        double distance = Math.sqrt((xx - x) * (xx - x) + (yy - y) * (yy - y));

        // Add node to heap.
        if (heap.size() < k) {                              //PI = 3
          heap.add(new SortedPt(distance, new Pt(xx, yy)));
        } else if (distance < radius) {                         //PI = 4
          heap.poll();
          // System.out.println("POLLED: " + heap.poll());
          heap.add(new SortedPt(distance, new Pt(xx, yy)));
        }
      }

      int pointQuadrant = 0;

      // Dig to find the quadrant (x, y) belongs to.
      if (nw != null && region.contains(x, y)) {                    //PI = 6
        nw.knn(k, x, y, heap);
        pointQuadrant = NORTH_WEST;
      } else if (ne != null && region.contains(x, y)) {                 //PI = 8
        ne.knn(k, x, y, heap);
        pointQuadrant = NORTH_EAST;
      } else if (sw != null && region.contains(x, y)) {                 //PI = 10
        sw.knn(k, x, y, heap);
        pointQuadrant = SOUTH_WEST;
      } else if (se != null && region.contains(x, y)) { // Use else clause?     //PI = 12
        se.knn(k, x, y, heap);
        pointQuadrant = SOUTH_EAST;
      }

      if (pointQuadrant == 0) {                             //PI = 13
        // System.out.println("UNDEFINED QUADRANT?");
        // return;
      }

      // Get largest radius.
      double radius = heap.isEmpty() ? POSITIVE_INFINITY : heap.peek().dist;        //PI = 14

      // Find the center of this region at (cx, cy)
      long cx = (region.x1 + region.x2) / 2;
      long cy = (region.y1 + region.y2) / 2;

      // Compute the horizontal (dx) and vertical (dy) distance from the
      // point (x, y) to the nearest cell.
      long dx = Math.abs(x - cx);
      long dy = Math.abs(y - cy);

      boolean checkHorizontalCell = radius >= dx;
      boolean checkVerticalCell = radius >= dy;
      boolean checkDiagonalCell = checkHorizontalCell && checkVerticalCell;

      // TODO(williamfiset): Refactor.
      if (heap.size() == k) {                               //PI = 15

        if (isNorth(pointQuadrant)) {                           //PI = 16
          if (pointQuadrant == NORTH_WEST) {                        //PI = 17
            if (checkHorizontalCell) if (ne != null) ne.knn(k, x, y, heap);     //PI = 19
            if (checkVerticalCell) if (sw != null) sw.knn(k, x, y, heap);       //PI = 21
            if (checkDiagonalCell) if (se != null) se.knn(k, x, y, heap);       //PI = 23
          } else {
            if (checkHorizontalCell) if (nw != null) nw.knn(k, x, y, heap);     //PI = 25
            if (checkVerticalCell) if (se != null) se.knn(k, x, y, heap);       //PI = 27
            if (checkDiagonalCell) if (nw != null) nw.knn(k, x, y, heap);       //PI = 29
          }
        } else {
          if (pointQuadrant == SOUTH_WEST) {                        //PI = 30
            if (checkHorizontalCell) if (se != null) se.knn(k, x, y, heap);     //PI = 32
            if (checkVerticalCell) if (nw != null) nw.knn(k, x, y, heap);       //PI = 34
            if (checkDiagonalCell) if (ne != null) ne.knn(k, x, y, heap);       //PI = 36
          } else {
            if (checkHorizontalCell) if (sw != null) sw.knn(k, x, y, heap);     //PI = 38
            if (checkVerticalCell) if (ne != null) ne.knn(k, x, y, heap);       //PI = 40
            if (checkDiagonalCell) if (nw != null) nw.knn(k, x, y, heap);       //PI = 42
          }
        }

        // Still need to find k - heap.size() nodes!
      } else {

        // explore all quadrants ?
        // Do it lazy? Inspect return val after each call?

        for (int quadrant = 1; quadrant <= 4; quadrant++) {             //PI = 43

          if (quadrant == pointQuadrant) continue;                  //PI = 44
          radius = heap.isEmpty() ? POSITIVE_INFINITY : heap.peek().dist;       //PI = 45
          checkHorizontalCell = radius >= dx;
          checkVerticalCell = radius >= dy;
          checkDiagonalCell = checkHorizontalCell && checkVerticalCell;

          // No validation
          if (heap.size() != k) {                           //PI = 46
            if (isNorth(pointQuadrant)) {                       //PI = 47
              if (pointQuadrant == NORTH_WEST) {                    //PI = 48,
                if (ne != null) ne.knn(k, x, y, heap);                  //PI = 49
                if (sw != null) sw.knn(k, x, y, heap);                  //PI = 50
                if (se != null) se.knn(k, x, y, heap);                  //PI = 51
              } else {
                if (nw != null) nw.knn(k, x, y, heap);                  //PI = 52
                if (se != null) se.knn(k, x, y, heap);                  //PI = 53
                if (nw != null) nw.knn(k, x, y, heap);                  //PI = 54
              }
            } else {
              if (pointQuadrant == SOUTH_WEST) {                    //PI = 55
                if (se != null) se.knn(k, x, y, heap);                  //PI = 56
                if (nw != null) nw.knn(k, x, y, heap);                  //PI = 57
                if (ne != null) ne.knn(k, x, y, heap);                  //PI = 58
              } else {
                if (sw != null) sw.knn(k, x, y, heap);                  //PI = 59
                if (ne != null) ne.knn(k, x, y, heap);                  //PI = 60
                if (nw != null) nw.knn(k, x, y, heap);                  //PI = 61
              }
            }

            // must intersect
          } else {

            if (isNorth(pointQuadrant)) {                       //PI = 62
              if (pointQuadrant == NORTH_WEST) {                    //PI = 63
                if (checkHorizontalCell) if (ne != null) ne.knn(k, x, y, heap);     //PI = 65
                if (checkVerticalCell) if (sw != null) sw.knn(k, x, y, heap);       //PI = 67
                if (checkDiagonalCell) if (se != null) se.knn(k, x, y, heap);       //PI = 69
              } else {
                if (checkHorizontalCell) if (nw != null) nw.knn(k, x, y, heap);     //PI = 71
                if (checkVerticalCell) if (se != null) se.knn(k, x, y, heap);       //PI = 73
                if (checkDiagonalCell) if (nw != null) nw.knn(k, x, y, heap);       //PI = 75
              }
            } else {
              if (pointQuadrant == SOUTH_WEST) {                    //PI = 76
                if (checkHorizontalCell) if (se != null) se.knn(k, x, y, heap);     //PI = 78
                if (checkVerticalCell) if (nw != null) nw.knn(k, x, y, heap);       //PI = 80
                if (checkDiagonalCell) if (ne != null) ne.knn(k, x, y, heap);       //PI = 82
              } else {
                if (checkHorizontalCell) if (sw != null) sw.knn(k, x, y, heap);     //PI = 84
                if (checkVerticalCell) if (ne != null) ne.knn(k, x, y, heap);       //PI = 86
                if (checkDiagonalCell) if (nw != null) nw.knn(k, x, y, heap);       //PI = 88
              }
            }
          }
        } // for
      } // if
    } // method
                                            //PI = 88, S = 1
  } // node

KTH-DD2480-Group-2 / Algorithms