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

//Jason Kim
//CSE 680 SU06


//Class: BFS.java
//Runs a BFS Search on a given Graph builty by Graph.java as an input. 

public class BFS {



    private ST visited = new ST(); //ST is a store object to store Visited Nodes (See ST Class at bottom)
    //constructor
    // run BFS in graph G from given source vertex s
    public BFS(Graph G, String s) 
	{

        // put source actor name on the queue using queue class (see queue class at bottom)
        Queue q = new Queue();
        q.enqueue(s);
        visited.put(s, "");
        
        while (!q.isEmpty()) 
		{
            String v = (String) q.dequeue();//pop off item
            String[] neighbors = G.neighbors(v);//get neighbors
            for (int i = 0; i < neighbors.length; i++) 
			{
                String w = neighbors[i];
                if (visited.get(w) == null)  // search all possible paths in queue
				{
                    q.enqueue(w);
                    visited.put(w, v); // put visited back into queue
                }
            }
        }
    }

    // See if Path to Kevin Bacon exsists 
    public boolean isReachable(String v) 
	{ 
		return visited.get(v) != null; 
	}

    //Return length of the shortest path
    public int pathLength(String v) {
        int len = -1;
        while (visited.get(v) != null) {
            v = (String) visited.get(v);
            len++;
        }
        return len;
    }

    // Print shortest path to screen
    public void showPath(String v) 
	{
		String temp;
        while (visited.get(v) != null) 
		{
			
            System.out.println(v);
			v = (String) visited.get(v);
			temp = v;
			if(visited.get(temp) != null)
				System.out.println("stars in / also stars");
        }
    }


    //Return Shortest Path as an Array of Strings
    public String[] path(String v) 
	{ 
        int N = pathLength(v);
        String[] p = new String[N+1];
        for (int i = 0; i <= N; i++) 
		{
            p[i] = v;
            v = (String) visited.get(v);
        }
        return p;
    }

//===========Visited Nodes Store=================
	//class used to store Visited Nodes
	public class ST 
	{
    		private HashMap st = new HashMap();

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

    		public String[] visit() 
			{
        		Set visitvalues = st.entrySet();
        		String[] visit = new String[st.size()];
        		Iterator it = visitvalues.iterator(); //use java util iterator
        		for (int i = 0; i < st.size(); i++) 
				{
            			Map.Entry entry = (Map.Entry) it.next();
            			visit[i] = (String) entry.getKey();
        		}
        		return visit;
    		}
	}
//================Queue Class==================
	public class Queue //Basic Queue Class
	{
    	Node first;        // beginning of queue
    	Node last;         // end of queue

   	 public class Node //Node class
	 {
        	Object item;
        	Node next;
    	}

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

		// Put Item into Queue
    	public void enqueue(Object aItem) 
		{
        	Node x = new Node();
       		x.item = aItem;
        	x.next = null;
        	if (isEmpty()) first = x;
        	else last.next = x;
        	last = x;
    	}

		// Remove 
    	public Object dequeue() 
		{
        	Object val = first.item;
        	first = first.next;
        	return val;
    	}
	}

}