This project gives you an opportunity to work further with linked lists, and with generic packages.

Below is the specification of a generic template package that provides linked lists whose elements can be of an arbitrary type. (This file is online in programs131.) It is assumed that each element contains a field that can be used as a key, a value that allows elements to be inserted in a list such that the key sequence is preserved. For example, a list of students might be ordered by the students' identification number, or by their names.

Your task in this project is just to implement the package body. You can use Chess_Lists as a starting point. We will supply a test program; your implementation must pass all the tests in the test program. Your package body must use a LAVS for storage management.

NOTE: Grading on this project will be different, to give you a large incentive to develop correct implementations for all the list operations running correctly. 20%, or 4 points, are allocated for code style. 80%, or 16 points, are allocated for correctness: if your implementation passes all the tests, you earn 16/16 points; otherwise you earn 0/16 points. Normal "late fee" rules apply.

WHAT TO SUBMIT: No test plan or user guide is required. Just submit listings for the package spec and body and for the test program, along with your test results.

GENERIC

  TYPE InfoType IS PRIVATE;
  TYPE KeyType IS PRIVATE;

  WITH FUNCTION "<"(L, R: InfoType) RETURN Boolean;
  -- callback indicates how to compare two elements
  WITH FUNCTION RetrieveKey(Item: InfoType) RETURN KeyType;
  -- callback to retrieve a key from an element
  WITH PROCEDURE DisplayInfo(Item: IN InfoType);
  -- callback to display a single element

PACKAGE Singly_Linked_Lists_Generic IS
------------------------------------------------------------------
--| Generic specification for simple linked lists with a single
--| pointer, carrying values of type InfoType
--|
--| Adapted from Program 8.1,
--| Ada 95 Software Construction and Data Structures
--| Author: Michael B. Feldman, The George Washington University
--| Last Modified: September 2001
------------------------------------------------------------------

  TYPE List IS PRIVATE;

  PROCEDURE MakeEmpty (L: IN OUT List);
  -- Pre:  L may be empty
  -- Post: L is empty, that is, has no elements

  PROCEDURE AddToFront (L: IN OUT List; Item: IN InfoType);
  -- Pre:  Item is defined; L may be empty
  -- Post: Item is inserted at the beginning of L

  PROCEDURE AddToEnd (L: IN OUT List; Item: IN InfoType);
  -- Pre:  Item is defined; L may be empty
  -- Post: Item is appended to the end of L

  FUNCTION CopyList(L: IN List) RETURN List;
  -- Pre:  L may be empty
  -- Post: returns a complete copy of the list L

  PROCEDURE DisplayList(L: IN List);
  -- Pre:  L may be empty
  -- Post: displays the contents of L's Info fields, in the
  --   order in which they appear in L

  PROCEDURE InsertByKey
    (L: IN OUT List; Item: IN InfoType; Success: OUT Boolean);
  -- Pre:  L may be empty; Item is defined
  -- Post: Inserts Item into L, in sequence by key.
  --       No more than one element with a given key can be inserted.
  --       Sets Success to False if L already contains an element
  --       whose key is the same as Item's key.
  --       Sets Success to True if the insertion has been done
  --       successfully.

  PROCEDURE DeleteByKey
    (L: IN OUT List; Key: IN KeyType; Success: OUT Boolean);
  -- Pre:  L may be empty; Key is defined
  -- Post: If L contains an element whose key is Key, deletes
  --       that element from L and sets Success to True.
  --       Sets Success to False if L does not contain such an element.

  PROCEDURE RetrieveByKey
    (L: IN OUT List; Key: IN KeyType;
     Item: OUT InfoType; Success: OUT Boolean);
  -- Pre:  L may be empty; Key is defined
  -- Post: If L contains an element whose key is Key, returns that
  --       element in Item and sets Success to True.
  --       Sets Success to False if L does not contain such an element.

  -- Active traversal controls

  TraversalError: EXCEPTION;

  PROCEDURE StartTraversal(L: IN OUT List);
  -- Pre:  L may be empty
  -- Post: Initializes an active list traversal

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

  FUNCTION RetrieveCurrentInfo(L: List)  RETURN InfoType;
  -- Pre:    L is defined
  -- Post:   Returns the Info field of the current node in the
  --         traversal
  -- Raises: TraversalError if L is empty or we are at the end of L

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

PRIVATE

  TYPE ListNode;
  TYPE ListPtr IS ACCESS ListNode;
  TYPE ListNode IS RECORD
    Info: InfoType;
    Next: ListPtr;
  END RECORD;

  TYPE List IS RECORD
    Head: ListPtr;
    Tail: ListPtr;
    WhichElement: ListPtr; -- used in active traversal
  END RECORD;

END Singly_Lists_Generic;