{ Read the file INCLUDE to learn how to include this file in your program }

{
    Create a new element record with data field n and next field nil,
    and return a pointer to it in newElement.
}

procedure MakeNewElement (var newElement: ElementPtrType; n: integer);
begin
    new (newElement);
    newElement^.data := n;
    newElement^.next := nil;
end;


{
    Insert itemToInsert into the list at the proper place.
    There are three cases:  if the list is empty, we create a list consisting
    of the single item; if the item is smaller than the first item of the list,
    we put it there; otherwise we find the position where itemToInsert should
    go and put it there.  The last case requires us to keep track of the list
    element before the insertion point.
}

procedure Insert (itemToInsert: integer;  var list: ElementPtrType);
var
    newElement, insertAfter: ElementPtrType;
    done: boolean;
begin
    MakeNewElement (newElement, itemToInsert);
    if list = nil then begin
	list := newElement;
    end else if itemToInsert <= list^.data then begin
	newElement^.next := list;
	list := newElement;
    end else begin
	insertAfter := list;
	done := false;
	while not done do begin
	    if insertAfter^.next = nil then begin
		insertAfter^.next := newElement;
		done := true;
	    end else if itemToInsert <= insertAfter^.next^.data then begin
		newElement^.next := insertAfter^.next;
		insertAfter^.next := newElement;
		done := true;
	    end else begin
		insertAfter := insertAfter^.next;
	    end;
	end;
    end;
end;

{Write out the elements of a list.}

procedure WriteList (list: ElementPtrType);
var
    p: ElementPtrType;
begin
    if list = nil then begin
	writeln ('Empty list.');
    end else begin
	p := list;
	while p <> nil do begin
	    write (p^.data:4);
	    p := p^.next;
	end;
	writeln;
    end;
end;


{Build a sorted list from data values provided by the user.}

procedure ReadList (var list: ElementPtrType);
var
    n: integer;
begin
    writeln ('Please type list items followed by a 0.');
    list := nil;
    read (n);
    while n <> 0 do begin
	Insert (n, list);
	read (n);
    end;
    readln;
    WriteList (list);
end;


{Copy listSource into listDest.}

procedure MakeCopy (var listDest: ElementPtrType;  listSource: ElementPtrType);
var
    tailDest: ElementPtrType;
begin
    if listSource = nil then begin
	listDest := nil
    end else begin
	MakeNewElement (listDest, listSource^.data);
	tailDest := listDest;
	listSource := listSource^.next;
	while listSource <> nil do begin
	    MakeNewElement (tailDest^.next, listSource^.data);
	    tailDest := tailDest^.next;
	    listSource := listSource^.next;
	end;
    end;
end;

{
    Find an item in a list, and either return a pointer to it or indicate
    that it isn't in the list.
}

procedure Find (itemToFind: integer;  list: ElementPtrType;
		var foundPtr: ElementPtrType;  var found: boolean);
begin
    foundPtr := nil;
    found := false;
    while (list <> nil) and not found do begin
	if list^.data = itemToFind then begin
	    foundPtr := list;
	    found := true;
	end else begin
	    list := list^.next;
	end;
    end;
end;