package fr.uge.code.camp;

import static org.junit.jupiter.api.Assertions.*;

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.NoSuchFileException;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.time.Duration;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.HashSet;
import java.util.List;
import java.util.Optional;
import java.util.Set;

import org.junit.jupiter.api.MethodOrderer;
import org.junit.jupiter.api.Nested;
import org.junit.jupiter.api.Order;
import org.junit.jupiter.api.Test;
import org.junit.jupiter.api.TestMethodOrder;
import org.junit.jupiter.api.io.TempDir;

class Session7Test {

	private static Path ensureInProjectOrShares(String file) throws IOException {
		var path = Paths.get(file);
		if (Files.exists(path)) {
			return path;
		}
		// Same relative path, but under folder "/mnt/shares/..." instead of "data"
		var relative = Paths.get("").relativize(path);
		var fallback = Paths.get("/mnt/shares/igm/prof/pivoteau/JCC/Session7").resolve(relative);

		if (!Files.exists(fallback)) {
			throw new NoSuchFileException("Missing file in both locations: " + path + " and " + fallback);
		}
		return fallback;
	}

	@Nested
	@TestMethodOrder(MethodOrderer.OrderAnnotation.class)
	public final class Ex1Combinations {

		static long countCombinations(int k, int n) {
			if (k < 0 || n < 0 || k > n) {
				return 0;
			}
			k = Math.min(k, n - k);

			long result = 1;
			for (int i = 1; i <= k; i++) {
				result = result * (n - i + 1) / i;
			}
			return result;
		}

		@Test
		@Order(11)
		void testSlowCombinations() throws IOException {
			var path = ensureInProjectOrShares("data/combinations.data");
			for (var line : Files.readAllLines(path)) {
				var tokens = line.split(" ");
				assertTrue(tokens.length >= 2, "bad line in data/combinations.data: " + line);
				var n = Integer.parseInt(tokens[0]);
				var k = Integer.parseInt(tokens[1]);

				var expected = new HashSet<BitSet>();
				for (var index = 2; index < tokens.length; index++) {
					var combination = parseCombination(tokens[index], k, n);
					expected.add(combination);
				}

				var result = Session7.slowCombinations(k, n);
				assertEquals(expected, Set.copyOf(result));
			}
		}

		@Test
		@Order(12)
		void testSlowCombinationsSize() {
			for (int n = 0; n < 23; n++) {
				for (int k = 0; k <= n; k++) {
					var n0 = n;
					var k0 = k;
					var expected = countCombinations(k, n);
					var result = assertTimeoutPreemptively(Duration.ofMillis(3_000),
							() -> Session7.slowCombinations(k0, n0), "timeout for n = " + n + " and k = " + k);
					assertEquals(expected, result.size(), " for n = " + n + " and k = " + k);
				}
			}
		}

		private static BitSet parseCombination(String token, int k, int n) {
			var combination = new BitSet(n);
			if (token.equals("-")) {
				assertEquals(0, k, "bad combination in data/slow-combinations.data: " + token);
				return combination;
			}
			assertEquals(k, token.length(), "bad combination in data/slow-combinations.data: " + token);
			for (var index = 0; index < token.length(); index++) {
				var value = Character.digit(token.charAt(index), 10);
				assertTrue(value >= 0 && value < n, "bad combination in data/slow-combinations.data: " + token);
				assertFalse(combination.get(value), "bad combination in data/slow-combinations.data: " + token);
				combination.set(value);
			}
			return combination;
		}


		@Test
		@Order(13)
		void testCombinations() throws IOException {
			var path = ensureInProjectOrShares("data/combinations.data");
			for (var line : Files.readAllLines(path)) {
				var tokens = line.split(" ");
				assertTrue(tokens.length >= 2, "bad line in data/combinations.data: " + line);
				var n = Integer.parseInt(tokens[0]);
				var k = Integer.parseInt(tokens[1]);

				var expected = new HashSet<BitSet>();
				for (var index = 2; index < tokens.length; index++) {
					var combination = parseCombination(tokens[index], k, n);
					expected.add(combination);
				}

				var result = Session7.combinations(k, n);
				assertEquals(expected, Set.copyOf(result));
			}
		}
		
		@Test
		@Order(14)
		void testCombinationsSize() {
			for (int n = 0; n < 23; n++) {
				for (int k = 0; k <= n; k++) {
					var n0 = n;
					var k0 = k;
					var expected = countCombinations(k, n);
					var result = assertTimeoutPreemptively(Duration.ofMillis(500), () -> Session7.combinations(k0, n0),
							"timeout for n = " + n + " and k = " + k);
					assertEquals(expected, result.size(), " for n = " + n + " and k = " + k);
				}
			}
		}
	}

	@Nested
	@TestMethodOrder(MethodOrderer.OrderAnnotation.class)
	public final class Ex2Colors {

		private static boolean[][] readGraph(Path path) throws IOException {
			var lines = Files.readAllLines(path);
			var n = Integer.parseInt(lines.get(0));
			var graph = new boolean[n][n];

			for (var i = 0; i < n; i++) {
				var row = lines.get(i + 1).toCharArray();
				for (var j = 0; j < n; j++) {
					graph[i][j] = row[j] == '1';
				}
			}
			return graph;
		}

		private static Set<String> readExpectedColorings(Path path) throws IOException {
			return Set.copyOf(Files.readAllLines(path).stream().toList());
		}

		private static void assertMatchesOneExpectedColoring(Optional<int[]> result, Set<String> expected,
				String message) {
			if (expected.isEmpty()) {
				assertTrue(result.isEmpty(), message);
				return;
			}
			assertTrue(result.isPresent(), message + " - no coloring found");
			assertTrue(expected.contains(Arrays.toString(result.orElseThrow())), message);
		}

		@Test
		@Order(21)
		void testThreeColorsBruteForceFiles(@TempDir Path tempDir) throws IOException {
			Path dir = ensureInProjectOrShares("data/Colors");
			var files = Files.list(dir).filter(path -> path.toString().endsWith(".data")).sorted().toList();

			for (var dataPath : files) {
				var fileName = dataPath.getFileName().toString();
				if (fileName.startsWith("._")) {
					continue;
				}
				var outPath = dir.resolve(fileName.replace(".data", ".out"));
				var expected = readExpectedColorings(outPath);
				var graph = readGraph(dataPath);

				var result = assertTimeoutPreemptively(Duration.ofMillis(10_000),
						() -> Session7.threeColorsBruteForce(graph), "timeout with file " + dataPath);
				assertMatchesOneExpectedColoring(result, expected, "problem with file " + fileName);
			}
		}

		@Test
		@Order(22)
		void testThreeColorsFiles(@TempDir Path tempDir) throws IOException {
			Path dir = ensureInProjectOrShares("data/Colors");
			var files = Files.list(dir).filter(path -> path.toString().endsWith(".data")).sorted().toList();

			for (var dataPath : files) {
				var fileName = dataPath.getFileName().toString();
				if (fileName.startsWith("._")) {
					continue;
				}
				var outPath = dir.resolve(fileName.replace(".data", ".out"));
				var expected = readExpectedColorings(outPath);
				var graph = readGraph(dataPath);

				var result = assertTimeoutPreemptively(Duration.ofMillis(1_000), () -> Session7.threeColors(graph),
						"timeout with file " + dataPath);
				assertMatchesOneExpectedColoring(result, expected, "problem with file " + fileName);
			}
		}
	}

	@Nested
	@TestMethodOrder(MethodOrderer.OrderAnnotation.class)
	public final class Ex3Queens {

		@Test
		@Order(30)
		void testAllTuplesSize() {
			try {
				Session7.allTuples(1, 1);
			} catch (UnsupportedOperationException e) {
				return;
			}
			for (int n = 0; n < 5; n++) {
				for (int k = 0; k <= 6; k++) {
					var n0 = n;
					var k0 = k;
					var expected = Math.powExact(n0, k0);
					var result = assertTimeoutPreemptively(Duration.ofMillis(3_000), () -> Session7.allTuples(k0, n0),
							"timeout for n = " + n + " and k = " + k);
					assertEquals(expected, result.size(), "for allTuples(k, n), for n = " + n + " and k = " + k);
				}
			}
		}

		private static List<Integer> parseTuple(String token, int k, int n) {
			var tuple = new ArrayList<Integer>(k);
			for (var index = 0; index < token.length(); index++) {
				var value = Character.digit(token.charAt(index), 10);
				tuple.add(value);
			}
			return tuple;
		}

		@Test
		@Order(31)
		void testAllTuples() throws IOException {
			try {
				Session7.allTuples(1, 1);
			} catch (UnsupportedOperationException e) {
				return;
			}
			var path = ensureInProjectOrShares("data/all-tuples.data");
			for (var line : Files.readAllLines(path)) {
				var tokens = line.split(" ");
				assertTrue(tokens.length >= 2, "bad line in data/all-tuples.data: " + line);
				var n = Integer.parseInt(tokens[0]);
				var k = Integer.parseInt(tokens[1]);

				var expected = new HashSet<List<Integer>>();
				for (var index = 2; index < tokens.length; index++) {
					var tuple = parseTuple(tokens[index], k, n);
					assertTrue(expected.add(tuple), "duplicate tuple in data/all-tuples.data: " + tokens[index]);
				}

				var result = assertTimeoutPreemptively(Duration.ofMillis(3_000), () -> Session7.allTuples(k, n),
						"timeout for n = " + n + " and k = " + k);
				assertEquals(expected.size(), result.size(), "for allTuples(k, n), for n = " + n + " and k = " + k);
				assertEquals(expected, Set.copyOf(result), "for allTuples(k, n), for n = " + n + " and k = " + k);
			}
		}

		@Test
		@Order(32)
		void testAllPermutations() throws IOException {
			try {
				Session7.allPermutations(1);
			} catch (UnsupportedOperationException e) {
				return;
			}
			var path = ensureInProjectOrShares("data/all-permutations.data");
			for (var line : Files.readAllLines(path)) {
				var tokens = line.split(" ");
				assertTrue(tokens.length >= 1, "bad line in data/all-permutations.data: " + line);
				var n = Integer.parseInt(tokens[0]);

				var expected = new HashSet<List<Integer>>();
				for (var index = 1; index < tokens.length; index++) {
					var permutation = parseTuple(tokens[index], n, n);
					assertTrue(expected.add(permutation),
							"duplicate permutation in data/all-permutations.data: " + tokens[index]);
				}

				var result = assertTimeoutPreemptively(Duration.ofMillis(3_000), () -> Session7.allPermutations(n),
						"timeout for n = " + n);
				assertEquals(expected.size(), result.size(), "for allPermutations(n), for n = " + n);
				assertEquals(expected, Set.copyOf(result), "for allPermutations(n), for n = " + n);
			}
		}

		@Test
		@Order(33)
		void testQueensBruteForce(@TempDir Path tempDir) throws IOException {
			Path path = ensureInProjectOrShares("data/queens.data");

			for (var line : Files.readAllLines(path)) {
				var tmp = line.split(" ");

				var n = Integer.parseInt(tmp[0]);
				if (n >= 11) {
					break;
				}
				var expected = Integer.parseInt(tmp[1]);
				var result = assertTimeoutPreemptively(Duration.ofMillis(1_000), () -> Session7.nQueensBruteForce(n),
						"timeout for n = " + n);
				assertEquals(expected, result.size(), " for n = " + n);
			}
		}

		@Test
		@Order(34)
		void testQueensBactrack(@TempDir Path tempDir) throws IOException {
			Path path = ensureInProjectOrShares("data/queens.data");

			for (var line : Files.readAllLines(path)) {
				var tmp = line.split(" ");

				var n = Integer.parseInt(tmp[0]);
				if (n >= 14) {
					break;
				}
				var expected = Integer.parseInt(tmp[1]);
				var result = assertTimeoutPreemptively(Duration.ofMillis(3_000), () -> Session7.nQueens(n),
						"timeout for n = " + n);
				assertEquals(expected, result.size(), " for n = " + n);
			}
		}
	}
}