(* lista.2linkitettytoteutus.p SJ *)

module lista interface;

export lista = ( LIST, LIST_POSITION, LIST_CREATE, LIST_INSERT,
	LIST_DELETE, LIST_FIRST, LIST_FIRST, LIST_EOL, LIST_RETRIEVE,
	LIST_NEXT);


import element;

type	LIST_NODE = ^LIST_NODE_RECORD;
		LIST_NODE_RECORD = record
						next,
						prev : LIST_NODE;
						elem : ELEMENT;
					end;

		LIST = ^LIST_RECORD;
		LIST_RECORD = record
						first,
						last : LIST_NODE;
					end;
		LIST_POSITION = LIST_NODE;

procedure LIST_CREATE(var L : LIST);
procedure LIST_INSERT(L : LIST; p : LIST_POSITION; x : ELEMENT);
procedure LIST_DELETE(L : LIST; p : LIST_POSITION);
function LIST_RETRIEVE(L : LIST; p : LIST_POSITION) : ELEMENT;
function LIST_FIRST(L : LIST) : LIST_POSITION;
function LIST_NEXT(L : LIST; p : LIST_POSITION) : LIST_POSITION;
function LIST_EOL(L : LIST) : LIST_POSITION;

end. (* interface *)

module lista implementation;

import element;

procedure LIST_CREATE(var L : LIST);
begin
	new(L);
	L^.first := nil;
	L^.last := nil;
end;


procedure LIST_INSERT(L : LIST; p : LIST_POSITION; x : ELEMENT);
	var q : LIST_POSITION;
begin
	new(q);
	q^.elem := x;

	if p <> nil then begin 			(* lisäys muualle kuin loppuun *)
		q^.next := p;					(* 4 linkin päivitystä *)
		q^.prev := p^.prev;
		p^.prev := q;
		if q^.prev <> nil then
			q^.prev^.next := q			(* ei alkuun*)
		else	
			L^.first := q				(* lisäys alkuun *)

	end else begin					(* lisäys listan loppuun *)
		q^.next := nil;					(* 4 linkin päivitystä *)
		q^.prev := L^.last;
		L^.last := q;
		if q^.prev <> nil then
			q^.prev^.next := q			(* lisäys epätyhjään listaan *)
		else
			L^.first := q				(* lisäys tyhjään listaan *)
	end
end; (* LIST_INSERT() *)


procedure LIST_DELETE(L : LIST; p : LIST_POSITION);
begin								(* 4 linkin päivitystä *)
	if p^.next <> nil then
		p^.next^.prev := p^.prev		(* muu kuin viimeinen *)
	else
		L^.last := p^.prev;				(* viimeinen *)

	if p^.prev <> nil then
		p^.prev^.next := p^.next		(* muu kuin ensimmäinen *)
	else
		L^.first := p^.next;			(* ensimmäinen *)

	p^.next := NIL; p^.prev := NIL;

	dispose(p);
end;


function LIST_RETRIEVE(L : LIST; p : LIST_POSITION) : ELEMENT;
begin
	LIST_RETRIEVE := p^.elem;
end;

function LIST_NEXT(L : LIST; p : LIST_POSITION) : LIST_POSITION;
begin
	LIST_NEXT := p^.next;
end;


function LIST_FIRST(L : LIST) : LIST_POSITION;
begin
	LIST_FIRST := L^.first
end;


function LIST_EOL(L : LIST) : LIST_POSITION;
begin
	LIST_EOL := NIL
end;


end. (* implementation *)