/**
 * Find the shortest city-to-city distance in number of moves. We take in the
 * endpoints of the search and return the closest city by reference. We also
 * return the number of steps to that point.
 *
 * This would be much better if we could use a map!
 */
int city_distance(City *from, City *to, City **closest, std::vector<std::pair<City *, unsigned int> >& history, unsigned int depth) {
	
	// Don't bother going further if we've found an easier solution
	static unsigned int foundDepth = 0;
	if(depth == 0) {
		foundDepth = 0;
	} else if(foundDepth > 0 && depth > foundDepth) {
		return -1;
	}
	
	// Look us up in the history; have we been here before?
	std::vector<std::pair<City *, unsigned int> >::iterator histit;
	for(histit = history.begin(); histit != history.end(); histit ++) {
		if(histit->first == from) {
			
			// If we've been here before in fewer steps, send the kill signal
			if(histit->second <= depth) {
				return -1;
				
			// Otherwise, update the depth to our new, lower number
			} else {
				histit->second = depth;
				break;
			}
		}
	}
	
	// It's entirely possible this wasn't in the history at all, so we need to
	// add it, of course.
	if(histit == history.end()) {
		history.push_back(std::make_pair(from, depth));
	}
	
	// If we've reached our destination, return the depth
	if(from == to) {
		foundDepth = depth;
		return depth;
	}
	
	/**
	 * Now we have the task of looping through the neighbors and making the
	 * recursive call on them, then tallying up the number of moves and figuring
	 * out which one is the shortest. Oh joy!
	 */
	
	// The first step is to see if we're neighboring the target as-is.
	if(from->is_neighbor(to)) {
		return city_distance(to, to, closest, history, depth + 1);
	}
	
	// If not, we recurse with each neighbor and store the minimum distance
	unsigned int min = 0;
	for(std::vector<City *>::const_iterator it = from->get_neighbors().begin(); it != from->get_neighbors().end(); it ++) {
		if(*it == NULL) {
			continue;
		}
		
		// Propagate the search down once more
		int dist = city_distance(*it, to, closest, history, depth + 1);
		
		// If we received a -1, it means this path is hopeless
		if(dist == -1) {
			continue;
		}
		
		// If this is shorter than we had previously, store it
		if(min == 0 || (unsigned int)dist < min) {
			if(depth == 0) {
				*closest = *it;
			}
			min = dist;
		}
		
		// We can't have a path shorter than 2 moves, so might as well bail out
		if(min == 2) {
			return 2;
		}
	}
	
	// We can never have a 0-move solution, so this means that it was a dead-end
	if(min == 0) {
		return -1;
	} else {
		return min;
	}
}


/**
 * Driver function for recursive algorithm. See above.
 */
unsigned int city_distance(City *from, City *to, City **closest) {
	// We must have both parameters non-null
	assert(from != NULL && to != NULL);
	
	// The distance between a city and itself is zero
	if(from == to) {
		*closest = to;
		return 0;
	}
	
	// The distance between a city and its neighbor is one
	if(from->is_neighbor(to)) {
		*closest = to;
		return 1;
	}
	
	// Make a history vector
	std::vector<std::pair<City *, unsigned int> > history;
	
	// Recursively search the tree
	*closest = NULL;
	int dist = city_distance(from, to, closest, history, 0);
	
	return (unsigned int)dist;
}