billwolf%hazel.cs.clemson.edu@hubcap.clemson.edu (William Thomas Wolfe,2847,) (08/11/89)
From article <6448@ux.cs.man.ac.uk>, by chl@r1.uucp (Charles Lindsey): > But how DO you manipulate linked lists in Ada using Generics? > > Suppose I want to write a simple procedure to find the last element of a > linked list. I try the following: > > generic > type T is private; > type LINK; > type PLINK is access LINK; > type LINK is record > VAL: T; > NEXT: PLINK; > end record; > function FIND_LAST(LIST: PLINK) return PLINK is [...] OK, let's start with basics. This is the general paradigm for doing a data structure ADT in Ada: generic type Stored_ADT is limited private; with procedure Assign (To : in out Stored_ADT; From : in Stored_ADT) is <>; -- other procedures & functions as necessary... package Generic_Data_Structure is type Data_Structure is limited private; procedure Do_Something_With (The_Structure : in out Data_Structure); -- other procedures and functions as necessary... private type Data_Structure_Descriptor; -- definition of this type is left to the implementation... type Data_Structure is access Data_Structure_Descriptor; end Generic_Data_Structure; It is now a simple matter to implement the function Obtain_Last_Element which returns an object of type Stored_ADT. From there, all the user needs to do is instantiate the Generic_Data_Structure package with the type of data to be stored. Note that the Assign procedure should do a complete copy of the ADT in question; if this overhead is intolerable, it is a simple matter to use a pointer type as the type of object to be stored in the list, rather than storing the ADT directly; thus, the user would actually have a list of pointers. I am sending Mr. Lindsey a copy of the Generic_Linked_List package from my personal toolbox, so that he might have an example to work with. Anyone interested in doing Ada ADTs should also read the text _Software Components with Ada_, by Grady Booch, which will provide a general introduction to the topic of designing and implementing ADTs. Bill Wolfe, wtwolfe@hubcap.clemson.edu