/*************************************************************************
 *  Kompilacja:  javac EdgeWeightedGraph.java
 *  Wykonanie:    java EdgeWeightedGraph V E
 *  Zależności: Bag.java Edge.java
 *
 *  Nieskierowany graf ważony zaimplementowany za pomocą list sąsiedztwa.
 *  Krawędzie równoległe i pętle zwrotne są dozwolone
 *
 *************************************************************************/

/**
 *  Klasa <tt>EdgeWeightedGraph</tt> reprezentuje nieskierowany graf wierzchołków o nazwach
 *  od 0 do V-1, gdzie każda krawędź ma wagę o wartości rzeczywistej.
 *  Obsługuje następujące operacje: dodawanie krawędzi do grafu,
 *  przechodzenie po wszystkich sąsiadach wierzchołka.
 *  Krawędzie równoległe i pętle zwrotne są dozwolone.
 *  <p>
 *  Dodatkową dokumentację można znaleźć w <a href="http://algs4.cs.princeton.edu/43mst">podrozdziale 4.3</a> książki
 *  <i>Algorytmy, wydanie czwarte</i> Roberta Sedgewicka i Kevina Wayne'a.
 */


public class EdgeWeightedGraph {
    private final int V;
    private int E;
    private Bag<Edge>[] adj;
    
   /**
     * Tworzenie pustego grafu ważonego o V wierzchołkach.
     */
    public EdgeWeightedGraph(int V) {
        if (V < 0) throw new RuntimeException("Liczba wierzcholkow musi byc nieujemna");
        this.V = V;
        this.E = 0;
        adj = (Bag<Edge>[]) new Bag[V];
        for (int v = 0; v < V; v++) adj[v] = new Bag<Edge>();
    }

   /**
     * Tworzenie losowego grafu ważonego o V wierzchołkach i E krawędziach.
     * Oczekiwany czas wykonania jest proporcjonalny do V + E.
     */
    public EdgeWeightedGraph(int V, int E) {
        this(V);
        if (E < 0) throw new RuntimeException("Liczba krawedzi musi byc nieujemna");
        for (int i = 0; i < E; i++) {
            int v = (int) (Math.random() * V);
            int w = (int) (Math.random() * V);
            double weight = Math.round(100 * Math.random()) / 100.0;
            Edge e = new Edge(v, w, weight);
            addEdge(e);
        }
    }

   /**
     * Tworzenie grafu ważonego na podstawie strumienia wejściowego.
     */
    public EdgeWeightedGraph(In in) {
        this(in.readInt());
        int E = in.readInt();
        for (int i = 0; i < E; i++) {
            int v = in.readInt();
            int w = in.readInt();
            double weight = in.readDouble();
            Edge e = new Edge(v, w, weight);
            addEdge(e);
        }
    }

   /**
     * Zwraca liczbę wierzchołków w grafie.
     */
    public int V() {
        return V;
    }

   /**
     * Zwracanie liczby krawędzi w grafie.
     */
    public int E() {
        return E;
    }


   /**
     * Dodawanie krawędzi e do grafu.
     */
    public void addEdge(Edge e) {
        int v = e.either();
        int w = e.other(v);
        adj[v].add(e);
        adj[w].add(e);
        E++;
    }


   /**
     * Zwracanie krawędzi incydentnych do wierzchołka v jako obiektu Iterable.
     * Aby przejść po krawędziach incydentnych do wierzchołka v należy użyć zapisu foreach:
     * <tt>for (Edge e : graph.adj(v))</tt>.
     */
    public Iterable<Edge> adj(int v) {
        return adj[v];
    }

   /**
     * Zwracanie wszystkich krawędzi grafu jako obiektu Iterable.
     * Aby przejść po krawędziach, należy użyć zapisu foreach:
     * <tt>for (Edge e : graph.edges())</tt>.
     */
    public Iterable<Edge> edges() {
        Bag<Edge> list = new Bag<Edge>();
        for (int v = 0; v < V; v++) {
            int selfLoops = 0;
            for (Edge e : adj(v)) {
                if (e.other(v) > v) {
                    list.add(e);
                }
                // Dodawanie tylko jednej kopii każdej pętli zwrotnej
                else if (e.other(v) == v) {
                    if (selfLoops % 2 == 0) list.add(e);
                    selfLoops++;
                }
            }
        }
        return list;
    }



   /**
     * Zwracanie łańcucha znaków reprezentującego dany graf
     */
    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 (Edge e : adj[v]) {
                s.append(e + "  ");
            }
            s.append(NEWLINE);
        }
        return s.toString();
    }

   /**
     * Klient testowy
     */
    public static void main(String[] args) {
        EdgeWeightedGraph G;

        if (args.length == 0) {
            // Wczytywanie grafu ze standardowego wejścia
            G = new EdgeWeightedGraph(new In());
        }
        else {
            // Losowy graf o V wierzchołkach i E krawędziach z dozwolonymi krawędziami równoległymi
            int V = Integer.parseInt(args[0]);
            int E = Integer.parseInt(args[1]);
            G = new EdgeWeightedGraph(V, E);
        }

        StdOut.println(G);
    }

}
