15.10 Addresses and Generic Sorting Techniques

One of the techniques that made the generic approach to data structures work in the first place was taking care to have all operations such as comparisons located in the module that defined the ADT. This works fairly well in the case of lists, where not much comparison work needs to be done. However, the very warp and woof of inserting and deleting in some structures is ties up with the making of comparisons. In the case of binary trees, B-trees, and heaps, this was accomplished by importing a compare procedure from the module defining the ADT. However, if truly generic software is required, this will not quite do.

It will also not quite do if the generic routine being considered is a sort. Suppose one wanted to write a sort routine that could sort any kind of data. It has already been shown that the only two routines that need to know about the data type are Swap and Compare. As shown in section 8.4.3, Swap can be made absolutely generic, because all that is involved is moving around a specified number of memory locations, and this can be achieved without the procedure having to know anything about the type‹though at the usual cost that the Swap is not able to check for type. One simply writes:

PROCEDURE Swap (VAR a, b : ARRAY OF CHAR);

The question that remains is, can the comparison procedure be made generic in the same way, and then passed as a parameter to the module doing sorting. One might like to have:

TYPE
  CompareResults = (less, equal, greater);
  CompareProcs = PROCEDURE (ARRAY OF LOC, ARRAY OF LOC) : CompareResults;

and in the sorting module, a procedure like

PROCEDURE SetSortingProc (theProc : CompareProcs);

One might be tempted to suppose that one could then write such a procedure as

PROCEDURE CompareCards (a, b : CARDINAL) : CompareResults;

and issue a call

SetSortingProc (CompareCards);

Alas, an attempt to do this produces an error, because the parameters of a procedure assigned to a procedure variable must exactly match those in the type of the procedure variable, not just be assignment compatible as are CARDINAL and ARRAY OF LOC.

What to do? Suppose, instead of the above, one defined:

TYPE
  CompareProcs = PROCEDURE (ADDRESS, ADDRESS) : CompareResults;

and

PROCEDURE CompareCards (a, b : ADDRESS) : CompareResults;
VAR
  first, second : POINTER TO CARDINAL;
BEGIN
  first := a;
  second := b;
  IF first^ < second^
    THEN 
      RETURN less;
    ELSIF first^ > second^  THEN
      RETURN greater;
    ELSE
      RETURN equal;
    END;
END CompareCards;

Now, a call to

SetSortingProc (CompareCards);

would compile correctly, as the parameters would match as they are supposed to. Of course, the sort would itself have to be, say

PROCEDURE HeapSort (VAR source: ARRAY OF ADDRESS; lBound, uBound : CARDINAL);

Here is a small definition module that summarizes the definitions needed thus far. It includes a procedure type for printing data and two sort definitions. Others could be added.

DEFINITION MODULE pSorting;
(* by R. Sutcliffe
   to demonstrate sorting using only addresses *)

FROM SYSTEM IMPORT
  ADDRESS;
  
(* The sorting procedures in this module take parameters that are arrays of pointers to the data.  These in turn must be already initialized to point to the actual data. *)

TYPE
  printProc = PROCEDURE (ARRAY OF ADDRESS, (* the array to print *)
                CARDINAL, CARDINAL, (* starting and ending indices *)
                CARDINAL (* field width information *));
  compareResults = (less, equal, greater);
  compareProc = PROCEDURE (ADDRESS, ADDRESS) : compareResults;
  (* procedures of this type take two addresses of items to compare, not the data itself. *)

PROCEDURE ShellSort (VAR source: ARRAY OF ADDRESS;
        lBound, uBound : CARDINAL);

PROCEDURE QuickSort (VAR source: ARRAY OF ADDRESS;
        lBound, uBound : CARDINAL);

PROCEDURE SetCompareProc (theProc : compareProc);
(* must be set by caller *)

END pSorting.

In principle this kind of definition suffices to develop generic sorting routines. The same objections to this kind of genericity are present as for those of the generic list routines discussed above. There is no longer any type checking whatsoever. If the programmer is happy with that loss, such routines may suffice. If all that is available is standard Modula-2, such routines must suffice. However, there is at least one other way of approaching the question of writing generic routines and data structures, and it will be presented in Chapter 16 in a discussion of Standard Generic Modula-2.