package edu.rice.comp322;

import edu.rice.hj.api.HjFuture;
import edu.rice.hj.api.HjMetrics;
import edu.rice.hj.api.SuspendableException;
import edu.rice.hj.runtime.config.HjSystemProperty;
import edu.rice.hj.runtime.util.Pair;

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

import static edu.rice.hj.Module0.abstractMetrics;
import static edu.rice.hj.Module0.doWork;
import static edu.rice.hj.Module0.launchHabaneroApp;
import static edu.rice.hj.Module1.async;
import static edu.rice.hj.Module1.future;
import static edu.rice.hj.experimental.ModuleZ.finish;

/**
 * Solution to Worksheet 5.
 *
 * @author Shams Imam
 */
public final class BinomialCoefficient {

    /**
     * Disallow instance creation of utility class.
     */
    private BinomialCoefficient() {
        super();
    }

    /**
     * The main method.
     *
     * @param args an array of {@link String} objects.
     */
    public static void main(final String[] args) {

        final int n = 20;
        final int k = 12;

        HjSystemProperty.abstractMetrics.set(true);

        launchHabaneroApp(() -> {
            finish(() -> {
                async(() -> {
                    final int r = sequentialChoose(n, k);
                    System.out.println("sequentialChoose(" + n + ", " + k + ") = " + r);
                });
            });
            printAbstractMetrics();
        });

        if (false)
            launchHabaneroApp(() -> {
                finish(() -> {
                    async(() -> {
                        final int r = parallelizedChoose(n, k);
                        System.out.println("parallelizedChoose(" + n + ", " + k + ") = " + r);
                    });
                });
                printAbstractMetrics();
            });

        if (false)
            launchHabaneroApp(() -> {
                finish(() -> {
                    async(() -> {
                        final int r = sequentialMemoizedChoose(n, k);
                        System.out.println("sequentialMemoizedChoose(" + n + ", " + k + ") = " + r);
                    });
                });
                printAbstractMetrics();
            });

        if (false)
            launchHabaneroApp(() -> {
                finish(() -> {
                    async(() -> {
                        final int r = futureMemoizedChoose(n, k);
                        System.out.println("futureMemoizedChoose(" + n + ", " + k + ") = " + r);
                    });
                });
                printAbstractMetrics();
            });

        if (false)
            launchHabaneroApp(() -> {
                finish(() -> {
                    async(() -> {
                        final int r = futureMemoizedChoose2(n, k);
                        System.out.println("futureMemoizedChoose2(" + n + ", " + k + ") = " + r);
                    });
                });
                printAbstractMetrics();
            });

    }

    private static void printAbstractMetrics() {
        final HjMetrics abstractMetrics = abstractMetrics();
        System.out.println("  Work = " + abstractMetrics.totalWork());
        System.out.println("  CPL = " + abstractMetrics.criticalPathLength());
    }

    private static int sequentialChoose(final int n, final int k) {

        if (n == 0 || k == 0 || n == k) {
            return 1;
        }
        final int left = sequentialChoose(n - 1, k - 1);
        final int right = sequentialChoose(n - 1, k);

        doWork(1);
        return left + right;
    }

    private static int parallelizedChoose(final int n, final int k)
        throws SuspendableException {

        if (n == 0 || k == 0 || n == k) {
            return 1;
        }
        final HjFuture<Integer> leftFuture = future(() -> parallelizedChoose(n - 1, k - 1));
        final HjFuture<Integer> rightRuture = future(() -> parallelizedChoose(n - 1, k));

        final Integer left = leftFuture.get();
        final Integer right = rightRuture.get();
        doWork(1);
        return left + right;
    }

    private static final Map<Pair<Integer, Integer>, Integer> smCache = new ConcurrentHashMap<>();

    private static int sequentialMemoizedChoose(final int n, final int k) {

        final Pair<Integer, Integer> nk = Pair.factory(n, k);
        if (smCache.containsKey(nk)) {
            return smCache.get(nk);
        }

        if (n == 0 || k == 0 || n == k) {
            return 1;
        }
        final int left = sequentialMemoizedChoose(n - 1, k - 1);
        final int right = sequentialMemoizedChoose(n - 1, k);

        doWork(1);
        final int result = left + right;
        smCache.put(nk, result);
        return result;
    }

    private static final Map<Pair<Integer, Integer>, Integer> fmsCache = new ConcurrentHashMap<>();

    private static int futureMemoizedChoose(final int n, final int k) throws SuspendableException {

        final Pair<Integer, Integer> nk = Pair.factory(n, k);
        if (fmsCache.containsKey(nk)) {
            return fmsCache.get(nk);
        }

        if (n == 0 || k == 0 || n == k) {
            return 1;
        }
        final HjFuture<Integer> leftFuture = future(() -> futureMemoizedChoose(n - 1, k - 1));
        final HjFuture<Integer> rightRuture = future(() -> futureMemoizedChoose(n - 1, k));

        final Integer left = leftFuture.get();
        final Integer right = rightRuture.get();

        doWork(1);
        final int result = left + right;
        fmsCache.put(nk, result);
        return result;
    }

    private static final Map<Pair<Integer, Integer>, HjFuture<Integer>> fmfCache = new ConcurrentHashMap<>();

    private static int futureMemoizedChoose2(final int n, final int k) throws SuspendableException {

        final Pair<Integer, Integer> nk = Pair.factory(n, k);
        if (fmfCache.containsKey(nk)) {
            return fmfCache.get(nk).get();
        }

        final HjFuture<Integer> resultFuture = future(() -> {
            if (n == 0 || k == 0 || n == k) {
                return 1;
            }

            final HjFuture<Integer> leftFuture = future(() -> futureMemoizedChoose2(n - 1, k - 1));
            final HjFuture<Integer> rightRuture = future(() -> futureMemoizedChoose2(n - 1, k));

            final Integer left = leftFuture.get();
            final Integer right = rightRuture.get();

            doWork(1);
            return left + right;
        });
        fmfCache.put(nk, resultFuture);
        return resultFuture.get();
    }
}