/**
 * A class for a graph of words, with two words adjacent if and only if
 * they are the same length and differ in exacly one letter
 * All words are converted to lower case before being inserted into the graph
 * by the add routine.
 * 
 * Used in HW7 of Boston University CAS CS 112 A1, Spring 2007
 *
 * @author Leo Reyzin
 *
 */
public class WordGraph {

	// Inner classes
	/**
	 * A single vertex of WordGraph; can be constructed and modified
	 * only by the WordGraph class -- public methods are accessors only,
	 * any methods that construct or modify are private
	 * @author Leo Reyzin
	 */
public static class Vertex {
		private char[] word; // the name of the vertex
		private VertexListNode neighbors; // linked list of neighbors
		private boolean visited; // used for searching the graph
		private Vertex predecessor; // /used for searching the graph
		
		/**
		 * Constructs a vertex with name word, and no neighbors
		 * @param word vertex name
		 */
		private Vertex (String word) {
			this.word = word.toCharArray();
			// neighbors is already null
		}

		/**
		 * Adds a single neighbor u to the list; does not check if it should be
		 * a neighbor; does not add this as a neighbor of u
		 * @param u neigbor to add
		 */
		private void addNeighbor(Vertex u) {
			neighbors = new VertexListNode (u, neighbors);
		}
		
		/**
		 * Returns >0 if the name of this is alphabetically after the name of v,
		 * < 0 if the the name of v is alphabetically after the name of this,
		 * and 0 if the two are equal
		 * @param v what this is compared to
		 * @return comparison result
		 */
		public int compareTo (Vertex v) {
			return compareTo(v.word);
		}

		/**
		 * Compares the name of this to secondWord,
		 * returning >0 if the name of this is alphabetically after secondWord,
		 * < 0 if secondWord is alphabetically after the name of this,
		 * and 0 if the two are equal
		 * @param secondWord
		 * @return comparison result
		 */
		public int compareTo(char[] secondWord) {
			int lengthDiff = word.length - secondWord.length;
			int minLength;
			if (lengthDiff>0)
				minLength = secondWord.length;
			else
				minLength = word.length;
			for (int i=0; i<minLength; i++) {
				if (word[i]<secondWord[i])
					return -1;
				if (word[i]>secondWord[i])
					return 1;
			}
			// We exited the loop, which means that so far all
			// the characters have been equal.  Thus,
			// the words are equal if lengthdiff is 0,
			// or whichever word is longer is the greater word
			return lengthDiff;
		}
		

		/**
		 * @return The name of the vertex
		 */
		public String toString() {
			return new String (word);
		}
		
		/**
		 * Useful for debugging
		 * @return A string with the name of the vertex and the neighbors
		 */
		public String printWithNeighbors () {
			String ret = new String(word);
			ret += ": ";
			for (VertexListNode p = neighbors; p!=null; p=p.next) {
				ret+=" " + new String(p.v.word);
			}
			return ret;
		}
	} // End of inner class Vertex


	
	/**
	 * A simple linked list node
	 * @author Leo Reyzin
	 */
	private static class VertexListNode {
		Vertex v;
		VertexListNode next;
		VertexListNode(Vertex v, VertexListNode next) {
			this.v = v;
			this.next = next;
		}
	} // End of inner class VertexListNode

	/**
	 * A linked-list-based queue of Vertices 
	 * @author Leo Reyzin
	 */
      public static class VertexQueue {
		private VertexListNode head = null; // when head is null, queue is empty, and tail is undefined (perhaps null, but not necessarily)
									// when head is not null, tail is also not null
		private VertexListNode tail = null;

		/**
		 * Add a vertex to the queue
		 * @param v the vertex to be added
		 */
		public void enqueue(Vertex v) {
			if (head != null) {
				tail.next = new VertexListNode (v, null);
				tail = tail.next;
			}
			else
				head = tail = new VertexListNode (v, null);
			
		}
		
		/**
		 * Remove a vertex from the queue
		 * @return vertex removed, or null if queue is empty
		 */
		public Vertex dequeue() {
			if (head == null)
				return null;
			Vertex ret = head.v;
			head = head.next;
			return ret;
		}
		
		/**
		 * @return true if the queue is empty, false otherwise
		 */
		public boolean isEmpty() {
			return head == null;
		}
	} // End of inner class VertexQueue
	
	/**
	 * A linked-list-base stack of vertices
	 * @author reyzin
	 */
	public static class VertexStack {
		private VertexListNode top = null;

		/**
		 * Adds a vertex to the stack
		 * @param v vertext to be pushed on
		 */
		public void push (Vertex v) {
			top = new VertexListNode (v, top);
		}

		/**
		 * Remove a vertex from the stack
		 * @return vertex removed, or null if stack is empty
		 */
		public Vertex pop () {
			if (top == null)
				return null;
			Vertex ret = top.v;
			top = top.next;
			return ret;
		}

		/**
		 * @return true if the queue is empty, false otherwise
		 */
		public boolean isEmpty() {
			return top == null;
		}
	} // End of inner class VertexStack

	// Beginning of the WordGraph class itself
	private Vertex [] vertices; // The array of all the graph's vertices; must be distinct lowercase names, sorted alphabetically
								// locations size and above are meaningless
	private int size; // the number of vertices in the vertices array, which are in locations 0..size-1

	/**
	 * Constructs a graph that can hold at most maxSize vertices
	 * (adding any more vertices will cause a costly reallocation)
	 * @param maxSize maximum number of anticipated vertices; allocates an array of that size
	 */
	public WordGraph (int maxSize) {
// FILL IN HERE
	}

	/**
	 * Adds a vertex to the graph, connecting it to its neighbors, and its neighbors to it
	 * Finds the neighbors by trying all possible one-letter substitutes
	 * addVertex calls must be on distinct vertices and in alphabetical order --
	 * else, addVertex will throw an UnsupportedOperationException
	 * @param name the name of the vertex to be added; will be converted to lowercase
	 */
	public void addVertex(String name) {
// FILL IN HERE; THE find METHOD DIRECTLY BELOW WILL BE USEFUL
	}
	
	/**
	 * If a vertex named name exists in the the array vertices between
	 * positions begin and end (inclusive), then
	 * returns the position where this vertex is.
	 * If such a vertex does not exist, returns a negative value
	 *  
	 * Both begin and end are assumed to be nonnegative and below size 
	 * 
	 * @param name the name of the vertex we are looking for
	 * @param begin beginning location (inclusive) of the array where to search; assumed >=0 and < size
	 * @param end end location (inclusive) of the array where to search; assumed >=0 and < size
	 * @return the position in the vertices array if found; a negative value if not 
	 */
	private int find (char[] name, int begin, int end) {
// FILL IN HERE; USE BINARY SEARCH
}
	

	/**
	 * Finds a vertex by name in the graph
	 * @param name the name of the vertex 
	 * @return the vertex itself, or null if no vertex by such name is in the graph
	 */
	public Vertex find (String name) {
// FILL IN HERE; THE METHOD find DIRECTLY ABOVE WILL BE USEFUL
	}
	
	
	/**
	 * Uses breadth-first-search to find the path with the fewest intermediate points
	 * from vertex begin to vertex end.  Returns a stack with begin on top,
	 * followed by nodes of the path in order, followed by end, if a path exists.
	 * Returns null if no path exists.
	 * 
	 * @param begin the node to start at
	 * @param end the node to end up at
	 * @return stack of the path from begin to end, with begin on top, or null if no path
	 */
	VertexStack bfs(Vertex begin, Vertex end) {		
// FILL IN HERE
	}

}