-- edited by Teitelman, December 14, 1982 3:45 pm
DIRECTORY
Environment USING [Comparison],
RTBasic USING [Type, nullType]
;
List: CEDAR DEFINITIONS =
BEGIN
Types
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
Predicates: IsAList, IsAListOfRefAny, EqLists, Member
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] ;
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.
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];
same as Memb except uses RefAnyOps.EqualRefs to compare ref against each element.
constructors of lists: Cons, Append, Reverse, Remove, Union, Intersection, ListDifference ...
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];
like some constructors, but destructive to structure: Nconc, DReverse, DSubst ...
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]
like Append except second argument is an element, not a list
= 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.
extractors: NthTail NthElement, Car, Cdr, Cadr, Cddr, etc.
NthTail:
PROC[list:
LIST OF REF ANY, n:
INT]
RETURNS[
LIST
OF
REF
ANY];
negative numbers mean count from the end, e.g. -1 means last tail.
returns NIL if n > Length[list].
NthElement:
PROC[list:
LIST OF REF ANY, n:
INT]
RETURNS[
REF
ANY];
negative numbers mean count from the end, e.g. -1 means last element of list.
raises NotThatLong if fewer than ABS[n] elements.
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]};
Alist operations: DotCons, Assoc, PutAssoc
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];
miscellaneous: Length, Map, Subst
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];
Sorting
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'.
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, --