package local.test;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

public class LinkedWords {
//        static final int SIZE = 10_000;
        static final int SIZE = 300_000;
//    static final int SIZE = 1_000_000;

//    static final int SEQUENTIAL_THRESHOLD = 500;
//    static final int SEQUENTIAL_THRESHOLD = 1_000;
    static final int SEQUENTIAL_THRESHOLD = 5_000;
//    static final int SEQUENTIAL_THRESHOLD = 10_000;
//    static final int SEQUENTIAL_THRESHOLD = 50_000;
//    static final int SEQUENTIAL_THRESHOLD = 100_000;
//    static final int SEQUENTIAL_THRESHOLD = Integer.MAX_VALUE;


    public static void main(String[] args) {
        String word = "0";

        ArrayList<String> words = new ArrayList<>();
        for (int i = 0; i < SIZE; i++) {
            words.add((i % 100) + "");
        }

        long t1 = System.currentTimeMillis();
        Set<String> linkedWords = getLinkedWords(word, words);
        System.out.println(System.currentTimeMillis() - t1);

        long t2 = System.currentTimeMillis();
        Set<String> linkedWordsForeach = getLinkedWordsForeach(word, words);
        System.out.println(System.currentTimeMillis() - t2);

        long t3 = System.currentTimeMillis();
        Set<String> linkedWordsRecursiveAction = getLinkedWordsRecursiveAction(word, words);
        System.out.println(System.currentTimeMillis() - t3);

        long t4 = System.currentTimeMillis();
        Set<String> linkedWordsRecursiveAction2 = getLinkedWordsRecursiveAction2(word, words);
        System.out.println(System.currentTimeMillis() - t4);
    }

    private static Set<String> getLinkedWords(String s, List<String> words) {
        Set<String> tmp = new HashSet<String>();
        for (int i = 0; i < words.size() - 1; i++) {
            if (s.equals(words.get(i))) {
                tmp.add(words.get(i + 1));
            }
        }
        return tmp;
    }

    private static Set<String> getLinkedWordsForeach(String s, List<String> words) {
        Set<String> tmp = new HashSet<String>();
        String prev = null;
        for (String word : words) {
            if (prev != null && prev.equals(s)) {
                tmp.add(word);
            }
            prev = word;
        }
        return tmp;
    }

    private static Set<String> getLinkedWordsRecursiveAction(String s, ArrayList<String> words) {
        ConcurrentHashMap.KeySetView<String, Boolean> acc = ConcurrentHashMap.newKeySet();
        ForkJoinPool forkJoinPool = ForkJoinPool.commonPool();
        forkJoinPool.invoke(new LinkedWordsAction(s, words, 0, words.size(), acc));
        return acc;
    }

    private static class LinkedWordsAction extends RecursiveAction {
        final String word;
        final ArrayList<String> words;

        final int low;
        final int high;

        final Set<String> acc;

        public LinkedWordsAction(String word, ArrayList<String> words, int low, int high, Set<String> acc) {
            this.word = word;
            this.words = words;
            this.low = low;
            this.high = high;
            this.acc = acc;
        }

        @Override
        protected void compute() {
            if (high - low <= SEQUENTIAL_THRESHOLD) {
                for (int i = low; i < high; ++i) {
                    if (word.equals(words.get(i))) {
                        acc.add(words.get(i + 1));
                    }
                }
            } else {
                int mid = low + (high - low) / 2;
                LinkedWordsAction left = new LinkedWordsAction(word, words, low, mid, acc);
                LinkedWordsAction right = new LinkedWordsAction(word, words, mid, high, acc);
                invokeAll(left, right);
                if (words.get(mid - 1).equals(word)) {
                    acc.add(words.get(mid));
                }
            }

        }
    }

    private static Set<String> getLinkedWordsRecursiveAction2(String s, ArrayList<String> words) {
        ConcurrentHashMap.KeySetView<String, Boolean> acc = ConcurrentHashMap.newKeySet();
        ForkJoinPool forkJoinPool = ForkJoinPool.commonPool();
        forkJoinPool.invoke(new LinkedWordsAction2(s, words, 0, words.size(), acc, null));
        return acc;
    }

    private static class LinkedWordsAction2 extends RecursiveAction {
        final String word;
        final ArrayList<String> words;

        final int low;
        final int high;

        final Set<String> acc;

        LinkedWordsAction2 next;

        public LinkedWordsAction2(String word, ArrayList<String> words, int low, int high, Set<String> acc, LinkedWordsAction2 next) {
            this.word = word;
            this.words = words;
            this.low = low;
            this.high = high;
            this.acc = acc;
            this.next = next;
        }

        @Override
        protected void compute() {
            int l = low;
            int h = high;
            LinkedWordsAction2 right = null;
            while (h - l > SEQUENTIAL_THRESHOLD && getSurplusQueuedTaskCount() <= 3) {
                int mid = (l + h) >>> 1;
                right = new LinkedWordsAction2(word, words, mid, h, acc, right);
                right.fork();
                h = mid;
            }
            atLeaf(l, h);
            while (right != null) {
                if (right.tryUnfork()) // directly calculate if not stolen
                    right.atLeaf(right.low, right.high);
                else {
                    right.join();
                }
                if (words.get(right.low - 1).equals(word)) {
                    acc.add(words.get(right.low));
                }
                right = right.next;
            }
        }

        private void atLeaf(int l, int h) {
            for (int i = l; i < h; ++i) {
                if (word.equals(words.get(i))) {
                    acc.add(words.get(i + 1));
                }
            }
        }
    }

}