MODULE OSCQueue;
IMPORT OSC, KernelLog;
CONST
InitHeapSize = 1024;
Trace* = FALSE;
TYPE
PacketArray = POINTER TO ARRAY OF OSC.OSCBundle;
OSCQueue* = OBJECT
VAR
q: PacketArray;
size: LONGINT;
PROCEDURE &Init*;
BEGIN
NEW(q, InitHeapSize);
size := 0;
END Init;
PROCEDURE grow;
VAR
biggerq: PacketArray;
i: LONGINT;
BEGIN
NEW(biggerq, 2*LEN(q));
FOR i:=0 TO LEN(q)-1 DO biggerq[i] := q[i]; END;
q := biggerq;
END grow;
PROCEDURE IsEmpty*(): BOOLEAN;
BEGIN {EXCLUSIVE}
RETURN size = 0;
END IsEmpty;
PROCEDURE Queue*(p: OSC.OSCBundle);
VAR
element, parent: LONGINT;
temp: OSC.OSCBundle;
BEGIN { EXCLUSIVE }
IF Trace THEN KernelLog.String('OSCQueue: Insert with bundle: '); KernelLog.Ln; p.dump(0); KernelLog.Ln; END;
IF size = LEN(q) THEN grow; END;
q[size] := p;
element := size; parent := (element-1) DIV 2;
INC(size);
WHILE (element > 0) & q[element].IsBefore(q[parent]) DO
temp := q[parent]; q[parent] := q[element]; q[element] := temp;
element := parent; parent := (element-1) DIV 2;
END;
IF Trace THEN KernelLog.String('Insertion at element: '); KernelLog.Int(element, 4); KernelLog.Ln; END;
END Queue;
PROCEDURE Peek*(): OSC.OSCBundle;
BEGIN
ASSERT(size > 0);
RETURN q[0];
END Peek;
PROCEDURE Dequeue*(): OSC.OSCBundle;
VAR
min, temp: OSC.OSCBundle;
element, left, right: LONGINT;
BEGIN { EXCLUSIVE }
min := q[0];
q[0] := q[size-1]; DEC(size);
element := 0; left := 1; right := 2;
WHILE ((size-1) >= right ) &
(~q[element].IsBefore(q[left]) OR
~q[element].IsBefore(q[right])) DO
IF q[left].IsBefore(q[right]) THEN
temp := q[element]; q[element] := q[left]; q[left] := temp;
element := left;
ELSE
temp := q[element]; q[element] := q[right]; q[right] := temp;
element := right;
END;
left := 2*element+1;
right := 2*element+2;
END;
IF ((size-1) = left) & (~q[element].IsBefore(q[left])) THEN
temp := q[element]; q[element] := q[left]; q[left] := temp;
element := left;
END;
RETURN min;
END Dequeue;
PROCEDURE checkheap(idx: LONGINT): BOOLEAN;
VAR
left, right: LONGINT;
res: BOOLEAN;
BEGIN
left := idx*2+1; right := idx*2+2;
IF (left < size) & ~q[idx].IsBeforeEqual(q[left]) THEN RETURN FALSE; END;
IF (right < size) & ~q[idx].IsBeforeEqual(q[right]) THEN RETURN FALSE; END;
res := TRUE;
IF (left < size) THEN res := res & checkheap(left); END;
IF (right < size) THEN res := res & checkheap(right); END;
RETURN res;
END checkheap
END OSCQueue;
PROCEDURE TestQueue*;
VAR
b: OSC.OSCBundle;
q: OSCQueue;
tt: OSC.OSCTimeTag;
i: LONGINT;
BEGIN
NEW(q);
NEW(tt); tt.Set(10,0); NEW(b, tt, NIL, 0); q.Queue(b);
IF ~ q.checkheap(0) THEN KernelLog.String('Heapviolation!'); KernelLog.Ln; END;
NEW(tt); tt.Set(11,0); NEW(b, tt, NIL, 0); q.Queue(b);
IF ~ q.checkheap(0) THEN KernelLog.String('Heapviolation!'); KernelLog.Ln; END;
NEW(tt); tt.Set(14,0); NEW(b, tt, NIL, 0); q.Queue(b);
IF ~ q.checkheap(0) THEN KernelLog.String('Heapviolation!'); KernelLog.Ln; END;
NEW(tt); tt.Set(12,0); NEW(b, tt, NIL, 0); q.Queue(b);
IF ~ q.checkheap(0) THEN KernelLog.String('Heapviolation!'); KernelLog.Ln; END;
NEW(tt); tt.Set(13,100); NEW(b, tt, NIL, 0); q.Queue(b);
IF ~ q.checkheap(0) THEN KernelLog.String('Heapviolation!'); KernelLog.Ln; END;
NEW(tt); tt.SetImmediately; NEW(b, tt, NIL, 0); q.Queue(b);
IF ~ q.checkheap(0) THEN KernelLog.String('Heapviolation!'); KernelLog.Ln; END;
NEW(tt); tt.Set(13,101); NEW(b, tt, NIL, 0); q.Queue(b);
IF ~ q.checkheap(0) THEN KernelLog.String('Heapviolation!'); KernelLog.Ln; END;
NEW(tt); tt.Set(13,99); NEW(b, tt, NIL, 0); q.Queue(b);
IF ~ q.checkheap(0) THEN KernelLog.String('Heapviolation!'); KernelLog.Ln; END;
NEW(tt); tt.SetImmediately; NEW(b, tt, NIL, 0); q.Queue(b);
IF ~ q.checkheap(0) THEN KernelLog.String('Heapviolation!'); KernelLog.Ln;
FOR i:=0 TO q.size-1 DO q.q[i].dump(0); END; END;
NEW(tt); tt.Set(9,0); NEW(b, tt, NIL, 0); q.Queue(b);
IF ~ q.checkheap(0) THEN KernelLog.String('Heapviolation!'); KernelLog.Ln; END;
NEW(tt); tt.Set(15,0); NEW(b, tt, NIL, 0); q.Queue(b);
IF ~ q.checkheap(0) THEN KernelLog.String('Heapviolation!'); KernelLog.Ln; END;
KernelLog.String('size: '); KernelLog.Int(q.size, 4); KernelLog.Ln;
KernelLog.String('isempty:'); KernelLog.Boolean(q.IsEmpty()); KernelLog.Ln;
WHILE ~q.IsEmpty() DO
b := q.Dequeue(); b.dump(0);
IF ~ q.checkheap(0) THEN KernelLog.String('Heapviolation!'); KernelLog.Ln; END;
END;
NEW(q);
NEW(tt); tt.Set(1,0); NEW(b, tt, NIL, 0); q.Queue(b);
IF ~ q.checkheap(0) THEN KernelLog.String('Heapviolation!'); KernelLog.Ln; END;
NEW(tt); tt.Set(3,0); NEW(b, tt, NIL, 0); q.Queue(b);
IF ~ q.checkheap(0) THEN KernelLog.String('Heapviolation!'); KernelLog.Ln; END;
NEW(tt); tt.Set(5,0); NEW(b, tt, NIL, 0); q.Queue(b);
IF ~ q.checkheap(0) THEN KernelLog.String('Heapviolation!'); KernelLog.Ln; END;
NEW(tt); tt.Set(8,0); NEW(b, tt, NIL, 0); q.Queue(b);
IF ~ q.checkheap(0) THEN KernelLog.String('Heapviolation!'); KernelLog.Ln; END;
NEW(tt); tt.Set(10,100); NEW(b, tt, NIL, 0); q.Queue(b);
IF ~ q.checkheap(0) THEN KernelLog.String('Heapviolation!'); KernelLog.Ln; END;
KernelLog.String('size: '); KernelLog.Int(q.size, 4); KernelLog.Ln;
KernelLog.String('isempty:'); KernelLog.Boolean(q.IsEmpty()); KernelLog.Ln;
WHILE ~q.IsEmpty() DO
b := q.Dequeue(); b.dump(0);
IF ~ q.checkheap(0) THEN KernelLog.String('Heapviolation!'); KernelLog.Ln; END;
END;
KernelLog.String('TestQueue done');
END TestQueue;
END OSCQueue.
OSCQueue.TestQueue ~