CS131

Project #2

Due Date: Tuesday, October 22, 2002

The purpose of this project is to give you some experience programming with linked structures and using one data structure to implement another.Consider a tourist map such as this one:

It includes many sites of interest; government buildings, historical sites, and, in general, things like hotels and restaurants.When such a map is online, it is frequently possible to query it dynamically and get a map that shows for example Òall the hotels within 500meters of the American Embassy.ÓWe need a data structure to hold the necessary information so thatwe can dynamically produce themaps.

A natural structure is a map grid.

We can reference any cell in the grid by its grid coordinates:X and Y. At first glance, a natural data structure might seem to be a 2 dimensional array.What if X and Y range from 1-10,000?How much space would the array require?
Since we anticipate many fewer "attractions" than grid cells, most of the array would be empty.Instead we will use a list of lists.You will implement and test the following package according to the following diagram.Arrows represent pointers to cells and circles represent NULL pointers.Info is the contents of the GridCell record.The main list is ordered by ascending X value, the secondary lists are ordered by ascending Y.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Here is the package specification

PACKAGE MapGrids IS

------------------------------------------------------------------------

--| Specification for package MapGrids

--| Author: John L. Sibert, The George Washington University

--| Last Modified: October 2002

------------------------------------------------------------------------

TYPE AttractionTypeIS ( Hotel,Restaurant,Historic);

TYPE GridCell ;

TYPE GridPointer IS ACCESS GridCell;

TYPE GridCellIS RECORD

Name : STRING(1..15);

CellType : AttractionType;

GridX : Natural;

GridY : Natural;

NextX : GridPointer;

NextY: GridPointer;

END RECORD;

PROCEDURE SetName(Cell : IN GridPointer;Name : INSTRING);

--Pre Cell and Name are defined

-- Post Cell.ALL.Nameis set to Name

PROCEDURE SetType(Cell : IN GridPointer;Kind : INAttractionType);

--Pre Cell and Kind are defined

-- Post Cell.ALL. CellType is set to Kind

PROCEDURE SetXY(Cell : IN GridPointer;X : IN Natural;Y : IN Natural);

--Pre Cell, X, and Y are defined

-- Post Cell.ALL. X is set to X, Cell.ALL.Y is set to Y

PROCEDURE AddGridCell (Cell : IN GridPointer; Grid: IN OUT GridPointer);

--Pre Cell is defined,Name,CellType,GridX,and GridY are defined,

-- NextX and NextY may be undefined

--Post Cell is inserted in the grid,the grid remains ordered

PROCEDURE DeleteGridCell(X , Y:  IN  Natural; Grid: IN OUT GridPointer);

-- Pre:X and Y are defined, Grid is not empty

-- Post: The GridCell located at X,Y is deleted

END MapGrids;


 
 

What to submit:

Submit your project in the form of a Case Study as described in Feldman/Koffman and done in CSci 51. You may attach this assignment sheet as a problem statement, then write the Design, Test Planning, Implementation, and Testing sections, referring to this sheet where appropriate. Deliverables should include:

*Document for your algorithm with detailed explanations.

*Code -- a listing (.lsb) file 

*Source Code -- .adb 

*Document for your test plan

*Test Results -- a printout (turnin script)

Zip all 5 of these files into a zip archive using your last name, that is, lastname.zip.Email the zip file to your TA, be sure to include cs131 on the subject line of your email. 

Grading:

Grading for this project will be 0-20 points, as follows: Design: 0-2, Test Plan: 0-4 Program Implementation 0-10, Code style and layout, 0-4.