Keep Urgent Events in a Stable Queue in BBC Micro BASIC

An urgent event should not wait behind three routine ones. But two equally urgent events should not swap places unpredictably either. This small queue gives priority and fairness a precise rule: higher priority first, earlier insertion first when tied.

Include and initialise

Reserve A(4) for events, B(4) for priorities, public V/P/R/O/N/M/E/D and private J/K. Reserve lines 3000–3460, including the separated insertion and removal branches. Combine routines.bas with your caller using build.py and keep END, STOP or a jump before the helper. C64/BBC use GOSUB; Spectrum uses GO SUB. Private J/K must not be outer loop variables.

Call 3000 for a new queue. It clears all public fields and both arrays. N is the active count from zero to four. Retain N/A/B between requests. Active pairs must be sorted by descending priority; the helper checks that precondition before changing them.

Insert or remove one event

Set M=0, new event E and new priority D, then call 3100 to insert. Set M=1 and call 3100 to remove the highest-priority pair. Supply byte-valued events and priorities;255 is a valid event, so use the result flag rather than treating the returned event as an absence test.

O=0 rejects invalid count/mode, active pairs, ordering or insertion inputs. The queue survives unchanged. Valid requests return O=1. R=1 reports a change and V/P describes the inserted or removed pair. A full insertion or empty removal is a valid no-op: R=0,V=255,P=0. A full queue rejects a new event even if its priority is higher; it does not evict an existing one.

Removal shifts the remaining active pairs and clears the vacated pair to zero. Insertion keeps existing equal priorities first. Inputs M/E/D survive. Removal ignores E/D because they are not inputs to that operation. This BASIC port explicitly checks numeric/ordering preconditions that byte-valued assembly callers must also respect.

The reusable routine

Reusable numbered routines

3000 LET V=0: LET P=0: LET R=0: LET O=0: LET N=0: LET M=0: LET E=0: LET D=0
3010 FOR J=1 TO 4: LET A(J)=0: LET B(J)=0: NEXT J: RETURN
3100 LET V=255: LET P=0: LET R=0: LET O=0
3110 IF N<0 OR N>4 OR N<>INT (N) THEN RETURN
3120 IF M<>0 AND M<>1 THEN RETURN
3130 IF N=0 THEN GOTO 3210
3140 FOR J=1 TO N
3150 IF A(J)<0 OR A(J)>255 OR A(J)<>INT (A(J)) THEN RETURN
3160 IF B(J)<0 OR B(J)>255 OR B(J)<>INT (B(J)) THEN RETURN
3170 IF J=1 THEN GOTO 3190
3180 IF B(J)>B(J-1) THEN RETURN
3190 NEXT J
3210 IF M=1 THEN GOTO 3400
3220 IF E<0 OR E>255 OR E<>INT (E) THEN RETURN
3230 IF D<0 OR D>255 OR D<>INT (D) THEN RETURN
3240 LET O=1
3250 IF N=4 THEN RETURN
3260 LET K=N+1
3270 IF K=1 THEN GOTO 3320
3280 IF B(K-1)>=D THEN GOTO 3320
3290 LET A(K)=A(K-1): LET B(K)=B(K-1): LET K=K-1: GOTO 3270
3320 LET A(K)=E: LET B(K)=D: LET N=N+1: LET V=E: LET P=D: LET R=1: RETURN
3400 LET O=1
3410 IF N=0 THEN RETURN
3420 LET V=A(1): LET P=B(1): LET N=N-1
3430 IF N=0 THEN GOTO 3460
3440 FOR J=1 TO N: LET A(J)=A(J+1): LET B(J)=B(J+1): NEXT J
3460 LET A(N+1)=0: LET B(N+1)=0: LET R=1: RETURN

Insertion shifts the tail backwards so it cannot overwrite a pair before moving it. Removal shifts the surviving prefix forwards. One owner must perform each whole call; this is not an interrupt-safe producer/consumer queue.

Service a retained queue

The normal caller inserts events 11, 22, 33, 44 with priorities 1, 9, 9, 3. Removal returns 22, 33, 44, 11. The equal-priority 22 and 33 keep their insertion order. A fifth removal exercises the empty no-op.

Example calls from the maintained caller

100 GOSUB 3000: LET AA=0: LET BB=0
110 LET M=0: LET E=11: LET D=1
120 GOSUB 3100: GOSUB 2000
130 LET M=0: LET E=22: LET D=9
140 GOSUB 3100: GOSUB 2000
150 LET M=0: LET E=33: LET D=9
160 GOSUB 3100: GOSUB 2000
170 LET M=0: LET E=44: LET D=3
180 GOSUB 3100: GOSUB 2000
190 LET AA=1: LET BB=1: LET M=1
200 GOSUB 3100: GOSUB 2000
210 IF V<>22 THEN LET AA=0
220 IF P<>9 THEN LET BB=0
230 GOSUB 3100: GOSUB 2000
240 IF V<>33 THEN LET AA=0
250 IF P<>9 THEN LET BB=0
260 GOSUB 3100: GOSUB 2000
270 IF V<>44 THEN LET AA=0
280 IF P<>3 THEN LET BB=0
290 GOSUB 3100: GOSUB 2000
300 IF V<>11 THEN LET AA=0
310 IF P<>1 THEN LET BB=0
320 GOSUB 3100: GOSUB 2000
330 PRINT "PRIO RESULTS";AA;BB
340 ?(MB+995)=AA: ?(MB+996)=BB: ?(MB+997)=GD: ?(MB+998)=WC-256*INT (WC/256): ?(MB+999)=INT (WC/256): ?(MB+1000)=239: STOP

Line 2000, AA/BB/JJ/KK (Z/Q on Spectrum) and the mailbox are observation machinery. A game keeps its own queue, sets M/E/D, calls 3100 and checks both O and R. The complete native trace checks all fields and array cells after every request.

Customise urgency

The custom caller mixes priorities 0 and 255, keeping ties stable at the maximum too. Choose what those numbers mean for your game; the queue does not decide whether a sound, collision or scene change is urgent.

A plain FIFO is simpler when urgency is unnecessary. A binary heap can suit a much larger queue. High-priority traffic can starve routine work, so a game needing service guarantees must add an explicit budget or scheduling policy. The adjacent round-robin technique provides a different fairness rule, not an automatic replacement.

Mistake and repair

The wrong caller discards each requested priority by setting D=0. All events now tie, so the queue behaves as a FIFO and returns 11 before urgent 22. Both saved checks fail. Preserve priority alongside each event; the repair matches the normal source and loaded program exactly.

Cost and Maths for Games

The routine validates and searches at most four pairs. Insertion moves at most three existing pairs; removal moves at most three and clears one vacated pair. There is no allocation, clock or display upload. BASIC array cells carry interpreter-managed numeric storage, not a packed sixteen-byte structure.

Maths for Games connects ordering, stable ties and bounded lists. The Craft connects those rules to which events the player should hear or see first and what happens when a queue fills.

Machine and measured size

BBC BASIC arrays include element zero; this one-based array interface leaves it unused. Its diagnostic uses MODE 7 and HIMEM=&6000 to separate program storage, mailbox and screen. The helper itself changes neither mode nor HIMEM.

The numbered helper occupies 791 tokenised program bytes on this interpreter, including line headers. This excludes the caller, test tables, numeric scalar/array storage, interpreter stacks and ROM. Tokenised size is not machine-code size or a hardware-cycle count. No real-time or whole-game performance budget is inferred from the diagnostic. The caller’s AA/BB, JJ/KK and RAM mailbox are observation machinery, not required game state.

Execution evidence

Working, custom, deliberately wrong and exact repaired callers executed through BBC Micro’s stock BASIC interpreter under Emu198x 0.44.2. Build198x 0.2.9 tokenises C64 PRG and Spectrum TAP programs. C64 enters stock RUN, Spectrum uses ROM tape loading, and BBC enters every numbered source line through MOS/BASIC. Actual loaded program bytes, complete state packets, positive completion/count/guards and visible result pixels are checked. After the positive completion marker, the observer advances two complete display frames before capturing, so a partially scanned final character cannot masquerade as a finished picture. Firmware is not distributed.

An independent mathematical/order model checks the trace and rejects altered source, configuration, loaded program, state, completion and image evidence. Host exhaustive checks complement the native boundary/sequential examples; those host ranges are not claimed as natively exhaustive. The supplied diagnostic callers deliberately end with STOP; the interpreter report is expected. The wrong caller prints 0,0 and the normal/custom/repaired callers print 1,1.

Public CI checks retained evidence; it does not execute restricted firmware. Refresh with python3 scripts/verify-basic-services.py priority-event-queue bbc-micro --tools /path/to/extracted/releases and inspect with python3 scripts/check-basic-services.py priority-event-queue.

Explore further

Compare the assembly technique. The BASIC game-flow routine makes session boundaries explicit. Complete source and native evidence.