import java.math.BigInteger;

/** Future Factorial computes factorial of a positive BigInteger <i>n</i>.
    It computes factorial as a product of the range of integers from 1 to
    <i>n</i>.  It illustrates concurrent recursive divide and conquer on
    the range of integers to be multiplied.  A non-minimal range is 
    is divided in half, and futures are used to compute the 
    rangeproducts for each subrange concurrently. 

    @author CarlManning, caroma@ai.mit.edu<br>
    Copyright (c) 1999 Massachusetts Institute of Technology
**/
class FutureFactorial { 
  public static BigInteger factorial(final BigInteger n) {
    if (1 == n.signum()) // positive
      return rangeProduct(ONE, n);
    else
      throw new IllegalArgumentException("n < 1");
  }
  static final BigInteger ONE = BigInteger.ONE;
  static final BigInteger TWO = new BigInteger("2");
  public static BigInteger rangeProduct(final BigInteger lo,
					final BigInteger hi) {
    if      (lo.equals(hi))            return lo;
    else if ((lo.add(ONE)).equals(hi)) return lo.multiply(hi);
    else {
      final BigInteger mid = (lo.add(hi)).divide(TWO);
      // future creation cannot be nested in .value() expression, else thread
      // would wait for value before creating second future -- non concurrent.
      Future loProd = (new Future() { { start(); }
                         public Object compute() {
			   return rangeProduct(lo, mid); }});
      Future hiProd = (new Future() { { start(); }
	                 public Object compute() {
			   return rangeProduct(mid.add(ONE), hi); }});
      return ((BigInteger)loProd.value()).multiply((BigInteger)hiProd.value());
    }
  }
  // test 
  public static void main(String[] parameters) {
    BigInteger parameter =
      new BigInteger(parameters.length == 0 ? "10" : parameters[0]);
    System.out.print("factorial("+parameter+") = "); System.out.flush();
    BigInteger result = factorial(parameter);
    System.out.println(result);
  }
}


/** A future can be used to return a placeholder for a value while
    concurrently computing the value.  It is particularly useful if
    the value won't be used immediately.  <p>
    
    Future must be extended with a <code>compute()</code> method.
    This can be done using an anonymous class at the point the the
    future is created, e.g., <pre>
    .  Future hiProd = (new Future() { 
    .	                 public Object compute() {
    .			   return rangeProduct(mid.add(ONE), hi); }
    .			 { start(); }})</pre>
    Note the <code> { start(); } </code> initializer, which starts
    the future running; it must not be called until the derived
    object is fully initialized, including any free final vars in
    the anonymous class. <p>
    
    The future value can later be accessed by calling the
    <code> value() </code> method; any thread which calls this will
    wait if necessary until the thread computing the value has completed.
    If the computation throws an Error or RuntimeException, then
    <code> value() </code> will also throw the exception. <p>

    Future implements Runnable rather than extending Thread so that when the
    computing thread has be completed it can be garbage collected.  **/
abstract class Future implements Runnable {
  // --- fields ---
  private State myState = UNINITIALIZED;
  private Object myValue = null;
  // --- constants for state ---
  private static class State {
    private String stateName;
    State(String stateName) { this.stateName = stateName; }
    public String toString() { return stateName; }
  }
  private static final
    State UNINITIALIZED          = new State("Uninitialized");
  private static final
    State INITIALIZED_AND_STARTED= new State("Initialized and started");
  private static final
    State COMPLETED_RETURN       = new State("Completed with return");
  private static final
    State COMPLETED_THROW        = new State("Completed with throw");
  // --- constructor ---
  Future() {}
  /** Start computing value of future in a new thread. <code>start()</code>
      must not be called until future is initialized; this includes
      initializing free final variables in derived classes' compute
      method.  It may be called at end of initialization of a derived
      class IF that class is anonymous or final (so no classes can
      ever be derived from it).
      @throws IllegalStateException if has already been started.
  **/
  public synchronized void start() {
    if (myState == UNINITIALIZED) {
      Thread thread = new Thread(this);
      thread.start(); 
      myState = INITIALIZED_AND_STARTED;
      return;
    } else {
      throw new IllegalStateException("Already started.");
    }
  }
  /** compute value of future; called by run after future is started **/
  protected abstract Object compute(); 
  // --- Runnable ---
  public synchronized void run() { 
    while (myState == UNINITIALIZED) 
      try { this.wait(); } catch (InterruptedException e) {}
    
    if (myState == INITIALIZED_AND_STARTED) {
      try { 
	myValue = compute();
	myState = COMPLETED_RETURN;
      } catch(Throwable t) {
	myValue = t;
	myState = COMPLETED_THROW;
      }
      this.notifyAll();
    }
  }
  /** get value of future, waiting for computation to complete if necessary.
      @throws Error if {@link #compute()} completes by throwing an Error.
      @throws RuntimeException if {@link #compute()} completes by throwing
      a runtime exception. **/
  public synchronized Object value() {
    while (! (myState == COMPLETED_RETURN || myState == COMPLETED_THROW)) {
      try {
	this.wait();
      }
      catch (InterruptedException e) {
	throw new Error(e.toString());
      }
    }
    if (myState == COMPLETED_RETURN)
      return myValue;
    else { // myState == COMPLETED_THROW
      Throwable thrown = (Throwable) myValue;
      if (dbgLev> 0) thrown.printStackTrace();
      if (thrown instanceof Error) throw (Error) thrown;
      else throw (RuntimeException) thrown;
    }
  }
  public String toString() {
    return "Future(state="+myState+", value="+myValue+")";}
  public static int dbgLev = 1;
}