package algs24;
import stdlib.*;
/* ***********************************************************************
 *  Compilation:  javac PerfectPower.java
 *  Execution:    java PerfectPower x | more
 *
 *  Print out all 64-bit integers of the form a^b where b <= x.
 *
 *  Limitations
 *  ----------
 *    - currently prints out duplicates, i.e., when a itself is a perfect
 *      power, then there is more than one way to get a^b
 *
 *  % java PerfectPower 2
 *  4 = 2^2
 *  8 = 2^3
 *  9 = 3^2
 *  16 = 2^4
 *  16 = 4^2
 *  25 = 5^2
 *  27 = 3^3
 *
 *  % java PerfectPower 10
 *  1024 = 2^10
 *  ...
 *  7450580596923828125 = 5^27
 *  7516865509350965248 = 52^11
 *  8335775831236199424 = 78^10
 *  8650415919381337933 = 13^17
 *  9065737908494995456 = 38^12
 *
 *************************************************************************/

public class XPerfectPower implements Comparable<XPerfectPower> {
  private final long value;
  private final int a;
  private final int b;

  public XPerfectPower(int a, int b) {
    this.value = power(a, b);
    this.a = a;
    this.b = b;
  }

  // brute force exponentation suffices
  public static long power(int a, int b) {
    long pow = 1;
    for (int i = 0; i < b; i++) {
      pow *= a;
    }
    return pow;
  }

  public int compareTo(XPerfectPower that) {
    if      (this.value < that.value) return -1;
    else if (this.value > that.value) return +1;
    else                              return  0;
  }

  public String toString() {
    return value + " = " + a + "^" + b;
  }


  public static void main(String[] args) {
    int x = 2;
    if (args.length == 1) x = Integer.parseInt(args[0]);

    // initialize priority queue
    MinPQ<XPerfectPower> pq = new MinPQ<>();

    // maximum power representable as a long is 2^62
    for (int b = x; b <= 62; b++) {
      pq.insert(new XPerfectPower(2, b));
    }

    // find smallest power, print out, and update
    while (!pq.isEmpty()) {
      XPerfectPower p = pq.delMin();
      StdOut.println(p);

      // add next perfect power if it doesn't overflow a long
      if (Math.pow(p.a + 1, p.b) < Long.MAX_VALUE)
        pq.insert(new XPerfectPower(p.a + 1, p.b));
    }
  }

}