TopoSortTest.Mesa
Last tweaked by Mike Spreitzer on May 18, 1988 10:03:35 am PDT
DIRECTORY Basics, List, Random, TopoSort;
TopoSortTest:
CEDAR
PROGRAM
IMPORTS Basics, List, Random, TopoSort
=
BEGIN
LORA: TYPE ~ LIST OF REF ANY;
Node: TYPE ~ REF NodePrivate;
NodePrivate:
TYPE ~
RECORD [
x, y, id: INT,
prev, next: Node];
IntPair: TYPE ~ RECORD [x, y, id: INT];
first: Node ← NIL;
loraFirst: LORA ← NIL;
count: INT ← 0;
Clear: PROC ~ {first ← NIL; loraFirst ← NIL; count ← 0};
Add:
PROC [x, y, id:
INT] ~ {
n: Node ~ NEW [NodePrivate ← [x, y, id, NIL, first]];
n.prev ← IF first=NIL THEN n ELSE first.prev;
n.prev.next ← n;
n.next.prev ← n;
first ← n;
loraFirst ← CONS[NEW[IntPair ← [x, y, id]], loraFirst];
count ← count + 1;
RETURN};
Adds:
PROC [n, scope, seed:
INT, easy:
BOOL] ~ {
divisor: INT ~ INT.LAST/scope;
rs: Random.RandomStream ~ Random.Create[range: scope*divisor, seed: seed];
FOR i:
INT
DECREASING
IN [1 .. n]
DO
x: INT ~ rs.NextInt/divisor;
Add[x, IF easy THEN x ELSE rs.NextInt/divisor, i];
ENDLOOP;
RETURN};
SortRing:
PROC
RETURNS [cost:
INT ← 0] ~ {
IF first#
NIL
THEN {
Handle: TYPE ~ TopoSort.Handle;
last: Node ← first.prev;
GetLink:
PROC [from: Handle]
RETURNS [Handle] ~ {
n: Node ~ NARROW[from];
IF n=NIL THEN RETURN [first];
IF n=last THEN RETURN [NIL];
RETURN [n.next]};
SetLink:
PROC [from, to: Handle] ~ {
nf: Node ~ NARROW[from];
nt: Node ~ NARROW[to];
IF nf=NIL THEN first ← nt ELSE nf.next ← nt;
IF nt=NIL THEN last ← nf ELSE nt.prev ← nf;
RETURN};
Compare:
PROC [a, b: Handle]
RETURNS [TopoSort.PartialComparison] ~ {
na: Node ~ NARROW[a];
nb: Node ~ NARROW[b];
cx: Basics.Comparison ~ Basics.CompareInt[na.x, nb.x];
cy: Basics.Comparison ~ Basics.CompareInt[na.y, nb.y];
cost ← cost+1;
IF cx=cy THEN RETURN [LOOPHOLE[cx]];
RETURN [incomparable]};
TopoSort.ListSort[NIL, NIL, GetLink, SetLink, Compare];
SetLink[last, first];
RETURN}};
SortList2:
PROC
RETURNS [cost:
INT ← 0] ~ {
IF first#
NIL
THEN {
GetLink:
PROC [from:
REF
ANY]
RETURNS [
REF
ANY] ~ {
n: LORA ~ NARROW[from];
IF n=NIL THEN RETURN [loraFirst];
RETURN [n.rest]};
SetLink:
PROC [from, to:
REF
ANY] ~ {
nf: LORA ~ NARROW[from];
nt: LORA ~ NARROW[to];
IF nf=NIL THEN loraFirst ← nt ELSE nf.rest ← nt;
RETURN};
Compare:
PROC[ref1:
REF
ANY, ref2:
REF
ANY]
RETURNS [TopoSort.PartialComparison] ~ {
n1: LORA ~ NARROW[ref1];
n2: LORA ~ NARROW[ref2];
r1: REF IntPair ~ NARROW[n1.first];
r2: REF IntPair ~ NARROW[n2.first];
cx: Basics.Comparison ~ Basics.CompareInt[r1.x, r2.x];
cy: Basics.Comparison ~ Basics.CompareInt[r1.y, r2.y];
cost ← cost+1;
IF cx#cy THEN ERROR;
RETURN [LOOPHOLE[cx]]};
TopoSort.ListSort[NIL, NIL, GetLink, SetLink, Compare];
RETURN}};
SortList1:
PROC
RETURNS [cost:
INT ← 0] ~ {
IF first#
NIL
THEN {
Compare:
PROC[ref1:
REF
ANY, ref2:
REF
ANY]
RETURNS [Basics.Comparison] ~ {
r1: REF IntPair ~ NARROW[ref1];
r2: REF IntPair ~ NARROW[ref2];
cx: Basics.Comparison ~ Basics.CompareInt[r1.x, r2.x];
cy: Basics.Comparison ~ Basics.CompareInt[r1.y, r2.y];
cost ← cost+1;
IF cx#cy THEN ERROR;
RETURN [cx]};
loraFirst ← List.Sort[loraFirst, Compare];
RETURN}};
Check:
PROC ~ {
seen: INT ← 0;
na: Node ← first;
IF na=NIL THEN {IF count#0 THEN ERROR; RETURN};
DO
noteq: BOOL ← FALSE;
FOR nb: Node ← na.next, nb.next
WHILE nb#first
DO
cx: Basics.Comparison ~ Basics.CompareInt[na.x, nb.x];
cy: Basics.Comparison ~ Basics.CompareInt[na.y, nb.y];
eq: BOOL ~ cx=equal AND cy=equal;
IF cx=equal
AND cy=equal
THEN {
IF noteq THEN ERROR--didn't bunch equal values--;
IF nb.id < na.id THEN ERROR--not stable--;
}
ELSE noteq ← TRUE;
IF cx#cy THEN LOOP;
IF cx=greater THEN ERROR;
ENDLOOP;
na ← na.next;
seen ← seen + 1;
IF na=first THEN EXIT;
ENDLOOP;
IF seen # count THEN ERROR};
Comparem:
PROC ~ {
n: Node ← first;
l: LORA ← loraFirst;
DO
r: REF IntPair ~ NARROW[l.first];
IF r.id # n.id THEN ERROR;
n ← n.next;
l ← l.rest;
IF (l=NIL) # (n=first) THEN ERROR;
IF l=NIL THEN EXIT;
ENDLOOP;
RETURN};
ListForm: TYPE ~ LIST OF IntPair;
Report:
PROC [from, thru: Node ←
NIL, count:
CARDINAL ← 60000]
RETURNS [l: ListForm] ~ {
l ← NIL;
IF from=NIL THEN from ← first;
IF first=NIL THEN RETURN;
{tail: ListForm ← l ← LIST[[0, 0, 0]];
n: Node ← from;
WHILE count#0
DO
tail ← tail.rest ← CONS[[n.x, n.y, n.id], NIL];
IF n=thru THEN EXIT;
n ← n.next;
count ← count - 1;
IF n=from THEN EXIT;
ENDLOOP;
RETURN [l.rest]}};
END.