I'm doing the week 3 Assignment of Princeton Algorithm Part I. The last part is my codes for class BruteCollinearPoints. I cannot pass the following test. The test says that after I new an object BruteCollinearPoints, it mutate the input array points and find the instance variable of my object BruteCollinearPoints changed.

I certainly know the direct method to avoid this fail is to copy every elements of points to another arrayNew. Then do operation to arrayNew. However I want to know concrete example to make my code wrong. Because the result will directly point to the Point Object which is immutable, how is it possible to mutate Point[] points to change my result? I try many methods in my IDE but cannot reproduce this bug. I really want someone can show me solid example to make this bug occur and let me have a deeper understanding of immutable data type. Thank you.

It give me a feeling like following:

Item[] array = new Item[]{item0, item1, item2, item3} // Item is some immutable type.
Item[] array2 = new Item[2];
array2[0] = array[2];
array2[1] = array[1];
.....// Then doing some operation on ``array``
.....// Then my array2[0] array2[1] will change.

How is it possible? There should be some loopholes in my code but I can't see it. I really want to understand this loophole instead of directly using another absolutely right to bypass it.

===========

Test 10: check that data type is immutable by testing whether each method
     returns the same value, regardless of any intervening operations
* input8.txt
- failed after 11 operations involving BruteCollinearPoints
- first and last call to segments() returned different arrays

- sequence of operations was:
      BruteCollinearPoints collinear = new 

BruteCollinearPoints(points);
      collinear.segments()
      mutate array returned by last call to segments()
      mutate array returned by last call to segments()
      collinear.numberOfSegments() -> 2
      mutate array returned by last call to segments()
      collinear.numberOfSegments() -> 2
      collinear.numberOfSegments() -> 2
      mutate points[] array that was passed to constructor
      mutate array returned by last call to segments()
      collinear.segments()

- failed on trial 1 of 100

* equidistant.txt
- failed after 22 operations involving BruteCollinearPoints
- first and last call to segments() returned different arrays

- failed on trial 1 of 100

==> FAILED

==========================

import java.util.Arrays;

public class BruteCollinearPoints {    
    private final LineSegment[] lineResults;
    private final int numOfSeg;
    public BruteCollinearPoints(Point[] points) {
        if (points == null || points.length == 0) {
            throw new IllegalArgumentException();
        }

        for (Point p : points) {
            if (p == null) {
                throw new IllegalArgumentException();
            }
        }        
        for (int i = 0; i < points.length - 1; i++) {
            for(int j = i + 1; j < points.length; j++ ) {
                if (points[i].compareTo(points[j]) == 0) {
                    throw new IllegalArgumentException();
                }
            }                
        }
        Point[][] results = new Point[points.length][4];
        int tempNumOfSeg = 0;
        for (int i = 0; i < points.length; i++) {
            for (int j = i + 1; j < points.length; j++) {
               double slopeij = points[i].slopeTo(points[j]);
               for (int k = j + 1; k < points.length; k++) {
                   if (points[i].slopeTo(points[k]) == slopeij) {
                       for (int l = k + 1; l < points.length; l++) {
                           if (points[i].slopeTo(points[l]) == slopeij) {
                               results[tempNumOfSeg][0] = points[i];
                               results[tempNumOfSeg][1] = points[j];
                               results[tempNumOfSeg][2] = points[k];
                               results[tempNumOfSeg][3] = points[l];
                               Arrays.sort(results[tempNumOfSeg]);
                               tempNumOfSeg++;
                           }
                       }
                   }
               }
            }
        }
        LineSegment[] tempLineResults = new LineSegment[tempNumOfSeg];
        for (int i = 0; i < tempNumOfSeg; i++) {
            tempLineResults[i] = new LineSegment(results[i][0],results[i][3]);
        }
        lineResults = tempLineResults;
        numOfSeg = tempNumOfSeg;

    }    // finds all line segments containing 4 points
    public int numberOfSegments() {
        return numOfSeg;
    }        // the number of line segments
    public LineSegment[] segments() {
        return lineResults;
    }                // the line segments

    public static void main(String[] args) {
     // read the n points from a file

    }    
}

solution

use this code as a reference

import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.MergeX;

public class BruteCollinearPoints {

    private final LineSegment[] segments;
    private int segmentsSize = 0;

    /** finds all line segments containing 4 points */
    public BruteCollinearPoints(Point[] points) {
        if (points == null) {
            throw new IllegalArgumentException("points can't be null");
        }
        for (Point p : points) {
            if (p == null) {
                throw new IllegalArgumentException("point can't be null");
            }
        }

        Point[] p = new Point[points.length];
        System.arraycopy(points, 0, p, 0, points.length);
        segments = analyzeSegments(p);
    }

    private LineSegment[] analyzeSegments(Point[] points) {
        LineSegment[] tmpSegments = new LineSegment[points.length * 4];
        MergeX.sort(points);
        for (int i = 0; i < points.length; i++) {
            for (int j = i + 1; j < points.length; j++) {
                for (int k = j + 1; k < points.length; k++) {
                    for (int m = k + 1; m < points.length; m++) {
                        Point p = points[i];
                        Point q = points[j];
                        Point r = points[k];
                        Point s = points[m];
                        if (Double.compare(p.slopeTo(q), p.slopeTo(r)) == 0 && Double.compare(p.slopeTo(q), p.slopeTo(s)) == 0) {
                            tmpSegments[segmentsSize++] = new LineSegment(p, s);
                        }
                    }
                }
            }
        }
        LineSegment[] resultSegments = new LineSegment[segmentsSize];
        for (int i = 0; i < segmentsSize; i++) {
            resultSegments[i] = tmpSegments[i];
        }
        return resultSegments;
    }

    /** the number of line segments */
    public int numberOfSegments() {
        return segmentsSize;
    }

    /** the line segments */
    public LineSegment[] segments() {
        LineSegment[] returnSegments = new LineSegment[segments.length];
        System.arraycopy(segments, 0, returnSegments, 0, segments.length);
        return returnSegments;
    }

    public static void main(String[] args) {
        // read the n points from a file
        In in = new In(args[0]);
        int n = in.readInt();
        Point[] points = new Point[n];
        for (int i = 0; i < n; i++) {
            String s = in.readString();
            if ("null".equals(s)) {
                points[i] = null;
            } else {
                int x = Integer.parseInt(s);
                int y = in.readInt();
                points[i] = new Point(x, y);
            }
        }

        BruteCollinearPoints collinear = new BruteCollinearPoints(points);

        // draw the points
        StdDraw.enableDoubleBuffering();
        StdDraw.setXscale(0, 32768);
        StdDraw.setYscale(0, 32768);
        for (Point p : points) {
            p.draw();
        }
        StdDraw.show();

        // print and draw the line segments
        for (LineSegment segment : collinear.segments()) {
            StdOut.println(segment);
            segment.draw();
        }
        StdDraw.show();
    }
}

by the way, this is a great course

0 Answers