--* From bmt@spadserv.watson.ibm.com  Thu Dec 10 20:53:08 1992
--* Received: from spadserv.watson.ibm.com by radical.watson.ibm.com (AIX 3.2/UCB 5.64/900524)
--*           id AA12840; Thu, 10 Dec 1992 20:53:08 -0500
--* Received: by spadserv.watson.ibm.com (AIX 3.2/UCB 5.64/900524)
--*           id AA17929; Thu, 10 Dec 1992 20:58:20 -0500
--* Date: Thu, 10 Dec 1992 20:58:20 -0500
--* From: bmt@spadserv.watson.ibm.com
--* X-External-Networks: yes
--* Message-Id: <9212110158.AA17929@spadserv.watson.ibm.com>
--* To: axc-bug@radical.watson.ibm.com
--* Subject: no meaning found for error, although Exit exports it.

--@ Fixed  by: SMW Fri Oct 08 12:19:58 1993
--@ Tested by: <name of new or existing file in test directory>
--@ Summary:   <One line description of real problem and the fix>


--
-- list.as:  linked lists
--

#include "aslib.as"

ListCategory S ==>
	Object
	Aggregate S
	Conditional

	nil:	   %
	cons:	   (S, %) -> %
	list:	   Iterator S -> %

	first:	   % -> S
	rest:	   % -> %

	setFirst!: (%, S) -> S
	setRest!:  (%, %) -> %
	reverse!:  % -> %
        concat!:   (%, %) -> %
        concat:    (%, %) -> %

        member?:   (S, %) -> Bit
        apply:     (%, SingleInteger) -> S

List(S: with Object): with ListCategory S == add

	macro Rep0== P
	macro Rep == P
	macro R	  == Record(first: S, rest: Rep0)

	-- This local domain gives an untagged union of Records and Nil.
	P: with
		nil?:	 % -> Bit
		nilptr:	 %
		recptr:	 R -> %
		value:	 % -> R
	    == add
		macro  Rep == Pointer
		import Rep
		nil? (p: %): Bit == nil? rep p
		nilptr: %	 == per nil
		recptr(r: R): %	 == r pretend %
		value(p: %): R	 == p pretend R

	import R
	import S
	import Rep
	import Bit
	import String

	default	n: SingleInteger

	rec(x: %): R		 == value rep x	  -- non-empty % as a Record

	empty?(l: %): Bit	 == nil? rep l
	#(l: %): SingleInteger   == (n := 0; for i in l repeat n := n + 1; n)
	nil: %			 == per nilptr
	cons(a: S, l: %): %	 == per recptr [a, rep l]

	list(its: Iterator S): % == [its]

	map(f: S->S,   l: %): %	     == [f(a)   for a in l]
	map(f:(S,S)->S,l1:%,l2:%): % == [f(a,b) for a in l1 for b in l2]

	first (l: %): S		 == rec(l).first
	rest  (l: %): %		 == per rec(l).rest

	setFirst!(l: %, a: S): S == rec(l).first := a
	setRest! (l: %, t: %): % == per (rec(l).rest := rep t)

	reverse! (l: %): % ==
		r := nil
		while l repeat
			t := rest l
			setRest!(l, r)
			r := l
			l := t
		r

        concat! (l1:%, l2:%):% ==
            empty? l1 => l2
            l := l1
            while (t:=rest l) repeat l:=t
            setRest!(l, l2)
            l1

        concat(l1:%, l2:%):% ==
            empty? l1 => l2
            cons(first l1, concat(rest l1, l2))

        member?(v:S, l:%):Bit ==
            for x in l repeat
               if v=x then return true
            false

        apply(l:%, i:SingleInteger):S ==
            for j in 1..i while l repeat l:=rest l
            l => first l
            error "apply: too few elements in list"


	(l1: % = l2: %): Bit ==
		while l1 and l2 repeat
			first l1 ~= first l2 => return false
			l1 := rest l1
			l2 := rest l2
		empty? l1 and empty? l2

	(l1: % ~= l2: %): Bit == ~(l1 = l2)

	apply(p: Outport, l: %): Outport ==
		empty? l => p "list()"
		p "list("
		p first l
		for a in rest l repeat p(", ")(a)
		p  ")"

	test(l: %): Bit == not empty? l

	iterator(l: %): Iterator S == iterate
		while l repeat
			yield first l
			l := rest l

	[ita: Iterator S]: % ==
		h := l := nil
		for a in ita repeat
			t := l
			l := cons(a, nil)
			empty? t => h := l
			setRest!(t, l)
		h