Due Date: beginning of class, Thursday, October 18, 2001
This project uses material from Chapter 8 of the CSci 131 book, and
the two supplements Active Traversals
and Incremental ADT Development Using Stubs
This project continues Projects 1 and 2, gives you an opportunity to work with linked lists.
In Project 1, a Knight's Tour is played with data received interactively from a human user. In Project 2, you developed a modified Knight's Tour program that gives the user the option of entering moves interactively or letting the computer generate the moves.
In this project, you will extend Project 2 so that once a game begins, the program will "remember" all valid moves in the game, and, once the game ends, allow the user to select a "replay" option that will re-run the latest game. Each actual move will be displayed in sequence on the board; after each move the program will wait for the user to press RETURN before continuing. The move sequence will be "remembered" in a linked list; each new move will be added to the end of the list, and the replay will be done by means of an active traversal of the list.
WITH Chessboards;
USE Chessboards;
PACKAGE Chess_Lists IS
------------------------------------------------------------------
--| Specification for simple linked lists with a single pointer,
--| carrying values of type Chessboards.Position
--|
--| 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; Pos: IN Position);
-- Pre: Pos is defined; L may be empty
-- Post: Pos is inserted at the beginning of L
PROCEDURE AddToEnd (L: IN OUT List; Pos: IN Position);
-- Pre: Pos is defined; L may be empty
-- Post: Pos 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 Position fields, in
the
-- order in which they appear in L
-- 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 RetrieveCurrentElement(L: List) RETURN Position;
-- Pre: L is defined
-- Post: Returns the Position 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
Pos: Position;
Next: ListPtr;
END RECORD;
TYPE List IS RECORD
Head: ListPtr;
Tail: ListPtr;
WhichElement: ListPtr; -- used in active traversal
END RECORD;
END Chess_Lists;