-- 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, -->>
<<>>
<<>>