import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Random;

public class TestGen {
	final String TEST_PATH = "../tests/";
	final String DESCR_PATH = "../tests/tests.description";
	PrintWriter descFile;
	int tests;
	Random random;

	public void run() {
		System.err.println(TEST_PATH);
		File dir = new File(TEST_PATH);
		if (!dir.exists()) {
			dir.mkdir();
		}
		tests = 0;
		random = new Random(34757239);
		try {
			descFile = new PrintWriter(DESCR_PATH);
		} catch (FileNotFoundException e) {
			System.err.println("Exception " + e);
			System.exit(239);
		}
		printTest(new int[] { 0, 0, 1 }, "Sample test");
		printTest(new int[] { 0, 0, 1, 0 }, "Sample test, answer is 0");
		printTest(new int[] { 0, 3, -1 }, "Sample test. Invalid z-function");
		printTest(new int[] { -1, -1, -1 }, "Sample test, answer is 2^n");
		printTest(new int[] { 0 }, "Min test");
		printTest(new int[] { -1 }, "Min test");
		printTest(new int[] { 0, -1, 5, 5, -1, -1, -1, 0 },
				"Hand test with answer 0");
		printTest(new int[] { 0, 3, 3, -1, 1 }, "Hand test with answer 0");
		printTest(new int[] { 0, 2, 2, -1 }, "Hand test with answer 0");
		printTest(new int[] { 0, 4, 3, -1, -1, 1 },
				"Hand test with answer 0. Size of cycle > 3");
		for (int n : new int[] { 1000, 999, 30, 57, 300}) {
			int a[] = generateRandomSequence(n, -1, -1);
			printTest(a, String.format("all -1 of length %d", n));
		}
		for (int n : new int[] { 57, 64, 832, 300, 324, 239, 999, 1000 }) {
			int p = random.nextInt(20) + 50;
			int a[] = noise(generateRandomSequence(n, 1, 1), p);
			a[0] = 0;
			printTest(a, String.format("all 1 of length %d with noise", n));
		}
		for (int n : new int[] { 57, 64, 832, 300, 324, 239, 999, 1000 }) {
			int p = random.nextInt(20) + 50;
			int a[] = noise(generateRandomSequence(n, 0, 0), p);
			printTest(a, String.format("all 0 of length %d with noise", n));
		}
		for (int i = 0; i < 10; i++) {
			int n = random.nextInt(10) + 5;
			int a[] = generateRandomSequence2(n);
			a[0] = -1;
			printTest(a, "Small random test with noise");
		}
		for (int i = 0; i < 10; i++) {
			int n = random.nextInt(10) + 10;
			int p = random.nextInt(15) + 40;
			int a[] = generateRandomSequence(n, 0, 1);
			int z[] = noise(calcZ(a), p);
			printTest(z, "Z-function for small random sequence with noise");
		}
		for (int i = 0; i < 10; i++) {
			int n = random.nextInt(10) + 10;
			int p = random.nextInt(15) + 40;
			int a[] = generateRandomSequence(n, 0, 1);
			int z[] = noise(calcZ(a), p);
			z[0] = random.nextInt(n) + 1;
			printTest(z, "Z-function for small random sequence with noise, z[0] is spoiled");
		}
		for (int i = 0; i < 5; i++) {
			int n = random.nextInt(200) + 800;
			int a[] = generateRandomSequence2(n);
			a[0] = 0;
			printTest(a, "Big random test with noise");
		}
		for (int n : new int[] { 57, 239, 998, 999, 1000 }) {
			int p = random.nextInt(50) + 30;
			int a[] = noise(generateReversed(n), p);
			a[0] = 0;
			printTest(a, String.format(
					"Reversed permutation of size %d with noise", n));
		}
		for (int n : new int[] { 57, 239, 998, 999, 1000 }) {
			int p = random.nextInt(50) + 30;
			int a[] = noise(generateAlmostIdentity(n), p);
			a[0] = 0;
			printTest(a, String.format(
					"Almost identity permutation of size %d with noise", n));
		}
		for (int n : new int[] { 57, 239, 300, 999, 1000 }) {
			int z[] = generateRandomCycle(n);
			printTest(z, String.format("Random cycle n = %d", n));
		}
		for (int n : new int[] { 57, 239, 300, 525, 839, 777, 757, 557, 999, 1000 }) {
			int z[] = generateSpecialBigCycle(n);
			printTest(z, String.format("Special big cycle n = %d", n));
		}
		for (int i = 0; i < 5; i++) {
			int n = random.nextInt(200) + 800;
			int p = random.nextInt(50) + 40;
			int a[] = generateRandomSequence(n, 0, 1);
			int z[] = noise(calcZ(a), p);
			z[0] = 0;
			printTest(z, "Z-function for large random sequence with noise");
		}
		descFile.close();
	}

	private int[] generateSpecialBigCycle(int n) {
		int z[] = new int[n];
		Arrays.fill(z, -1);
		z[0] = 0;
		int start = n / 2;
		int cur = start;
		int add = 1;
		for (int i = 0; i < 6; i++) {
			z[add] = cur;
			cur += add;
			add++;
		}
		z[cur - start] = start;
		return z;
	}

	private int[] generateAlmostIdentity(int n) {
		int z[] = new int[n];
		for (int i = 0; i < n; i++) {
			z[i] = Math.min(i, n - i);
		}
		return z;
	}

	private int[] generateRandomCycle(int n) {
		int z[] = new int[n];
		boolean was[] = new boolean[n];
		Arrays.fill(z, -1);
		z[0] = 0;
		int start = random.nextInt(n - 1);
		was[start] = true;
		was[start + 1] = true;
		z[1] = start;
		int cur = start + 1;
		while (true) {
			ArrayList<Integer> possible = new ArrayList<Integer>();
			for (int i = 0; i < n; i++) {
				if (was[i] || z[Math.abs(cur - i)] != -1) {
					continue;
				}
				if (z[Math.abs(start - i)] == -1
						&& Math.abs(start - i) != Math.abs(cur - i)) {
					possible.add(i);
				}
			}
			if (possible.isEmpty()) {
				break;
			}
			int next = possible.get(random.nextInt(possible.size()));
			was[next] = true;
			if (cur < next) {
				z[next - cur] = cur;
			} else {
				z[cur - next] = next;
			}
			cur = next;
		}
		if (cur < start) {
			z[start - cur] = cur;
		} else {
			z[cur - start] = start;
		}
		return z;
	}

	private int[] generateRandomSequence2(int n) {
		int a[] = new int[n];
		a[0] = 0;
		for (int i = 1; i < n; i++) {
			a[i] = random.nextInt(n - i + 2) - 1;
		}
		return a;
	}

	private int[] generateReversed(int n) {
		int a[] = new int[n];
		a[0] = 0;
		for (int i = 1; i < n; i++) {
			a[i] = n - i;
		}
		return a;
	}

	private int[] generateThueMorse(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = Integer.bitCount(i) & 1;
		}
		return a;
	}

	private int[] calcZ(int[] a) {
		int z[] = new int[a.length];
		z[0] = 0;
		int l = 0;
		int r = 0;
		for (int i = 1; i < a.length; i++) {
			int j = 0;
			if (i <= r) {
				j = Math.min(r - i + 1, z[i - l]);
			}
			while (i + j < a.length && a[j] == a[i + j]) {
				j++;
			}
			if (i + j - 1 > r) {
				l = i;
				r = i + j - 1;
			}
			z[i] = j;
		}
		return z;
	}

	private void printTest(int[] a, String description) {
		++tests;
		String test = String.format("%02d", tests);
		System.out.println("Generating test " + test);
		try {
			PrintWriter out = new PrintWriter(TEST_PATH + "/" + test);
			out.println(a.length);
			for (int i = 0; i < a.length; i++) {
				if (i > 0) {
					out.print(" ");
				}
				out.print(a[i]);
			}
			out.println();
			out.close();
			descFile.println("Test " + test + " : " + description);
		} catch (FileNotFoundException e) {
			System.err.println("Can't generate test " + tests + " exception "
					+ e);
			System.exit(239);
		}

	}

	private int[] noise(int[] a, int p) {
		int res[] = new int[a.length];
		for (int i = 0; i < a.length; i++) {
			int q = random.nextInt(100);
			if (q < p) {
				res[i] = -1;
			}
		}
		return res;
	}

	private int[] generateRandomSequence(int n, int from, int to) {
		int res[] = new int[n];
		for (int i = 0; i < n; i++) {
			res[i] = random.nextInt(to - from + 1) + from;
		}
		return res;
	}

	public static void main(String[] args) {
		new TestGen().run();
	}

}
