MapCell.java https://docs.google.com/document/d/1rWUV603JrG7b46AQQjGY1AlK4Y0BxzlMPWiA2i9zMWg/edit?usp=sharing Map.Java

https://docs.google.com/document/d/1XHva_soQZX81w2duKpX0_cU8ffN4QbhFgPI4bph5Ly0/edit?usp=sharing

public interface ArrayStackADT { /** Adds one element to the top of this stack. * @param dataItem data item to be pushed onto stack */ public void push (T dataItem); /** Removes and returns the top element from this stack. * @return T data item removed from the top of the stack */ public T pop() throws EmptyStackException;

/** Returns without removing the top element of this stack. * @return T data item on top of the stack */ public T peek() throws EmptyStackException; /** Returns true if this stack contains no elements. * @return true if the stack is empty; false otherwise */ public boolean isEmpty();

/** Returns the number of data items in this stack. * @return int number of data items in this stack */ public int size();

/** Returns a string representation of this stack. * @return String representation of this stack */ public String toString(); }

1. Introduction The Western Power Company (WPC) has an electrical grid that allows it to deliver electricity to its customers. The grid consists of a set of electrical switches and cables. A new customer C wants to know whether WPC can provide electricity to its property. For this assignment, you will design and implement a program in Java to determine whether the electrical grid of WPC can deliver power to the new customer C: The program needs to determine whether the set of electrical switches of WPC's grid can be used to form a path from WPC (where the electricity is generated) to C's house. You are given a map of the city, which is divided into rectangular cells to simplify the task of computing the required path. There are different types of map cells: e an initial map cell, where WPC is located, a map cell where the house of customer C is situated, * map cells containing blocks of houses of other customers, * map cells containing electrical switches. There are 3 types of electrical switches: omni switches. An omni switch located in a cell L can be used to interconnect all the neighboring map cells of L. A cell L has at most 4 neighboring cells that we will denote as the north, south, east, and west neighbors. The omni switch can be used to interconnect o all neighbors of L; of a map cell; neighbors of a map cell. o vertical switches. A vertical switch can be used to connect the north and south neighbors o horizontal switches, A horizontal switch can be used to connect the east and west The following figure shows an example of a map divided into cells. Each map cell has up to 4 neighboring cells indexed from 0 to 3. Given a cell, the north neighboring cell has index 0 and the remaining neighboring cells are indexed in clockwise order. For example, in the figure the neighboring cells of cell 6 are indexed from 0 to 3 as follows: Neighbor with index 0 is cell 3, neighbor with index 1 is cell 5, neighbor with index 2 is cell 7, and neighbor with index 3 is cell 11. Note that some cells have fewer than 4 neighbors and the indices of these neighbors might not be consecutive numbers; for example, cell 9 in the figure has 3 neighbors indexed 0, 1, and 3 A path from the WPC cell (cell number 1 in the figure) to C's house (cell number 10) is the following: 1,2, 3, 4, 5, 6,7, 9, 10. Note that a path cannot go from cell 3 to cell 6, because the horizontal switch in cell 3 only connects cells 2 and 4. Similarly from cell 5 a path cannot go to cell 8; also from cell 8 it is not possible to go to cell 10. Since cell 11 does not contain a switch, such a cell cannot be part of a path from WPC to C. 1.1 Valid Paths When looking for a path the program must satisfy the following conditions: The path can go from the WPC cell or from an omni switch cell to the following neighboring cells: o the customer cell o an omni switch cell o the north cell or the south cell, if such a cell is a vertical switch o the east cell or the west cell, if such a cell is a horizontal switch. The path can go from a vertical switch cell to the following neighboring cells: . o The north cell or the south cell, if such a cell is either the customer cell C, an omni switch cell or a vertical switch cell The path can go from a horizontal switch cell to the following neighboring cells: . o The east cell or the west cell, if such a cell is either the customer cell C, am omni switch cell, or a horizontal switch cell. If while looking for a path the program finds that from the current cell there are several choices as to which adjacent cell to use to continue the path, your program must select the next cell for the path in the following manner: the program prefers the customer cell over the other cells; if there is no customer cell adjacent to the current cell, then the program must prefer the omni switch cell over the other cells; if there is no omni switch cell the program chooses the smallest indexed cell that satisfies the conditions described above * e 2. Classes to Implement A description of the classes that you need to implement in this assignment is given below. You can implement more classes, if you want. You cannot use any static instance variables. You cannot use java's provided Stack class or any of the other java classes from the java library that implements collections. The data structure that you must use for this assignment is an array, as described in Section 2.1 ArrayStack.java This class implements a stack using an array. The header of this class must be this public class ArravStack implements KTS You can download ArrayStackADT java from the course's website. This class will have the following private instance variables: * private T] stack. This array will store the data items of the stack. . private int top. This variable stores the position of the last of data item in the stack. In the constructor this variable must be initialized to -1, this means that the stack is empty. Note that this is different from the way in which the variable top is used in the lecture notes This class needs to provide the following public methods. * public ArravStack0. Creates an empty stack. The default initial capacity of the array used to store * public AxravStacklint initialCaracitv). Creates an empty stack using an array of length equal to * public void push (Tdataltem). Adds dataltem to the top of the stack. If the array storing the data the items of the stack is 20 the value of the parameter tems is full, you will increase its capacity as follows : o If the capacity of the array is smaller than 100, then the capacity of the array will be increased by a factor of 2 Otherwise, the capacity of the array will increase by 50. So, if, for example, the size of the array is 100 and the array is full, when a new item is added the size of the array will increase to 150 o . public Tpop) throws tion, Removes and returns the data item at the top of the is thrown if the stack is empty. If after removing a data item from stack. An the stack the number of data items remaining is smaller than one third of the length of the array you need to shrink the size of the array by half, to do this create a new array of size equal to half of the size of the original array and copy the data items there For example, if the stack is stored in an array of size 100 and it contains 34 data items, after performing a pop operation the stack will contain only 33 data items. Since 33 Run Configurations..." menu item. Make it sure that the "Java Application->FindConnection" is the active selection on the left-hand side. Select the "Arguments" tab. Enter the name of the file for the map in the "Program arguments" text box 5.1 Class Map.java This class represents the map of the city including the location of the WPC cell and the C cell. The methods that you might use from this class are the following: o public Map (String inpuFile) throns This method reads the input file and displays the map on the screen. An Invali is thrown if the inputFile has the wrong format. o public MapCell getStart). Returns a MapCell object representing the cell where the Western Power Company is located. 5.2 Class MapCell.java This class represents the cells of the map. Objects of this class are created inside the class Map when its constructor reads the map file. The methods that you might use form this class are the following: o public MapCell ueiehbourCell (int throws luvalidNeighbaurlndexFxceptian. As explained above, each cell of the map has up to four neighbouring cells, indexed from 0 to 3. This method returns either a MapCell object representing the i-th neighbor of the current cell or null if such a neighbor does not exist. Remember that if a cell has fewer than 4 neighbouring cells, these peighbours do not necessarily need to appear at consecutive index values. So, it might be, for example, that not null. An negative or larger than 3. 2) is null, but this.getNeighbaux() for all other values of are exception must be thrown if the value of the parameter is o public baalean methods: isBlack), isQmniSwitch), isPowerStationl), isCustoner), return true if this MapCell object represents a cell corresponding to a block of houses, an omni switch, a vertical switch, a horizontal switch, the initial cell where the WPC is located, or the destination cell C where the customer house is, respectively. o public boolean isMarkedQ) returns true if this MapCell object represents a cell that has been marked as inStack or autQfStack. o public void markInStack marks this MapCell object as inStack. o public void markQutStacko marks this MapCell object as qutQfStack