queues.inc — FIFOs, LIFOs, 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 macro sets separate, and keep namespace "pollution" down:

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

note that the queue types differ with respect to the permissible "payload". FIFOs allow every value qqPut to be of a different data 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 an 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("total of ",str(qqLength(Q),0,0)," elements queued.\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.

qpDiscardP(P, prio)

removes all elements of the given priority, leaves elements with other priorities untouched.

qpGet(P)

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

qpGetP(P, prio)

removes the first element of the given priority from the queue, even if higher priority elements exist, and expands to (returns) that value. same provisos as qqGet.

qpLength(P)

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

qpLengthP(P, prio)

expands to the number of elements of the given priority 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. that is, if you never supply the optional argument, the priority queue works exactly like a FIFO. expands to (returns) nothing.