import java.util.HashMap;
import java.util.Set;
import java.util.Iterator;
import java.util.Map;

//Jason Kim
//CSE 680 SU06


//Class: Graph.java
//Basically builds the Graph object given input, using a Hashmap of Linked Lists.


public class Graph 
{
		
	private ST list;     //ST is a store object Hash Map of linked lists (See ST Class at bottom)
    //constructor
    //New Graph, No Vertexes, No Neighbors
    public Graph() 
	{
        list = new ST();
    }

    // Adds Edge from veterx v to vertex w
    public void addEdge(String v, String w) 
	{
        if (list.get(v) == null) addVertex(v);
        if (list.get(w) == null)  addVertex(w);
        LinkList vlist = (LinkList) list.get(v);
        LinkList wlist = (LinkList) list.get(w);
        vlist.insert(w);
        wlist.insert(v);
    }

    // Add a new vertex v with no neighbors if no vertex exists
    public void addVertex(String v) 
	{
        if (list.get(v) == null)
            list.put(v, new LinkList());
    }

    // Return the degree of vertex v
    public int degree(String v) 
	{
        LinkList linklist = (LinkList) list.get(v);
        if (linklist == null) 
			return 0;
        else                 
			return linklist.size();
    }

    // Return the array of v
    public String[] neighbors(String v) {
        LinkList linklist = (LinkList) list.get(v);
        if (linklist == null) 
			return new String[0];
        else                 
			return linklist.toArray();
    }

    //
    public String toString() 
	{
        String s = "";
        String[] vertices = list.linked();
        for (int v = 0; v < vertices.length; v++) 
		{
            LinkList linklist = (LinkList) list.get(vertices[v]);
            s += vertices[v] + ": " + linklist + "\n";
        }
        return s;
    }

//=================Linked List===============
// Use Link List for Graph
public class LinkList 
{
    	Node first;        // Start of list (see class Node)
    	int N;             // Size of list

		// Link list Helper Class
    	public class Node 
		{
        	String name;
        	Node next;
        	Node(String name, Node next) 
			{
            	this.name = name;
            	this.next = next;
       		}
    	}

    	public boolean isEmpty() 
		{ 
			return (first == null); 
		}
    	public int size()
		{ 
			return N; 
		}

		//INSERT
    	public void insert(String s) 
		{
       		first = new Node(s, first);
       		N++;
    	}

        //Get String from List
    	public String toString() 
		{
       		 String s = "";
       		 for (Node x = first; x != null; x = x.next)
       		     s = x.name + ", " + s;
       		 return "{ " + s + "}";
    	}

     //Get Array of Strings
   	 public String[] toArray() 
	 {
       	 String[] names = new String[N];
       	 int i = N;
       	 for (Node x = first; x != null; x = x.next)
       	     names[--i] = x.name;
       	 return names;
    	}
    }


//=============HASH MAP===================
		//Class to hold LinkListed Nodes
    	public class ST 
		{
    		private HashMap st = new HashMap();

    		public void put(String linked, Object value) { st.put(linked, value);   }
    		public Object get(String linked)              { return st.get(linked);   }
    		public String toString()                     { return st.toString(); }

    		public String[] linked() 
			{
				Set linkedvalues = st.entrySet();
				String[] linked = new String[st.size()];
				Iterator it = linkedvalues.iterator();
				for (int i = 0; i < st.size(); i++) 
				{
					Map.Entry entry = (Map.Entry) it.next();
					linked[i] = (String) entry.getKey();
				}
					return linked;
    		}
	}


}