-- edited by Teitelman, December 14, 1982 3:45 pm DIRECTORY Environment USING [Comparison], RTBasic USING [Type, nullType] ; List: CEDAR DEFINITIONS = BEGIN AList: TYPE = LIST OF DottedPair; DottedPair: TYPE = REF DottedPairNode; DottedPairNode: TYPE = RECORD [key, val: REF ANY]; CompareProc: TYPE = PROC[ref1: REF ANY, ref2: REF ANY] RETURNS [Comparison]; Comparison: TYPE = Environment.Comparison; NotATail: SIGNAL [list, tailOfList: LIST OF REF ANY] RETURNS[LIST OF REF ANY]; -- raised by LDiff NotThatLong: ERROR [list: LIST OF REF ANY, n: INT]; -- raised by NthElement IsAList: PROC [ref: REF ANY _ NIL, underType: RTBasic.Type _ RTBasic.nullType] RETURNS [result: BOOLEAN]; IsAListOfRefAny: PROC [ref: REF ANY, underType: RTBasic.Type _ RTBasic.nullType] RETURNS [result: BOOLEAN, list: LIST OF REF ANY]; EqLists: PUBLIC PROC [l1, l2: LIST OF REF ANY, compareLists: BOOLEAN _ FALSE] RETURNS [BOOLEAN] ; Memb: PROC [ref: REF ANY, list: LIST OF REF ANY] RETURNS[BOOLEAN] = INLINE {UNTIL list = NIL DO IF list.first = ref THEN RETURN[TRUE]; list _ list.rest; ENDLOOP; RETURN[FALSE]}; Member: PROC [ref: REF ANY, list: LIST OF REF ANY] RETURNS[BOOLEAN]; Cons: PROC [ref: REF ANY, list: LIST OF REF ANY] RETURNS [LIST OF REF ANY] = INLINE {RETURN[Zone.CONS[ref, list]]}; Append: PROC[l1: LIST OF REF ANY, l2: LIST OF REF ANY _ NIL] RETURNS [LIST OF REF ANY]; -- if l2 is NIL, copies top level of l1. CopyTopList: PROC[list: LIST OF REF ANY] RETURNS [LIST OF REF ANY] = INLINE {RETURN[Append[list]]}; Remove: PROC[ref: REF ANY, list: LIST OF REF ANY] RETURNS[LIST OF REF ANY]; Reverse: PROC [list: LIST OF REF ANY] RETURNS[LIST OF REF ANY]; Union: PROC [l1, l2: LIST OF REF ANY] RETURNS[LIST OF REF ANY]; Intersection: PROC [l1, l2: LIST OF REF ANY] RETURNS[LIST OF REF ANY]; ListDifference: PROC [l1, l2: LIST OF REF ANY] RETURNS[LIST OF REF ANY]; -- all elements in l1 not in l2 LDiff: PROC [list, tailOfList: LIST OF REF ANY] RETURNS[LIST OF REF ANY]; Nconc: PROC [l1, l2: LIST OF REF ANY] RETURNS[LIST OF REF ANY]; -- like Append Nconc1: PROC [list: LIST OF REF ANY, ref: REF ANY] RETURNS[LIST OF REF ANY] = INLINE { z: LIST OF REF ANY _ list; IF z = NIL THEN RETURN[Cons[ref, NIL]]; UNTIL z.rest = NIL DO z _ z.rest; ENDLOOP; z.rest _ Cons[ref, NIL]; RETURN[list]; }; DRemove: PROC [ref: REF ANY, list: LIST OF REF ANY] RETURNS[LIST OF REF ANY]; -- like Remove DReverse: PROC [list: LIST OF REF ANY] RETURNS[LIST OF REF ANY]; -- like Reverse DSubst: PROC [new, old: REF ANY, expr: LIST OF REF ANY] RETURNS[LIST OF REF ANY] ; -- like Subst. NthTail: PROC[list: LIST OF REF ANY, n: INT] RETURNS[LIST OF REF ANY]; NthElement: PROC[list: LIST OF REF ANY, n: INT] RETURNS[REF ANY]; Cdr: PROC[list: LIST OF REF ANY] RETURNS[LIST OF REF ANY] = INLINE {RETURN[IF list = NIL THEN NIL ELSE list.rest]}; Cddr: PROC[list: LIST OF REF ANY] RETURNS[LIST OF REF ANY] = INLINE {RETURN[IF list = NIL OR list.rest = NIL THEN NIL ELSE list.rest.rest]}; Car: PROC[list: LIST OF REF ANY] RETURNS[REF ANY] = INLINE {RETURN[IF list = NIL THEN NIL ELSE list.first]}; Cadr: PROC[list: LIST OF REF ANY] RETURNS[REF ANY] = INLINE {RETURN[IF list = NIL OR list.rest = NIL THEN NIL ELSE list.rest.first]}; Assoc: PROC [key: REF ANY, aList: AList] RETURNS[REF ANY]; DotCons: PROC [key, val: REF ANY] RETURNS [DottedPair]; PutAssoc: PROC [key: REF ANY, val: REF ANY, aList: AList] RETURNS[AList]; Length: PROC [list: LIST OF REF ANY] RETURNS[INT]; Map: PROC [list: LIST OF REF ANY, proc: PROCEDURE[REF ANY, LIST OF REF ANY]] ; Subst: PROC [new, old: REF ANY, expr: LIST OF REF ANY] RETURNS [LIST OF REF ANY]; Sort: PROC [list: LIST OF REF ANY, compareProc: CompareProc _ Compare] RETURNS[LIST OF REF ANY]; UniqueSort: PROC [list: LIST OF REF ANY, compareProc: CompareProc _ Compare] RETURNS[LIST OF REF ANY]; Compare: CompareProc; Zone: PRIVATE ZONE; -- quantized zone used for storing new ListNodes, such as those created by append, reverse, etc. END. 10-Feb-82 14:24:31 Added ListZone. Cons. Changed SortList to Sort a la Mark Brown's ListSortRef Package June 1, 1982 3:28 pm Value returned by Length now an INT. 'x' and 'y' arguments changed to 'list' 'ref' or 'l1', 'l2'. ┤Types Predicates: IsAList, IsAListOfRefAny, EqLists, Member true each of the corresponding elements of l1 and l2 are =. If compareLists is TRUE, then for corresponding elements of l1, l2 that are of type LIST OF REF ANY, will compare the two elements using EqLists recursively. For more general comparisons, see RefAnyOps.Equal. same as Memb except uses RefAnyOps.EqualRefs to compare ref against each element. constructors of lists: Cons, Append, Reverse, Remove, Union, Intersection, ListDifference ... like some constructors, but destructive to structure: Nconc, DReverse, DSubst ... like Append except second argument is an element, not a list extractors: NthTail NthElement, Car, Cdr, Cadr, Cddr, etc. negative numbers mean count from the end, e.g. -1 means last tail. returns NIL if n > Length[list]. negative numbers mean count from the end, e.g. -1 means last element of list. raises NotThatLong if fewer than ABS[n] elements. Alist operations: DotCons, Assoc, PutAssoc miscellaneous: Length, Map, Subst Sorting Edited on December 14, 1982 3:45 pm, by Teitelman changed NthElement to raise a signal if ABS[n] > Length[List] changes to: NotATail, NotThatLong, NthTail, NthElement, -- Э╩ЮЦ "Cedar" styleШJШ1JШЪ╧k Ш JЪЬЭЬШJЪЬЭЬШJШЧJШJЪ╨lnЬЭЬЭЬШJЪЭШheadЩJЪ╧nЬЭЬЭЬЭЬШ!JЪЯ ЬЭЬЭЬШ&JЪ ЯЬЭЬЭЬЭЬЭЬШ2JЪЯЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШLJЪЯ ЬЭЬШ*JЪЯЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬ╧cШbJЪЯЬЭЬЭЬЭЬЭЬЭЬЭЬаШKЧЪЬ╤npr)Щ5JЪЯЬЭЬЭЬЭЬЭЬ.ЭЬ ЭЬШjJЪЯЬЭЬЭЬЭЬ.ЭЬ ЭЬЭЬЭЬЭЬЭЬШГЪЯЬЭЬЭЬ ЭЬЭЬЭЬЭЬЭЬШbJЪЬOЭЬ╣ЩМЧЪЯЬЭЬЭЬЭЬЭЬЭЬЭЬШBJЪЬЭШJЪЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШVJЪЭЬЭЬШЧЪЯЬЭЬЭЬЭЬЭЬЭЬЭЬШEJЩQЧЧЪЬ╨prGЩ^ЪЯЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШJJЪЬЭЬЭЬЭЬШ(ЧJЪЯЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬа(ШБЪЯЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШDJЪЬЭЬЭЬШ ЧJЪЯЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШLJЪЯЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШAJЪЯЬЭЬ ЭЬЭЬЭЬЭЬЭЬЭЬШ?JЪЯЬЭЬ ЭЬЭЬЭЬЭЬЭЬЭЬШGJЪЯЬЭЬ ЭЬЭЬЭЬЭЬЭЬЭЬаШiJЪЯЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШIЧЪЬ6вЩQJЪЯЬЭЬ ЭЬЭЬЭЬЭЬЭЬЭЬаШNЪЯЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШKJЪа<ЩШwJШЩ1JЩ=JЪЬ╧r.Щ:ЧJЩJЩЧЕЧ`▓