Queue/Definition: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 3,761: | Line 3,761: | ||
=={{header|jq}}== |
=={{header|jq}}== |
||
Since jq is a purely functional language, the entities chosen to represent queues |
|||
must somehow be presented to the functions that operate on them. |
|||
The approach taken here is to use a JSON object with a key named "queue" |
|||
that is to operate on it. |
|||
to hold the contents of the queue. This allows us to "pop" a queue by modifying |
|||
.queue while returning the popped item in the same object under a different key. |
|||
The definition of pop as given below is idiomatic in jq but implies |
|||
that popping an empty queue yields [null, []] rather than an error. An |
|||
alternative definition, pop_or_error, is also given to illustrate |
|||
how an error condition can be generated. |
|||
⚫ | |||
def fifo: []; |
|||
There are three possibilities for defining `pop` on an empty queue: |
|||
⚫ | |||
# Do not make a special case of it, which in our case would mean that `{queue: []} | pop` would emit `{queue: [], item: null}` |
|||
def pop: [.[0], .[1:]]; |
|||
# Raise an error |
|||
# Emit nothing |
|||
Here (1), is questionable as the queue might contain null, so here we define |
|||
⚫ | |||
`pop_or_error`, which raises an error when given an empty queue, and `pop`, which |
|||
emits the empty stream when given an empty queue. |
|||
In order to facilitate observing the evolving states of queues during processing, |
|||
we use the same `observe` function defined at [[Stack]]. |
|||
⚫ | |||
⚫ | |||
# Input: an object |
|||
⚫ | |||
# Output: the updated object with .emit filled in from `update|emit`. |
|||
<syntaxhighlight lang="jq">fifo | pop # produces [null,[]] |
|||
# `emit` may produce a stream of values, which need not be strings. |
|||
def observe(update; emit): |
|||
def s(stream): reduce stream as $_ (null; |
|||
if $_ == null then . |
|||
elif . == null then "\($_)" |
|||
else . + "\n\($_)" |
|||
end); |
|||
.emit as $x |
|||
| update |
|||
| .emit = s($x // null, emit); |
|||
⚫ | |||
| push(42) # enqueue |
|||
| push(43) # enqueue |
|||
⚫ | |||
| .[0] # the value |
|||
# produces 43 |
|||
fifo |
def fifo: {queue: []}; |
||
| fifo|push(2) as $q2 |
|||
# Is the input an object that represents the empty queue? |
|||
| [($q1|pop|.[0]), ($q2|pop|.[0])] |
|||
def isempty: |
|||
# produces: [1, 2]</syntaxhighlight> |
|||
type == "object" |
|||
and (.queue | length == 0); # so .queue == null and .queue == [] are equivalent |
|||
⚫ | |||
def pop: if isempty then empty else .item = .queue[0] | .queue |= .[1:] end; |
|||
⚫ | |||
⚫ | |||
# fifo | pop // "nothing" # produces the string "nothing" |
|||
⚫ | |||
| observe(push(42); "length after pushing: \(.queue | length)" ) |
|||
| observe(push(43); "length after pushing: \(.queue | length)" ) |
|||
⚫ | |||
| .emit, .item |
|||
⚫ | |||
'''Output''' |
|||
<pre> |
|||
length after pushing: 1 |
|||
length after pushing: 2 |
|||
42 |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |