<<>> <> <> <> <> <> 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]; }; <> <> Cons: PUBLIC PROC [list: LIST OF Rope.ROPE, r: Rope.ROPE] RETURNS [LIST OF Rope.ROPE] = { RETURN[CONS[r, list]]; }; 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]; }; CopyTopList: PUBLIC PROC [list: LIST OF Rope.ROPE] RETURNS [LIST OF Rope.ROPE] = { RETURN[Append[list, NIL]]; }; <> 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. <<>>