Re: Hopefully simple question regarding generics

Re: Hopefully simple question regarding generics

[Stephen J Bevan]

In article <1991Oct16.085901@lglsun.epfl.ch> gauthier@lglsun.epfl.ch (Michel Ga
uthier) writes:

       [ my question on how to parameterise a sort over the collection
         deleted ]

     Bert Laverman replies:

     [ lists and arrays are too different, so don't even bother ... ]

   This is quite a good answer. May I add some other remarks?

   Array sorting algorithms implicitely use array operations, which are
   not list operations. If you want a general sorting algorithm, you
   must explicit these as generic parameters, and build as procedures
   the corresponding actual parameters, one set for arrays, and one set
   for lists, and (why not?) a set for sequential files if applicable.


I realise that using the same function to sort an array collection and
a list collection is not a good idea in terms of performance (maybe I
should have made this clear in my original post).

When I talk about a collection, I mean any object that satisfies a
certain interface i.e. it should be parameterised over the type and
should provide an indexing operator.  I realise that an indexing
operator is inefficient for a list, but that is besides the point
here.  The result of this is not meant to be part of a real program (I
don't even have an Ada compiler), it is just something I feel I need
to know to understand Ada better.

So, can anybody give me an example of how I do the above?

Thanks again,

Stephen J. Bevan				bevan@cs.man.ac.uk

Re: Hopefully simple question regarding generics

[netnews.upenn.edu!uofs!guinness.cs.uofs.edu!beidler]

In article <1991Oct16.085901@lglsun.epfl.ch>, gauthier@lglsun.epfl.ch (Michel G
authier) writes:
|> 
|> Stephen J Bevan writes:
|> 
|> >I read (and think I understand) the following in "Software Engineering
|> >with Ada" by Booch :- 
|> >[ generic array sorter's interface deleted ]
|> >
|> >What I'd like to know is how can I change it so that it doesn't assume
|> >the items to sort are in an array i.e. how to I parameterize the above
|> >over the implementation of the items to be sorted.  For example, say I
|> >want to sort a list as opposed to an array.  With a parameterized
|> >version I could then do something like :-
|> >
|> >  procedure STRING_LIST_SORT is new 
|> >    SORT(ITEM => CHARACTER,
|> >         INDEX => POSITIVE,
|> >         ITEMS => STRING,
|> >         COLLECTION => LIST  -- or maybe LIST(INDEX, ITEM) ???
|> >         "<" => "<");
|>

 
Laverman and Gauthier's separate replies gave excellent advise.

Let me take a slightly different approach -- does Bevan need to change the gene
ric sort at all?
Specifically, if the generic sort is something like

generic
    type Object_Type is private
    type Array_range is (<>) ;
    type array_type is array (Array_range) of Object_Type ;
    with function "<" (left, right: Object_Type return boolean ;
procedure Sort (An_Array : in out AArray_Type) ;

if the objects are pointers to the values and the sort orders the pointers acco
rding to the 
values of the objects being represented by the strings, lists, or whateverthe p
ointers are
pointing to, he can use this generic Sort directly simply by defining a special
 purpose

    function less_than (left, right : Object_Type) return boolean ;

that does the comparisons he want between the objects he is trying to manipulat
e.  Then
use this function to instantiate the "<" generic formal parameter to Sort and h
e's is business.
Further, since he is only moving the locations of the pointers and not trying t
o physically
move the objects being referenced by indirection, he is as safde an he can be, 
given that
he is using private types.  It might be wise to create a "limited private" vers
ion of this
Sort,

generic
    type Object_Type is limited private
    type Array_range is (<>) ;
    type array_type is array (Array_range) of Object_Type ;
    with function "<" (left, right: Object_Type return boolean ;
    with procedure SWAP (left, right : in out OBJECT_TYPE) ;
procedure Sort (An_Array : in out AArray_Type) ;

which would need a procedure, like SWAP, to flip the object references around.

-- 
+-----------------------------------------------------------------------------+
|  John (Jack) Beidler				                              |
|  Prof. of Computer Science  Internet (VAX/VMS)  BEIDLER@JAGUAR.UOFS.ED      |
|  University of Scranton     Internet (SUN/UNIX) BEIDLER@GUINNESS.CS.UOFS.EDU|
|  Scranton, PA 18510	      Bitnet   (VAX/VMS)  BEIDLER@SCRANTON            |
|                                                                             |
|          Phone: (717) 941-7446	 FAX:   (717) 941-4250                |
+-----------------------------------------------------------------------------+

Re: Hopefully simple question regarding generics

[mcsun!hp4nl!gufalet.let.rug.nl!rug4!laverman]

Jack Beidler writes:
> ...
>he is using private types.  It might be wise to create a "limited private" ver
sion of this
>Sort,
>
>generic
>    type Object_Type is limited private
>    type Array_range is (<>) ;
>    type array_type is array (Array_range) of Object_Type ;
>    with function "<" (left, right: Object_Type return boolean ;
>    with procedure SWAP (left, right : in out OBJECT_TYPE) ;
>procedure Sort (An_Array : in out AArray_Type) ;
>
>which would need a procedure, like SWAP, to flip the object references around.

Actually, the Modular Pascal standard library shows that even this interface ca
n be
cut down:

	PROCEDURE sort(lo, hi: integer;
		       FUNCTION before(i, j: integer): boolean;
		       PROCEDURE swap(i, j: integer));

If you've already taken the test and the swapping out of the sorter, why keep t
he array?
This way the sorter is at the minimal need-to-know situation. This form of prog
ramming
generics has more the aspect of frame-work reuse, than routine-reuse.

Okay, okay. So maybe an Ada compiler will want to expand those generic paramete
rs
inline. Still, I think this is an excellent example of use of procedural parame
ters,
and in most cases the loss caused by the procedure calls will be minimal.

Greetings, Bert
-- 
#include <std/disclaimer>

  Bert Laverman,  Dept. of Computing Science, Groningen University
  laverman@cs.rug.nl			bert@arrakis.nl.mugnet.org