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]; 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 }; 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. ZRopeListImpl.mesa This module provides some utilities for manipulating lists of ropes. Last Edited by: Stewart.pa, December 16, 1983 11:21 am Predicates. Constructors. These procedures do not disturb their arguments. Destructive Constructors. destructivell2 reverses list. copied from Lisp DREVERSE function Miscellaneous. Sorting. 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. 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). make each pair of consecutive elements of l into a sorted list of length 2, then merge it into lists. 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). try to make a # NIL. a # NIL OR x > xMax. a#NIL AND b#NIL Э╩ ╠Ц "Cedar" styleШheadЩIbodyЪЬDЩDLЪЬ6Щ6code2Ъ╧k Ш MЪЬЭЬШMЪЬЭЬЭЬШ"MЪЬ Ш ЧЧMЪЬЭЬЭШMЪЭЬШЪЭЬШMЪЭШMЪЭЬ ШЧЪЬЩЪ╧n ЬЭЬЭЬ ЭЬЭЬЭЬЭЬЭЬЭЬЭЬШYJЪЭЬ ЭЬЭЬЭЬШJЪЭЬЭЬЭЬЭЬЭЬЭЬЭЬШ+ЪЭЬЭЬЭШJЪ ЭЬЭЬЭЬЭЬЭЬШJЪЭЬ&ЭЬЭЬЭЬЭЬЭЬШEJШ JШ JЪЭЬШЧJЪЭЬЭЬШMШЧЪЮЬЭЬЭЬЭЬЭЬЭЬ ЭЬЭЬЭЬЭЬЭЬШ_ЪЭЬЭЬЭШMЪЭЬ!ЭЬЭЬЭЬШ5MШMЪЭЬШЧMЪЭЬЭЬШMШЧЧЪЬ Щ LЩ0ЪЮЬЭЬЭЬ ЭЬЭЬЭЬЭЬЭЬЭЬЭЬШTJЪ ЬЭЬЭЬЭЬЭЬШJШ JЪЭЬЭЬЭЬЭЬШJЪЬЭЬШJШЪЭЬЭЬЭШJЪЬ ЭЬШ JШJЪЭЬШЧJЪЭЬШMШЧJШЪЮЬЭЬЭЬЭЬЭЬЭЬ ЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШyJЪ ЬЭЬЭЬЭЬЭЬШЪЭЬЭЬЭШЪЭЬЭЬ!ЭЬШ-ЪЭЬЭЬЭЬШJЪЬЭЬ ЭЬШJЪЬШJЪЬШЧЪЭЬШJЪЬ ЭЬШ"JЪЬШJЪЬШЧJЪЬШЧJШJЪЭЬШ ЧJЪЬ╧cШЧЪЮЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШYЪЭЬЭЬЭШJЪЬЭЬШJШJЪЭЬШЧMШЧЧЪЬЩЪЮЬЭЬЭЬ ЭЬЭЬЭЬЭЬЭЬЭЬЭЬШUMЪЭЬЭЬЭЬЭЬШMЪЭЬЭЬЭЬЭЬШMШ ЪЭЬЭЬЭШMШ MЪЭЬШЧMШ MШЧЪЮЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШOJЪЬ@Щ@Ъ ЬЭЬЭЬЭЬЭЬШ$JЪ ЭЬЭЬЭЬЭЬЭЬШJШ ЪЭЬ ЭЬЭШJЪЬ Ш JЪЬ Ш JЪЬШJЪЭЬШЧJЪЭЬШЧMШЧЪЮЬЭЬЭЬЭЬЭЬЭЬ ЭЬЭЬЭЬЭЬЭЬЭЬЭЬШoJЪ ЬЭЬЭЬЭЬЭЬШJШ ЪЭЬЭЬЭШЪЭЬЭЬШ&JЪ ЭЬЭЬЭЬЭЬ ЯШ@JШJЪЭЬШ JЪЬШЧJШJШJЪЭЬШЧJЪЭЬШMШЧЧЪЬЩЪЮЬЭЬЭЬЭЬЭЬЭЬЭЬ ЭЬ ШKЪЭЬЭЬЭШMШMШMЪЭЬШЧMЪЭЬ ШMШЧЪЮЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШFЪЭЬЭЬЭШMЪЬШMШMЪЭЬШЧMШЧЧЪЬЩЪЮЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШeJЪЬXЩXJЪЬQЩQJЪЬЩJЪЬЭЬЭЬЭЬШ!JЪ Ь ЭЬЭЬЭЬЭЬЭЬЭЬШ0JЪЬЭЬЯ.ШBЪЬЭЬ ЭЬЭЬЭЬЭЬЭЬЭЬШ7JЪЬQЩQJЪЬ<Щ