DIRECTORY Basics USING [Comparison]; GList: CEDAR DEFINITIONS = BEGIN List: TYPE = REF ANY; Comparison: TYPE = Basics.Comparison; CompareProc: TYPE = PROC [ref1: REF ANY, ref2: REF ANY] RETURNS [Comparison]; EqLists: PROC [l1, l2: List] RETURNS [BOOL]; Member: PROC [ref: REF ANY, list: List] RETURNS [BOOL]; Append: PROC [l1: List, l2: List _ NIL] RETURNS [List]; Copy: PROC [list: List] RETURNS [List]; Reverse: PROC [list: List] RETURNS [List]; Remove: PROC [ref: REF ANY, list: List] RETURNS [List]; Union: PROC [l1, l2: List] RETURNS [List]; Intersection: PROC [l1, l2: List] RETURNS [List]; ListDifference: PROC [l1, l2: List] RETURNS [List]; Nconc: PROC [l1, l2: List] RETURNS [List]; DReverse: PROC [list: List] RETURNS [List]; DRemove: PROC [ref: REF ANY, list: List] RETURNS [List]; DSubst: PROC [new, old: REF ANY, list: List] RETURNS [List]; NthTail: PROC [list: List, n: INT] RETURNS [List]; NthElement: PROC [list: List, n: INT] RETURNS [REF ANY]; Length: PROC [list: List] RETURNS [INT]; Subst: PROC [new, old: REF ANY, list: List] RETURNS [List]; Kill: PROC [list: List]; Sort: PROC [list: List, compareProc: CompareProc] RETURNS [List]; UniqueSort: PROC [list: List, compareProc: CompareProc] RETURNS [List]; Merge: PROC [x, y: List, compareProc: CompareProc] RETURNS [List]; IncompatibleType: ERROR [ref: REF ANY]; NotAListType: ERROR; END. HGList.mesa Copyright c 1986 by Xerox Corporation. All rights reversed. Adapted by Bertrand Serlet, May 12, 1986 10:24:52 am PDT from List.mesa Bertrand Serlet, May 22, 1986 0:27:40 am PDT In this interface type denotes a variety of LIST OF REF (e.g. LIST OF REF INT). 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 and constants Has to be a variety of LIST OF REF 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. With l2=NIL, returns a top-level copy of l1. Appends with l2=NIL. Returns a reversed copy of the list. Removes all instances of ref from the list, returning a copy as far as necessary. 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. 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 Reverse, but alters the list like Remove, but removes the ref from the list destructively, and ONLY removes the first occurrence of ref. Substitutes new for each occurrence of old. 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. first element is n=1. raises an error if fewer than ABS[n] elements. Miscellaneous Returns the # of elements in the list Returns a copy of the list, substituing new for each occurrence 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. 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. Errors raised by various functions when given ref is not of given type raised by various functions when given type is not of the form LIST OF REF Κi– "Cedar" style˜codešœ ™ Kšœ Οmœ1™