/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 *
 */

import java.util.concurrent.*;
import java.util.concurrent.atomic.*;

/**
 * ForkJoinTasks that are always linked in binary parent-child
 * relationships and perform a completion (continuation) action when
 * both subtasks complete. Compared to Recursive tasks,
 * BinaryCompletionTasks may have smaller stack space footprints and
 * faster completion mechanics but higher per-task footprints.
 *
 * <p> <b>Sample Usage.</b>  A version of Fibonacci:
 * <pre>
 * class Fib extends BinaryCompletionTask {
 *   final int n;
 *   int result;
 *   Fib(int n) { this.n = n; }
 *   protected boolean compute() {
 *       if (n &gt; 1) {
 *          linkAndForkSubtasks(new Fib(this, n-1), new Fib(this, n-2));
 *          return false;
 *       }
 *       else {
 *          result = n; // fib(0)==0; fib(1)==1
 *          return propagateCompletion();
 *       }
 *   }
 *   protected void onSubtaskCompletion(BinaryCompletionTask x, BinaryCompletionTask y) {
 *      result = ((Fib)x).result + ((Fib)y).result;
 *   }
 * }
 * </pre>
 * An alternative, and usually faster strategy is to instead use a
 * loop to fork subtasks:
 * <pre>
 *   protected boolean compute() {
 *     Fib f = this;
 *     while (f.n &gt; 1) {
 *        Fib left = new Fib(f, f.n - 1);
 *        Fib right = new Fib(f, f.n - 2);
 *        f.linkSiblings(left, right);
 *        right.fork(); // fork right
 *        f = left;     // loop on left
 *     }
 *     f.result = f.n;
 *     return f.propagateCompletion();
 *   }
 * }
 * </pre>
 */
public abstract class BinaryCompletionTask extends ForkJoinTask<Void> {

    /**
     * Parent to propagate completion; nulled after completion to
     * avoid retaining entire tree as garbage
     */
    final BinaryCompletionTask parent;

    /**
     * Sibling to access on subtask joins, also nulled after completion.
     */
    BinaryCompletionTask sibling;

    /**
     * Creates a new action with the given parent (or null if none). 
     */
    protected BinaryCompletionTask(BinaryCompletionTask parent) {
        this.parent = parent;
    }

    /**
     * The main computation performed by this task. If this method
     * throws an exception, this failure is propagated to all
     * non-completed ancestor tasks.
     *
     * @return true if the root of this computation is known to have completed
     */
    protected abstract boolean compute();

    protected final boolean exec() {
        try {
            return compute();
        } catch(Throwable ex) {
            return propagateException(ex);
        }
    }

    public final Void getRawResult() { return null; }
    protected final void setRawResult(Void mustBeNull) { }

    /**
     * Returns this task's parent, or null if none.
     * @return this task's parent, or null if none.
     */
    public final BinaryCompletionTask getParent() {
        return parent;
    }

    /**
     * Returns this task's sibling, or null if none or this task is
     * already complete.
     * @return this task's sibling, or null if none.
     */
    public final BinaryCompletionTask getSibling() {
        return sibling;
    }

    /**
     * Establishes sibling links for the given tasks.
     * @param x one subtask
     * @param y the other subtask
     * @throws NullPointerException if either argument is null.
     */
    public final void linkSiblings(BinaryCompletionTask x, BinaryCompletionTask y) {
        x.sibling = y;
        y.sibling = x;
    }

    /**
     * Convenience method equivalent to <tt>linkSiblings</tt> followed
     * by forking each.
     * @param x one subtask
     * @param y the other subtask
     * @throws NullPointerException if either argument is null.
     */
    public final void linkAndForkSubtasks(BinaryCompletionTask x, BinaryCompletionTask y) {
        x.sibling = y;
        y.sibling = x;
        y.fork();
        x.fork();
    }

    /**
     * Sets the sibling of this task
     * @param s the sibling
     */
    public void setSibling(BinaryCompletionTask s) {
        sibling = s;
    }

    /**
     * Overridable callback action triggered upon <tt>completed</tt>
     * subtasks.  Upon invocation, both subtasks have completed.
     * After return, this task <tt>isDone</tt> and is joinable by
     * other tasks. The default version of this method does nothing.
     * But it may be overridden in subclasses to perform some action
     * (for example a reduction) when this task is completes.
     * @param x one subtask
     * @param y the other subtask
     */
    protected void onSubtaskCompletion(BinaryCompletionTask x, 
                                       BinaryCompletionTask y) {
    }

    /**
     * Overridable callback action triggered when 
     * subtasks encounter exceptions.  Upon invocation, the given subtask
     * has encountered the given exception.
     * After return, this task <tt>isCompletedAbnormally</tt> and is joinable by
     * other tasks. The default version of this method does nothing.
     * @param x the subtask encountering the exception
     * @param ex the exception
     */
    protected void onSubtaskException(BinaryCompletionTask x, Throwable ex) {
    }

    /**
     * If this task has a sibling that is also complete, invokes
     * <tt>onSubtaskCompletion</tt> of parent task, and in turn its
     * parent, and so on.
     *
     * @return true if the ultimate parent of this task is done.
     */
    protected final boolean propagateCompletion() {
        BinaryCompletionTask a = this, p;
        while ((p = a.parent) != null) {
            if (p.compareAndSetForkJoinTaskTag((short)0, (short)1))
                return false;
            else {
                p.onSubtaskCompletion(a, a.sibling);
                a = p;
            }
        }
        a.quietlyComplete();
        return true;

    }

    /**
     * Completes this task abnormally and propagates to parent
     * tasks. Unless this task is already cancelled or aborted,
     * <tt>completeExceptionally</tt> with the given exception, and
     * then similarly completes parent (if one exists) and so on.
     * @param ex the exception to throw when joining this task
     * @return true (always) to simply usage.
     */
    public final boolean propagateException(Throwable ex) {
        BinaryCompletionTask a = this;
        while (!a.isDone()) {
            BinaryCompletionTask p;
            a.completeExceptionally(ex);
            if ((p = a.parent) == null)
                break;
            else {
                p.onSubtaskException(a, ex);
                a = p;
            }
        }
        return true;
    }

    /**
     * Resets the internal bookkeeping state of this task, erasing
     * simpling (but not parent) linkages.
     */
    public void reinitialize() {
        sibling = null;
        super.reinitialize();
    }


}