package com.example.portfolio3;

// origin: <https://moodle.ruc.dk/course/section.php?id=211877>

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/// foo
public class GraphAlgorithms {

	/// foo
	GraphAlgorithms() { }

	/// calculate the length of a path or another collection of edges
	///
	/// does not require the edges to form a path
	///
	/// @param edges  foo
	/// @return int
	public static int pathLength(final Collection<Edge> edges) {
		return edges.stream().mapToInt(e -> e.weight()).sum();
	}

	/// checks whether a list of edges form a path so that
	///
	/// the to-vertex in one edge is the from-vertex of the next
	///
	/// @param edges  foo
	/// @return       boolean
	public static boolean isPath(final List<Edge> edges) {
		for (int i = 1; i < edges.size(); i++) {
			if (edges.get(i - 1).to() != edges.get(i).from()
			) {
				return false;
			}
		}

		return true;
	}

	/// Calculates the length of a path vertices in a graph
	///
	/// return null if vertices are not connected as a path
	///
	/// @param g     foo
	/// @param path  foo
	/// @return      Integer
	public static Integer pathLength(
		final Graph g, final List<Vertex> path
	) {
		int length = 0;
		for (int i = 1; i < path.size(); i++) {
			Integer w = g.getWeight(
				path.get(i - 1), path.get(i));
			if (w == null) {
				return null;
			}
			length += w;
		}

		return length;
	}

	//------------------------------------------------------------
	//
	// Comparators and sorting methods

	/// Comparator of edges based on weight
	///
	/// can be used for sorting a list of edges
	///
	/// @param e1  foo
	/// @param e2  foo
	/// @return    int
	static int cmpEdgeWeight(final Edge e1, final Edge e2) {
		int w1 = e1.weight();
		int w2 = e2.weight();
		if (w1 != w2) {
			return w1 - w2;
		}
		if (e1.from() != e2.from()) {
			return e1.from().name().compareTo(
				e2.from().name());
		}

		return e1.to().name().compareTo(e2.to().name());
	}

	/// Comparator of edges based on from-vertex
	///
	/// can be used for sorting a list of edges
	///
	/// @param e1  foo
	/// @param e2  foo
	/// @return    int
	static int cmpEdgeFrom(final Edge e1, final Edge e2) {
		if (e1.from() != e2.from()) {
			return e1.from().name().compareTo(
				e2.from().name());
		}
		int w1 = e1.weight();
		int w2 = e2.weight();
		if (w1 != w2) {
			return w1 - w2;
		}

		return e1.to().name().compareTo(e2.to().name());
	}

	/// Comparator of edges based on from-vertex
	///
	/// can be used for sorting a list of edges
	///
	/// @param e1  foo
	/// @param e2  foo
	/// @return    int
	static int cmpEdgeTo(final Edge e1, final Edge e2) {
		if (e1.to() != e2.to()) {
			return e1.to().name().compareTo(
				e2.to().name());
		}
		if (e1.from() != e2.from()) {
			return e1.from().name().compareTo(
				e2.from().name());
		}
		int w1 = e1.weight();
		int w2 = e2.weight();

		return w1 - w2;
	}

	/// sort a collection of edges based on their weights
	///
	/// @param edges  foo
	/// @return       List<Edge>
	static List<Edge> sortEdges(final Collection<Edge> edges) {
		ArrayList<Edge> list = new ArrayList<>(edges);
		Collections.sort(list, GraphAlgorithms::cmpEdgeWeight);

		return list;
	}

	/// sort a collection of edges based on from-vertex
	///
	/// @param edges  foo
	/// @return       List<Edge>
	static List<Edge> sortEdgesFrom(final Collection<Edge> edges) {
		ArrayList<Edge> list = new ArrayList<>(edges);
		Collections.sort(list, GraphAlgorithms::cmpEdgeFrom);

		return list;
	}

	/// sort a collection of edges based on to-vertex
	///
	/// @param edges  foo
	/// @return       List<Edge>
	static List<Edge> sortEdgesTo(final Collection<Edge> edges) {
		ArrayList<Edge> list = new ArrayList<>(edges);
		Collections.sort(list, GraphAlgorithms::cmpEdgeTo);

		return list;
	}

	/// sort a collection of vertices based on their name
	///
	/// @param vertices  foo
	/// @return          List<Vertex>
	public static List<Vertex> sortVertex(
		final Collection<Vertex> vertices
	) {
		ArrayList<Vertex> list = new ArrayList<>(vertices);
		Collections.sort(list, (Vertex v1, Vertex v2) ->
			v1.name().compareTo(v2.name()));

		return list;
	}

	//------------------------------------------------------------
	//
	// Algorithms for traverse and minimum spanning tree

	/// traverse a graph depth first from a given vertex
	/// return the set of visited vertices
	///
	/// @param g  foo
	/// @param v  foo
	/// @return   Set<Vertex>
	public static Set<Vertex> visitBreadthFirst(
		final Graph g, final Vertex v
	) {
		HashSet<Vertex> thisLevel = new HashSet<>();
		HashSet<Vertex> nextLevel = new HashSet<>();
		HashSet<Vertex> visited = new HashSet<>();
		thisLevel.add(v);
		while (thisLevel.size() > 0) {
			System.out.println("level " + thisLevel);
			for (Vertex w:thisLevel) {
				//System.out.println("visited " + w);
				visited.add(w);
				Collection<Edge> outedge = g.outEdge(w);
				if (outedge == null) {
					continue;
				}
				for (Edge e: outedge) {
					if (visited.contains(e.to())) {
						continue;
					}
					if (thisLevel.contains(e.to())) {
						continue;
					}
					nextLevel.add(e.to());
				}
			}
			thisLevel = nextLevel;
			nextLevel = new HashSet<Vertex>();
		}

		return visited;
	}

	/// traverse a graph depth first from a given vertex
	/// return the set of visited vertices
	///
	/// @param g  foo
	/// @param v  foo
	/// @return   Set<Vertex>
	public static Set<Vertex> visitDepthFirst(
		final Graph g, final Vertex v
	) {
		HashSet<Vertex> visit = new HashSet<>();
		visitDepthFirst(g, v, visit);

		return visit;
	}

	/// foo
	///
	/// @param g        foo
	/// @param v        foo
	/// @param visited  foo
	private static void visitDepthFirst(
		final Graph g, final Vertex v, final Set<Vertex> visited
	) {
		if (visited.contains(v)) {
			return;
		}
		//System.out.println("visited "+v);
		visited.add(v);
		for (Edge e: g.outEdge(v)) {
			visitDepthFirst(g, e.to(), visited);
		}
	}

	/// an implementation of Prim's algorithm
	///
	/// naive implementation without priorityqueue
	///
	/// @param g  foo
	/// @return   Set<Edge>
	public static Set<Edge> minimumSpanningTree(final Graph g) {
		Collection<Edge> edges = g.edges();
		HashSet<Edge> mst = new HashSet<>();
		HashSet<Vertex> frontier = new HashSet<>();
		for (Edge e:edges) {
			frontier.add(e.from());
			break;
		}
		while (true) {
			Edge nearest = null;
			for (Edge e: edges) {
				if (!frontier.contains(e.from())) {
					continue;
				}
				if (frontier.contains(e.to())) {
					continue;
				}
				if (nearest == null
					|| nearest.weight() > e.weight()
				) {
					nearest = e;
				}
			}
			if (nearest == null) {
				break;
			}
			mst.add(nearest);
			frontier.add(nearest.to());
		}

		return mst;
	}

	/// returns the tree of shortest paths
	/// from start to all vertices in the graph
	///
	/// naive implementation without a prorityqueue
	///
	/// @param g      foo
	/// @param start  foo
	/// @return       Set<Edge>
	public static Set<Edge> dijkstra(
		final Graph g, final Vertex start
	) {

		// create table for done, prev and weight from start
		int maxint = Integer.MAX_VALUE;
		HashSet<Vertex> done = new HashSet<>();
		HashMap<Vertex, Edge> prev = new HashMap<>();
		HashMap<Vertex, Integer> weight = new HashMap<>();
		for (Vertex w: g.vertices()) {
			weight.put(w, maxint);
		}

		// start node is done, distance 0 from start
		weight.put(start, 0);
		done.add(start);

		while (true) {

			// find nearest from a done vertex
			Vertex nearest = null;
			int neardist = maxint;
			Edge done2near = null;
			for (Vertex w1:done) {
				for (Edge e :g.outEdge(w1)) {
					Vertex w2 = e.to();
					if (done.contains(w2)) {
						continue;
					}
					if ((weight.get(w1)
						+ e.weight())
						< neardist
					) {
						nearest = e.to();
						neardist = weight.get(w1)
							+ e.weight();
						done2near = e;
					}
				}
			}

			//System.out.println("find nearest "+done2near);
			// if no more, then we are done
			if (nearest == null) {
				break;
			}

			// update distance from this node to other nodes
			for (Edge e1 : g.outEdge(nearest)) {
				Vertex w3 = e1.to();
				int wght = e1.weight();
				if (weight.get(w3) > (neardist + wght)) {
					weight.put(w3, neardist + wght);
				}
			}
			done.add(nearest);
			prev.put(nearest, done2near);
			weight.put(nearest, neardist);
		}

		return new HashSet<Edge>(prev.values());
	}

	//------------------------------------------------------------
	//
	// IO operations

	/// read a comma-separated file
	/// in the format <vertex> , <vertex> , <weight>
	///
	/// stores file as bidirectional graph
	///
	/// @param g     foo
	/// @param file  foo
	public static void readGraph(final Graph g, final String file) {
		try {
			BufferedReader in = new BufferedReader(
				new FileReader(file));
			for (String line = in.readLine();
				line != null;
				line = in.readLine()
			) {
				if (line.length() == 0) {
					continue;
				}
				String[] arr = line.split(",");
				if (arr.length != 3) {
					throw new RuntimeException(
						"CSV file format error: "
						+ line);
				}
				g.insertEdge(arr[0].trim(),
					arr[1].trim(),
					Integer.parseInt(arr[2].trim()));
				g.insertEdge(arr[1].trim(),
					arr[0].trim(),
					Integer.parseInt(arr[2].trim()));
			}
			in.close();
		} catch (IOException e) {
			throw new RuntimeException(e);
		}
	}

	/// foo
	///
	/// @param g  foo
	public static void printGraph(final Graph g) {
		for (Vertex v: sortVertex(g.vertices())) {
			System.out.println(v.toString());
			for (Edge e: sortEdgesTo(g.outEdge(v))) {
				System.out.println("  " + e.toString());
			}
		}
	}

	/// store a list of lines as a file
	///
	/// @param list  foo
	/// @param f     foo
	public static void storeStrings(
		final List<String> list, final String f
	) {
		try {
			PrintWriter out = new PrintWriter(
				new FileWriter(f));
			for (String s: list) {
				out.println(s);
			}
			out.close();
		} catch (IOException e) {
			throw new RuntimeException(e);
		}
	}

	/// read a file a returns a list of lines
	///
	/// @param f  foo
	/// @return   ArrayList
	public static ArrayList<String> loadStrings(final String f) {
		ArrayList<String> list = new ArrayList<>();
		try {
			BufferedReader in = new BufferedReader(
				new FileReader(f));
			while (true) {
				String s = in.readLine();
				if (s == null) {
					break;
				}
				list.add(s);
			}
			in.close();
		} catch (IOException e) {
			throw new RuntimeException(e);
		}

		return list;
	}
}