// SPDX-FileCopyrightText: 2025 <Ian Valentin Christensen stud-ianc@ruc.dk>
// SPDX-FileCopyrightText: 2025 Jonas Smedegaard <dr@jones.dk>
// SPDX-License-Identifier: GPL-3.0-or-later

package dk.biks.bachelorizer;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.HashMap;
import java.util.Map;
import java.util.List;
import java.util.Random;
import java.util.Set;
import java.util.stream.Collectors;

import com.example.portfolio3.AdjListGraph;
import com.example.portfolio3.AbstractGraph;
import com.example.portfolio3.GraphAlgorithms;
import com.example.portfolio3.MatrixGraph;
import com.example.portfolio3.Vertex;

/// Bachelorizer - database model
///
/// Slurps and parses data from upstream-provided comma-separated file.
///
/// @version 0.0.1
/// @see <https://moodle.ruc.dk/mod/assign/view.php?id=523186>
public final class Graph extends Storage {

	/// amount of iterations in demo
	private static final int DEMO_ITERATIONS = 1000000;

	/// path to source file for graph
	private String path = "combi.txt";

	/// data about combinations as a Graph
	private AbstractGraph g;

	/// Default constructor
	// to silence javadoc
	private Graph() {}

	/// constructor with custom file source
	///
	/// @param path  path to source file for graph
	private Graph(final String path) {
		this.path = path;
	}

	/// JVM entry point
	///
	/// @param args  command-line arguments
	public static void main(final String[] args) {
		Graph g;

		// first argument, if provided, is the data file path;
		// else use upstream named file in current directory.
		g = (args.length > 0)
			? new Graph(args[0])
			: new Graph();

		g.initialize();
		g.demo();
	}

	/// load graph from file
	void initialize() {

		// read into temporary graph to resolve vertice count
		//
		// use Adjacency List Representation:
		//  * cheap to bootstrap (done once)
		//  * simple to count vertices (done once): O(1)
		AbstractGraph _g = new AdjListGraph();
		GraphAlgorithms.readGraph(_g, path);
		Integer _vertice_count = _g.vertices().size();

		// read into final graph
		//
		// use Adjacency Matrix Representation:
		//  * expensive to bootstrap (done once)
		//    * simple to add edges but needs vertice count
		//  * simple to get edges (done repeatedly): O(1)
		//
		// TODO: avoid reading and parsing file twice
		g = new MatrixGraph(_vertice_count);
		GraphAlgorithms.readGraph(g, path);
	}

	/// check that a graph is connected
	///
	/// If check fails, throw an unchecked exception,
	/// since it occurs at runtime and is unrecoverable.
	///
	/// Time complexity of the operation is O(n²)
	/// where n is the amount of vertices,
	/// since visitDepthFirst() recurses out-edges of all vertices.
	///
	/// @throws   IllegalArgumentException
	/// https://docs.oracle.com/javase/tutorial/essential/exceptions/runtime.html
	public void assertConnected() {

		// collect all vertices in the graph
		Collection<Vertex> c = g.vertices();

		// pick a random vertice in the graph
		Vertex v = g.vertices().iterator().next();

		// collect the set of visitable vertices
		Set<Vertex> visited = GraphAlgorithms.visitDepthFirst(
			g, v);

		// throw exception if not all vertices were visited
		if (visited.size() != c.size()) {
			throw new IllegalArgumentException(
				"graph is not connected");
		}
	}

	/// sets of disjoint choices
	///
	/// @return   list of disjoint sets
	public ArrayList<Set<Vertex>> disjoint() {

		// get all subject modules
		//
		// TODO: optionally seed this, to enable ranking control
		List<Vertex> modules = new ArrayList<>(g.vertices());
		long seed = System.currentTimeMillis();
		Random random = new Random(seed);
		System.out.println(
			"Seed used for shuffling modules: " + seed);
		Collections.shuffle(modules, random);

		return disjoint(modules);
	}

	/// groups of disjoint choices seeded by priority list of choices
	///
	/// @param vip  Ordered list of subject modules to prioritize
	/// @return     List of sets of disjoint choices
	public ArrayList<Set<Vertex>> disjoint(final List<Vertex> vip) {
		ArrayList<Set<Vertex>> sets = new ArrayList<>();

		// track done subject modules as extendable set
		//
		// HashList used for efficient addition and lookup
		Set<Vertex> done = new HashSet<>();

		// convert module list to a set
		//
		// defined once outside loop as a slight optimization
		Set<Vertex> all_set = new HashSet<>(vip);

		// iterate over subject modules
		for (Vertex current : vip) {

			if (done.contains(current)) {
				continue;
			}

			// add set of current and any unconnected modules
			Set<Vertex> isolated = new HashSet<>();
			isolated.add(current);
			for (Vertex compared: vip) {

				// skip if already done
				if (compared.equals(current)
					|| done.contains(compared)) {
					continue;
				}

				if (isolated.stream().allMatch(u ->
					g.getWeight(u,compared) == null)
				) {
					isolated.add(compared);
				}
			}

			// add as set and omit from future iterations
			sets.add(isolated);
			done.addAll(isolated);
		}

		return sets;
	}

	/// sum of students' selections as a graph
	///
	/// @param sets  list of disjoint choices
	/// @return      groups of disjoint choices as a graph
	private AbstractGraph moduleGroups(
		final ArrayList<Set<Vertex>> sets
	) {
		AbstractGraph h = new AdjListGraph();
		Map<Set<Vertex>, String> groupLabel = new HashMap<>();
		for (Set<Vertex> groupSet : sets) {

			// stringify each group of module selections
			String name = groupSet.stream()
				.map(Vertex::toString)

				// avoid differently sorted duplicates
				.sorted()

				// formatting of groups as vertices
				.collect(Collectors.joining(
					", ", "{", "}"));

			// map group to name of group
			groupLabel.put(groupSet, name);
		}

		for (Set<Vertex> s: sets) {
			for (Set<Vertex> t: sets) {
				if (t == s) {
					continue;
				}

				// process each pair only once
				if (s.hashCode() > t.hashCode()) {
					continue;
				}

				// accumulate student count across set
				int sum = 0;
				for (Vertex v: s) {
					// students with this choice
					for (Vertex w: t) {
						Integer weight =
						  g.getWeight(v, w);
						if (weight != null) {
							sum += weight;
						}
					}
				}
				// ensure h is treated as undirected
				h.insertEdge(
					groupLabel.get(s),
					groupLabel.get(t),
					sum);
				h.insertEdge(
					groupLabel.get(t),
					groupLabel.get(s),
					sum);
			}
		}
		return h;
	}

	/// loop through random combinations of sets of modules
	///
	/// @param g  sets of disjoint choices as a graph
	/// @return   best path among many random ones
	private static long[] solveManyTimes(final AbstractGraph g) {
		// number higher than total students
		long[] bestSolution = solve(g);
		for (int i = 1; i < DEMO_ITERATIONS; i++) {
			long[] solution = solve(g);
			if (solution[0] < bestSolution[0]) {
				// store shortest path
				bestSolution = solution;
			}
		}
		return bestSolution;
	}

	/// find total weight of random path through disjoint choice sets
	///
	/// @param g  sets of disjoint choices as a graph
	/// @return   total weight of random path and its seed as array
	private static long[] solve(final AbstractGraph g) {

		/// parameters for solution
		long[] solution = new long[] {0, 0};

		List<Vertex> path = new ArrayList<>(g.vertices());
		solution[1] = System.currentTimeMillis();
		Random random = new Random(solution[1]);

		// order of list contents becomes path order
		Collections.shuffle(path, random);

		for (int i = 0; i < path.size() - 1; i++) {
			solution[0] += g.getWeight(
				path.get(i), path.get(i + 1));
		}
		return solution;
	}

	/// Demo function to solve assignment
	private void demo() {

		System.out.println("\n\nGraph of choices constructed:");
		GraphAlgorithms.printGraph(g);

		// ensure the graph is connected
		assertConnected();
		System.out.println(
			"\n\nGraph is connected"
			  + " (otherwise an exception was thrown)");

		// collect disjoint choice sets
		ArrayList<Set<Vertex>> s = disjoint();
		System.out.printf(
			"\n\n%d disjoint choice sets collected:\n",
			s.size());
		for (Set<Vertex> verticeSet: s) {
			System.out.print(
				"set(" + verticeSet.size() + "):");
			for (Vertex v: GraphAlgorithms.sortVertex(
				verticeSet)
			) {
				System.out.print(" " + v.toString());
			}
			System.out.println();
		}

		// construct graph of disjoint choices
		AbstractGraph h = moduleGroups(s);
		System.out.println(
			"\n\nGraph of disjoint choices constructed:");
		GraphAlgorithms.printGraph(h);

		// find path through disjoint choice graph
		long[] solution = solveManyTimes(h);
		System.out.printf(
			"\n\nSolution with disjoint choices found: "
			+ "%d (disjoint shuffle seed: %d)%n",
			solution[0], solution[1]);
	}
}