#N	singly linked list
#

box slist { type T } is
	export length, all, point, search, append, prepend, first, last,
		`[]`, delete, delete_point;

	type link := pointer {node};

	box node is
		T data;
		link next;
	end box;

	link head, point_node;

	func int length is
		int n := 0;
		link p := head;

		while p.notnull do
			n := n + 1;
			p := p^.next;
		end while;

		return n;
	end func;

	func ref T point is
		return(point_node^.data);
	end func;

	gen ref T all is
		link p := head;

		while p.notnull do

#  Grab the pointer to the next node before yielding
#  point in case the caller destroys it.

			point_node := p;
			p := p^.next;

			yield point_node^.data;
		end while;

		point_node.setnull;
	end gen;

	func bool search(T v) is

		for T i := all do
			if i == v then
				return true;
			end if;
		end for;

		return false;
	end func;

	proc append (T elem) is
		link p;

		if head.isnull then
			head.new;
			assert head.notnull;
			assert not head.isnull;

			head^.data := elem;
			point_node := head;
			return;
		end if;

		p := head;
		while p^.next.notnull do
			p := p^.next;
		end while;

		p^.next.new;
		p := p^.next;
		p^.data := elem;
		point_node := p;
	end proc;

	proc prepend (T elem) is
		link p;

		if head.isnull then
			head.new;
		else
			p := head;
			head.new;
			head^.next := p;
		end if;

		head^.data := elem;
		point_node := head;
	end proc;

	func ref T first is

		point_node := head;
		return head^.data;
	end func;

	func ref T last is
		link p := head;

		while p^.next.notnull do
			p := p^.next;
		end while;

		point_node := p;
		return p^.data;
	end func;

	func ref T `[]` (int n) is
		link p := head;

		while n > 1 do
			assert p.notnull;

			p := p^.next;
			n := n - 1;
		end while;

		assert p.notnull;

		point_node := p;
		return p^.data;
	end func;

	proc delete_node (ref link x) is
		link p;

		if head == x then
			head := x^.next;
		else
			p := head;
			while p^.next <> x do
				p := p^.next;
			end while;

			p^.next := x^.next;
		end if;

		x.free;
		point_node.setnull;
	end proc;

	proc delete (int i) is
		@ `[]` (i);		# unroll this later for speed
		delete_point;
	end proc;

	proc delete_point is

		assert(point_node.notnull);
		delete_node(point_node);
	end proc;

end box;