import java.io.*;
import java.util.*;

import static java.util.Arrays.asList;

public class Tests {
    static final int MIN_N = 1;
    static final int MAX_N = 50;
    static final int MIN_C = 1;
    static final int MAX_C = 10;
    static final char FROM = 'a';
    static final char TO = 'z';

    static final String testMask = "%02d";
    static final String testRoot = "tests";
    static final String descName = "tests.lst";

    final Random random = new Random(7023842358235832895L);
    final PrintWriter descriptions;

    int testNo = 0;

    private static void rmrf(File f) {
        if (f.exists()) {
            if (f.isDirectory()) {
                for (File ch : f.listFiles()) {
                    rmrf(ch);
                }
            }
            f.delete();
        }
    }

    private void assertBetween(int min, long value, int max) {
        if (!(min <= value && value <= max)) {
            throw new AssertionError(value + " not between "  + min + " and " + max);
        }
    }

    private void validateTest(Collection<String> words) {
        assertBetween(MIN_N, words.size(), MAX_N);
        for (String word : words) {
            assertBetween(MIN_C, word.length(), MAX_C);
            for (int i = 0; i < word.length(); i++) {
                assertBetween(FROM, word.charAt(i), TO);
            }
        }
        if (words.size() != (new HashSet<>(words)).size()) {
            throw new AssertionError("There are some equal words");
        }
    }

    private void writeTest(Collection<String> test, String descriptionFmt, Object... args) throws IOException {
        test = new ArrayList<>(test);
        ++testNo;
        String desc = String.format(descriptionFmt, args);
        String text = String.format(testMask + ": " + desc, testNo);
        validateTest(test);
        try (PrintWriter out = new PrintWriter(String.format(testRoot + "/" + testMask, testNo))) {
            out.println(test.size());
            for (String s : test) {
                out.println(s);
            }
        }
        System.out.println(text);
        descriptions.println(text);
    }

    public Tests() throws IOException {
        File root = new File(testRoot);
        rmrf(root);
        root.mkdirs();
        descriptions = new PrintWriter(testRoot + "/" + descName);
        try {
            run();
        } finally {
            descriptions.close();
        }
    }

    private void handMade() throws IOException {
        writeTest(asList("north", "eastern", "european", "regional", "contest"), "Sample test");
        writeTest(asList("a"), "Minimal test");
        writeTest(asList("a", "n"), "Two smallest different words");
        writeTest(asList("test", "contest"), "A word and a suffix");
        writeTest(asList("contests", "contest"), "A word and a prefix");
        writeTest(asList("contests", "contesty"), "Two words with big common prefix");
        writeTest(asList("abcdef", "defghi", "bcdefgh"), "Longest word does not start in the root");
        writeTest(asList("abcdef", "defghi", "bcdefgh", "defjkl", "bcdefjk"), "Longest words do not start in the root and the tree has branches");
        writeTest(asList("abcdef", "defghi", "defdef"), "Non-oriented cycle of length 3 in an oriented overlap graph");
        writeTest(asList("abcdef", "defabc"), "Oriented cycle of length 2 in an oriented overlap graph");
        writeTest(asList("abcde", "deabc"), "Oriented cycle of length 2 with different weights of edges in an oriented overlap graph");
        writeTest(asList("abcdef", "defghi", "ghiabc"), "Oriented cycle of length 3 in an oriented overlap graph");
        writeTest(asList("abcdef", "bcdghi", "cdghjk"), "Some secondary prefix overlap");

        writeTest(asList("abcdefghij", "defqrt"), "Branch starts from the middle");
        writeTest(asList("ababababa", "bc", "bcd", "bcde"), "Multiple ways to start a fork from");
        writeTest(asList("abcdefgh", "abczefgh", "fgx"), "A word can be added to different branches");
        writeTest(asList("abcde", "abafg", "babc", "bcdh"), "A word can be added to different branches with different results");
        writeTest(asList("ababababab", "bac", "bacd", "bacde"), "Multiple ways to attach a string");
    }

    private String randomString(int size, int alphabet) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < size; ++i) {
            sb.append((char) (random.nextInt(alphabet) + 'a'));
        }
        return sb.toString();
    }

    private List<String> randomSubstrings(String base, int count) {
        List<String> rv = new ArrayList<>(count);
        for (int i = 0; i < count; ++i) {
            int a, b;
            do {
                a = random.nextInt(base.length() + 1);
                b = random.nextInt(base.length() + 1);
            } while (a == b || Math.min(a, b) + 10 < Math.max(a, b));
            rv.add(base.substring(Math.min(a, b), Math.max(a, b)));
        }
        return rv;
    }

    private void randomSubstringsWrapper(String base, int count, int howMany) throws IOException {
        for (int i = 0; i < howMany; ++i) {
            writeTest(new HashSet<>(randomSubstrings(base, count)), count + " random substrings of '" + base + "'");
        }
    }

    private List<String> generateInlays(int length, int alphabet) {
        String[] v = new String[50];
        for (int i = 0; i < v.length; ++i) {
            int index = random.nextInt(i + 1);
            if (index == i) {
                v[i] = randomString(length, alphabet);
            } else {
                int a, b;
                do {
                    a = random.nextInt(length) + 1;
                    b = random.nextInt(length) + 1;
                } while (a == b);
                String prefix = v[index].substring(Math.min(a, b), Math.max(a, b));
                String suffix = randomString(length - prefix.length(), alphabet);
                v[i] = prefix + suffix;
            }
        }
        return Arrays.asList(v);
    }

    private void generateInlaysWrapper(int alphabet, int howMany) throws IOException {
        for (int i = 0; i < howMany; ++i) {
            writeTest(new HashSet<>(generateInlays(10, alphabet)), "Random inlays with alphabet size " + alphabet);
        }
    }

    private void generateDuplicatedInlaysWrapper(int alphabet, int howMany) throws IOException {
        for (int i = 0; i < howMany; ++i) {
            List<String> inlays = generateInlays(5, alphabet);
            for (int j = 0; j < inlays.size(); ++j) {
                inlays.set(j, inlays.get(j) + inlays.get(j));
            }
            writeTest(new HashSet<>(inlays), "Random duplicated inlays with alphabet size " + alphabet);
        }
    }

    private void generateShuffledInlaysWrapper(int alphabet, int howMany) throws IOException {
        for (int i = 0; i < howMany; ++i) {
            List<String> inlays = generateInlays(5, alphabet);
            List<String> result = new ArrayList<>();
            for (int j = 0; j < inlays.size(); ++j) {
                result.add(inlays.get(j) + inlays.get(random.nextInt(inlays.size())));
            }
            writeTest(new HashSet<>(result), "Random shuffled inlays with alphabet size " + alphabet);
        }
    }

    private String nCopies(String what, int howMany) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < howMany; ++i) {
            sb.append(what);
        }
        return sb.toString();
    }

    private void maxAnswerTest() throws IOException {
        List<String> rv = new ArrayList<>();
        for (int i = 0; i < 25; ++i) {
            char c = (char) ('a' + i);
            rv.add(nCopies("" + c, 10));
            rv.add(c + nCopies("z", 9));
        }
        writeTest(rv, "Maximum answer test");
    }

    private void generateCyclicSubstrings(int alphabet, int times) throws IOException {
        for (int t = 0; t < times; ++t) {
            String s = randomString(50, alphabet);
            String s2 = s + s;
            List<String> test = new ArrayList<>();
            for (int i = 0; i < s.length(); ++i) {
                test.add(s2.substring(i, i + 10));
            }
            writeTest(test, "50 cyclic substrings of length 10 of string '" + s + "'");
        }
    }

    private void randomTests() throws IOException {
        randomSubstringsWrapper("abcdefghijklmnopqrstuvwxyz", 50, 3);
        randomSubstringsWrapper("aaaaaaaaaabaaaaaaaaaaaaaaa", 50, 3);
        randomSubstringsWrapper("abacabadabacabaeabacabadabacaba", 50, 3);

        generateInlaysWrapper(2, 3);
        generateInlaysWrapper(3, 3);
        generateInlaysWrapper(26, 3);

        generateDuplicatedInlaysWrapper(2, 3);
        generateDuplicatedInlaysWrapper(3, 3);
        generateDuplicatedInlaysWrapper(26, 3);

        generateShuffledInlaysWrapper(2, 3);
        generateShuffledInlaysWrapper(3, 3);
        generateShuffledInlaysWrapper(26, 3);

        generateCyclicSubstrings(2, 3);
        generateCyclicSubstrings(3, 3);
        generateCyclicSubstrings(26, 3);
    }

    private void run() throws IOException {
        handMade();
        maxAnswerTest();
        randomTests();
    }

    public static void main(String[] args) throws IOException {
        new Tests();
    }
}
