<> <> <> DIRECTORY Basics USING [Comparison], Rope USING [Compare, Equal, ROPE], RopeList; RopeListImpl: CEDAR PROGRAM IMPORTS Rope EXPORTS RopeList = BEGIN OPEN RopeList; <> 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]; }; <> <> 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; }; <> 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] = { <> 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]; }; <> 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; }; <> Sort: PUBLIC PROC [list: LIST OF Rope.ROPE, compareProc: CompareProc] RETURNS [LIST OF Rope.ROPE] = { <> <> <> 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]; <> <<4 or NIL, lists[2] is a sorted list of length 8 or NIL, etc.>> <> x: CARDINAL; --[0..max] xMax: CARDINAL _ 0; --[0..max) <> <> 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; <> <> <> x _ 0; IF a = NIL THEN { <> UNTIL (lists[x] # NIL OR x = xMax) DO x _ x+1 ENDLOOP; a _ lists[x]; lists[x] _ NIL; x _ x+1 }; < xMax.>> UNTIL x > xMax DO IF (b _ lists[x]) # NIL THEN { lists[x] _ NIL; mergeTo _ mergeToCons; DO <> 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. <<>>