RopeListImpl.mesa
This module provides some utilities for manipulating lists of ropes.
Last Edited by: Stewart.pa, December 16, 1983 11:21 am
DIRECTORY
Basics USING [Comparison],
Rope USING [Compare, Equal, ROPE],
RopeList;
RopeListImpl: CEDAR PROGRAM
IMPORTS Rope
EXPORTS RopeList =
BEGIN
OPEN RopeList;
Predicates.
EqualLists: PUBLIC PROC [l1, l2: LIST OF Rope.ROPE, case: BOOL ← TRUE] RETURNS [BOOL] = {
IF l1 = l2 THEN RETURN[TRUE];
IF l1 = NIL OR l2 = NIL THEN RETURN[FALSE];
UNTIL l1 = NIL DO
IF l2 = NIL THEN RETURN[FALSE];
IF Rope.Equal[l1.first, l2.first, case] THEN NULL ELSE RETURN[FALSE];
l1 ← l1.rest;
l2 ← l2.rest;
ENDLOOP;
RETURN[l2 = NIL];
};
Memb: PUBLIC PROC [list: LIST OF Rope.ROPE, r: Rope.ROPE, case: BOOL ← TRUE] RETURNS [BOOL] = {
WHILE list # NIL DO
IF Rope.Equal[list.first, r, case] THEN RETURN[TRUE];
list ← list.rest;
ENDLOOP;
RETURN[FALSE];
};
Constructors.
These procedures do not disturb their arguments.
Append: PUBLIC PROC [l1, l2: LIST OF Rope.ROPE] RETURNS [val: LIST OF Rope.ROPE] = {
z: LIST OF Rope.ROPE ← NIL;
val ← l2;
IF l1 = NIL THEN RETURN[val];
val ← CONS[l1.first, val];
z ← val;
UNTIL (l1 ← l1.rest) = NIL DO
z.rest ← CONS[l1.first, z.rest];
z ← z.rest;
ENDLOOP;
RETURN[val];
};
Remove: PUBLIC PROC [list: LIST OF Rope.ROPE, r: Rope.ROPE, case: BOOL ← TRUE] RETURNS [val: LIST OF Rope.ROPE ← NIL] = {
z: LIST OF Rope.ROPE ← NIL;
UNTIL list = NIL DO
IF NOT Rope.Equal[list.first, r, case] THEN {
IF val = NIL THEN {
val ← CONS[list.first, NIL];
z ← val;
}
ELSE {
z.rest ← CONS[list.first, z.rest];
z ← z.rest;
};
};
list ← list.rest;
ENDLOOP;  
}; -- of Remove  
Reverse: PUBLIC PROC [list: LIST OF Rope.ROPE] RETURNS [val: LIST OF Rope.ROPE ← NIL] = {
UNTIL list = NIL DO
val ← CONS[list.first, val];
list ← list.rest;
ENDLOOP;
};
Destructive Constructors.
DAppend: PUBLIC PROC [l1, l2: LIST OF Rope.ROPE] RETURNS [val: LIST OF Rope.ROPE] = {
IF l1 = NIL THEN RETURN[l2];
IF l2 = NIL THEN RETURN[l1];
val ← l1;
WHILE l1.rest # NIL DO
l1 ← l1.rest;
ENDLOOP;
l1.rest ← l2;
};
DReverse: PUBLIC PROC [list: LIST OF Rope.ROPE] RETURNS [LIST OF Rope.ROPE] = {
destructivell2 reverses list. copied from Lisp DREVERSE function
l1, l2, l3: LIST OF Rope.ROPE ← NIL;
IF list = NIL THEN RETURN[NIL];
l3 ← list;
UNTIL (l1 ← l3) = NIL DO
l3 ← l3.rest;
l1.rest ← l2;
l2 ← l1;
ENDLOOP;
RETURN[l2];
};
DRemove: PUBLIC PROC [list: LIST OF Rope.ROPE, r: Rope.ROPE, case: BOOL ← TRUE] RETURNS [LIST OF Rope.ROPE] = {
l, l1: LIST OF Rope.ROPE ← NIL;
l ← list;
UNTIL l = NIL DO
IF Rope.Equal[l.first, r, case] THEN {
IF l1 = NIL THEN RETURN[l.rest]; -- ref was first object on list
l1.rest ← l.rest;
RETURN[list];
};
l1 ← l;
l ← l.rest;
ENDLOOP;
RETURN [list];
};
Miscellaneous.
Length: PUBLIC PROC [list: LIST OF Rope.ROPE] RETURNS [length: INT ← 0] = {
WHILE list # NIL DO
length ← length + 1;
list ← list.rest;
ENDLOOP;
RETURN[length];
};
Map: PUBLIC PROC [list: LIST OF Rope.ROPE, proc: PROC [Rope.ROPE]] = {
WHILE list # NIL DO
proc[list.first];
list ← list.rest;
ENDLOOP;
};
Sorting.
Sort: PUBLIC PROC [list: LIST OF Rope.ROPE, compareProc: CompareProc] RETURNS [LIST OF Rope.ROPE] = {
The sort is destructive and NOT stable, that is, the relative positions in the result of
nodes with equal keys is unpredictible. For a nondestructive sort, copy l first.
The sort does one CONS.
a, b, mergeTo: LIST OF Rope.ROPE;
mergeToCons: LIST OF Rope.ROPE = CONS[NIL, NIL];
max: CARDINAL = 22; --number of bits in word-address space minus 2
lists: ARRAY [0..max) OF LIST OF Rope.ROPE ← ALL [NIL];
lists[0] is a sorted list of length 2 or NIL, lists[1] is a sorted list of length
4 or NIL, lists[2] is a sorted list of length 8 or NIL, etc.
When Sort returns, lists = ALL [NIL] again (we do some extra work to assure this).
x: CARDINAL; --[0..max]
xMax: CARDINAL ← 0; --[0..max)
make each pair of consecutive elements of l into a sorted list of length 2,
then merge it into lists.
UNTIL (a ← list) = NIL OR (b ← a.rest) = NIL DO
list ← b.rest;
IF compareProc[a.first, b.first] = less THEN {
a.rest ← b;
b.rest ← NIL;
}
ELSE {
b.rest ← a;
a.rest ← NIL;
a ← b;
};
x ← 0;
DO
IF (b ← lists[x]) = NIL THEN {
lists[x] ← a; EXIT }
ELSE { --merge (equal length) lists a and b
lists[x] ← NIL;
mergeTo ← mergeToCons;
DO --assert a#NIL, b#NIL
IF compareProc[a.first, b.first] = less THEN {
mergeTo.rest ← a; mergeTo ← a;
IF (a ← a.rest) = NIL THEN { mergeTo.rest ← b; EXIT } }
ELSE { 
mergeTo.rest ← b; mergeTo ← b;
IF (b ← b.rest) = NIL THEN { mergeTo.rest ← a; EXIT } }
ENDLOOP;
a ← mergeToCons.rest;
x ← x+1;
IF x > xMax AND (xMax ← x) = max THEN ERROR }
ENDLOOP;
ENDLOOP;
xMax now contains the largest x such that lists[x] # NIL.
if l's length was even, a = NIL; if l's length was odd, a = single element list.
merge a and elements of lists into result (held in a).
x ← 0;
IF a = NIL THEN {
try to make a # NIL.
UNTIL (lists[x] # NIL OR x = xMax) DO x ← x+1 ENDLOOP;
a ← lists[x]; lists[x] ← NIL; x ← x+1 };
a # NIL OR x > xMax.
UNTIL x > xMax DO
IF (b ← lists[x]) # NIL THEN {
lists[x] ← NIL;
mergeTo ← mergeToCons;
DO
a#NIL AND b#NIL
IF compareProc[a.first, b.first] = less THEN {
mergeTo.rest ← a; mergeTo ← a;
IF (a ← a.rest) = NIL THEN { mergeTo.rest ← b; EXIT } }
ELSE { 
mergeTo.rest ← b; mergeTo ← b;
IF (b ← b.rest) = NIL THEN { mergeTo.rest ← a; EXIT } }
ENDLOOP;
a ← mergeToCons.rest };
x ← x+1;
ENDLOOP;
RETURN [a]
};
Compare: PUBLIC CompareProc = {
RETURN [Rope.Compare[s1: r1, s2: r2, case: TRUE]];
};
IgnoreCase: PUBLIC CompareProc ={
RETURN [Rope.Compare[s1: r1, s2: r2, case: FALSE]];
};
END.