package algs42;

import stdlib.*;
import algs13.Bag;

// See instructions below
public class MyGarbageCollector {

	/////////////////////////////////////////////////////////////////////////
	// Do not modify anything in this section
	// This is a representation of a graph using Node objects, rather than ints.
	// To build the graph, we use an array of Node objects.
	/////////////////////////////////////////////////////////////////////////
	static class Node {
		private String key;
		private Bag<Node> adj;
		public Node (String key) {
			this.key = key;
			this.adj = new Bag<> ();
		}
		public String toString () { return key; }
		public void addEdgeTo (Node n) { adj.add (n); }
		public Bag<Node> adj () { return adj; }
	}
	Node[] node;
	int V;
	int E;
	public static boolean DEBUG = false;
	public MyGarbageCollector (int V) {
		if (V < 0) throw new IllegalArgumentException("Number of vertices in a Digraph must be nonnegative");
		this.V = V;
		this.E = 0;
		this.node = new Node[V];
		for (int i=0; i<V; i++)  {
			node[i] = new Node ("n" + (DEBUG ? i : StdRandom.uniform (100)));
		}
	}
	public MyGarbageCollector(Digraph G) {
		this (G.V ()); // run the first constructor
		for (int v=0; v<V; v++)  {
			for (int w : G.adj (v))
				addEdge(v, w);
		}
	}
	public MyGarbageCollector(In in) {
		this (in.readInt()); // run the first constructor
		int E = in.readInt();
		if (E < 0) throw new IllegalArgumentException("Number of edges in a Digraph must be nonnegative");
		for (int i = 0; i < E; i++) {
			int v = in.readInt();
			int w = in.readInt();
			addEdge(v, w);
		}
	}
	public void addEdge(int v, int w) {
		if (v < 0 || v >= V) throw new IndexOutOfBoundsException("vertex " + v + " is not between 0 and " + (V-1));
		if (w < 0 || w >= V) throw new IndexOutOfBoundsException("vertex " + w + " is not between 0 and " + (V-1));
		node[v].addEdgeTo (node[w]);
		E++;
	}
	public String toString() {
		StringBuilder s = new StringBuilder();
		String NEWLINE = System.getProperty("line.separator");
		s.append(V + " vertices, " + E + " edges " + NEWLINE);
		for (int v = 0; v < V; v++) {
			s.append(String.format("%s: ", node[v]));
			for (Node w : node[v].adj ()) {
				s.append(String.format("%s ", w));
			}
			s.append(NEWLINE);
		}
		return s.toString();
	}
	public void toGraphviz(String filename) {
		GraphvizBuilder gb = new GraphvizBuilder ();
		for (int v = 0; v < V; v++) {
			gb.addNode (node[v]);
			for (Node n : node[v].adj ())
				gb.addEdge (node[v], n);
		}
		gb.toFile (filename);
	}

	/////////////////////////////////////////////////////////////////////////
	// You may modify anything below this.
	/////////////////////////////////////////////////////////////////////////
	// Your goal is to complete the methods below.
	// All of these methods may take time order V+E (where E is the number of edges)
	// You should not need to add any new fields.
	// You can define new functions.
	//
	// mark returns an array of booleans: returnValue[i] should be true iff node[i] is
	// reachable from node[s] by following the pointers in the adjacency list.
	public boolean[] mark (int s) {
		// TODO
		return null;
	}

	// isTree returns true if the object graph rooted at node[s] is a (rooted out) tree.
	public boolean isTree (int s) {
		// TODO
		return false;
	}

	// hasCycle returns true if there is a cycle reachable from node[s].
	public boolean hasCycle (int s) {
		// TODO
		return false;
	}

	// I used the following function to print boolean arrays:
	//
	//     public static String booleanArraytoString (boolean[] a) {
	//         StringBuilder sb = new StringBuilder ();
	//         sb.append ("[");
	//         boolean comma = false;
	//         for (boolean b : a) {
	//             if (comma) { sb.append (", "); } else { comma = true; }
	//             sb.append (b ? '1' : '0');
	//         }
	//         sb.append ("]");
	//         return sb.toString ();
	//     }
	//
	// Here are my results on three files from the data directory:
	//
	// tinyDG.txt
	// marked( 0): [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]
	// marked( 1): [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
	// marked( 2): [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]
	// marked( 3): [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]
	// marked( 4): [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]
	// marked( 5): [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]
	// marked( 6): [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1]
	// marked( 7): [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
	// marked( 8): [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1]
	// marked( 9): [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1]
	// marked(10): [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1]
	// marked(11): [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1]
	// marked(12): [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1]
	// isTree:     [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
	// hasCycle:   [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
	//
	// tinyDGex2.txt
	// marked( 0): [1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0]
	// marked( 1): [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
	// marked( 2): [1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0]
	// marked( 3): [1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0]
	// marked( 4): [0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
	// marked( 5): [1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0]
	// marked( 6): [1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0]
	// marked( 7): [0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1]
	// marked( 8): [0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0]
	// marked( 9): [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0]
	// marked(10): [1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0]
	// marked(11): [0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1]
	// isTree:     [0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0]
	// hasCycle:   [1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0]
	//
	// tinyDAG.txt
	// marked( 0): [1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1]
	// marked( 1): [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
	// marked( 2): [1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1]
	// marked( 3): [0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]
	// marked( 4): [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
	// marked( 5): [0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0]
	// marked( 6): [0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1]
	// marked( 7): [0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1]
	// marked( 8): [0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1]
	// marked( 9): [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1]
	// marked(10): [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0]
	// marked(11): [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]
	// marked(12): [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
	// isTree:     [0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1]
	// hasCycle:   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

	public static void main (String[] args) {
		//MyGarbageCollector.DEBUG = true; // Gives nice node names for debugging
		//StdRandom.setSeed (0); // Gives reproduceable results for debugging
		//MyGarbageCollector G = new MyGarbageCollector (new In ("data/tinyDG.txt"));
		//MyGarbageCollector G = new MyGarbageCollector (DigraphGenerator.binaryTree (20));
		//MyGarbageCollector G = new MyGarbageCollector (DigraphGenerator.rootedInTree (20));
		//MyGarbageCollector G = new MyGarbageCollector (DigraphGenerator.rootedOutTree (20));
		//MyGarbageCollector G = new MyGarbageCollector (DigraphGenerator.cycle (10));
		//MyGarbageCollector G = new MyGarbageCollector (DigraphGenerator.dag (20, 20));
		//MyGarbageCollector G = new MyGarbageCollector (DigraphGenerator.tournament (8));
		//MyGarbageCollector G = new MyGarbageCollector (DigraphGenerator.strong (20, 36, 4));
		//MyGarbageCollector G = new MyGarbageCollector (DigraphGenerator.strong (20, 36, 4));
		MyGarbageCollector G = new MyGarbageCollector (DigraphGenerator.simple (20, 20));
		StdOut.println(G.toString ());
		G.toGraphviz ("g.png");

		// TODO
		// write some tests.
	}

}