RosaryTest.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Michael Plass, January 29, 1986 5:52:42 pm PST
DIRECTORY Rosary, Atom, Random;
RosaryTest: CEDAR PROGRAM
IMPORTS Rosary, Atom, Random ~ BEGIN
ROSARY: TYPE ~ Rosary.ROSARY;
list: LIST OF REF ← CreateList[11];
CreateList: PROC [n: INT] RETURNS [list: LIST OF REF ← NIL] ~ {
i: LONG CARDINAL ← 0;
p: PROC[atom: ATOM] ~ {
IF INT[i] >= n THEN RETURN;
IF i MOD 11 = 0 THEN {
FOR j: LONG CARDINAL IN [0..4] DO
list ← CONS[atom, list];
i ← i + 1;
ENDLOOP;
}
ELSE {list ← CONS[atom, list]; i ← i + 1}
};
UNTIL INT[i] >= n DO
Atom.MapAtoms[p];
ENDLOOP;
};
ConsecMap: PROC [s: Rosary.Segment, action: Rosary.RunActionType] RETURNS [quit: BOOLEAN] ~ {
refInt: REF INT ~ NARROW[NARROW[s.base, REF Rosary.RosaryRep.object].data];
start: INT ~ refInt^+s.start;
FOR i: INT IN [start..start+s.size) DO
IF action[NEW[INT ← i], 1] THEN RETURN [TRUE];
ENDLOOP;
RETURN [FALSE];
};
Consec: PROC [start, size: INT] RETURNS [ROSARY] ~ {
RETURN [Rosary.FromObject[size, NEW[INT←start], ConsecMap]]
};
Check: PROC [segment: Rosary.Segment, list: LIST OF REF] ~ {
l: LIST OF REF ← list;
action: Rosary.ActionType ~ {
IF item # l.first THEN ERROR;
l ← l.rest;
};
[] ← Rosary.Map[segment, action];
IF l # NIL THEN ERROR;
};
Equal: PROC [r1, r2: ROSARY] RETURNS [BOOL] ~ {
i: INT ← 0;
size: INT ← Rosary.Size[r1];
IF size # Rosary.Size[r2] THEN RETURN [FALSE];
WHILE i # size DO
b1: Rosary.Buffer ← Rosary.FetchBuffer[r1, i];
b2: Rosary.Buffer ← Rosary.FetchBuffer[r2, i];
FOR j: NAT IN [0..b1.count) DO
IF b1.a[j] # b2.a[j] THEN RETURN [FALSE];
ENDLOOP;
i ← i + b1.count;
ENDLOOP;
RETURN [TRUE]
};
CheckBuffer: PROC [rosary: ROSARY, list: LIST OF REF] ~ {
l: LIST OF REF ← list;
index: INT ← 0;
WHILE index < Rosary.Size[rosary] DO
b: Rosary.Buffer ← Rosary.FetchBuffer[rosary, index];
IF b.count = 0 THEN ERROR;
FOR i: NAT IN [0..b.count) DO
IF b.a[i] # l.first THEN ERROR;
l ← l.rest;
ENDLOOP;
index ← index + b.count;
ENDLOOP;
};
CheckControl: PROC [list1, list2: LIST OF REF] ~ {
l1: LIST OF REF ← list1;
l2: LIST OF REF ← list2;
WHILE l1 # NIL DO
IF l1.first # l2.first THEN ERROR;
l1 ← l1.rest;
l2 ← l2.rest;
ENDLOOP;
};
FromList: PROC [list: LIST OF REF] RETURNS [rosary: ROSARY] ~ {
rosary ← NIL;
FOR l: LIST OF REF ← list, l.rest UNTIL l = NIL DO
rosary ← Rosary.Concat[rosary, Rosary.FromItem[l.first]];
ENDLOOP;
};
Run: PROC [ops: INT, paranoid: BOOL ← FALSE] ~ {
rosary: ROSARY ← Rosary.FromList[list];
Check[[rosary], list];
FOR i: INT IN [0..ops) DO
s1, e1, s2, e2, s3, e3, tail: LIST OF REF;
a1: INT ← Random.ChooseInt[NIL, 0, rosary.Size];
a2: INT ← Random.ChooseInt[NIL, 0, rosary.Size];
IF a1 > a2 THEN {t: INT ~ a1; a1 ← a2; a2 ← t};
[s1, e1, tail] ← SplitOff[list, a1];
[s2, e2, tail] ← SplitOff[tail, a2-a1];
[s3, e3, tail] ← SplitOff[tail, rosary.Size-a2];
IF i MOD 2 = 0 THEN {
list ← Join[s2, e2, s1, e1, s3];
rosary ← Rosary.Cat[Rosary.Substr[rosary, a1, a2-a1], Rosary.Substr[rosary, 0, a1], Rosary.Substr[rosary, a2, rosary.Size-a2]];
}
ELSE {
list ← Join[s1, e1, s3, e3, s2];
rosary ← Rosary.Cat[Rosary.Substr[rosary, 0, a1], Rosary.Substr[rosary, a2, rosary.Size-a2], Rosary.Substr[rosary, a1, a2-a1]];
};
IF paranoid THEN Check[[rosary], list];
ENDLOOP;
Check[[rosary], list];
};
SplitOff: PROC [list: LIST OF REF, n: INT] RETURNS [first, last, tail: LIST OF REF] ~ {
IF n = 0 THEN RETURN [NIL, NIL, list];
first ← last ← list;
FOR i: INT IN [0..n-1) DO last ← last.rest ENDLOOP;
tail ← last.rest;
last.rest ← NIL;
};
Join: PROC [s1, e1, s2, e2, s3: LIST OF REF] RETURNS [LIST OF REF] ~ {
IF s1 # NIL THEN {e1.rest ← s2; s2 ← s1; IF e2 = NIL THEN e2 ← e1};
IF s2 # NIL THEN {e2.rest ← s3; s3 ← s2};
RETURN [s3]
};
Reverse: PROC [r: ROSARY] RETURNS [ROSARY] ~ {
IF Rosary.Size[r] < 2 THEN RETURN [r]
ELSE RETURN [Rosary.FromObject[size: Rosary.Size[r], data: r, mapRuns: ReverseMap, substr: ReverseSubstr]]
};
ReverseMap: Rosary.MapRunsProc ~ {
base: ROSARY ~ NARROW[NARROW[s.base, REF Rosary.RosaryRep.object].data];
FOR i: INT DECREASING IN [s.start..s.size) DO
IF Rosary.MapRuns[[base, i, 1], action] THEN RETURN [TRUE];
ENDLOOP;
RETURN [FALSE];
};
ReverseSubstr: Rosary.SubstrProc ~ {
data: ROSARY ~ NARROW[NARROW[base, REF Rosary.RosaryRep.object].data];
RETURN [Reverse[Rosary.Substr[data, data.size-(start+len), len]]]
};
END.