import static java.util.Arrays.*;
import static java.util.stream.Collectors.*;

import java.text.CollationKey;
import java.text.Collator;
import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Locale;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.function.Function;
import java.util.regex.Pattern;
import java.util.stream.IntStream;

public class ArrayInitializerRaceConditionTest {

public static void main(String[] args) throws Exception {
for (int k = 0; k <= 100; k++) {
for (int n = 4; n <= 16; n++) {
Map<String, CollationKey> cache = new ConcurrentHashMap<String, CollationKey>();
List<IndexEntry> index = IntStream.range(0, 50000).mapToObj(i -> new IndexEntry(i, o -> tokenize(o, cache))).collect(toList());
CollationKey[] query = tokenize(12345, cache);

ExecutorService threadPool = Executors.newFixedThreadPool(n);

List<Future<List<IndexEntry>>> tasks = IntStream.range(0, n).mapToObj(t -> {
return threadPool.submit(() -> {
return find(query, index);
});
}).collect(toList());

threadPool.shutdown();

Set<String> output = new LinkedHashSet<String>();
for (Future<List<IndexEntry>> task : tasks) {
output.add(task.get().toString());
}
System.out.format("%02d-%02d: %s%n", k, n, output);
}
}
}

private static final Collator COLLATOR = Collator.getInstance(Locale.ENGLISH);
private static final Pattern SPACE = Pattern.compile("");

private static CollationKey[] tokenize(Object sequence, Map<String, CollationKey> cache) {
return SPACE.splitAsStream(sequence.toString()).map(s -> getCollationKey(s, cache)).toArray(CollationKey[]::new);
}

private static CollationKey getCollationKey(String word, Map<String, CollationKey> cache) {
return cache.computeIfAbsent(word, COLLATOR::getCollationKey);
}

private static List<IndexEntry> find(CollationKey[] query, List<IndexEntry> index) {
List<IndexEntry> matches = new ArrayList<IndexEntry>();

for (IndexEntry i : index) {
CollationKey[] key = i.getKey();
CollationKey[] commonName = matchFirstCommonSequence(new CollationKey[][] { query, key });

if (commonName != null && commonName.length >= query.length) {
matches.add(i);
}
}

return matches;
}

private static <E> E[] matchFirstCommonSequence(E[][] names) {
E[] common = null;
for (E[] words : names) {
if (common == null) {
// initialize common with current word array
common = words;
} else {
// find common sequence
common = firstCommonSequence(common, words);
// no common sequence
if (common == null) {
return null;
}
}
}
return common;
}

private static <E> E[] firstCommonSequence(E[] seq1, E[] seq2) {
E[] matchSeq = null;
for (int i = 0; i < seq1.length; i++) {
for (int j = 0; j < seq2.length; j++) {
// common sequence length
int len = 0;

// iterate over common sequence
while (equals(seq1, i + len, seq2, j + len)) {
len++;
}

// check if a common sequence was found
if (len > 0) {
return copyOfRange(seq1, i, i + len);
}
}
}
return matchSeq;
}

private static boolean equals(Object[] seq1, int i1, Object[] seq2, int i2) {
if (i1 < seq1.length && i2 < seq2.length) {
Object o1 = seq1[i1];
Object o2 = seq2[i2];

try {
Objects.requireNonNull(o1, "ARRAY ELEMENTS CANNOT BE NULL");
Objects.requireNonNull(o2, "ARRAY ELEMENTS CANNOT BE NULL");
} catch (NullPointerException e) {
System.out.println("o1 was " + o1);
System.out.println("o2 was " + o2);
System.out.println("seq1 was " + asList(seq1));
System.out.println("seq2 was " + asList(seq2));
throw e;
}

return o1.equals(o2);
}

return false;
}

private static class IndexEntry {

private Object object;
private Function<Object, CollationKey[]> prepare;

private CollationKey[] key;

public IndexEntry(Object object, Function<Object, CollationKey[]> prepare) {
this.object = object;
this.prepare = prepare;
}

public CollationKey[] getKey() {
if (key == null && object != null) {
key = prepare.apply(object);

// CONFIRM THAT ARRAY ELEMENTS ARE NOT NULL (this is always the case, so an exception is never thrown here)
for (CollationKey k : key) {
if (k == null) {
throw new IllegalStateException("CollationKey is NULL");
}
}
}
return key;
}

@Override
public String toString() {
return object.toString();
}
}

}