(* The queue is implemented as an inverted heap, i.e. the top element is the one with lowest "priority" *)

MODULE Queue;
IMPORT Out;	(* for testing *)

TYPE
	Data = INTEGER;		(* assumes 0 <= x < 5000 *)
	Location = INTEGER;
	Entry = RECORD
		entry: Data;
		prior: REAL
	END;

CONST MAXQSIZE = 5000;	(* overkill *)

VAR
	queue: ARRAY MAXQSIZE+1 OF Entry;	(* +1 because we're going to start our array from index 1 to avoid unnecessary effort *)
	n: INTEGER;				(* queue[1..n] holds our queue *)
	location: ARRAY 5000 OF Location;

	i: INTEGER;	(* for testing *)

PROCEDURE Clear*();
BEGIN
	n := 0
END Clear;

PROCEDURE Enqueue*(x: Data; p: REAL);
BEGIN
	n := n+1;
	queue[n].entry := x; queue[n].prior := p;
	location[x] := n;
	Percolate(n)
END Enqueue;

PROCEDURE Requeue*(x: Data; p: REAL);
VAR t: REAL;
BEGIN
	t := queue[location[x]].prior;
	queue[location[x]].prior := p;
	IF p > t THEN
		SiftDown(n,location[x])
	ELSE
		Percolate(location[x])
	END
END Requeue;

PROCEDURE Dequeue*(): Data;
VAR t: Data;
BEGIN
	t := queue[1].entry;
	queue[1] := queue[n];
	SiftDown(n-1,1);
	n := n-1;
	RETURN t
END Dequeue;

(* ------------------- PRIVATE (NON-EXPORTED) PROCEDURES ------------------- *)

PROCEDURE Percolate(i: INTEGER);
VAR j,k: INTEGER;
BEGIN
	k := i;
	REPEAT
		j := k;
		IF (j > 1) & (queue[k].prior < queue[j DIV 2].prior) THEN k := j DIV 2 END;	(* < because we want the smallest at the top *)
		SwapEntry(queue[j],queue[k])
	UNTIL j = k;
END Percolate;

PROCEDURE SiftDown(n,i: INTEGER);
VAR j,k: INTEGER;
BEGIN
	k := i;
	REPEAT
		j := k;
		(* If node j has children, find its smaller child *)
		IF (2*j <= n) & (queue[2*j].prior < queue[k].prior) THEN k := 2*j END;
		IF (2*j < n) & (queue[2*j+1].prior < queue[k].prior) THEN k := 2*j+1 END;
		SwapEntry(queue[j],queue[k])
	UNTIL j = k
END SiftDown;

PROCEDURE SwapEntry(VAR x,y: Entry);
VAR t: Entry;
BEGIN
	SwapInt(location[x.entry],location[y.entry]);
	t := x;	x := y;	y := t
END SwapEntry;

PROCEDURE SwapInt(VAR x,y: INTEGER);
VAR t: INTEGER;
BEGIN
	t := x;	x := y;	y := t
END SwapInt;

(* ------------------------------------------------------------------------- *)

BEGIN
	Clear;
	Enqueue(10, 7);
	Enqueue(45, 17);
	Enqueue(23, 4);
	Enqueue(19, 6);
	Requeue(23, 50);
	FOR i := 1 TO n DO
		Out.Int(queue[i].entry,0);
		Out.Char(' ');
		Out.Real(queue[i].prior);
		Out.Ln
	END;
	Out.Ln;
	i := n;
	WHILE i # 0 DO
		Out.Int(Dequeue(),0);
		Out.Char(' ');
		i := i-1
	END;
	Out.Ln
END Queue.