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

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

From Project 1, you now have a basic ADT package Cars for constructing, and retrieving fields from, car records, and a companion child package Cars.IO for reading and writing car records. From Project 2 you have a table manager, which can do database-type operations on collections of car records. Each TableType variable uses an unsorted array to store up to 25 car records. Methods are provided to insert, delete, retrieve, and replace records, as well as to empty the table and to display its current contents.

In Project 3 you will add backup and restore operations to the table manager, and then reimplement the table manager using ordered linked lists with head and tail pointers.

Part I:

In the table manager from Project 2, any data inserted into a table is lost when the client program terminates. This is very unrealistic. In this part, you'll add to the table manager one exception and the following two methods:

  FileNotFound: EXCEPTION;

  PROCEDURE Save (OneTable: IN TableType; FileName: IN String);
  -- Pre:    OneTable and FileName are defined
  -- Post:   The given file is created
  --         and the contents of OneTable are written to it

  PROCEDURE Restore (OneTable: OUT TableType; FileName: IN String);
  -- Pre:    OneTable and FileName are defined
  -- Post:   If FileName exists as a file, it is opened and its contents
  --         are read into OneTable
  -- Raises: FileNotFound if FileName doesn't exist as a file

Part II:

In this part you will reimplement the table manager so that each table is stored as a linked list instead of an array. First, copy car_tables.ads into a new file car_tables_list.ads, then modify this new file as follows:

WITH Cars;
PACKAGE Car_Tables_List IS

-- Do not change ANYTHING between here and the word PRIVATE

PRIVATE

  TYPE ListNode;
  TYPE ListPtr IS ACCESS ListNode;
  TYPE ListNode IS RECORD
    Data: Cars.CarType;
    Next: ListPtr;
  END RECORD;

  TYPE List IS RECORD
    Head: ListPtr;
    Tail: ListPtr;
  END RECORD;

  Capacity: Positive := 25;
  SUBTYPE TableSize  IS Natural RANGE 0..Capacity;

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

END Car_Tables_List;

Second, develop the package body for this new package, so that it uses the data structures given above.

As in Project 2, you are to develop this new implementation incrementally. You should be able to reuse some of your test programs from previous projects.

What to submit:

Submit several listings for the package body, one for each successful stage in the development; also submit the various versions of your test program, the various incremental test runs, and your test plan.

Grading:

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