queues.inc — FIFO, LIFO, and priority queues

the 'queues.inc' file provides three types of queue, first in - first out (FIFO), last in - first out (LIFO), and simple priority based queues, in SDL for the Persistence of Vision Raytracer, version 3.8 or later.

the macro names are prefixed by an abbreviation of their respective "type", to keep the sets separate:

each set has a q?Create macro which returns an "object" (dictionary) which becomes the required argument to the other macros. when done using a queue, q?Discard will free up most of the memory used, the data, but the queue remains usable.

note that the queue types differ wrt the permissible "payloads". FIFOs allow every value qqPut to be of a different type, as do priority queues. however, stacked values, ie qsPushed, must all be of the same type as the first.

since usage of the queue types/macros is almost identical, the descriptions in the FIFO section mostly apply to all; the LIFO and priority queue sections only note the differences.

FIFO

QQ_MAXQUEUE

optionally declare this (integer) value to override the queue length limit, the default maximum is 10000 elements. this is the upper (length) limit for all queues created in that scene. must be declared before the '#include' statement.

qqCreate(len, optional strict)

this macro expands to a new queue object, sized for up to 'len' data elements, at least two. the corresponding identifier/variable becomes the mandatory first argument supplied to the other macros.

'strict' is a(n optional) boolean value which must be '0' or '1'. it selects the behaviour when a queue empty, or full, error condition arises. if true (that is '1') an error will be raised and parsing is aborted, otherwise the qqGet and qqPut macros will appear to work normal. strict true is the default.

qqDiscard(Q)

as the name suggests, qqDiscard simply frees the memory occupied by the data elements, think "reset". it does not #undef the 'Q' variable itself. the macro expands to (returns) nothing.

qqGet(Q)

removes the first element from the queue and expands to (returns) that value.

calling qqGet with an empty queue is an error, unless the queue was created with strict false; in which case an empty queue returns empty strings.

qqLength(Q)

expands to the current length of queue 'Q'.

qqPut(Q, elem)

appends 'elem' to the end of queue 'Q'. unless strict is false, overfilling a queue will raise an error. note that if strict is false and the full condition arises, the macro will appear to have worked, when in fact 'elem' has simply been discarded. returns/expands to nothing.

code example

the simple code example shows a small number of dissimilar items of data first queued, then retrieved for display. 

    #version 3.8;

    global_settings {assumed_gamma 1}

    #declare C = color rgbt <.123,.456,.789,1>;

    #include "queues.inc"

    #declare Q = qqCreate(5,);

    qqPut(Q,array [2] {.65, .6999999})

    qqPut(Q,501)

    qqPut(Q,C)

    qqPut(Q,concat("rgbft <",vstr(5,C,",",0,4),">"))

    #debug concat("queued ",str(qqLength(Q),0,0)," elements.\n")

    #declare A = qqGet(Q);
    #debug concat("array: ",str(A[0],0,8),", ",str(A[1],0,8),".\n")

    #debug concat("integer: ",str(qqGet(Q),0,0),".\n")

    #debug concat("colour: ",vstr(5,qqGet(Q),",",0,6),".\n")

    #debug concat("string: \"",qqGet(Q),"\".\n")

    qqDiscard(Q)

    #undef Q

LIFO

QS_MAXSTACK

as QQ_MAXQUEUE.

qsCreate(size, optional strict)

as qqCreate, but expands to a stack "object".

qsDiscard(S)

as qqDiscard.

qsPop(S)

removes the "top of stack" value from 'S' and expands to (returns) that. same provisos as qqGet.

qsPush(S, elem)

adds 'elem' as the new "top of stack" value of 'S'. the second and subsequent 'elem's must be of the same type as the first. otherwise as qqPut.

qsSize(S)

expands to the number of elements on stack 'S'.

priority queues

QP_MAXPRIO

as QQ_MAXQUEUE.

qpCreate(len, optional strict)

this macro expands to a new priority queue object, sized for up to a total of 'len' data elements, at least two. the corresponding identifier/variable becomes the mandatory first argument supplied to the other macros.

'strict', a boolean, works as described under qqCreate.

qpDiscard(P)

as qqDiscard.

qpGet(P)

removes the first, highest priority element from the queue, and expands to (returns) that value. same provisos as qqGet.

note, if there is a demand for retrieving given priority elements exclusively, I'd consider adding such a macro. write.

qpLength(P)

expands to the number of elements queued in 'P'.

qpPut(P, elem, optional prio)

appends 'elem' to the end of the given priority queue in 'P', defaulting to the lowest priority ('1') when the optional argument is omitted; the legal range for 'prio' is: 1,..,5. in other words, if you never supply the optional argument, the priority queue works exactly like a FIFO.

returns/expands to nothing. wrt strict, the same provisos apply as for qqGet.