package algs42;

import java.util.Iterator;
import java.util.LinkedList;
import algs13.Queue;
import stdlib.*;

public class MyEuler {
	// local copy of the graph
	private Queue<Integer>[] adj;
	private int E;
	private boolean isEulerian = true;

	@SuppressWarnings("unchecked")
	public MyEuler(Digraph G) {
		// create local copy of graph
		adj = new Queue[G.V()];
		for (int v = 0; v < G.V(); v++) {
			adj[v] = new Queue<>();
			for (int w : G.adj(v))
				adj[v].enqueue(w);
		}
		// get initial number of edges
		E = G.E ();
		if (E == 0) {
			isEulerian = true;
			return;
		}
		// find starting vertex with at least one edge
		int s = 0;
		while (adj[s].isEmpty ())
			s++;

		// TODO
	}
	public Iterable<Integer> tour() {
		// TODO
		return null;
	}
	public boolean isEulerian() {
		return isEulerian;
	}

	public static boolean isTour(Digraph G, Iterable<Integer> tour) {
		@SuppressWarnings("unchecked")
		LinkedList<Integer>[] adj = new LinkedList[G.V()];
		int E = G.E ();
		for (int v = 0; v < G.V(); v++) {
			adj[v] = new LinkedList<>();
			for (int w : G.adj(v))
				adj[v].add(w);
		}
		if (tour == null)
			return E == 0;
		Iterator<Integer> it = tour.iterator ();
		if (!it.hasNext())
			return E == 0;
		int s = it.next();
		int v = s;
		while (it.hasNext()) {
			int w = it.next();
			if (adj[v].contains(w)) {
				adj[v].remove((Integer) w);
				E--;
				v = w;
			} else {
				throw new Error();
			}
		}
		if (v != s) throw new Error();
		if (E != 0) throw new Error();
		return (v == s) && (E == 0);
	}

	public static Digraph inOutEqual (int V, int E) {
		// random graph of V vertices and approximately E edges
		// with indegree[v] = outdegree[v] for all vertices
		Digraph G = new Digraph(V);
		int[] indegree  = new int[V];
		int[] outdegree = new int[V];
		int deficit = 0;
		for (int i = 0; i < E - deficit/2; i++) {
			int v = StdRandom.uniform(V);
			int w = StdRandom.uniform(V);
			if (v == w) { i--; continue; }
			G.addEdge(v, w);
			if (outdegree[v] >= indegree[v]) deficit++;
			else                             deficit--;
			outdegree[v]++;
			if (indegree[w] >= outdegree[w]) deficit++;
			else                             deficit--;
			indegree[w]++;
		}
		while (deficit > 0) {
			int v = StdRandom.uniform(V);
			int w = StdRandom.uniform(V);
			if (v == w) continue;
			if (outdegree[v] >= indegree[v]) continue;
			if (indegree[w]  >= outdegree[w]) continue;
			G.addEdge(v, w);
			if (outdegree[v] >= indegree[v]) deficit++;
			else                             deficit--;
			outdegree[v]++;
			if (indegree[w] >= outdegree[w]) deficit++;
			else                             deficit--;
			indegree[w]++;
		}
		return G;
	}
	public static void main(String[] args) {
		//args = new String[] { "data/tinyDG.txt" }; // NO
		//args = new String[] { "data/tinyCG.txt" }; // NO
		//args = new String[] { "data/tinyDGeuler9.txt" }; // YES
		//args = new String[] { "data/tinyDGeuler2.txt" }; // YES
		//args = new String[] { "data/tinyDGeuler3.txt" }; // YES
		//args = new String[] { "data/tinyDGeuler4.txt" }; // YES
		//args = new String[] { "data/tinyDGeuler5.txt" }; // NO
		//args = new String[] { "data/tinyDGeuler6.txt" }; // YES
		//args = new String[] { "data/tinyDGeuler7.txt" }; // NO
		//args = new String[] { "data/tinyDGeuler8.txt" }; // YES
		//args = new String[] { "data/tinyDGeuler9.txt" }; // YES
		args = new String[] { "20", "40" };

		Digraph G;
		if (args.length == 1) {
			In in = new In(args[0]);
			G = DigraphGenerator.fromIn(in);
		} else {
			int V = Integer.parseInt(args[0]);
			int E = Integer.parseInt(args[1]);
			while (true) {
				G = inOutEqual(V,E);
				if (new KosarajuSharirSCC(G).count () == 1)
					break;
			}
		}
		StdOut.println(G);
		YEuler euler0 = new YEuler(G, 1);
		if (euler0.isEulerian()) {
			for (int v : euler0.tour())
				StdOut.print(v + " ");
			StdOut.println();
		} else {
			StdOut.println("Not eulerian");
		}
		if (!isTour(G,euler0.tour())) StdOut.println("Not a tour");
		YEuler euler1 = new YEuler(G, 2);
		if (euler1.isEulerian()) {
			for (int v : euler1.tour())
				StdOut.print(v + " ");
			StdOut.println();
		} else {
			StdOut.println("Not eulerian");
		}
		if (!isTour(G,euler1.tour())) StdOut.println("Not a tour");
	}
}