[comp.lang.modula2] : Abstract data types and generics

warwick@cs.uq.oz.au (Warwick Allison) (04/05/91)

In AL281785@VMTECSLP.BITNET (RoDoGu) writes:

>PROCEDURE QSort(N: CARDINAL; Less: CompareProc; Swap: SwapProc);
>
>  PROCEDURE Sort(l,r: CARDINAL);
>	...
>  END Sort;

And????

BEGIN
	Sort(1,N)
END Qsort;

Is that right?  Perhaps Qsort needs Lower,Upper rather than N, to
facilitate sorting arrays, etc. of ranges [0..3], etc. or perhaps
INTEGERS would be better, for eg. [-32..31]... etc.

Very interesting code though.

Thanks.
Warwick.
--
  _--_|\   	warwick@cs.uq.oz.au
 /      *  <--	Computer Science Department,
 \_.--._/ 	University of Queensland,
       v    	AUSTRALIA.

Volker.Koenig@p3.f4031.n241.z2.fidonet.org (Volker Koenig) (04/10/91)

Hi Warwick!


In a messages sent 06 Apr 91 to All Warwick Allison wrote:


 >> PROCEDURE QSort(N: CARDINAL; Less: CompareProc; Swap: SwapProc);
 >>
 >> PROCEDURE Sort(l,r: CARDINAL);
 >> ...
 >> END Sort;

 WA> And????

 WA> BEGIN
 WA>         Sort(1,N)
 WA> END Qsort;

 WA> Very interesting code though.

Yes, that's true.

But I don't need to sort abstract arrays since I mostly make use of dynamic structures. Taking a bath I just got an idea how to change this sorting-procedure to be useed with dynamic structures.

But there should be some conventions to make it less complicated.

You will have to define dynamic data types as RECORDs (as it will mostly be done). The pointers linking them should be the very first two elements of these records. They sould have a defined order. So a data structure would have to look like

RECORD
   prev,
   next    : POINTER TO RECORD;
   data    : AnythingElse
END;

You will then have to define a CompareProc for your structure as

PROCEDURE(ADDRESS,ADDRESS):BOOLEAN;

to sort the nodes of the list in ascending order it should be defined as

ADDRESS^.data > ADDRESS^.data

to return TRUE in case the items are not in right order.

An external individual SwapProc is not needed since the swapping can be done by changing the links.

Now you will have to define the header of the Sort like this:

PROCEDURE Sort(Root:ADDRESS; MustSwap:CompareProc);

TYPE    AbstractPtr : POINTER TO Abstract;
        Abstract    : RECORD
                        prev,
                        next    : AbstractPtr
                      END;

VAR     Ptr         : AbstractPtr;

        PROCEDURE Swap(Ptr1,Ptr2);
        (* re-links the two elements by changing their pointers *)

BEGIN
  Ptr := Root;

 (* insert your favourite sorting-routine for dynamit structures here, with perhaps something like :

  IF MustSwap(Ptr1,Ptr2) THEN Swap(Ptr1,Ptr2) END;

*)


END Sort;


Does anyone have a complete source for such a thing or have I been the first one to use something like it (I don's hope)?




Volker.



--  
uucp: uunet!m2xenix!puddle!2!241!4031.3!Volker.Koenig
Internet: Volker.Koenig@p3.f4031.n241.z2.fidonet.org