// 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.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 {

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

	/// Default constructor
	///
	/// @param path  path to data file
	private Graph(final String path) {

		// 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
		AbstractGraph g = new MatrixGraph(_vertice_count);
		GraphAlgorithms.readGraph(g, path);

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

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

		// collect disjoint choice sets
		ArrayList<Set<Vertex>> s = disjoint(g);
		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, g);
		System.out.println(
			"\n\nGraph of disjoint choices constructed:");
		GraphAlgorithms.printGraph(h);

		// find path through disjoint choice graph
		System.out.print(
			"\n\nSolution with disjoint choices found: ");
		System.out.println(
			goodSolution(h));

		// release temporary variables for garbage collection
		_g = null;
		_vertice_count = null;
	}

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

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

		Graph combi = new Graph(path);
	}

	/// utility function to 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.
	///
	/// @param g  Graph to inspect
	/// @throws   IllegalArgumentException
	/// https://docs.oracle.com/javase/tutorial/essential/exceptions/runtime.html
	public static void assertConnected(final AbstractGraph g) {

		// 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
	///
	/// @param g  Graph to inspect
	/// @return   list of disjoint sets
	public static ArrayList<Set<Vertex>> disjoint(
		final AbstractGraph g
	) {

		// get all subject modules
		//
		// TODO: optionally seed this, to enable ranking control
		List<Vertex> modules = new ArrayList<>(g.vertices());
		Collections.shuffle(modules);

		return disjoint(g, modules);
	}

	/// groups of disjoint choices seeded by priority list of choices
	///
	/// @param g    Graph to inspect
	/// @param vip  Ordered list of subject modules to prioritize
	/// @return     List of sets of disjoint choices
	public static ArrayList<Set<Vertex>> disjoint(
		final AbstractGraph g, 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
	/// @param g     choices as weights in graph
	/// @return      groups of disjoint choices as a graph
	public static AbstractGraph moduleGroups(
		final ArrayList<Set<Vertex>> sets, final AbstractGraph g
	) {
		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 out of a hundred shuffles
	public static int goodSolution(final AbstractGraph g) {
		// number higher than total students
		int bestPathCost = Integer.MAX_VALUE;
		for (int i = 0; i < 10000; i++) {
			int cost = solution(g);
			if (cost < bestPathCost) {
				// store shortest path
				bestPathCost = cost;
			}
		}
		return bestPathCost;
	}

	/// finds lengh of random path through disjoint module choices
	///
	/// @param g  sets of disjoint choices as a graph
	/// @return   weight of final random path
	private static int solution(final AbstractGraph g) {
		List<Vertex> path = new ArrayList<>(g.vertices());
		// order of list contents becomes path order
		Collections.shuffle(path);
		int cost = 0;
		for (int i = 0; i < path.size() - 1; i++) {
			// get weight between next vertices in module group graph
			cost += g.getWeight(path.get(i), path.get(i + 1));
		}
		return cost;
	}
}