package ru.maxkar.java;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class Generator {

    private static final int PAR = 8;
    private static final int PAR_MIN = 300;

    private static final ExecutorService exec = Executors
            .newFixedThreadPool(PAR);

    private static void doRange(int[] cur, int[] next, int id, int size,
            int min, int max) {
        for (int i = min; i < max; i++)
            if (cur[i] >= 0)
                next[i + size] = id;
    }

    public static void fillProducts(int[] cur, int[] next, int id, int size) {
        doRange(cur, next, id, size, 0, cur.length - size);
    }

    public static void fillProductsPar(final int[] cur, final int[] next,
            final int id, final int size) {
        final int realLast = (cur.length - size);
        final int step = realLast / PAR;
        int ptr = 0;
        final List<Future<?>> futures = new ArrayList<>();
        for (int i = 0; i < PAR - 1; i++) {
            final int start = ptr;
            final int end = ptr + step;
            futures.add(exec.submit(new Runnable() {
                @Override
                public void run() {
                    doRange(cur, next, id, size, start, end);
                }
            }));
            ptr = end;
        }
        final int lastPtr = ptr;
        futures.add(exec.submit(new Runnable() {
            @Override
            public void run() {
                doRange(cur, next, id, size, lastPtr, realLast);
            }
        }));

        for (Future<?> f : futures)
            try {
                f.get();
            } catch (InterruptedException e) {
                // FIXME: !
            } catch (ExecutionException e) {
                // FIXME: !
            }
    }

    public static void fillProductsAny(int[] cur, int[] next, int id, int size) {
        final int realLast = (cur.length - size);
        if (realLast <= PAR_MIN)
            fillProducts(cur, next, id, size);
        else
            fillProductsPar(cur, next, id, size);
    }

    public static void printAnswer(int[][] ans, int sum, int[] weights) {
        if (ans[ans.length - 1][sum] == -1) {
            System.out.println("Not found");
            return;
        }

        System.out.print("Found :");
        int rest = sum;
        int ptr = ans[ans.length - 1][rest];
        while (ptr > 0) {
            final int wname = ptr - 1;
            System.out.print(" " + weights[wname]);
            rest -= weights[wname];
            ptr = ans[wname][rest];
        }
        System.out.println();
    }

    public static void printAnswerAlt(int[][] ans, int sum, int[] weights) {
        if (ans[ans.length - 1][sum] == -1) {
            System.out.println("Not found");
            return;
        }

        System.out.print("Found :");
        int rest = sum;
        for (int i = weights.length; i -- > 0;) {
            if (ans[i][rest] < 0) {
                final int w = weights[i];
                System.out.print(" " + w);
                rest -= w;
            }
        }
        System.out.println();
    }
    
    public static void qsolve(int sum, int[] weights) {
        final int[][] steps = new int[weights.length + 1][];
        final int[] start = new int[sum + 1];
        Arrays.fill(start, -1);
        start[0] = 0;
        steps[0] = start;
        
        int[] queue = new int[sum + 1];
        int queec = 1;
        queue[0] = 0;

        for (int i = 0; i < weights.length; i++) {
            final int[] next = steps[i].clone();
            final int id = i + 1;
            steps[id] = next;
            
            final int w = weights[i];
            
            final int queel = queec;
            for (int queep = 0; queep < queel; queep++) {
                final int qw = queue[queep];
                final int nw = qw + w;
                if (nw <= sum && next[nw] < 0) {
                    next[nw] = id;
                    queue[queec++] = nw;
                }
            }
        }
        printAnswer(steps, sum, weights);
    }

    public static void solve(int sum, int[] weights) {
        final int[][] steps = new int[weights.length + 1][];
        int[] current = new int[sum + 1];
        Arrays.fill(current, -1);
        current[0] = 0;
        steps[0] = current;

        for (int i = 0; i < weights.length; i++) {
            final int id = i + 1;
            final int[] next = current.clone();
            steps[id] = next;
            fillProductsAny(current, next, id, weights[i]);
            current = next;
        }
        printAnswer(steps, sum, weights);
        printAnswerAlt(steps, sum, weights);
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        solve(1, new int[] { 1, 2, 4, 6, 8, 16, 32, 64, 128, 256 });
        solve(100, new int[] { 1, 2, 4, 6, 8, 16, 32, 64, 128, 256 });
        
        solve(321230, new int[] { 16648, 28450, 13524, 12991, 13593, 4797,
                18596, 10680, 17865, 25254, 23808, 27379, 6657, 3325, 7573,
                5126, 14361, 17311, 4578, 9632, 12375, 15291, 13814, 7935,
                22872, 26001, 7895, 9854, 20650, 3317, 23612, 5258, 15092,
                1171, 7528, 26422, 19202, 23453, 18628, 4293, 15008, 24880,
                24119, 21476, 29331, 3093, 8820, 11034, 6879, 29859, 24913,
                22327, 29880, 24401, 383, 28490, 1960, 7673, 29307, 19311,
                24713, 2632, 11248, 2261, 17632, 16322, 26870, 17694, 23047,
                13155, 15627, 11247, 25238, 8480, 6236, 4343, 16317, 2668,
                11793, 9485, 10799, 4823, 16498, 23618, 14526, 12048, 18346,
                28581, 7984, 731, 17158, 26949, 21531, 23965, 17754, 12625,
                7170, 1924, 26609, 21243, 18748, 13556, 19710, 25036, 8157,
                23372, 26228, 353, 24819, 11351, 28590, 10866, 14783, 895,
                15260, 15715, 2238, 26571, 14970, 13764, 19156, 6041, 1615,
                2947, 24500, 19495, 9775, 4290, 9661, 1083 });
        exec.shutdown();
    }
}