Skip to main content
ICT
Lesson AB27 - Java Lists and Iterators
 
Main   Previous Next
 

LAB ASSIGNMENT AB27.1 page 9 of 10

SMBoundedEnv

Background:

In the original version of the case study, the BoundedEnv class uses a two-dimensional array of Locatable objects, theGrid, to represent the region in which the simulation takes place.  However, it raises the issue of a very large grid of fish that might not fit into memory. A related concern is that even for a moderate sized grid that does not strain memory limits, the size of the grid may be much larger than the number of fish in the model, thereby wasting space and, perhaps, time.

Consider an alternate representation where the fish in each row are stored in a singly linked list. The implementation of theGrid becomes a one-dimensional array where each entry is a reference to the first node in the linked list for that row, or null if the row is empty. Each list node contains a fish and a reference to the node containing the next fish in that row. The linked list is ordered by column index of the location of the fish, from smallest to largest.

In the example below, a 5 x 5 grid is diagrammed on the left and the list representation of that grid is shown on the right. In this representation, theGrid[2] is a reference to the first node of a list containing two fish: a fish facing north at location (2,1) and a fish facing west at location (2,4). The element theGrid[1] is null, indicating that there are no fish in that row.

List Representation

A two-dimensional array in which most of the elements are "empty" is a sparse array. There are different data structures for representing a sparse two-dimensional array.  We investigate a structure that uses an array of rows, where each row is a linked list of Locatable objects.

Assignment:

  1. Implement a class to represent a very large bounded environment that contains relatively few fish. Define an SMBoundedEnv class that uses a sparse matrix.

  2. This version should extend SquareEnvironment and should use an array of linked lists to represent the grid of Locatable objects.).

  3. Each element in the array should be a linked list of the objects that occur in that row of the grid, in increasing column order.

  4. The linked list should be of type java.util.LinkedList.

  5. All LinkedList traversals should be done using Iterator objects.

  6. If you are using the graphical user interface, edit the MBSGUI class and add SMBoundedEnv to the list of classes that can represent bounded environments. Now when you read in a file specifying a bounded environment, you will be given a choice as to which representation you would like to use.

Instructions:

  1. Modify and write code as necessary to satisfy the above specifications.

  2. Test the SMBoundedEnv class using appropriate test configurations to ensure that all conditions function correctly.

  3. Submit the source for the SMBoundedEnv class only.

Main   Previous Next
Contact
 © ICT 2006, All Rights Reserved.