DIRECTORY Atom USING [PropList, DottedPair, DottedPairNode], Basics USING [Comparison]; List: CEDAR DEFINITIONS = BEGIN AList: TYPE = Atom.PropList; DottedPair: TYPE = Atom.DottedPair; DottedPairNode: TYPE = Atom.DottedPairNode; LORA: TYPE = LIST OF REF ANY; Comparison: TYPE = Basics.Comparison; CompareProc: TYPE = PROC[ref1: REF ANY, ref2: REF ANY] RETURNS [Comparison]; EqLists: PROC [l1, l2: LORA] RETURNS [BOOL]; Memb: PROC [ref: REF ANY, list: LORA] RETURNS[BOOL]; Append: PROC[l1: LORA, l2: LORA _ NIL] RETURNS[LORA]; Remove: PROC[ref: REF ANY, list: LORA] RETURNS[LORA]; Reverse: PROC [list: LORA] RETURNS[LORA]; Union: PROC [l1, l2: LORA] RETURNS[LORA]; Intersection: PROC [l1, l2: LORA] RETURNS[LORA]; ListDifference: PROC [l1, l2: LORA] RETURNS[LORA]; LDiff: PROC [list, tailOfList: LORA] RETURNS[LORA]; Nconc: PROC [l1, l2: LORA] RETURNS[LORA]; Nconc1: PROC [list: LORA, ref: REF ANY] RETURNS[LORA]; DRemove: PROC [ref: REF ANY, list: LORA] RETURNS[LORA]; DReverse: PROC [list: LORA] RETURNS[LORA]; DSubst: PROC [new, old: REF ANY, expr: LORA] RETURNS[LORA]; NthTail: PROC[list: LORA, n: INT] RETURNS[LORA]; NthElement: PROC[list: LORA, n: INT] RETURNS[REF ANY]; 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: LORA] RETURNS[INT]; Map: PROC [list: LORA, proc: PROC[REF ANY, LORA]]; Subst: PROC [new, old: REF ANY, expr: LORA] RETURNS [LORA]; Kill: PROC [list: LORA]; Sort: PROC [list: LORA, compareProc: CompareProc _ Compare] RETURNS[LORA]; UniqueSort: PROC [list: LORA, compareProc: CompareProc _ Compare] RETURNS[LORA]; Merge: PROC [x,y: LORA, compareProc: CompareProc] RETURNS [LORA]; Compare: CompareProc; NotATail: SIGNAL [list, tailOfList: LORA] RETURNS[LORA]; END. List.mesa Copyright c 1985 by Xerox Corporation. All rights reserved. Teitelman, December 14, 1982 3:45 pm Rovner, May 13, 1983 10:21 am Levin, August 8, 1983 4:50 pm Russ Atkinson (RRA) February 20, 1985 12:15:13 pm PST Beach, February 22, 1985 11:15:09 am PST Doug Wyatt, February 24, 1985 8:20:17 pm PST Note: unless otherwise noted, the operations listed below assume that the input list arguments are acyclic, and will produce acyclic lists. The user is cautioned that use of cyclic lists may result in either infinite loops or infinite recursion (producing a machine crash). Types Predicates TRUE iff each of the corresponding elements of l1 and l2 are =. TRUE iff ref occurs in list. Constructors Appends l2 to a copy of l1. Removes all instances of ref from the list, returning a copy as far as necessary. Returns a reversed copy of the list. Returns the union of the two lists, but does not copy l2; this is really only a union if there were no duplicates in either list. Returns the intersection of the two lists, but does not copy l1; this is really only a intersection if there were no duplicates in either list. Returns a list containing all elements in l1 not in l2. The returned list may share with l1. Returns a list of those elements in list up to tailOflist. tailOflist must be a tail of list, i.e. eq to some number of cdrs of list, or else the signal NotATail is raised. If tailOflist is NIL, returns list. Otherwise, always returns new structure. Constructors, but destructive to structure like Append, but modifies l1; a cycle will be formed if any tail of l1 is EQ to any tail of l2. returns IF l1 # NIL THEN l1 ELSE l2 like Nconc except second argument is an element, not a list. Returns IF list # NIL THEN list ELSE LIST[ref]. like Remove, but removes the ref from the list destructively, and ONLY removes the first occurrence of ref. like Reverse, but alters the list like Subst. Extractors 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. Association List Operations returns the value associated with key in aList (returns NIL if no such key) equivalent to NEW[DottedPairNode _ [key, val]] (slightly slower, but generates less code) returns a list containing the new association; PutAssoc alters the previous association if it was present, and otherwise places the new association at the tail of the old list. Miscellaneous Returns the # of elements in the list Calls proc for each element in the list with the REF contained in the element and the element itself. Equivalent to the following code: FOR each: LORA _ list, each.rest UNTIL l = NIL DO proc[each.first, each]; ENDLOOP; Returns a copy of the list, substituing new for each occurence of old. Equivalent to the following code (but not recursive): SELECT TRUE FROM expr = NIL => RETURN [NIL]; old = expr.first => RETURN [CONS[new, Subst[new, old, expr.rest]]]; ENDCASE => RETURN [CONS[expr.first, Subst[new, old, expr.rest]]]; Assigns NIL to the first and rest fields of every node in the list. This is useful when trying to get all of the list returned to free storage, since a conservatively retained list node will not then keep the rest ot the list in existence. Kill works for circular lists. Equivalent to: WHILE list # NIL DO next: LORA _ list.rest; list.rest _ NIL; list.first _ NIL; ENDLOOP; Sorting ... destructively sorts the given list in increasing order according to compareProc. The sort is not stable, so order of equal elements is not preserved. ... is like Sort, but removes duplicates in a separate pass over the sorted list ... destructively merges two lists according to compareProc. If the input lists are sorted in increasing order, then the output list will be sorted in increasing order. .. a general (although slow) CompareProc that can sort lists where all of the elements are the same type. Element types supported are ROPE, REF INT, or ATOM. Errors raised by LDiff ΚΌ– "Cedar" style˜codešœ ™ Kšœ Οmœ1™