/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

// Jacobi iteration without any matrix

import java.util.concurrent.*;

public class CC4 {

    public static void main(String[] args) throws Exception {
        int n = 1024;
        int steps = 1000;

        try {
            if (args.length > 0)
                n = Integer.parseInt(args[0]);
            if (args.length > 1)
                steps = Integer.parseInt(args[1]);
        }

        catch (Exception e) {
            System.out.println("Usage: java CC4 <size> <max steps>]");
            return;
        }

        int nreps = 10;
        Driver driver = new Driver(1, n, 1, n, steps);
        for (int rep = 0; rep < nreps; ++rep) {
            long startTime = System.currentTimeMillis();
            driver.invoke();
            
            long time = System.currentTimeMillis() - startTime;
            double secs = ((double)time) / 1000.0;

            System.out.println("Compute Time: " + secs);
            driver.reinitialize();
            Thread.sleep(1000);
        }
        System.out.println(ForkJoinPool.commonPool());
    }


    abstract static class MatrixTree extends CountedCompleter<Void> {
        long value;
        MatrixTree(CountedCompleter<?> p, int c) { super(p, c); }
    }

    static final class LeafNode extends MatrixTree {
        LeafNode(CountedCompleter<?> p) {
            super(p, 0);
            value = ThreadLocalRandom.current().nextLong();
        }

        public final void compute() {
            long x = value;
            x ^= x << 13;
            x ^= x >>> 7;
            x ^= x << 17;
            value = x;
            tryComplete();
        }
    }

    static final class FourNode extends MatrixTree {
        MatrixTree q1;
        MatrixTree q2;
        MatrixTree q3;
        MatrixTree q4;
        FourNode(CountedCompleter<?> p) {
            super(p, 3);
        }

        public void onCompletion(CountedCompleter<?> caller) {
            long md = q1.value, m;
            if ((m = q2.value) > md)
                md = m;
            if ((m = q3.value) > md)
                md = m;
            if ((m = q4.value) > md)
                md = m;
            value = md;
            setPendingCount(3);
        }

        public final void compute() {
            q4.fork();
            q3.fork();
            q2.fork();
            q1.compute();
        }
    }


    static final class TwoNode extends MatrixTree {
        MatrixTree q1;
        MatrixTree q2;

        TwoNode(CountedCompleter<?> p) {
            super(p, 1);
        }

        public void onCompletion(CountedCompleter<?> caller) {
            long md = q1.value, m;
            if ((m = q2.value) > md)
                md = m;
            value = md;
            setPendingCount(1);
        }

        public final void compute() {
            q2.fork();
            q1.compute();
        }

    }

    static final class Driver extends RecursiveAction {
        MatrixTree mat;
        int firstRow; int lastRow;
        int firstCol; int lastCol;
        final int steps;
        int nleaf;

        Driver(int firstRow, int lastRow,
               int firstCol, int lastCol,
               int steps) {
            this.firstRow = firstRow;
            this.firstCol = firstCol;
            this.lastRow = lastRow;
            this.lastCol = lastCol;
            this.steps = steps;
            mat = build(null, firstRow, lastRow, firstCol, lastCol);
            System.out.println("Using " + nleaf + " segments");

        }

        MatrixTree build(MatrixTree p,
                         int lr, int hr, int lc, int hc) {
            int rows = (hr - lr + 1);
            int cols = (hc - lc + 1);

            int mr = (lr + hr) >>> 1; // midpoints
            int mc = (lc + hc) >>> 1;

            int hrows = (mr - lr + 1);
            int hcols = (mc - lc + 1);

            if (rows * cols <= 1) {
                ++nleaf;
                return new LeafNode(p);
            }
            else if (hrows * hcols >= 1) {
                FourNode q = new FourNode(p);
                q.q1 = build(q, lr,   mr, lc,   mc);
                q.q2 = build(q, lr,   mr, mc+1, hc);
                q.q3 = build(q, mr+1, hr, lc,   mc);
                q.q4 = build(q, mr+1, hr, mc+1, hc);
                return q;
            }
            else if (cols >= rows) {
                TwoNode q = new TwoNode(p);
                q.q1 = build(q, lr, hr, lc,   mc);
                q.q2 = build(q, lr, hr, mc+1, hc);
                return q;
            }
            else {
                TwoNode q = new TwoNode(p);
                q.q1 = build(q, lr,   mr, lc, hc);
                q.q2 = build(q, mr+1, hr, lc, hc);
                return q;
            }
        }

        static void doCompute(MatrixTree m, int s) {
            for (int i = 0; i < s; ++i) {
                m.setPendingCount(3);
                m.invoke();
                m.reinitialize();
            }
        }

        public void compute() {
            doCompute(mat, steps);
            long md = mat.value;
            if (md == 0)
                System.out.println("max diff after " + steps + " steps = " + md);
        }
    }


}