[](https://hex.pm/packages/qu)
<!-- END HEADER -->
`Qu` is an Elixir library that provides a single interface to four different types of
queues: FIFO, LIFO, circular, and priority.
## Usage
All of the queue types support the same operations: `Qu.put/2` to add an item,
`Qu.pop/1` to remove the head, `Qu.peek/1` to view the head without removal,
`Qu.pull/2` to remove multiple items, and `Qu.size/1` to get the number of
items in the queue. These operations are demonstrated below. For more details
about the queue operations, see the documentation for each function.
To create and fill a FIFO queue with a maximum size of 3, use `Qu.new/2` and
then apply `Qu.put/2` in a reduction:
```elixir
fifo = Qu.new(:fifo, max_size: 3)
#=> #FIFO<read: [], write: [], size: 0, max_size: 3>
fifo =
Enum.reduce(["a", "b", "c"], fifo, fn item, q ->
{:ok, q} = Qu.put(q, item)
q
end)
#=> #FIFO<read: [], write: ["c", "b", "a"], size: 3, max_size: 3>
```
A priority queue expects items of the form `{priority_key, value}`. Here is
how to create and populate a priority queue where items are popped in
ascending order of priority:
```elixir
prio = Qu.new(:priority, priority_order: :asc)
Enum.reduce([{1, "a"}, {2, "b"}, {3, "c"}], prio, fn item, q ->
{:ok, q} = Qu.put(q, item)
q
end)
#=> #Priority<heap: #PairingHeap<root: {1, "a"}, size: 3, mode: :min>, size: 3, max_size: nil>
```
For FIFO, LIFO, and priority queues, applying `Qu.put/2` to a full queue returns
`:error`:
```elixir
Qu.new(:fifo, max_size: 0) |> Qu.put(fifo, "a")
#=> :error
```
An error is never returned when adding items to a circular queue, since the
oldest item is discarded when inserting into a full circular queue. To preserve
the common interface, `Qu.put/2` still returns `{:ok, updated_queue}` for a
circular queue.
The head of the queue can be removed and returned with `Qu.pop/1`:
```elixir
{:ok, fifo} = Qu.new(:fifo) |> Qu.put("a")
Qu.pop(fifo)
#=> {:ok, "a", #FIFO<read: [], write: [], size: 0, max_size: nil>}
```
For all queue types, `Qu.pop/1` returns `:error` if the queue is empty:
```elixir
Qu.new(:fifo, max_size: 0) |> Qu.pop()
#=> :error
```
The head can be viewed without modifying the queue using `Qu.peek/1`:
```elixir
{:ok, fifo} = Qu.new(:fifo) |> Qu.put("a")
Qu.peek(fifo)
#=> {:ok, "a"}
```
Similar to `Qu.pop/1`, `Qu.peek/1` will return `:error` if the queue is empty.
Use `Qu.pull/2` to remove and return multiple items:
```elixir
fifo = Qu.new(:fifo, max_size: 3)
["a", "b", "c"]
|> Enum.reduce(fifo, fn item, q ->
{:ok, q} = Qu.put(q, item)
q
end)
|> Qu.pull(3)
#=> {["a", "b", "c"], #FIFO<read: [], write: [], size: 0, max_size: 3>}
```
Note that `Qu.pull/2` does not return `:error` if the queue is empty or if the
number of elements pulled is larger than the queue size.
For all of the queue types, `Qu.size/1` returns the current size of the queue:
```elixir
{:ok, fifo} = Qu.new(:fifo) |> Qu.put("a")
Qu.size(fifo)
#=> 1
```
All of the queue types also implement the `Enumerable` and `Collectable`
protocols, so that `Enum.reduce/3`, `Enum.to_list/1`, and `Enum.into/2` may
be used.
## Supported queue types
Listed below are the supported queue types, as well as notes about their
implementations and usage guidelines.
### FIFO
A first-in, first-out queue, in which the oldest item in the queue will
be the next item removed. If the queue has a finite maximum size and is full,
the next insert will fail.
The implementation follows the
[Erlang queue](https://www.erlang.org/doc/man/queue) and uses separate read and
write lists to achieve `O(1)` amortized time for insert and delete operations.
### LIFO
A last-in, first-out queue, in which the item most recently added to the
queue will be the next item removed. This is also known as a _stack_. If the
queue has a finite maximum size and is full, the next insert will fail.
The implementation uses a single Elixir list and has `O(1)` time for both
insert and delete operations.
### Circular
A circular queue is similar to a FIFO queue in that the oldest item in the
queue will be the next item removed. However, when adding an item to a full
circular queue, the oldest item will be discarded to preserve the fixed size.
An insert in a full circular queue will always succeed.
The implementation borrows from the FIFO implementation, but has a modified
`pop/1` function to achieve the properties described above.
### Priority
In a priority queue, items are added as key-value pairs, where the key is a
sortable priority. Items are removed in priority order, either descending or
ascending, depending on the configuration.
The implementation uses a heap, specifically a pairing heap
(see the [`PairingHeap`](https://hexdocs.pm/pairing_heap/PairingHeap.html)
Elixir library), which has `O(1)` insert time and `O(log n)` amortized deletion
time.
