GList.mesa
Copyright © 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
DIRECTORY
Basics USING [Comparison];
GList:
CEDAR
DEFINITIONS =
BEGIN
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
List:
TYPE =
REF
ANY;
Has to be a variety of LIST OF REF
Comparison: TYPE = Basics.Comparison;
CompareProc: TYPE = PROC [ref1: REF ANY, ref2: REF ANY] RETURNS [Comparison];
Predicates
EqLists:
PROC [l1, l2: List]
RETURNS [
BOOL];
TRUE iff each of the corresponding elements of l1 and l2 are =.
Member:
PROC [ref:
REF
ANY, list: List]
RETURNS [
BOOL];
TRUE iff ref occurs in list.
Constructors
Append:
PROC [l1: List, l2: List ←
NIL]
RETURNS [List];
Appends l2 to a copy of l1. With l2=NIL, returns a top-level copy of l1.
Copy:
PROC [list: List]
RETURNS [List];
Appends with l2=NIL.
Reverse:
PROC [list: List]
RETURNS [List];
Returns a reversed copy of the list.
Remove:
PROC [ref:
REF
ANY, list: List]
RETURNS [List];
Removes all instances of ref from the list, returning a copy as far as necessary.
Union:
PROC [l1, l2: List]
RETURNS [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.
Intersection:
PROC [l1, l2: List]
RETURNS [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.
ListDifference:
PROC [l1, l2: List]
RETURNS [List];
Returns a list containing all elements in l1 not in l2. The returned list may share with l1.
Constructors, but destructive to structure
Nconc:
PROC [l1, l2: List]
RETURNS [List];
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
DReverse:
PROC [list: List]
RETURNS [List];
like Reverse, but alters the list
DRemove:
PROC [ref:
REF
ANY, list: List]
RETURNS [List];
like Remove, but removes the ref from the list destructively, and ONLY removes the first occurrence of ref.
DSubst:
PROC [new, old:
REF
ANY, list: List]
RETURNS [List];
Substitutes new for each occurrence of old.
Extractors
NthTail:
PROC [list: List, n:
INT]
RETURNS [List];
negative numbers mean count from the end, e.g. -1 means last tail.
returns NIL if n > Length[list].
NthElement:
PROC [list: List, n:
INT]
RETURNS [
REF
ANY];
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
Length:
PROC [list: List]
RETURNS [
INT];
Returns the # of elements in the list
Subst:
PROC [new, old:
REF
ANY, list: List]
RETURNS [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]]];
Kill:
PROC [list: List];
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
Sort:
PROC [list: List, compareProc: CompareProc]
RETURNS [List];
... destructively sorts the given list in increasing order according to compareProc. The sort is not stable, so order of equal elements is not preserved.
UniqueSort:
PROC [list: List, compareProc: CompareProc]
RETURNS [List];
... is like Sort, but removes duplicates in a separate pass over the sorted list
Merge:
PROC [x, y: List, compareProc: CompareProc]
RETURNS [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
IncompatibleType:
ERROR [ref:
REF
ANY];
raised by various functions when given ref is not of given type
NotAListType:
ERROR;
raised by various functions when given type is not of the form LIST OF REF <Type>
END.