package graph;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

import uf.Elt;

// un graphe non orienté est représenté comme un graphe orienté
// avec l'invariant que x->y si et seulement si y->x

public class Undirected<V> extends Graph<V> {

  @Override
  public void addEdge(V x, V y) {
    super.addEdge(x, y);
    super.addEdge(y, x);
  }

  @Override
  public void removeEdge(V x, V y) {
    super.removeEdge(x, y);
    super.removeEdge(y, x);
  }

  // tous les arcs, une seule fois chacun (i.e. x->y mais pas y->x)
  public Set<Edge<V>> allEdges() {
    Set<Edge<V>> s = new HashSet<>();
    Set<V> seen = new HashSet<>();
    for (V u: this.vertices()) {
      for (V v: this.successors(u)) {
        if (seen.contains(v)) continue;
        s.add(new Edge<>(u, v));
      }
      seen.add(u); // on l'ajoute après, au cas où il y ait des boucles
    }
    return s;
  }
  
  // test d'acyclicité avec union-find
  public boolean isAcyclic() {
    if (this.vertices().isEmpty()) return true;
    // on construit les classes d'équivalence
    Map<V, Elt<V>> elt = new HashMap<>();
    for (V u: this.vertices())
      elt.put(u, new Elt<>(u));
    for (Edge<V> e: this.allEdges()) {
      Elt<V> es = elt.get(e.src), ed = elt.get(e.dst);
      if (es.find() == ed.find()) return false;
      es.union(ed);
    }
    return true;
  }    

  // test de connexité avec union-find
  public boolean isConnected() {
    if (this.vertices().isEmpty()) return true;
    // on construit les classes d'équivalence
    Map<V, Elt<V>> elt = new HashMap<>();
    for (V u: this.vertices())
      elt.put(u, new Elt<>(u));
    for (V u: this.vertices()) {
      Elt<V> eu = elt.get(u);
      for (V v: this.successors(u))
        eu.union(elt.get(v));
    }
    // puis on vérifie que tous les sommets sont dans la même classe
    V v0 = this.vertices().iterator().next();
    Elt<V> c0 = elt.get(v0);
    for (V u: this.vertices())
      if (elt.get(u).find() != c0)
        return false;
    return true;
  }    
  
  // composantes connexes, avec un parcours en profondeur
  public List<List<V>> components() {
    List<List<V>> r = new LinkedList<>();
    HashSet<V> visited = new HashSet<>();
    for (V v: this.vertices())
      if (!visited.contains(v)) {
        LinkedList<V> c = new LinkedList<>();
        componentsAux(visited, c, v);
        r.add(c);
      }
    return r;
  }
  
  private void componentsAux(HashSet<V> visited, LinkedList<V> c, V v) {
    Stack<V> stack = new Stack<V>();
    stack.push(v);
    while (!stack.isEmpty()) {
      v = stack.pop();
      if (visited.contains(v)) continue;
      visited.add(v);
      c.add(v);
      for (V w : this.successors(v))
        stack.push(w);
    }    
  }

  // composantes connexes d'un graphe non orienté
  // avec un parcours en profondeur
  public Map<V, Integer> numComponents() {
    Map<V, Integer> num = new HashMap<>();
    int nc = 0; // nombre de composantes
    for (V v: this.vertices())
      if (!num.containsKey(v))
        dfs(num, nc++, v);
    return num;
  }
  // parcours en profondeur à partir de v, en attribuant le numéro nc
  private void dfs(Map<V, Integer> num, int nc, V v) {
    if (num.containsKey(v)) return;
    num.put(v, nc);
    for (V w : this.successors(v))
      dfs(num, nc, w);
  }
  // ou sans récursivité
  private void numComponents(Map<V, Integer> num, int nc, V v) {
    Stack<V> stack = new Stack<V>();
    stack.push(v);
    while (!stack.isEmpty()) {
      v = stack.pop();
      if (num.containsKey(v)) continue;
      num.put(v, nc);
      for (V w : this.successors(v))
        stack.push(w);
    }    
  }

  public static Undirected<Integer> grid(int n, int m) {
    Undirected<Integer> g = new Undirected<>();
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++) {
        int v = m*i + j;
        g.addVertex(v);
        if (j < m-1) g.addEdge(v, v+1);
        if (i < n-1) g.addEdge(v, v+m);
      }
    return g;
  }
  
}

class TestUndirected {

  public static void main(String[] args) {
    
  }

}