The George Washington University
School of Engineering and Applied Science
Department of Computer Science
CSci 131 -- Algorithms and Data Structures I
Project #4
Due Date: start of class, Monday, April 1, 2002
http://www.seas.gwu.edu/~csci131/spring02/131s02p4.html

This project depends on material using Chapters 1-3 and Chapter 8 of the data structures book, as well as on the documents Incremental ADT Development Using Stubs and Active and Passive Traversals, which are online and linked from the course web page.

From previous projects, you now have

  • a basic ADT package Cars for constructing, and retrieving fields from, car records,
  • a companion child package Cars.IO for reading and writing car records,
  • a table manager, using a linked-list implementation, which can do database-type operations on collections of car records, with methods to insert, delete, retrieve, and replace records, as well as to empty the table, display its current contents, back up, and restore a table using a file.

Part I:

In this part you will add active-iteration controls to your car table package. Add the following to the public part of the package specification:

  -- Active traversal controls

  TraversalError: EXCEPTION;

  PROCEDURE StartTraversal(OneTable: IN OUT TableType);
  -- Pre:  OneTable may be empty
  -- Post: Initializes an active table traversal

  FUNCTION AtEndOfTable(OneTable: TableType) RETURN Boolean;
  -- Pre:  OneTable may be empty
  -- Post: Returns True if no more elements remain in a traversal,
  --       that is, we are at the end of the table

  FUNCTION RetrieveCurrentData(OneTable: TableType)  RETURN InfoType;
  -- Pre:    OneTable is defined
  -- Post:   Returns the Data field of the current element in the
  --         traversal
  -- Raises: TraversalError if OneTable is empty or we are at
  --         the end of OneTable

  PROCEDURE MoveToNextElement(OneTable: IN OUT TableType);
  -- Pre:    OneTable is defined
  -- Post:   Moves to the next node in the traversal
  -- Raises: TraversalError if OneTable is empty or we are at
  --         the end of OneTable

Also change the TableType data structure so we can keep track of the current element in an active traversal:

  TYPE TableType IS RECORD
    CurrentSize : TableSize := 0;
    Data        : List;
    WhichElement: ListPtr;
  END RECORD;

Test these active iteration controls with a test program. Feel free to use modified versions of earlier test programs.

Part II:

Now develop a menu-driven interactive client program (use Employee_UI as an example; you can modify a copy of it) with these end-user menu options:

  • file management: initialize data base; back up data base; restore data base
  • record transactions: add, delete, retrieve, and replace a car record
  • computational queries: display the number of cars of each brand; find the average price of the cars in the data base
The data base will, in this case, not be a single table, but an array of tables, one table for each brand of car. This array will be subscripted by the enumeration type representing the brands.

What to submit:

You are not required to submit incremental-development files, just the final version of each one.

Grading:

60% Correctness of Programs
20% Code Style
20% Quality of Test Plan