package algs44;
import stdlib.*;
import java.util.Iterator;
import java.util.NoSuchElementException;
/* ***********************************************************************
 *  Compilation:  javac AdjMatrixEdgeWeightedDigraph.java
 *  Execution:    java AdjMatrixEdgeWeightedDigraph V E
 *  Dependencies: StdOut.java
 *
 *  An edge-weighted digraph, implemented using an adjacency matrix.
 *  Parallel edges are disallowed; self-loops are allowd.
 *
 *************************************************************************/

public class XAdjMatrixEdgeWeightedDigraph {
  private final int V;
  private int E;
  private final DirectedEdge[][] adj;

  // empty graph with V vertices
  public XAdjMatrixEdgeWeightedDigraph(int V) {
    if (V < 0) throw new Error("Number of vertices must be nonnegative");
    this.V = V;
    this.E = 0;
    this.adj = new DirectedEdge[V][V];
  }

  // random graph with V vertices and E edges
  public XAdjMatrixEdgeWeightedDigraph(int V, int E) {
    this(V);
    if (E < 0) throw new Error("Number of edges must be nonnegative");
    if (E > V*V) throw new Error("Too many edges");

    // can be inefficient
    while (this.E != E) {
      int v = (int) (V * Math.random());
      int w = (int) (V * Math.random());
      double weight = Math.round(100 * Math.random()) / 100.0;
      addEdge(new DirectedEdge(v, w, weight));
    }
  }

  // number of vertices and edges
  public int V() { return V; }
  public int E() { return E; }


  // add directed edge v->w
  public void addEdge(DirectedEdge e) {
    int v = e.from();
    int w = e.to();
    if (adj[v][w] == null) {
      E++;
      adj[v][w] = e;
    }
  }

  // return list of neighbors of v
  public Iterable<DirectedEdge> adj(int v) {
    return new AdjIterator(v);
  }

  // support iteration over graph vertices
  private class AdjIterator implements Iterator<DirectedEdge>, Iterable<DirectedEdge> {
    private final int v;
    private int w = 0;
    public AdjIterator(int v) { this.v = v; }

    public Iterator<DirectedEdge> iterator() { return this; }

    public boolean hasNext() {
      while (w < V) {
        if (adj[v][w] != null) return true;
        w++;
      }
      return false;
    }

    public DirectedEdge next() {
      if (hasNext()) { return adj[v][w++];                 }
      else           { throw new NoSuchElementException(); }
    }

    public void remove()  { throw new UnsupportedOperationException();  }
  }


  // string representation of Graph - takes quadratic time
  public String toString() {
    String NEWLINE = System.getProperty("line.separator");
    StringBuilder s = new StringBuilder();
    s.append(V + " " + E + NEWLINE);
    for (int v = 0; v < V; v++) {
      s.append(v + ": ");
      for (DirectedEdge e : adj(v)) {
        s.append(e + "  ");
      }
      s.append(NEWLINE);
    }
    return s.toString();
  }


  // test client
  public static void main(String[] args) {
    int V = Integer.parseInt(args[0]);
    int E = Integer.parseInt(args[1]);
    XAdjMatrixEdgeWeightedDigraph G = new XAdjMatrixEdgeWeightedDigraph(V, E);
    StdOut.println(G);
  }

}