package it.univr.di.cstnu.util;

import it.unimi.dsi.fastutil.objects.Object2IntAVLTreeMap;
import it.unimi.dsi.fastutil.objects.Object2IntMap;
import it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap;
import it.unimi.dsi.fastutil.objects.Object2IntSortedMap;
import it.univr.di.cstnu.graph.LabeledNode;
import it.univr.di.cstnu.graph.STNEdge;
import it.univr.di.cstnu.graph.STNEdgeInt;
import it.univr.di.cstnu.graph.TNGraph;
import org.junit.Before;
import org.junit.Test;

import java.util.Objects;

import static org.junit.Assert.*;

/**
 * Test for GraphAlgs class
 */
public class GraphAlgsTest {

	GraphDistances graphDistances;
	LabeledNode A, B, C, X, Y, W, Z, Ω;


	/**
	 *
	 */
	@Before
	public void setUp() {
		graphDistances = new GraphDistancesImpl();
		A = new LabeledNode("A");
		B = new LabeledNode("B");
		C = new LabeledNode("C");
		X = new LabeledNode("X");
		Y = new LabeledNode("Y");
		W = new LabeledNode("W");
		Z = new LabeledNode("Z");
		Ω = new LabeledNode("Ω");
	}

	/**
	 * @throws IllegalArgumentException if fails
	 */
	@Test
	public void testBellmanFord_PotentialInconsistent() throws IllegalArgumentException {
		graphDistances.putDistance(W, Y, 1);
		graphDistances.putDistance(W, Ω, 2);
		graphDistances.putDistance(W, Z, -2);//create a negative cycle
		graphDistances.putDistance(X, W, 1);
		graphDistances.putDistance(X, Y, 1);
		graphDistances.putDistance(X, Ω, 3);
		graphDistances.putDistance(Y, W, -1);
		graphDistances.putDistance(Y, Ω, 4);
		graphDistances.putDistance(Z, X, 1);
		assertEquals("""
		             {
		             ❮W❯ -> {❮Y❯=>1, ❮Z❯=>-2, ❮Ω❯=>2}
		             ❮X❯ -> {❮W❯=>1, ❮Y❯=>1, ❮Ω❯=>3}
		             ❮Y❯ -> {❮W❯=>-1, ❮Ω❯=>4}
		             ❮Z❯ -> {❮X❯=>1}
		             }""", graphDistances.toString());

		final Object2IntMap<LabeledNode> potential = GraphAlgs.GET_BellmanFord_Potential(graphDistances, null);
		assertNull(potential);
	}

	/**
	 * Dijkstra
	 */
	@Test
	public void testGET_SSSP_Dijkstra() {
		final TNGraph<STNEdge> graph = new TNGraph<>("testDijkstra", STNEdgeInt.class);
		graph.addVertex(W);
		graph.addVertex(X);
		graph.addVertex(Y);
		graph.addVertex(Z);
		STNEdge e = new STNEdgeInt("WΩ", -1);
		graph.addEdge(e, W, Ω);
		e = new STNEdgeInt("XW", -1);
		graph.addEdge(e, X, W);
		e = new STNEdgeInt("XY", 1);
		graph.addEdge(e, X, Y);
		e = new STNEdgeInt("XZ", 2);
		graph.addEdge(e, X, Z);
		e = new STNEdgeInt("YΩ", 0);
		graph.addEdge(e, Y, Ω);
		e = new STNEdgeInt("ZΩ", 3);
		graph.addEdge(e, Z, Ω);
		assertNull(GraphAlgs.GET_SSSP_Dijkstra(graph, X, null));
		Objects.requireNonNull(graph.findEdge(W, Ω)).setValue(1);
		final Object2IntSortedMap<LabeledNode> result = new Object2IntAVLTreeMap<>(GraphAlgs.GET_SSSP_Dijkstra(graph, X, null));
		assertEquals("{❮W❯=>-1, ❮X❯=>0, ❮Y❯=>1, ❮Z❯=>2, ❮Ω❯=>0}", result.toString());
	}

	/**
	 *
	 */
	@Test
	public void testGET_SSSP_DijkstraGraphDistances() {
		graphDistances.putDistance(W, Ω, 1);
		graphDistances.putDistance(X, W, 2);
		graphDistances.putDistance(X, Y, 1);
		graphDistances.putDistance(X, Z, 2);
		graphDistances.putDistance(Y, Ω, 0);
		graphDistances.putDistance(Z, Y, 0);
		graphDistances.putDistance(Z, Ω, 3);
		assertEquals("""
		             {
		             ❮W❯ -> {❮Ω❯=>1}
		             ❮X❯ -> {❮W❯=>2, ❮Y❯=>1, ❮Z❯=>2}
		             ❮Y❯ -> {❮Ω❯=>0}
		             ❮Z❯ -> {❮Y❯=>0, ❮Ω❯=>3}
		             }""", graphDistances.toString());
		final boolean result = GraphAlgs.GET_SSSP_Dijkstra(graphDistances, X, null);
		assertTrue(result);
		assertEquals("{❮W❯=>2, ❮Y❯=>1, ❮Z❯=>2, ❮Ω❯=>1}", new Object2IntAVLTreeMap<LabeledNode>(graphDistances.getReachable(X)).toString());
	}

	/**
	 * @throws IllegalArgumentException if fails
	 */
	@Test
	public void testJohnson() throws IllegalArgumentException {
		graphDistances.putDistance(W, Y, 1);
		graphDistances.putDistance(W, Ω, 2);
		graphDistances.putDistance(W, Z, -1);
		graphDistances.putDistance(X, W, 1);
		graphDistances.putDistance(X, Y, 1);
		graphDistances.putDistance(X, Ω, 3);
		graphDistances.putDistance(Y, W, -1);
		graphDistances.putDistance(Y, Ω, 4);
		graphDistances.putDistance(Z, X, 1);
		assertEquals("""
		             {
		             ❮W❯ -> {❮Y❯=>1, ❮Z❯=>-1, ❮Ω❯=>2}
		             ❮X❯ -> {❮W❯=>1, ❮Y❯=>1, ❮Ω❯=>3}
		             ❮Y❯ -> {❮W❯=>-1, ❮Ω❯=>4}
		             ❮Z❯ -> {❮X❯=>1}
		             }""", graphDistances.toString());

		final Object2IntMap<LabeledNode> potential = GraphAlgs.GET_BellmanFord_Potential(graphDistances, null);
		assert potential != null;
		assertEquals(1, potential.getInt(W));
		assertEquals(0, potential.getInt(Z));
		final GraphDistances finalG = GraphAlgs.APSP_Johnson(graphDistances, potential);
		assert finalG != null;
		assertEquals(finalG, graphDistances);
		assertEquals("""
		             {
		             ❮W❯ -> {❮W❯=>0, ❮X❯=>0, ❮Y❯=>1, ❮Z❯=>-1, ❮Ω❯=>2}
		             ❮X❯ -> {❮W❯=>0, ❮X❯=>0, ❮Y❯=>1, ❮Z❯=>-1, ❮Ω❯=>2}
		             ❮Y❯ -> {❮W❯=>-1, ❮X❯=>-1, ❮Y❯=>0, ❮Z❯=>-2, ❮Ω❯=>1}
		             ❮Z❯ -> {❮W❯=>1, ❮X❯=>1, ❮Y❯=>2, ❮Z❯=>0, ❮Ω❯=>3}
		             }""", finalG.toString());
	}

	/**
	 * @throws IllegalArgumentException if fails
	 */
	@Test
	public void testJohnson1() throws IllegalArgumentException {
		graphDistances.putDistance(W, Y, 1);
		graphDistances.putDistance(W, Ω, 2);
		graphDistances.putDistance(W, Z, -1);
		graphDistances.putDistance(X, W, 1);
		graphDistances.putDistance(X, Y, 1);
		graphDistances.putDistance(X, Ω, 3);
		graphDistances.putDistance(Y, W, -1);
		graphDistances.putDistance(Y, Ω, 4);
		graphDistances.putDistance(Z, X, 1);
		assertEquals("""
		             {
		             ❮W❯ -> {❮Y❯=>1, ❮Z❯=>-1, ❮Ω❯=>2}
		             ❮X❯ -> {❮W❯=>1, ❮Y❯=>1, ❮Ω❯=>3}
		             ❮Y❯ -> {❮W❯=>-1, ❮Ω❯=>4}
		             ❮Z❯ -> {❮X❯=>1}
		             }""", graphDistances.toString());

		final Object2IntMap<LabeledNode> potential = GraphAlgs.GET_BellmanFord_Potential(graphDistances, null);
		assert potential != null;
		assertEquals(1, potential.getInt(W));
		assertEquals(0, potential.getInt(Z));
		final GraphDistances finalG = GraphAlgs.APSP_Johnson(graphDistances, potential);
		assert finalG != null;
		assertEquals("""
		             {
		             ❮W❯ -> {❮W❯=>0, ❮X❯=>0, ❮Y❯=>1, ❮Z❯=>-1, ❮Ω❯=>2}
		             ❮X❯ -> {❮W❯=>0, ❮X❯=>0, ❮Y❯=>1, ❮Z❯=>-1, ❮Ω❯=>2}
		             ❮Y❯ -> {❮W❯=>-1, ❮X❯=>-1, ❮Y❯=>0, ❮Z❯=>-2, ❮Ω❯=>1}
		             ❮Z❯ -> {❮W❯=>1, ❮X❯=>1, ❮Y❯=>2, ❮Z❯=>0, ❮Ω❯=>3}
		             }""", finalG.toString());
	}

	/**
	 * Tests {@link GraphAlgs#UPDATE_DISTANCES(GraphDistances, Object2IntMap, LabeledNode)}
	 */
	@Test
	public void updateDistancesTest() {
		final LabeledNode S = new LabeledNode("S");
		final LabeledNode T = new LabeledNode("T");
		graphDistances.putDistance(W, X, -2);
		graphDistances.putDistance(X, W, 4);
		graphDistances.putDistance(X, Y, 0);
		graphDistances.putDistance(T, W, -2);
		graphDistances.putDistance(Y, S, 4);
		graphDistances.putDistance(S, Y, -3);
		graphDistances.putDistance(T, S, -2);

		assertEquals("""
		             {
		             ❮S❯ -> {❮Y❯=>-3}
		             ❮T❯ -> {❮S❯=>-2, ❮W❯=>-2}
		             ❮W❯ -> {❮X❯=>-2}
		             ❮X❯ -> {❮W❯=>4, ❮Y❯=>0}
		             ❮Y❯ -> {❮S❯=>4}
		             }""", graphDistances.toString());
		final GraphDistances apsp = GraphAlgs.APSP_Johnson(graphDistances, null);
		assert apsp != null;
		assertEquals("""
		             {
		             ❮S❯ -> {❮Y❯=>-3}
		             ❮T❯ -> {❮S❯=>-2, ❮W❯=>-2, ❮X❯=>-4, ❮Y❯=>-5}
		             ❮W❯ -> {❮S❯=>2, ❮X❯=>-2, ❮Y❯=>-2}
		             ❮X❯ -> {❮S❯=>4, ❮W❯=>4, ❮Y❯=>0}
		             ❮Y❯ -> {❮S❯=>4}
		             }""", apsp.toString());
		final Object2IntMap<LabeledNode> potential = GraphAlgs.GET_BellmanFord_Potential(apsp, null);
		assert potential != null;
		final Object2IntMap<LabeledNode> expectedPotential = new Object2IntOpenHashMap<>();
		expectedPotential.put(T, 5);
		expectedPotential.put(S, 3);
		expectedPotential.put(W, 2);
		expectedPotential.put(X, 0);
		expectedPotential.put(Y, 0);
		assertEquals(expectedPotential, potential);
		apsp.putDistance(X, Y, -2);
		GraphAlgs.UPDATE_DISTANCES(apsp, potential, X);
		assertEquals("""
		             {
		             ❮S❯ -> {❮Y❯=>-3}
		             ❮T❯ -> {❮S❯=>-2, ❮W❯=>-2, ❮X❯=>-4, ❮Y❯=>-5}
		             ❮W❯ -> {❮S❯=>2, ❮X❯=>-2, ❮Y❯=>-2}
		             ❮X❯ -> {❮S❯=>2, ❮W❯=>4, ❮Y❯=>-2}
		             ❮Y❯ -> {❮S❯=>4}
		             }""", apsp.toString());
	}


}