.TH queue 3 "stdlib  1.15.3" "Ericsson AB" "ERLANG MODULE DEFINITION"
.SH MODULE
queue \- Abstract Data Type for FIFO Queues
.SH DESCRIPTION
.LP
This module implements (double ended) FIFO queues in an efficient manner\&.
.LP
All functions fail with reason \fIbadarg\fR if arguments are of wrong type, for example queue arguments are not queues, indexes are not integers, list arguments are not lists\&. Improper lists cause internal crashes\&. An index out of range for a queue also causes a failure with reason \fIbadarg\fR\&.
.LP
Some functions, where noted, fail with reason \fIempty\fR for an empty queue\&.
.LP
All operations has an amortized O(1) running time, except \fIlen/1\fR, \fIjoin/2\fR, \fIsplit/2\fR and \fIfilter/2\fR that are O(n)\&. To minimize the size of a queue minimizing the amount of garbage built by queue operations, the queues do not contain explicit length information, and that is why \fIlen/1\fR is O(n)\&. If better performance for this particular operation is essential, it is easy for the caller to keep track of the length\&.
.LP
Queues are double ended\&. The mental picture of a queue is a line of people (items) waiting for their turn\&. The queue front is the end with the item that has waited the longest\&. The queue rear is the end an item enters when it starts to wait\&. If instead using the mental picture of a list, the front is called head and the rear is called tail\&.
.LP
Entering at the front and exiting at the rear are reverse operations on the queue\&.
.LP
The module has several sets of interface functions\&. The "Original API", the "Extended API" and the "Okasaki API"\&.
.LP
The "Original API" and the "Extended API" both use the mental picture of a waiting line of items\&. Both also have reverse operations suffixed "_r"\&.
.LP
The "Original API" item removal functions return compound terms with both the removed item and the resulting queue\&. The "Extended API" contain alternative functions that build less garbage as well as functions for just inspecting the queue ends\&. Also the "Okasaki API" functions build less garbage\&.
.LP
The "Okasaki API" is inspired by "Purely Functional Data structures" by Chris Okasaki\&. It regards queues as lists\&. The API is by many regarded as strange and avoidable\&. For example many reverse operations have lexically reversed names, some with more readable but perhaps less understandable aliases\&.

.SH ORIGINAL API
.SH EXPORTS
.LP
.B
new() -> Q
.br
.RS
.TP
Types
Q = queue()
.br
.RE
.RS
.LP
Returns an empty queue\&.
.RE
.LP
.B
is_queue(Term) -> true | false
.br
.RS
.TP
Types
Term = term()
.br
.RE
.RS
.LP
Tests if \fIQ\fR is a queue and returns \fItrue\fR if so and \fIfalse\fR otherwise\&.
.RE
.LP
.B
is_empty(Q) -> true | false
.br
.RS
.TP
Types
Q = queue()
.br
.RE
.RS
.LP
Tests if \fIQ\fR is empty and returns \fItrue\fR if so and \fIfalse\fR otherwise\&.
.RE
.LP
.B
len(Q) -> N
.br
.RS
.TP
Types
Q = queue()
.br
N = integer()
.br
.RE
.RS
.LP
Calculates and returns the length of queue \fIQ\fR\&.
.RE
.LP
.B
in(Item, Q1) -> Q2
.br
.RS
.TP
Types
Item = term()
.br
Q1 = Q2 = queue()
.br
.RE
.RS
.LP
Inserts \fIItem\fR at the rear of queue \fIQ1\fR\&. Returns the resulting queue \fIQ2\fR\&.
.RE
.LP
.B
in_r(Item, Q1) -> Q2
.br
.RS
.TP
Types
Item = term()
.br
Q1 = Q2 = queue()
.br
.RE
.RS
.LP
Inserts \fIItem\fR at the front of queue \fIQ1\fR\&. Returns the resulting queue \fIQ2\fR\&.
.RE
.LP
.B
out(Q1) -> Result
.br
.RS
.TP
Types
Result = {{value, Item}, Q2} | {empty, Q1}
.br
Q1 = Q2 = queue()
.br
.RE
.RS
.LP
Removes the item at the front of queue \fIQ1\fR\&. Returns the tuple \fI{{value, Item}, Q2}\fR, where \fIItem\fR is the item removed and \fIQ2\fR is the resulting queue\&. If \fIQ1\fR is empty, the tuple \fI{empty, Q1}\fR is returned\&.
.RE
.LP
.B
out_r(Q1) -> Result
.br
.RS
.TP
Types
Result = {{value, Item}, Q2} | {empty, Q1}
.br
Q1 = Q2 = queue()
.br
.RE
.RS
.LP
Removes the item at the rear of the queue \fIQ1\fR\&. Returns the tuple \fI{{value, Item}, Q2}\fR, where \fIItem\fR is the item removed and \fIQ2\fR is the new queue\&. If \fIQ1\fR is empty, the tuple \fI{empty, Q1}\fR is returned\&. 
.RE
.LP
.B
from_list(L) -> queue()
.br
.RS
.TP
Types
L = list()
.br
.RE
.RS
.LP
Returns a queue containing the items in \fIL\fR in the same order; the head item of the list will become the front item of the queue\&.
.RE
.LP
.B
to_list(Q) -> list()
.br
.RS
.TP
Types
Q = queue()
.br
.RE
.RS
.LP
Returns a list of the items in the queue in the same order; the front item of the queue will become the head of the list\&.
.RE
.LP
.B
reverse(Q1) -> Q2
.br
.RS
.TP
Types
Q1 = Q2 = queue()
.br
.RE
.RS
.LP
Returns a queue \fIQ2\fR that contains the items of \fIQ1\fR in the reverse order\&.
.RE
.LP
.B
split(N, Q1) -> {Q2,Q3}
.br
.RS
.TP
Types
N = integer()
.br
Q1 = Q2 = Q3 = queue()
.br
.RE
.RS
.LP
Splits \fIQ1\fR in two\&. The \fIN\fR front items are put in \fIQ2\fR and the rest in \fIQ3\fR
.RE
.LP
.B
join(Q1, Q2) -> Q3
.br
.RS
.TP
Types
Q1 = Q2 = Q3 = queue()
.br
.RE
.RS
.LP
Returns a queue \fIQ3\fR that is the result of joining \fIQ1\fR and \fIQ2\fR with \fIQ1\fR in front of \fIQ2\fR\&.
.RE
.LP
.B
filter(Fun, Q1) -> Q2
.br
.RS
.TP
Types
Fun = fun(Item) -> bool() | list()
.br
Q1 = Q2 = queue()
.br
.RE
.RS
.LP
Returns a queue \fIQ2\fR that is the result of calling \fIFun(Item)\fR on all items in \fIQ1\fR, in order from front to rear\&.
.LP
If \fIFun(Item)\fR returns \fItrue\fR, \fIItem\fR is copied to the result queue\&. If it returns \fIfalse\fR, \fIItem\fR is not copied\&. If it returns a list the list elements are inserted instead of \fIItem\fR in the result queue\&.
.LP
So, \fIFun(Item)\fR returning \fI[Item]\fR is thereby semantically equivalent to returning \fItrue\fR, just as returning \fI[]\fR is semantically equivalent to returning \fIfalse\fR\&. But returning a list builds more garbage than returning an atom\&.
.RE
.SH EXTENDED API
.SH EXPORTS
.LP
.B
get(Q) -> Item
.br
.RS
.TP
Types
Item = term()
.br
Q = queue()
.br
.RE
.RS
.LP
Returns \fIItem\fR at the front of queue \fIQ\fR\&.
.LP
Fails with reason \fIempty\fR if \fIQ\fR is empty\&.
.RE
.LP
.B
get_r(Q) -> Item
.br
.RS
.TP
Types
Item = term()
.br
Q = queue()
.br
.RE
.RS
.LP
Returns \fIItem\fR at the rear of queue \fIQ\fR\&.
.LP
Fails with reason \fIempty\fR if \fIQ\fR is empty\&.
.RE
.LP
.B
drop(Q1) -> Q2
.br
.RS
.TP
Types
Item = term()
.br
Q1 = Q2 = queue()
.br
.RE
.RS
.LP
Returns a queue \fIQ2\fR that is the result of removing the front item from \fIQ1\fR\&.
.LP
Fails with reason \fIempty\fR if \fIQ1\fR is empty\&.
.RE
.LP
.B
drop_r(Q1) -> Q2
.br
.RS
.TP
Types
Item = term()
.br
Q1 = Q2 = queue()
.br
.RE
.RS
.LP
Returns a queue \fIQ2\fR that is the result of removing the rear item from \fIQ1\fR\&.
.LP
Fails with reason \fIempty\fR if \fIQ1\fR is empty\&.
.RE
.LP
.B
peek(Q) -> {value,Item} | empty
.br
.RS
.TP
Types
Item = term()
.br
Q = queue()
.br
.RE
.RS
.LP
Returns the tuple \fI{value, Item}\fR where \fIItem\fR is the front item of \fIQ\fR, or \fIempty\fR if \fIQ1\fR is empty\&.
.RE
.LP
.B
peek_r(Q) -> {value,Item} | empty
.br
.RS
.TP
Types
Item = term()
.br
Q = queue()
.br
.RE
.RS
.LP
Returns the tuple \fI{value, Item}\fR where \fIItem\fR is the rear item of \fIQ\fR, or \fIempty\fR if \fIQ1\fR is empty\&.
.RE
.SH OKASAKI API
.SH EXPORTS
.LP
.B
cons(Item, Q1) -> Q2
.br
.RS
.TP
Types
Item = term()
.br
Q1 = Q2 = queue()
.br
.RE
.RS
.LP
Inserts \fIItem\fR at the head of queue \fIQ1\fR\&. Returns the new queue \fIQ2\fR\&.
.RE
.LP
.B
head(Q) -> Item
.br
.RS
.TP
Types
Item = term()
.br
Q = queue()
.br
.RE
.RS
.LP
Returns \fIItem\fR from the head of queue \fIQ\fR\&.
.LP
Fails with reason \fIempty\fR if \fIQ\fR is empty\&.
.RE
.LP
.B
tail(Q1) -> Q2
.br
.RS
.TP
Types
Item = term()
.br
Q1 = Q2 = queue()
.br
.RE
.RS
.LP
Returns a queue \fIQ2\fR that is the result of removing the head item from \fIQ1\fR\&.
.LP
Fails with reason \fIempty\fR if \fIQ1\fR is empty\&.
.RE
.LP
.B
snoc(Q1, Item) -> Q2
.br
.RS
.TP
Types
Item = term()
.br
Q1 = Q2 = queue()
.br
.RE
.RS
.LP
Inserts \fIItem\fR as the tail item of queue \fIQ1\fR\&. Returns the new queue \fIQ2\fR\&.
.RE
.LP
.B
daeh(Q) -> Item
.br
.B
last(Q) -> Item
.br
.RS
.TP
Types
Item = term()
.br
Q = queue()
.br
.RE
.RS
.LP
Returns the tail item of queue \fIQ\fR\&.
.LP
Fails with reason \fIempty\fR if \fIQ\fR is empty\&.
.RE
.LP
.B
liat(Q1) -> Q2
.br
.B
init(Q1) -> Q2
.br
.B
lait(Q1) -> Q2
.br
.RS
.TP
Types
Item = term()
.br
Q1 = Q2 = queue()
.br
.RE
.RS
.LP
Returns a queue \fIQ2\fR that is the result of removing the tail item from \fIQ1\fR\&.
.LP
Fails with reason \fIempty\fR if \fIQ1\fR is empty\&.
.LP
The name \fIlait/1\fR is a misspelling - do not use it anymore\&.
.RE