The George Washington University
School of Engineering and Applied Science
Department of Computer Science

CSci 131 -- Data Structures
Project #5

Due Date: November 23, 1999

Here is the new tables_generic_list and the new lists_generic.

The purpose of this project is to gain more experience with linked lists, and also to explore active-iteration techniques. You will extend your Project 4 table package, and modify the Vehicles user interface client.

Part A:

Copy the generic table handler and backup/restore packages into a new set of files, then modify the private section, and bodies, of the original files so that a table is implemented as an ordered singly linked list with head and tail pointers. The idea is not to throw away the array version, and also not to change the public part of the specs at all! You can use the Generic Tables implemented with Linked Lists in section 9.4. But you need to fill out the stubs, and also modify the child package, Tables_Generic.Backup to work with linked lists.

Re-test using Vehicles. An important goal of this project is to show the advantage of having a general and well-thought-out interface to a package like this, so that it is possible to change implementations without causing any client code to be modified.

Part B:

(A) Make a minor modification to Vehicles and Vehicles.IO, such that the vehicle brand is an enumeration type instead of a string. 

TYPE Brands IS (Ford, Toyota, Volvo, Honda, Kia, Yamaha);
Re-test with your Project 4 vehicles user interface.
Most of you should already have this done in Project 4.

(B) Add LAVS (list-of-available-space) storage management (Section 9.2) to the linked-list tables package. Modify InitializeTable, Insert and Delete accordingly.

(C) Add active-iterator functionality (Section 9.6) to the linked-list table package.

  • Add two fields--Iterating (a Boolean) and WhichElement (a pointer)--to the TableType declaration. You'll need to make some small changes to the other table operations, to check the value of the Iterating flag.
  • Develop a child package, Tables_Generic.Iteration, with this spec (details on the procedures can be found in Section 9.6):
  PACKAGE Tables_Generic.Iteration IS

    PROCEDURE StartTraversal (T: IN OUT TableType);

    FUNCTION RetrieveCurrentElement (T: TableType) RETURN Element;

    FUNCTION MoreElements (T: TableType) RETURN Boolean;

    PROCEDURE MoveToNextElement (T: IN OUT TableType);

    PROCEDURE StopTraversal (T: IN OUT TableType);

  END Tables_Generic.Iteration;
(D) Add a new command to the user interface.
  • When this print operation is selected by the user, the interface will prompt the user for a brand name.
  • This operation will create a report that lists the number of vehicles in the table that have that brand name.
  • You must use the Tables_Generic.Iteration package to complete this part..
  • Example:
     Please enter a brand name > Honda
     The number of vehicles of this brand are: 5