George.Emery@p0.f6.n105.z1.fidonet.org (George Emery) (03/20/91)
Making use of procedure variables to set the sort method is old hat to most folks. What I'm trying to figure (can it even be done?) is a way to allow a procedure to sort different types of records. Say, for instance, you have several different types of records that happen to have integer values which are meaningful across all the records, but each record type has nothing else in common. Is there a way to write a generic sort routine? Or is this too far into object-oriented programming to not be Modula-2? GE -- uucp: uunet!m2xenix!puddle!6.0!George.Emery Internet: George.Emery@p0.f6.n105.z1.fidonet.org
warwick@cs.uq.oz.au (Warwick Allison) (03/21/91)
In <2848.27E71773@puddle.fidonet.org> George.Emery@p0.f6.n105.z1.fidonet.org (George Emery) writes: >Making use of procedure variables to set the sort method is old hat >to most folks. What I'm trying to figure (can it even be done?) is >a way to allow a procedure to sort different types of records. Say, for >instance, you have several different types of records that happen to >have integer values which are meaningful across all the records, but >each record type has nothing else in common. Is there a way to write >a generic sort routine? Or is this too far into object-oriented >programming to not be Modula-2? Of course! Anything is possible in Modula-2 :-) Sort this: VAR ToBeSorted:ARRAY Index OF RECORD CASE RecordType:RecordTypeEnumeration OF Type1: r1:POINTER TO ActualType1; | Type2: r2:POINTER TO ActualType2; | Type3: r3:POINTER TO ActualType3; END; END; Using the procedure: PROCEDURE OutOfOrder(a,b:Index):BOOLEAN; VAR aKey:INTEGER; BEGIN CASE ToBeSorted[a].RecordType OF Type1: aKey:=r1^.NumberOfToesField | Type2: aKey:=r2^.NumberOfNosesField | Type3: aKey:=r3^.NumberOfEyesField END; CASE ToBeSorted[a].RecordType OF Type1: RETURN aKey>r1^.NumberOfToesField | Type2: RETURN aKey>r2^.NumberOfNosesField | Type3: RETURN aKey>r3^.NumberOfEyesField END; END OutOfOrder; Sure, it's ugly, and the flexibility is low here, but it can be generalised. The main problem really is the provision of arrays of heterogeneous records, which is going to be a problem regardless of language! Basically, you must have a tag (it's even called that in M2) to determine which type of record the variant (called that too) represents. We are actually still sorting records of one type (that of ToBeSorted), but we cannot have: TYPE Foobar=ARRAY [1..10] OF (x OR y OR MAYBE z); so the problem never arises! Sure, we may use untagged variant records, but then the sort procedure would not know how to order the records. -- _--_|\ warwick@cs.uq.oz.au / * <-- Computer Science Department, \_.--._/ University of Queensland, v AUSTRALIA.
lins@Apple.COM (Chuck Lins) (03/22/91)
In article <2848.27E71773@puddle.fidonet.org> George.Emery@p0.f6.n105.z1.fidonet.org (George Emery) writes: >Making use of procedure variables to set the sort method is old hat >to most folks. What I'm trying to figure (can it even be done?) is >a way to allow a procedure to sort different types of records. Say, for instance, you have several different types of records that happen to have integer values which are meaningful across all the records, but each record type has nothing else in common. Is there a way to write a generic sort routine? Or is this too far into object-oriented programming to not be Modula-2? > >GE The sort routine should be given routines for swapping two elements given an index as well as routines for comparison and perhaps copying. The procedures are aware of the different arrays by the sort routine need not be. See 'The Modula-2 Software Component Library' volume 4, the chapter on sorting. -- Chuck Lins | "Is this the kind of work you'd like to do?" Apple Computer, Inc. | -- Front 242 20525 Mariani Avenue | Internet: lins@apple.com Mail Stop 37-BD | AppleLink: LINS@applelink.apple.com Cupertino, CA 95014 | "Self-proclaimed Object Oberon Evangelist" The intersection of Apple's ideas and my ideas yields the empty set.
seurer+@rchland.ibm.com (Bill Seurer) (03/22/91)
Here's a minimal example that does what you want (I think). I compiled
it and tried it with the test code and the end and it ran ok but I make
no guarantees!. A different sorting method might require a slightly
different interface and different compilers might require different
sorts of type coercions. Of course the interface to sort shown here
can't do much type checking since it uses the ADDRESS type. A "real" OO
language could do better.
-=-=-=-=-
DEFINITION MODULE sort;
FROM SYSTEM IMPORT ADDRESS;
TYPE
Result = (LessThan, Equal, GreaterThan);
CompareProc = PROCEDURE (ADDRESS, ADDRESS): Result;
SwapProc = PROCEDURE (ADDRESS, ADDRESS);
NextProc = PROCEDURE (ADDRESS): ADDRESS;
PROCEDURE Sort (list: ADDRESS;
Compare: CompareProc;
Swap: SwapProc;
Next: NextProc);
END sort.
-=-=-=-=-
IMPLEMENTATION MODULE sort;
FROM SYSTEM IMPORT ADDRESS;
PROCEDURE Sort (list: ADDRESS;
Compare: CompareProc;
Swap: SwapProc;
Next: NextProc);
(* Bubble sort shown for example purposes only *)
(* No one would really use it (hopefully) *)
VAR
this, that: ADDRESS;
BEGIN
this := list;
WHILE (this <> NIL) DO
that := Next(this);
WHILE (that <> NIL) DO
IF Compare(this, that) = GreaterThan THEN
Swap(this, that);
END (*If*);
that := Next(that);
END (*While*);
this := Next(this);
END (*While*);
END Sort;
END sort.
-=-=-=-=-
MODULE trySort;
IMPORT InOut, sort;
FROM SYSTEM IMPORT ADDRESS;
FROM Storage IMPORT ALLOCATE;
TYPE
ListPtr = POINTER TO ListRcd;
ListRcd = RECORD
val: CARDINAL;
next: ListPtr;
END (*List record*);
VAR
list, first: ListPtr;
PROCEDURE Comp (a, b: ADDRESS): sort.Result;
BEGIN
IF ListPtr(a)^.val < ListPtr(b)^.val THEN
RETURN sort.LessThan;
ELSIF ListPtr(a)^.val > ListPtr(b)^.val THEN
RETURN sort.GreaterThan;
ELSE (*IF ListPtr(a)^.val = ListPtr(b)^.val THEN*)
RETURN sort.Equal;
END (*Else*);
END Comp;
PROCEDURE Swap (a, b: ADDRESS);
VAR
tmp: CARDINAL;
BEGIN
tmp := ListPtr(a)^.val;
ListPtr(a)^.val := ListPtr(b)^.val;
ListPtr(b)^.val := tmp;
END Swap;
PROCEDURE Next(a: ADDRESS): ADDRESS;
BEGIN
RETURN ListPtr(a)^.next;
END Next;
BEGIN
NEW(first); list := first; list^.val := 9;
NEW(list^.next); list := list^.next; list^.val := 5;
NEW(list^.next); list := list^.next; list^.val := 3;
list^.next := NIL;
sort.Sort(first, Comp, Swap, Next);
list := first;
WHILE list <> NIL DO
InOut.WriteCard(list^.val, 2);
list := list^.next;
END (*While*);
InOut.WriteLn;
END trySort.
-=-=-=-=-=-
Output:
3 5 9
- Bill Seurer IBM: seurer@rchland Prodigy: CNSX71A
Rochester, MN Internet: seurer@rchland.vnet.ibm.comJon.Guthrie@p25.f506.n106.z1.fidonet.org (Jon Guthrie) (03/22/91)
On a message of 19-Mar-91, George Emery (1:105/6.0) Said: > Making use of procedure variables to set the sort method is old hat to > most folks. What I'm trying to figure (can it even be done?) is a way > to allow a procedure to sort different types of records. In C, this sort of thing is a piece of cake because of the looser typing. Unfortunately, there's no way to define the type of an array argument at runtime. So, unless you're willing to put up with a hideously ugly kludge, there's no way to write a general array sort in Modula-2. However... It IS possible to write a generic linked-list sorting routine in M-2. I, and others, have done so in C and I'm willing to convert the C code that I have into M-2. Of course, none of this does you the slightest bit of good if you don't want to sort linked lists. (You don't say what you want to sort, but most people prefer to deal with arrays.) -- uucp: uunet!m2xenix!puddle!106!506.25!Jon.Guthrie Internet: Jon.Guthrie@p25.f506.n106.z1.fidonet.org
George.Emery@p0.f6.n105.z1.fidonet.org (George Emery) (03/29/91)
Actually, I do prefer to use linked lists (some form of psychological limitation as a result of previous encounters with FORTH and LISP), particularly if I'm sorting large records. GE -- uucp: uunet!m2xenix!puddle!6.0!George.Emery Internet: George.Emery@p0.f6.n105.z1.fidonet.org
Jon.Guthrie@p25.f506.n106.z1.fidonet.org (Jon Guthrie) (04/03/91)
On a message of 28-Mar-91, George Emery (1:105/6.0) Said: > Actually, I do prefer to use linked lists (some form of psychological > limitation as a result of previous encounters with FORTH and LISP), > particularly if I'm sorting large records. Well, I tell you what. I've got the StonyBrook compiler on order and when it arrives, I'll recode the linked-list sort in Modula-2. It won't go out before this weekend (which is okay considering I'm so busy at work I won't have a chance to get to it before then) but I'll try and remember to post it. One thing though: I had completely forgotten about getting the generic pointer (of type ADDRESS, that is) to an array and passing THAT to the sorting routine. If you do that, then you can write a general sorting routine for arrays in Modula. (I simply had never thought of that before.) -- uucp: uunet!m2xenix!puddle!106!506.25!Jon.Guthrie Internet: Jon.Guthrie@p25.f506.n106.z1.fidonet.org