15.6 Heterogeneous Linked Lists

To end our discussion of tagged types and also of linked lists, we show in Program 15.10 a fully dynamic example. Once again we omit the output, which is again identical to that of Program 15.4.

Program 15.10
Creating a Linked List of Payroll Records

WITH Ada.Text_IO; USE Ada.Text_IO;
WITH Currency; USE Currency;
WITH Dates; USE Dates;
WITH Persons; USE Persons;
WITH Personnel; USE Personnel;
WITH Payroll; USE Payroll;
WITH Lists_Generic;
PROCEDURE Payroll_List IS
------------------------------------------------------------------------
--| Demonstrates the use of a heterogeneous list.
--| Author: Michael B. Feldman, The George Washington University 
--| Last Modified: September 1995                                     
------------------------------------------------------------------------
    
  TYPE PayrollPointer IS ACCESS ALL Person'Class;
  -- as before, this can designate a Person or anything
  -- derived from Person
  
  PROCEDURE PutPerson (Item: IN PayrollPointer) IS
  BEGIN
    Put(Item => Item.ALL);  -- dispatch to the appropriate Put
    Ada.Text_IO.Put_Line(Item => "------------------------");
  END PutPerson;

  PACKAGE PayrollLists IS NEW Lists_Generic
    (ElementType => PayrollPointer, DisplayElement => PutPerson);
  USE PayrollLists;
  -- The list element type is now a classwide pointer
  
  Company: List;
  Temp   : PayrollPointer;
  
BEGIN -- Payroll_List

  -- Construct all the people dynamically, and add each one
  -- to the end of the list as it is constructed. We no longer
  -- need an explicit variable for each person.
  
  Temp := NEW Person'(Persons.Constructors.MakePerson(
              Name      => "George",
              Gender    => Male,
              BirthDate => Date_Of(1971,Nov,2)));
  AddToEnd(Company, Temp);
  
  Temp := NEW Employee'(Personnel.Constructors.MakeEmployee(
                Name      => "Mary",  
                Gender    => Female,
                BirthDate => Date_Of(1950,Oct,21),
                ID        => 1234,
                StartDate => Date_Of(1989,Jul,1)));
  AddToEnd(Company, Temp);
  
  Temp := NEW Professional'(Payroll.Constructors.MakeProfessional(
             Name        => "Martha",
             Gender      => Female,
             BirthDate   => Date_Of(1947,Jul,8),
             ID          => 2222,
             StartDate   => Date_Of(1985,Jun,6),
             MonthSalary => MakeCurrency(50000.00)));
  AddToEnd(Company, Temp);
  
  Temp := NEW Sales'(Payroll.Constructors.MakeSales(
             Name       => "Virginia",
             Gender     => Female,
             BirthDate  => Date_Of(1955,Feb,1),
             ID         => 3456,
             StartDate  => Date_Of(1990,Jan,1),
             WeekSalary => MakeCurrency(2500.00),
             CommRate   => 0.25)); 
  AddToEnd(Company, Temp);
  
  Temp := NEW Clerical'(Payroll.Constructors.MakeClerical(
             Name       => "Herman",
             Gender     => Male,
             BirthDate  => Date_Of(1975,May,13),
             ID         => 1557,
             StartDate  => Date_Of(1991,Jul,1),
             HourlyWage => MakeCurrency(7.50)));
  AddToEnd(Company, Temp);
  
  -- Now we can display the list. 

  Display (Company);

END Payroll_List;

Here we use our generic singly linked list package from Section 14.5 ( Program 14.11), instantiating it for our class-wide access type and declaring a few useful variables:

    TYPE PayrollPointer IS ACCESS ALL Person'Class;
    -- as before, this can designate a Person or anything
    -- derived from Person
      
    PROCEDURE PutPerson(Item: IN PayrollPointer) IS
    BEGIN
      Put(Item => Item.ALL);   -- This will dispatch to the proper Put
      Ada.Text_IO.Put_Line(Item => "------------------------");
    END PutPerson;
    
    PACKAGE PayrollLists IS NEW Lists_Generic
      (ElementType => PayrollPointer, DisplayElement => PutPerson);
    USE PayrollLists;
    -- The list element type is now a classwide pointer
      
    Company: List;
    Temp   : PayrollPointer;

Note that the element type in each list node is one of our class-wide pointers. We can now use Temp as a "holding area" for a dynamically allocated Professional, for example, and then add it to the end of our company list:

    Temp := NEW Clerical'(Payroll.Constructors.MakeClerical(
               Name       => "Herman",
               Gender     => Male,
               BirthDate  => Date_Of(1975,May,13),
               ID         => 1557,
               StartDate  => Date_Of(1991,Jul,1),
               HourlyWage => MakeCurrency(7.50)));
    AddToEnd(Company, Temp);

Note also the PutPerson procedure with which we instantiate Lists_Generic. The first line of the procedure body calls Put with a parameter gotten by dereferencing the pointer. Since the pointer type is classwide, the Put that is actually called depends on the type of the pointer's designated value. This is another example of dispatching.

After building a linked list of five persons constructed in this manner, Display is called. This list procedure dispatches the appropriate Put to display each person:

    Display (Company);

This presentation has only scratched the surface of Ada's facilities for object-oriented programming; a full treatment is beyond the scope of this book. The discussion here should give you an indication of the power of type extension and dynamic dispatching, and perhaps an appreciation of why object-oriented programming has become such a popular technique for building software systems.

No technique is perfect, and there is a price to be paid for inheritance. Large, deep type hierarchies, while very powerful, can also be difficult to work with and maintain because all the derived types and operations depend very intimately on types and operations that are higher in the hierarchy. A change at the top can cause a "ripple effect" through the hierarchy; this may be an advantage, but the high degree of coupling among types might also have unanticipated effects.

As an example of why a large type hierarchy constructed with inheritance is often difficult to use and maintain, consider a variable Virginia of type Sales and an expression

    GenderOf(Virginia)

Now suppose a problem arises that leads you to suspect a bug in GenderOf. How do you know where to look for the definition and body of GenderOf? It is not defined in the same package with Sales; indeed, it is defined in Persons, at the top of the type hierarchy. To discover this, you must look in every package specification all the way up the hierarchy, because the operation could have been defined, like IdOf, in an intermediate package. The deeper the hierarchy, the more difficult it is to locate the definition of any given operation.

This is clearly quite different from the other ADTs we have seen, in which the type provided by the package and all its operations were defined in full in that package.

Like any other powerful tool, inheritance must be used with common sense and moderation, and the tradeoffs carefully considered. Use it to build hierarchical structures of types that are truly related in some obvious way; avoid the trap of using it solely because it is there.