package hw7sol;

/**
 * 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
	 * @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 = 0; // 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) {
		vertices = new Vertex[maxSize];
	}

	/**
	 * 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) {
		if (size == vertices.length) { // if the array is full (note: size should never be > vertices.length
			// double the size of the array, and copy it over
			Vertex[] newVertices = new Vertex[size==0?1:size*2];
			for (int i = 0; i < vertices.length; i++)
				newVertices[i] = vertices[i];
			vertices = newVertices;
		}

		name = name.toLowerCase();
		Vertex newVertex = new Vertex (name);
		if (size > 0 && newVertex.compareTo(vertices[size-1].word)<=0)
			throw new UnsupportedOperationException("add only distinct names and in alphabetical order");
		vertices[size] = newVertex;
		int beginSearch = 0, endSearch = size; // being and end of search range for neighbors
		++size;

		char [] namechars = name.toCharArray();
		
		 // loop through all positions
		for (int i = 0; i<namechars.length; i++) {
			char originalChar = namechars[i];
			// in each position, loop through  all characters less than in the new vertex
			// note that this generates words in alphabetical order 
			for (char sub = 'a'; sub<originalChar; sub++) {
				namechars[i] = sub;
				int neighbor = find(namechars, beginSearch, endSearch);
				// Regardless of whether the vertex has been found, because all the names we will search for
				// in the future will be greater than what we just searched for, we can start with abs(neighbor+1), by properties of find
				beginSearch = Math.abs(neighbor+1); 
				if (neighbor>=0) { // if the vertex has been found
					newVertex.addNeighbor(vertices[neighbor]);
					vertices[neighbor].addNeighbor(newVertex);
				}
			}
			namechars[i] = originalChar; // fix the position, before going on to the next one 
		}
	}
	
	/**
	 * 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, i.e., i such that vertices[i].word.compareTo(name) == 0
	 * 
	 * If such a vertex does not exist, returns -(1 + the first position in the array that is greater than name),
	 * i.e., i such that vertices[-(i+1)].word.compareTo(name)>0, but vertices[-(i+2)].word.compareTo(name) < 0,
	 * or, in other words -(1+insertion point of name).
	 * 
	 * For example, if vertices contains {"b", "d", "f"}, begin is 0, and end is 2 then it will return:
	 * 0 on input "b"
	 * 1 on input "d"
	 * 2 on input "f"
	 * -1 on input "a" (because the first position in the array that is greater than "a" is 0)
	 * -2 on input "c"
	 * -3 on input "e"
	 * -4 on input "g" and above
	 * 
	 * In particular, the vertex has been found if and only if the return value is >=0, and
	 * the vertices in locations Math.abs(return_value  + 1) and above are exactly the vertices that are greater than name,
	 * regardless of whether the vertex has been found
	 * 
	 * This behaviour is the same as Java's Arrays.binarySearch method
	 * 
	 * If end<begin, returns -(begin+1)
	 * 
	 * 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; -(1+insertion point) if not 
	 */
	private int find (char[] name, int begin, int end) {
		// Standard binary search, with a funny return
		while (begin<=end) {
			int mid = (begin+end)/2;
			int comparisonResult = vertices[mid].compareTo(name);
			if (comparisonResult == 0)
				return mid;
			else if (comparisonResult > 0)
				end = mid - 1;
			else
				begin = mid+1;
		}
		return -(begin+1);
	}
	

	/**
	 * 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) {
		int index = find (name.toCharArray(), 0, size-1);
		if (index>=0)
			return vertices[index];
		else
			return null;
	}
	
	
	/**
	 * 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) {		
		VertexQueue bfsQ = new VertexQueue(); // the queue of the vertices to examine
		VertexQueue visitedQ = new VertexQueue(); // the queue of the vertices whose visited flag has been set -- needed for clean-up

		// Start bfs at the begin node
		begin.visited = true;
		visitedQ.enqueue (begin);
		boolean found;
		if (begin == end)
			found = true;
		else {
			bfsQ.enqueue (begin);
			found = false;
		}
		
		while (!bfsQ.isEmpty() && !found) { // standard bfs
			Vertex v = bfsQ.dequeue();
			// enqueue every neighbor not yet visited, and set its predecessor
			for (VertexListNode p = v.neighbors; p != null; p = p.next) {
				if (!p.v.visited) {
					p.v.visited = true;
					p.v.predecessor = v;
					visitedQ.enqueue(p.v); // needed for clean-up later
					if (p.v == end) { // check if found at the enqueue time, rather than dequeue time
						found = true; // this way, you will find the vertex sooner, since it won't have
						break; // to make it all the way through the queue
					} 
					bfsQ.enqueue(p.v);
				}
			}
		} // Done with bfs main loop
		
		// Clean up -- unset the visited flags, to be able to do another bfs
		while (!visitedQ.isEmpty()) 
			visitedQ.dequeue().visited = false;

		// Compute the answer if it's been found, by following predecessors 
		if (found) {
			VertexStack answerPath = new VertexStack();
			Vertex v = end;
			
			while (v != begin) {
				answerPath.push(v);
				v = v.predecessor;
			}
			answerPath.push(v);
			return answerPath;
		}
		
		return null;
	}

}