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");
  }
}