We now build a generic version of our list package so that the element type is
not restricted to three-character strings. The specification for
Lists_Generic is given as
Program
14.11.
Program 14.11
GENERIC
TYPE ElementType IS PRIVATE;
WITH PROCEDURE DisplayElement (Item: IN ElementType);
PACKAGE Lists_Generic IS
------------------------------------------------------------------------
--| Specification for generic singly linked lists
--| Author: Michael B. Feldman, The George Washington University
--| Last Modified: September 1995
------------------------------------------------------------------------
TYPE List IS LIMITED PRIVATE;
ListEmpty: EXCEPTION;
PROCEDURE MakeEmpty (L : IN OUT List);
-- Pre: L is defined
-- Post: L is empty
FUNCTION IsEmpty (L : IN List) RETURN Boolean;
-- Pre: L is defined
-- Post: returns True if L is empty, False otherwise
PROCEDURE AddToFront (L: IN OUT List; Element: IN ElementType);
-- Pre: Element is defined; L may be empty
-- Post: Element is inserted at the beginning of L
FUNCTION RetrieveFront (L: IN List) RETURN ElementType;
-- Pre: L is defined; L may be empty
-- Post: returns a complete copy of the list L
-- Raises: ListEmpty if the list is empty before the retrieval
PROCEDURE RemoveFront (L: IN OUT List);
-- Pre: L is defined; L may be empty
-- Post: The first node of L is removed
-- Raises: ListEmpty if the list is empty before the removal
PROCEDURE AddToEnd (L: IN OUT List; Element: IN ElementType);
-- Pre: Element is defined; L may be empty
-- Post: Element is appended to the end of L
PROCEDURE Copy (Target: OUT List; Source: IN List);
-- Pre: Source may be empty
-- Post: Returns a complete copy of Source in Target
PROCEDURE Display (L: IN List);
-- Pre: L may be empty
-- Post: displays the contents of L's Element fields, in the
-- order in which they appear in L
PRIVATE
TYPE ListNode;
TYPE ListPtr IS ACCESS ListNode;
TYPE ListNode IS RECORD
Element: ElementType;
Next: ListPtr;
END RECORD;
TYPE List IS RECORD
Head: ListPtr;
Tail: ListPtr;
END RECORD;
END Lists_Generic;
The
generic parameters are ElementType, the element to be contained in
each list node, and DisplayElement. The latter parameter is needed
because the Display operation needs to know exactly how to display
each element of the list. It cannot simply call Ada.Text_IO.Put as
in the nongeneric version because the element type is not necessarily a string.
For example, if we had
SUBTYPE NameType IS String (1..20);
we
could instantiate the package as
PACKAGE NameLists IS
NEW Lists_Generic
(ElementType => NameType, DisplayElement => Ada.Text_IO.Put);
Of
course, this would display all the names on the list on a single line. To
tailor the DisplayElement operation better, we could write, in our
client program,
PROCEDURE DisplayName (Item: NameType) IS
BEGIN
Ada.Text_IO.Put (Item => Item);
Ada.Text_IO.New_Line;
END DisplayName;
and
instantiate the list package as
PACKAGE NameLists IS
NEW Lists_Generic
(ElementType => NameType, DisplayElement => DisplayName);
Similarly,
if ElementType were some record type, we would need only to
provide a procedure to display one record, and then instantiate the list
package with that procedure supplied as the parameter.
Now look at the type declaration for the list type:
TYPE List IS LIMITED PRIVATE;
We
have changed the list from PRIVATE to LIMITED
PRIVATE. This is because while a PRIVATE type allows
assignment and equality test, a LIMITED PRIVATE type has no
predefined operations at all, prohibiting even these two. As mentioned in
Section 14.3, it is desirable to disallow these
operations for linked lists
because they are misleading, copying and comparing only the header pointers
instead of the list itself.
LIMITED PRIVATE necessitates changing
the list Copy operation from a function to a procedure:
PROCEDURE Copy (Target: OUT List; Source: IN List);
because
writing
L2 := Copy (L1);
is
no longer allowed (the := is prohibited). Copying is done now by
writing
Copy (Target => L2, Source => L1);
that
is, as a procedure call.
To give us more flexibility in using the package, we have added four additional operations:
PROCEDURE MakeEmpty (L : IN OUT List);
FUNCTION IsEmpty (L : IN List) RETURN Boolean;
FUNCTION RetrieveFront (L: IN List) RETURN ElementType;
PROCEDURE RemoveFront (L: IN OUT List);
The
behavior of these operations is obvious from the postconditions.
RemoveFront results in a list like:
while MakeEmpty produces a list like:
We show MakeEmpty and RemoveFront as
Program
14.12 and
Program
14.13, respectively. Note that these operations, as written, do not use
Unchecked_Deallocation to return the discarded nodes to the
storage pool. Therefore, they remain allocated but completely inaccessible.
Over a long program execution, if these operations were done repeatedly, the
storage pool would be exhausted and Storage_Error would be raised.
We leave it as an exercise to correct this design flaw and to complete the
other operations in the package.
Program 14.12
MakeEmpty
SEPARATE (Lists_Generic) PROCEDURE MakeEmpty (L : IN OUT List) IS ------------------------------------------------------------------------ --| MakeEmpty - subunit of Lists_Generic --| Author: Michael B. Feldman, The George Washington University --| Last Modified: July 1995 ------------------------------------------------------------------------ BEGIN L.Head := NULL; L.Tail := NULL; END MakeEmpty;
Program 14.13
RemoveFront
SEPARATE (Lists_Generic)
PROCEDURE RemoveFront (L: IN OUT List) IS
------------------------------------------------------------------------
--| RemoveFront - subunit of Lists_Generic
--| Author: Michael B. Feldman, The George Washington University
--| Last Modified: September 1995
------------------------------------------------------------------------
Temp: ListPtr;
BEGIN -- RemoveFront
IF L.Head = NULL THEN
RAISE ListEmpty;
ELSE -- L.Head points to a node; remove it
Temp := L.Head;
L.Head := L.Head.ALL.Next; -- jump around first node
Dispose (X => Temp);
END IF;
END RemoveFront;
Copyright © 1996 by Addison-Wesley Publishing Company, Inc.