Data: GridWorld.jar
import java.util.ArrayList;
/**
* Grid provides an interface for a two-dimensional, grid-like
* environment containing arbitrary objects.
*/
public interface Grid<E>
{
/**
* Returns the number of rows in this grid.
* @return the number of rows, or -1 if this grid is unbounded
*/
int getNumRows();
/**
* Returns the number of columns in this grid.
* @return the number of columns, or -1 if this grid is unbounded
*/
int getNumCols();
/**
* Checks whether a location is valid in this grid.
* Precondition: loc is not null
* @param loc the location to check
* @return true if loc is valid in this grid,
* false otherwise
*/
boolean isValid(Location loc);
/**
* Puts an object at a given location in this grid.
* Precondition: (1) loc is valid in this grid (2)
* obj is not null
* @param loc the location at which to put the object
* @param obj the new object to be added
* @return the object previously at loc (or null
* if the location was previously unoccupied)
*/
E put(Location loc, E obj);
/**
* Removes the object at a given location from this grid.
* Precondition: loc is valid in this grid
* @param loc the location of the object that is to be removed
* @return the object that was removed (or null if the location
* is unoccupied)
*/
E remove(Location loc);
/**
* Returns the object at a given location in this grid.
* Precondition: loc is valid in this grid
* @param loc a location in this grid
* @return the object at location loc (or null
* if the location is unoccupied)
*/
E get(Location loc);
/**
* Gets the locations in this grid that contain objects.
* @return an array list of all occupied locations in this grid
*/
ArrayList<Location> getOccupiedLocations();
/**
* Gets the valid locations adjacent to a given location in all eight
* compass directions (north, northeast, east, southeast, south, southwest,
* west, and northwest).
* Precondition: loc is valid in this grid
* @param loc a location in this grid
* @return an array list of the valid locations adjacent to loc
* in this grid
*/
ArrayList<Location> getValidAdjacentLocations(Location loc);
/**
* Gets the valid empty locations adjacent to a given location in all eight
* compass directions (north, northeast, east, southeast, south, southwest,
* west, and northwest).
* Precondition: loc is valid in this grid
* @param loc a location in this grid
* @return an array list of the valid empty locations adjacent to
* loc in this grid
*/
ArrayList<Location> getEmptyAdjacentLocations(Location loc);
/**
* Gets the valid occupied locations adjacent to a given location in all
* eight compass directions (north, northeast, east, southeast, south,
* southwest, west, and northwest).
* Precondition: loc is valid in this grid
* @param loc a location in this grid
* @return an array list of the valid occupied locations adjacent to
* loc in this grid
*/
ArrayList<Location> getOccupiedAdjacentLocations(Location loc);
/**
* Gets the neighboring occupants in all eight compass directions (north,
* northeast, east, southeast, south, southwest, west, and northwest).
*
* Precondition: loc is valid in this grid
* @param loc a location in this grid
* @return returns an array list of the objects in the occupied locations
* adjacent to loc in this grid
*/
ArrayList<E> getNeighbors(Location loc);
}
// End of Class Grid
// Location Class
/**
* A Location object represents the row and column of a location
* in a two-dimensional grid.
* The API of this class is testable on the AP CSA and AB exams.
*/
public class Location implements Comparable
{
private int row; // row location in grid
private int col; // column location in grid
/**
* The turn angle for turning 90 degrees to the left.
*/
public static final int LEFT = -90;
/**
* The turn angle for turning 90 degrees to the right.
*/
public static final int RIGHT = 90;
/**
* The turn angle for turning 45 degrees to the left.
*/
public static final int HALF_LEFT = -45;
/**
* The turn angle for turning 45 degrees to the right.
*/
public static final int HALF_RIGHT = 45;
/**
* The turn angle for turning a full circle.
*/
public static final int FULL_CIRCLE = 360;
/**
* The turn angle for turning a half circle.
*/
public static final int HALF_CIRCLE = 180;
/**
* The turn angle for making no turn.
*/
public static final int AHEAD = 0;
/**
* The compass direction for north.
*/
public static final int NORTH = 0;
/**
* The compass direction for northeast.
*/
public static final int NORTHEAST = 45;
/**
* The compass direction for east.
*/
public static final int EAST = 90;
/**
* The compass direction for southeast.
*/
public static final int SOUTHEAST = 135;
/**
* The compass direction for south.
*/
public static final int SOUTH = 180;
/**
* The compass direction for southwest.
*/
public static final int SOUTHWEST = 225;
/**
* The compass direction for west.
*/
public static final int WEST = 270;
/**
* The compass direction for northwest.
*/
public static final int NORTHWEST = 315;
/**
* Constructs a location with given row and column coordinates.
* @param r the row
* @param c the column
*/
public Location(int r, int c)
{
row = r;
col = c;
}
/**
* Gets the row coordinate.
* @return the row of this location
*/
public int getRow()
{
return row;
}
/**
* Gets the column coordinate.
* @return the column of this location
*/
public int getCol()
{
return col;
}
/**
* Gets the adjacent location in any one of the eight compass directions.
* @param direction the direction in which to find a neighbor location
* @return the adjacent location in the direction that is closest to
* <tt>direction</tt>
*/
public Location getAdjacentLocation(int direction)
{
// reduce mod 360 and round to closest multiple of 45
int adjustedDirection = (direction + HALF_RIGHT / 2) % FULL_CIRCLE;
if (adjustedDirection < 0)
adjustedDirection += FULL_CIRCLE;
adjustedDirection = (adjustedDirection / HALF_RIGHT) * HALF_RIGHT;
int dc = 0;
int dr = 0;
if (adjustedDirection == EAST)
dc = 1;
else if (adjustedDirection == SOUTHEAST)
{
dc = 1;
dr = 1;
}
else if (adjustedDirection == SOUTH)
dr = 1;
else if (adjustedDirection == SOUTHWEST)
{
dc = -1;
dr = 1;
}
else if (adjustedDirection == WEST)
dc = -1;
else if (adjustedDirection == NORTHWEST)
{
dc = -1;
dr = -1;
}
else if (adjustedDirection == NORTH)
dr = -1;
else if (adjustedDirection == NORTHEAST)
{
dc = 1;
dr = -1;
}
return new Location(getRow() + dr, getCol() + dc);
}
/**
* Returns the direction from this location toward another location. The
* direction is rounded to the nearest compass direction.
* @param target a location that is different from this location
* @return the closest compass direction from this location toward
* target
*/
public int getDirectionToward(Location target)
{
int dx = target.getCol() - getCol();
int dy = target.getRow() - getRow();
// y axis points opposite to mathematical orientation
int angle = (int) Math.toDegrees(Math.atan2(-dy, dx));
// mathematical angle is counterclockwise from x-axis,
// compass angle is clockwise from y-axis
int compassAngle = RIGHT - angle;
// prepare for truncating division by 45 degrees
compassAngle += HALF_RIGHT / 2;
// wrap negative angles
if (compassAngle < 0)
compassAngle += FULL_CIRCLE;
// round to nearest multiple of 45
return (compassAngle / HALF_RIGHT) * HALF_RIGHT;
}
/**
* Indicates whether some other Location object is "equal to"
* this one.
* @param other the other location to test
* @return true if other is a
* Location with the same row and column as this location;
* false otherwise
*/
public boolean equals(Object other)
{
if (!(other instanceof Location))
return false;
Location otherLoc = (Location) other;
return getRow() == otherLoc.getRow() && getCol() == otherLoc.getCol();
}
/**
* Generates a hash code.
* @return a hash code for this location
*/
public int hashCode()
{
return getRow() * 3737 + getCol();
}
/**
* Compares this location to other for ordering. Returns a
* negative integer, zero, or a positive integer as this location is less
* than, equal to, or greater than other. Locations are
* ordered in row-major order.
* (Precondition: other is a Location object.)
* @param other the other location to test
* @return a negative integer if this location is less than
* other, zero if the two locations are equal, or a positive
* integer if this location is greater than other
*/
public int compareTo(Object other)
{
Location otherLoc = (Location) other;
if (getRow() < otherLoc.getRow())
return -1;
if (getRow() > otherLoc.getRow())
return 1;
if (getCol() < otherLoc.getCol())
return -1;
if (getCol() > otherLoc.getCol())
return 1;
return 0;
}
/**
* Creates a string that describes this location.
* @return a string with the row and column of this location, in the format
* (row, col)
*/
public String toString()
{
return "(" + getRow() + ", " + getCol() + ")";
}
}
// End of Class
// BoundedGrid Class
import java.util.ArrayList;
/**
* A BoundedGrid is a rectangular grid with a finite number of
* rows and columns.
* The implementation of this class is testable on the AP CS AB exam.
*/
public class BoundedGrid<E> extends AbstractGrid<E>
{
private Object[][] occupantArray; // the array storing the grid elements
/**
* Constructs an empty bounded grid with the given dimensions.
* (Precondition: rows > 0 and cols > 0.)
* @param rows number of rows in BoundedGrid
* @param cols number of columns in BoundedGrid
*/
public BoundedGrid(int rows, int cols)
{
if (rows <= 0)
throw new IllegalArgumentException("rows <= 0");
if (cols <= 0)
throw new IllegalArgumentException("cols <= 0");
occupantArray = new Object[rows][cols];
}
public int getNumRows()
{
return occupantArray.length;
}
public int getNumCols()
{
// Note: according to the constructor precondition, numRows() > 0, so
// theGrid[0] is non-null.
return occupantArray[0].length;
}
public boolean isValid(Location loc)
{
return 0 <= loc.getRow() && loc.getRow() < getNumRows()
&& 0 <= loc.getCol() && loc.getCol() < getNumCols();
}
public ArrayList<Location> getOccupiedLocations()
{
ArrayList<Location> theLocations = new ArrayList<Location>();
// Look at all grid locations.
for (int r = 0; r < getNumRows(); r++)
{
for (int c = 0; c < getNumCols(); c++)
{
// If there's an object at this location, put it in the array.
Location loc = new Location(r, c);
if (get(loc) != null)
theLocations.add(loc);
}
}
return theLocations;
}
@SuppressWarnings("unchecked")
public E get(Location loc)
{
if (!isValid(loc))
throw new IllegalArgumentException("Location " + loc
+ " is not valid");
return (E) occupantArray[loc.getRow()][loc.getCol()]; // unavoidable warning
}
public E put(Location loc, E obj)
{
if (!isValid(loc))
throw new IllegalArgumentException("Location " + loc
+ " is not valid");
if (obj == null)
throw new NullPointerException("obj == null");
// Add the object to the grid.
E oldOccupant = get(loc);
occupantArray[loc.getRow()][loc.getCol()] = obj;
return oldOccupant;
}
public E remove(Location loc)
{
if (!isValid(loc))
throw new IllegalArgumentException("Location " + loc
+ " is not valid");
// Remove the object from the grid.
E r = get(loc);
occupantArray[loc.getRow()][loc.getCol()] = null;
return r;
}
}
// End of Class
// Class AbstractGrid
import java.util.ArrayList;
/**
* AbstractGrid contains the methods that are common to grid
* implementations.
* The implementation of this class is testable on the AP CS AB exam.
*/
public abstract class AbstractGrid<E> implements Grid<E>
{
public ArrayList<E> getNeighbors(Location loc)
{
ArrayList<E> neighbors = new ArrayList<E>();
for (Location neighborLoc : getOccupiedAdjacentLocations(loc))
neighbors.add(get(neighborLoc));
return neighbors;
}
public ArrayList<Location> getValidAdjacentLocations(Location loc)
{
ArrayList<Location> locs = new ArrayList<Location>();
int d = Location.NORTH;
for (int i = 0; i < Location.FULL_CIRCLE / Location.HALF_RIGHT; i++)
{
Location neighborLoc = loc.getAdjacentLocation(d);
if (isValid(neighborLoc))
locs.add(neighborLoc);
d = d + Location.HALF_RIGHT;
}
return locs;
}
public ArrayList<Location> getEmptyAdjacentLocations(Location loc)
{
ArrayList<Location> locs = new ArrayList<Location>();
for (Location neighborLoc : getValidAdjacentLocations(loc))
{
if (get(neighborLoc) == null)
locs.add(neighborLoc);
}
return locs;
}
public ArrayList<Location> getOccupiedAdjacentLocations(Location loc)
{
ArrayList<Location> locs = new ArrayList<Location>();
for (Location neighborLoc : getValidAdjacentLocations(loc))
{
if (get(neighborLoc) != null)
locs.add(neighborLoc);
}
return locs;
}
/**
* Creates a string that describes this grid.
* @return a string with descriptions of all objects in this grid (not
* necessarily in any particular order), in the format {loc=obj, loc=obj,
* ...}
*/
public String toString()
{
String s = "{";
for (Location loc : getOccupiedLocations())
{
if (s.length() > 1)
s += ", ";
s += loc + "=" + get(loc);
}
return s + "}";
}
}
