CubeSum.java

Below is the syntax highlighted version of CubeSum.java from §2.4 Priority Queues.

/*************************************************************************
 *  Compilation:  javac CubeSum.java
 *  Execution:    java CubeSum N
 *  Dependencies: MinPQ.java
 * 
 *  Print out integers of the form a^3 + b^3 in sorted order, where
 *  0 <= a <= b <= N.
 *
 *  % java CubeSum 10
 *  0 = 0^3 + 0^3
 *  1 = 0^3 + 1^3
 *  2 = 1^3 + 1^3
 *  8 = 0^3 + 2^3
 *  9 = 1^3 + 2^3
 *  ...
 *  1512 = 8^3 + 10^3
 *  1729 = 9^3 + 10^3
 *  2000 = 10^3 + 10^3
 *
 *  Remarks
 *  -------
 *   - Easily extends to handle sums of the form f(a) + g(b)
 *   - Prints out a sum more than once if it can be obtained
 *     in more than one way, e.g., 539 = 3^3 + 8^3 = 6^3 + 7^3
 *
 *************************************************************************/

public class CubeSum implements Comparable<CubeSum> {
    private final int sum;
    private final int i;
    private final int j;

    public CubeSum(int i, int j) {
        this.sum = i*i*i + j*j*j;
        this.i = i;
        this.j = j;
    }

    public int compareTo(CubeSum that) {
        if (this.sum < that.sum) return -1;
        if (this.sum > that.sum) return +1;
        return 0;
    }

    public String toString() {
        return sum + " = " + i + "^3" + " + " + j + "^3";
    }


    public static void main(String[] args) {

        int N = Integer.parseInt(args[0]);

        // initialize priority queue
        MinPQ<CubeSum> pq = new MinPQ<CubeSum>();
        for (int i = 0; i <= N; i++) {
            pq.insert(new CubeSum(i, i));
        }

        // find smallest sum, print it out, and update
        while (!pq.isEmpty()) {
            CubeSum s = pq.delMin();
            StdOut.println(s);
            if (s.j < N) pq.insert(new CubeSum(s.i, s.j + 1));
        }
    }

}