Queue/Definition: Difference between revisions

=={{header|Component Pascal}}==

BlackBox Component Builder

<lang oberon2>

MODULE Queue;

IMPORT StdLog,Boxes;

TYPE

Queue* = POINTER TO RECORD

first,last: LONGINT;

queue: POINTER TO ARRAY OF Boxes.Object;

END;

PROCEDURE NewQueue*(cap: LONGINT): Queue;

VAR

q: Queue;

BEGIN

NEW(q);q.first := 0; q.last := 0;

NEW(q.queue,cap);

RETURN q

END NewQueue;

PROCEDURE (q: Queue) IsEmpty*(): BOOLEAN, NEW;

VAR

BEGIN

RETURN (q.first = q.last)

END IsEmpty;

PROCEDURE (q: Queue) Push*(o: Boxes.Object),NEW;

VAR

i,j,oldSize,newSize: LONGINT;

queue: POINTER TO ARRAY OF Boxes.Object;

BEGIN

IF q.IsEmpty() THEN

q.queue[q.last] := o;

q.last := (q.last + 1) MOD LEN(q.queue)

ELSE

q.queue[q.last] := o;

q.last := (q.last + 1) MOD LEN(q.queue);

IF q.first = q.last THEN

(* grow queue *)

newSize := LEN(q.queue) + (LEN(q.queue) DIV 2);

(* new queue*)

NEW(queue,newSize);

(* move data from old queue to new queue *)

i := q.first; j := 0;oldSize := LEN(q.queue) - q.first + q.last;

WHILE (j < oldSize ) & (j < LEN(queue) - 1) DO

queue[j] := q.queue[i];

i := (i + 1) MOD LEN(q.queue);INC(j)

END;

q.queue := queue;q.first := 0;q.last := j

END

END;

END Push;

PROCEDURE (q: Queue) Pop*(): Boxes.Object, NEW;

VAR

o: Boxes.Object;

BEGIN

ASSERT(~q.IsEmpty());

o := q.queue[q.first];

q.queue[q.first] := NIL;

q.first := (q.first + 1) MOD LEN(q.queue);

RETURN o;

END Pop;

END Queue.

</lang>

Interface extracted from implementation

<lang oberon2>

DEFINITION Queue;

IMPORT Boxes;

TYPE

Queue = POINTER TO RECORD

(q: Queue) IsEmpty (): BOOLEAN, NEW;

(q: Queue) Pop (): Boxes.Object, NEW;

(q: Queue) Push (o: Boxes.Object), NEW

END;

PROCEDURE NewQueue (cap: LONGINT): Queue;

END Queue.

</lang>