WorkDown:
PROC [start: Handle, limit:
LNAT]
RETURNS [head, tail, rest: Handle, done:
LNAT] ~ {
halimit: LNAT ~ limit/2;
rest ← GetLink[head ← tail ← start];
done ← 1;
IF rest=omega THEN RETURN;
rest ← GetLink[tail ← rest];
IF Compare[head, tail]=greater THEN {x: Handle ~ head; head ← tail; tail ← x; SetLink[head, tail]; SetLink[tail, rest]};
done ← 2;
WHILE rest#omega
AND done<=halimit
DO
leftend: Handle ~ rest;
heads: ARRAY Side OF Handle ← ALL[head];
tails: ARRAY Side OF Handle ← ALL[tail];
counts: ARRAY Side OF NATURAL ← ALL[done];
first: BOOL ← TRUE;
Output:
PROC [h, t: Handle] ~ {
IF first THEN {first ← FALSE; head ← h} ELSE SetLink[tail, h];
tail ← t;
RETURN};
[heads[r], tails[r], rest, counts[r]] ← WorkDown[rest, done];
done ← counts[l] + counts[r];
WHILE counts[l]#0
AND counts[r]#0
DO
rn: Handle ~ GetLink[heads[r]];
prev: Handle ← alpha;
FOR hl: Handle ← heads[l], GetLink[hl]
WHILE hl#leftend
DO
SELECT Compare[hl, heads[r]]
FROM
less, equal => {
ln: Handle ~ GetLink[hl];
Output[hl, hl];
IF prev=alpha THEN heads[l] ← ln ELSE SetLink[prev, ln];
IF hl=tails[l] THEN tails[l] ← prev;
counts[l] ← counts[l]-1};
greater => {Output[heads[r], heads[r]]; EXIT};
incomparable => prev ← hl;
ENDCASE => ERROR;
REPEAT FINISHED => Output[heads[r], heads[r]];
ENDLOOP;
counts[r] ← counts[r]-1;
heads[r] ← rn;
ENDLOOP;
IF counts[l]#0 THEN Output[heads[l], tails[l]];
IF counts[r]#0 THEN Output[heads[r], tails[r]];
IF first THEN ERROR;
SetLink[tail, rest];
ENDLOOP;
RETURN};