1 CS1027: Foundations of Computer Science II Assignment 4 Due: April 2, 11:55pm. Purpose To gain experience with • The solution of problems using circular arrays and queues • The design of algorithms...

The assignment is attached below


1 CS1027: Foundations of Computer Science II Assignment 4 Due: April 2, 11:55pm. Purpose To gain experience with • The solution of problems using circular arrays and queues • The design of algorithms in pseudocode and their implementation in Java. 1. Introduction For this assignment you will be given a map and you are required to write a program that finds a path from a starting location to a destination, if such a path exists. This assignment is similar to Assignment 2, except that this time you are required to find a shortest path from the starting location, the Middlesex College building, to the destination, your house. As in Assignment 2 the map is divided into the same set of rectangular cells: • A starting map cell, where the Middlesex College building is located. • A destination map cell where your house is situated. • Map cells containing blocks of houses or parks, where cars cannot drive. • Map cells containing roads, where cars can drive. There are several types of road cells: o Road intersections; up to four different roads can converge into a road intersection. A car coming into an intersection can turn in any direction where there is a road o North road, south road, east road, and west road cells. All these roads are one-way roads. Figure 1 shows an example of a map divided into cells and a shortest path from the starting map cell to the destination. Each map cell has up to 4 neighboring cells indexed from 0 to 3. Given a cell, the north neighboring cell has index 0, the east neighboring cell has index 1, the south neighbor has index 2, and the west neighbor has index 3. 2. Classes that You Need 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. The data structure that you must use for this assignment is an ordered list implemented using a circular array, as described in the next section. You cannot use any of the other java classes from the Java library that implement collections (i.e. you cannot use any java class that can store a set of 2 or more values). 2.1 CellData.java This class represents the data items that will be stored in the circular array. Each object of this class stores two things: an identifier and a value. This class will be declared as follows: public class CellData This class will have two instance variables: 2 • private T id. A reference to the identifier stored in this object/ • private int value. This is the value of the data item stored in this object. You need to implement the following methods in this class: • public CellData(T theId, int theValue). Constructor for the class. Initializes id to theId and value to theValue. • public int getValue(). Returns instance variable value. • public T getId(). Returns instance variable id. • public void setValue(int newValue). Assigns newValue to instance variable value. • public void setId(T newId). Assigns the value of newId to instance variable id. Figure 1. 2.2 OrderedCircularArray.java This class implements an ordered list using a circular array. This class must implement the interface SortedListADT.java. The header of this class must be this: public class OrderedCircularArray implements SortedListADT You can download SortedListADT.java from the course's website. This class must have the following private instance variables: • private CellData[] list. This array will store the data items of the ordered list. • private int front. This variable stores the position of the first data item in the list; this is the data item with the smallest value. In the constructor of this class this variable must be initialized to 1. North road Middlesex College cell Road crossing Destination Block of houses South road 1 2 3 4 5 6 East road Park 3 Note that this is different from the way in which the variable front is initialized in the lecture notes. private int rear. This is the index of the last data item in the ordered list; this is the data item with the largest value. In the constructor for this class this variable must be initialized to 0. Again, note that this is different from the way in which variable rear is used in the lecture notes. • private int count. The value of this variable is equal to the number of data items in the list. Circular array list stores objects of the class CellData. These objects are kept sorted in the array according to their integer value attributes. An example of the array list storing 3 CellData objects in order of their integer values is shown in the next page. This class needs to provide the following public methods. • public OrderedCircularArray(). Initializes the instance variables as specified above. Array list must initially have length 5. Note that when initializing array list as list = new CellData[5]; the compiler will issue an error message because type T is not known at compilation time. To solve the problem use casting (create an array of type CellData[] and then cast it to the type that you need). • public void insert (T id, int value). Adds a new CellData object storing the given id and value to the ordered list. You must ensure that after adding this new CellData object the list remains sorted. Note that the value of front must not change when adding a new CellData object into the list. For example, if the array list is the following and we invoke insert(“id 4”, 1), then the new array must be as follows If the array is full when the insert method is invoked, a new array of size twice as large as the original one must be created, and the information from the old array must be copied there. You must ensure that the value of front does not change. So, if in the above array with 5 elements we invoke insert(“id 5”,2), the new array must be as follows “id 1”, 3 “id 2”, 8 front rear “id 3”, 12 “id 4”, 20 0 1 2 3 4 list “id 4”, 20 “id 4”, 1 “id 1”, 3 front rear “id 2”, 8 “id 3”, 12 0 1 2 3 4 list “id 4”,1 “id 5”,2 front rear “id 1”,3 0 1 2 3 4 5 6 7 8 9 list “id 3”,12 “id 4”,20 “id 2”,8 4 • public int getValue(T id) throws InvalidDataItemException. Returns the integer value of the CellData object with the specified id. An InvalidDataItemException is thrown if no CellData object with the given id is in the ordered list. In this assignment we will assume that no two CellData objects in the ordered list have the same id. Note that to check whether an object with the given id is in the ordered list you need to scan the ordered list using linear search. To check if the CellData object stored in some position of the ordered list has the same id attribute as id you must use the equals method, not the “==” operator. • public void remove(T id) throws InvalidDataItemException. Removes from the ordered list the CellData object with the specified id. An InvalidDataItemException is thrown if no CellData object in the ordered list has the specified id. Note that the value of front must not change when removing a data item from the ordered list using this method. • public void changeValue (T id, int newValue) throws InvalidDataItemException. Changes the value attribute of the CellData object with the given id to the specified newValue. An InvalidDataItemException is thrown if no object in the ordered list has the given id. After changing the value of the CellData obejct, you need to ensure that the list is still sorted by value, so you might have to reorder some of the information stored in the circular array. Hint. First remove the CellData object with the given id and then add a new CellData item with the given id and newValue