This lab is about finding a path from some source city to a destination city. Ci
ID: 3787110 • Letter: T
Question
This lab is about finding a path from some source city to a destination city. Cities are
represented by the City enum in the provided jar file. CitySelector is a provided interface that
determines a “next hop” city (the next city to go to). CityPathConnector is a provided interface
that uses a CitySelector to determine a path from a given source city to a given destination city.
Starting from the source city, a CityPathConnector will get the next city to visit from its
CitySelector. The CityPathConnector will repeatedly do this until the CitySelector presents the
destination city, at which point the path is complete. The CityPathConnector needs to keep track
of which intermediary cities were visited.
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
/**
* Selects next cities at random. Keeps tracks of the cities that are
* selected until {@link #reset()} is called.
*
*
*/
public class RandomCitySelector implements CitySelector {
/**
* Tracks the list of selected cities.
* Cleared upon a call to {@link #reset()}.
*/
private List selectedCities;
/**
* Calls {@link #reset()}.
*/
public RandomCitySelector() {
reset();
}
/**
* Resets the list returned by {{@link #getSelectedCities()}.
*/
public void reset() {
selectedCities = new ArrayList();
}
/**
* Returns the list of selected cities since the most recent call to
* {@link #reset()}.
*
* @return list of selected cities.
*/
public List getSelectedCities() {
return selectedCities;
}
/**
* Selects a next city at random. null has an equal chance as any eligible
* city to be returned.
*/
@Override
public City getNextCity(final List pathList) {
City nextCity = null;
while (true) {
Random r = new Random();
int idx = r.nextInt(City.values().length + 1);
if (idx == City.values().length) {
nextCity = null;
break;
}
nextCity = City.values()[idx];
if (!pathList.contains(nextCity)) {
break;
}
}
selectedCities.add(nextCity);
return nextCity;
}
}
***Instructions***
Use the RandomCitySelector which will present cities or null values in random order. null value has equal chance as any eligible city to be presented.
public enum City {
/**
* Atlanta, GA.
*/
ATL,
/**
* New York, NY.
*/
NYC,
/**
* Chicago, IL.
*/
CHI,
/**
* Miami, FL.
*/
MIA,
/**
* New Orleans, LA.
*/
NOR,
/**
* Charlotte, NC.
*/
CHA,
/**
* Philadelphia, PA.
*/
PHI,
/**
* Los Angeles, CA.
*/
LAX,
/**
* Portland, OR.
*/
PDX,
/**
* Seattle, WA.
*/
SEA,
/**
* Denver, CO.
*/
DEN,
/**
* Houston, TX.
*/
HOU,
/**
* Boston, MA.
*/
BOS,
/**
* Washington, DC.
*/
WAS
}
*CitySelector*
import java.util.List;
/**
* Selects a next city destination.
*
*
*
*/
public interface CitySelector {
/**
* Selects a next city destination. Returns a city that's not in pathList,
* or returns null.
* @param pathList The list of cities that cannot be the next city.
* @return A city that's not in pathList or null.
*/
City getNextCity(List<City> pathList);
}
interface CityPathConnector
/**
* Determines {@link CityPath}s from a source {@link City} to a destination
* {@link City}.
*
*
*
*/
public interface CityPathConnector {
/**
* Determines a {@link CityPath} from {@code source} to {@code dest},
* using a stack internally.
*
* @param selector The selector that determines the order of city travel.
* @param source The source city.
* @param dest The destination city.
* @return The {@link CityPath} from {@code source} to {@code dest}.
*/
CityPath getPath(CitySelector selector, City source, City dest);
}
Explanation / Answer
City.java
public enum City {
/**
* Atlanta, GA.
*/
ATL,
/**
* New York, NY.
*/
NYC,
/**
* Chicago, IL.
*/
CHI,
/**
* Miami, FL.
*/
MIA,
/**
* New Orleans, LA.
*/
NOR,
/**
* Charlotte, NC.
*/
CHA,
/**
* Philadelphia, PA.
*/
PHI,
/**
* Los Angeles, CA.
*/
LAX,
/**
* Portland, OR.
*/
PDX,
/**
* Seattle, WA.
*/
SEA,
/**
* Denver, CO.
*/
DEN,
/**
* Houston, TX.
*/
HOU,
/**
* Boston, MA.
*/
BOS,
/**
* Washington, DC.
*/
WAS
}
CityPathConnector.java
import java.util.List;
/**
* Determines {@link CityPath}s from a source {@link City} to a destination
* {@link City}.
*
*
*
*/
public interface CityPathConnector {
/**
* Determines a {@link CityPath} from {@code source} to {@code dest},
* using a stack internally.
*
* @param selector The selector that determines the order of city travel.
* @param source The source city.
* @param dest The destination city.
* @return The {@link CityPath} from {@code source} to {@code dest}.
*/
List<City> getPath(CitySelector selector, City source, City dest);
}
CitySelector.java
import java.util.List;
/**
* Selects a next city destination.
*
*
*
*/
public interface CitySelector {
/**
* Selects a next city destination. Returns a city that's not in pathList,
* or returns null.
* @param pathList The list of cities that cannot be the next city.
* @return A city that's not in pathList or null.
*/
City getNextCity(List<City> pathList);
}
RandomCitySelector.java
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
/**
* Selects next cities at random. Keeps tracks of the cities that are
* selected until {@link #reset()} is called.
*
*
*/
public class RandomCitySelector implements CitySelector {
/**
* Tracks the list of selected cities.
* Cleared upon a call to {@link #reset()}.
*/
private List selectedCities;
/**
* Calls {@link #reset()}.
*/
public RandomCitySelector() {
reset();
}
/**
* Resets the list returned by {{@link #getSelectedCities()}.
*/
public void reset() {
selectedCities = new ArrayList();
}
/**
* Returns the list of selected cities since the most recent call to
* {@link #reset()}.
*
* @return list of selected cities.
*/
public List getSelectedCities() {
return selectedCities;
}
/**
* Selects a next city at random. null has an equal chance as any eligible
* city to be returned.
*/
@Override
public City getNextCity(final List pathList) {
City nextCity = null;
while (true) {
Random r = new Random();
int idx = r.nextInt(City.values().length + 1);
if (idx == City.values().length) {
nextCity = null;
break;
}
nextCity = City.values()[idx];
if (!pathList.contains(nextCity)) {
break;
}
}
selectedCities.add(nextCity);
return nextCity;
}
}
/*********************************************************************/
I have written two classes now. One is implementing CityPathConnector nterface to provide the required path.
Other is to demo the program, containing the main method.
CityPathConnectorImpl.java
import java.util.ArrayList;
import java.util.List;
public class CityPathConnectorImpl implements CityPathConnector{
@Override
public List<City> getPath(CitySelector selector, City source, City destination) {
// create a pathlist to store the path information
ArrayList<City> pathList = new ArrayList<City>();
// if either source or destination is null
if(source == null || destination == null) {
throw new IllegalArgumentException("Source and Destination Cities need to be given");
}
// if source and destination are same, we have already reached.
if(source == destination) {
pathList.add(source);
return pathList;
}
// add the source node to path
pathList.add(source);
// get the next city to hop in, it can give null also
City nextCityToGoTo = selector.getNextCity(pathList);
while(nextCityToGoTo != destination) {
if(nextCityToGoTo != null) {
pathList.add(nextCityToGoTo);
}
// again call for next city
nextCityToGoTo = selector.getNextCity(pathList);
}
// destination has been reached. Add it to path list
pathList.add(destination);
// Printing the path information
System.out.println("Path from " + source + " to " + destination);
for (int i=0; i<pathList.size(); i++) {
System.out.print(pathList.get(i));
if(i != pathList.size()-1) {
System.out.print(" -> ");
}
}
System.out.println();
return pathList;
}
}
FindPath.java
public class FindPath {
static RandomCitySelector randomCitySelector;
static CityPathConnector cityPathConnector;
public static void main(String[] args) {
randomCitySelector = new RandomCitySelector();
cityPathConnector = new CityPathConnectorImpl();
cityPathConnector.getPath(randomCitySelector,
City.CHA, City.HOU);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.