(*
The order is:
Jaylo, Frodo, Bilbo, Tesco, Dunno

Having a header cell would just complicate matters. The two-way links are essential because we want to be able to delete an element from the list
without having to loop all the way back round to find the one before it.
*)

MODULE ExA;
IMPORT In, Out, Random;

CONST MAXHOBBITNAME = 20;

TYPE
	Hobbit =	ARRAY MAXHOBBITNAME+1 OF CHAR;
	Menu =		POINTER TO MenuItem;
	MenuItem =	RECORD
				hobbit: Hobbit;
				prev,next: Menu
			END;

PROCEDURE Advance(VAR m: Menu; steps: INTEGER);
VAR i: INTEGER;
BEGIN
	FOR i := 0 TO steps-1 DO
		m := m.next
	END
END Advance;

PROCEDURE Clear;
BEGIN
	head := NIL;
	tail := NIL
END Clear;

PROCEDURE JoinTheFellowship(VAR m: Menu);	(* this procedure could alternatively have been called "Munch" (and indeed was at one point) *)
BEGIN
	(* The idea is that after this procedure, if the list isn't empty, m points to the element *before* the one which has just been erased *)

	IF head = tail THEN
		Clear;
		m := NIL
	ELSIF m = head THEN
		head := head.next;
		tail.next := head;
		head.prev := tail;
		m := tail
	ELSIF m = tail THEN
		m := m.prev;
		m.next := head;
		head.prev := m;
		tail := m
	ELSE
		m.next.prev := m.prev;
		m.prev.next := m.next;
		m := m.prev
	END
END JoinTheFellowship;

PROCEDURE Output;
VAR m: Menu;
BEGIN
	IF head = NIL THEN
		Out.String("NIL");
		RETURN
	END;

	m := head;
	REPEAT
		OutHobbit(m.hobbit);
		Out.Char(' ');
		OutHobbit(m.next.hobbit);
		Out.Ln;
		m := m.next
	UNTIL m = head;
END Output;

PROCEDURE OutputReverse;
VAR m: Menu;
BEGIN
	IF tail = NIL THEN
		Out.String("NIL");
		RETURN
	END;

	m := tail;
	REPEAT
		OutHobbit(m.hobbit);
		Out.Char(' ');
		OutHobbit(m.prev.hobbit);
		Out.Ln;
		m := m.prev
	UNTIL m = tail;
END OutputReverse;

PROCEDURE PushBack(VAR h: Hobbit);
BEGIN
	IF tail = NIL THEN
		NEW(head);
		tail := head;
		head.prev := head;
		head.next := head;
		head.hobbit := h;
	ELSE
		NEW(tail.next);
		tail.next.prev := tail;
		tail := tail.next;
		tail.next := head;
		head.prev := tail;
		tail.hobbit := h
	END
END PushBack;

PROCEDURE InHobbit(VAR h: Hobbit);
BEGIN
	In.Line(h)
END InHobbit;

PROCEDURE OutHobbit(VAR h: Hobbit);
BEGIN
	Out.String(h)
END OutHobbit;

PROCEDURE MakeRing;
VAR
	i: INTEGER;
	h: Hobbit;
BEGIN
	FOR i := 0 TO N-1 DO
		InHobbit(h);
		PushBack(h)
	END
END MakeRing;

PROCEDURE OutMenu;
VAR m: Menu;
BEGIN
	Random.Randomize;
	n := Random.Random() MOD N;	(* Random.Roll didn't work for some strange reason *)

	Out.Ln;
	Out.String("The Uruk-Thai - Upmarket Thai Cuisine for the Discerning Orc");
	Out.Ln;
	Out.String("Our motto: 'We wait until *after* they've had second breakfast'");
	Out.Ln;
	Out.String("---------------------------------------------------------------");
	Out.Ln;
	Out.Ln;
	Out.String("Today's Specials");
	Out.Ln;
	Out.String("----------------");
	Out.Ln;
	Out.Ln;
	Out.String("We are proud to announce that today's thunderball is: ");
	Out.Int(n,0);
	Out.Ln;
	Out.Ln;

	m := head;
	WHILE m # NIL DO
		Advance(m,n);
		OutHobbit(m.hobbit);
		Out.Ln;
		JoinTheFellowship(m)
	END
END OutMenu;

VAR
	n,N: INTEGER;
	head,tail: Menu;
BEGIN
	Out.String("Number of hobbits: ");
	In.Int(N);
	Clear;
	MakeRing;
	OutMenu
END ExA.