fifo v0.1.0 FIFO View Source

A first-in-first-out queue data structure for Elixir.

With a first-in-first-out (FIFO) queue, the first item inserted is the first item removed. A real-life analogy is the line, or queue, at the grocery store. The first person to get in line is the first person helped, and that order is maintained until the line is empty.

iex> queue = FIFO.new
#FIFO<[]>
iex> queue = queue |> FIFO.push(1) |> FIFO.push(2)
#FIFO<[1, 2]>
iex> {{:value, 1}, queue} = FIFO.pop(queue)
iex> queue
#FIFO<[2]>
iex> {{:value, 2}, queue} = FIFO.pop(queue)
iex> {:empty, queue} = FIFO.pop(queue)
iex> queue
#FIFO<[]>

Under the hood, this library uses the :queue data structure in Erlang's standard library: https://erlang.org/doc/man/queue.html. It wraps the Original API with a few name changes.

The reason for this library is to provide a more Elixir idiomatic queue implementation. For example, I renamed Erlang's is_empty/1 to empty?/1. More importantly, I reordered arguments to allow piping, so the queue is the first argument:

iex> FIFO.new |> FIFO.push(1) |> FIFO.push(2)
#FIFO<[1, 2]>

Additionally, this data structure implements three Elixir protocols: Inspect, Enumerable, and Collectable. Inspect allows pretty printing, as you can see in the example above. Enumerable and Collectable are useful for working with collections.

A limitation of this implementation is that queues cannot reliably be compared using ==/2. That is because of the way the Erlang library implements the queue to amortize operations. If you need to compare two queues, you can use FIFO.equal?/2.

iex> queue1 = FIFO.new(1..3)
iex> queue2 = FIFO.new |> FIFO.push(1) |> FIFO.push(2) |> FIFO.push(3)
iex> queue1 == queue2
false
iex> FIFO.equal?(queue1, queue2)
true

Link to this section Summary

Types

empty_out()

queue()

t()

tagged_value(term)

value_out()

Functions

empty?(fifo)

Returns true if the queue has no items. Returns false if the queue has items.

equal?(queue1, queue2)

Compares two queues. Returns true if they contain the same items in the same order, returns false if not.

filter(fifo, func)

Filters a queue.

from_list(list)

Creates a queue from a list.

join(fifo1, fifo2)

Returns a new queue which is a combination of queue1 and queue2. queue1 is in front of queue2.

length(fifo)

Returns the length of the queue.

member?(fifo, item)

Returns true if item matches a value in queue. Returns false if not.

new()

Returns an empty queue.

new(enumerable)

Creates a queue from an enumerable.

new(enumerable, transform)

Creates a queue from an enumerable via the transformation function.

pop(fifo)

Removes item from the front of the queue.

pop_r(fifo)

Returns an item from the end of the queue.

push(fifo, item)

Enqueues an item at the end of the queue.

push_r(fifo, item)

Enqueues an item at the front of the queue.

queue?(arg1)

Returns true if the given value is a queue. Returns false if not.

reverse(fifo)

Reverses a queue.

split(fifo, n)

Splits a queue into two queues, starting from the given position n.

to_list(fifo)

Returns a list of items in a queue.

Link to this section Types

empty_out()

Specs

empty_out() :: {:empty, t()}

queue()

(opaque)

Specs

queue()

t()

Specs

t() :: queue()

tagged_value(term)

Specs

tagged_value(term) :: {:value, term}

value_out()

Specs

value_out() :: {tagged_value(term()), t()}

Link to this section Functions

empty?(fifo)

Specs

empty?(t()) :: boolean()

Returns true if the queue has no items. Returns false if the queue has items.

Examples

iex> queue = FIFO.new
iex> FIFO.empty?(queue)
true

iex> queue = FIFO.from_list([1])
iex> FIFO.empty?(queue)
false

equal?(queue1, queue2)

Specs

equal?(t(), t()) :: boolean()

Compares two queues. Returns true if they contain the same items in the same order, returns false if not.

Because of the implementation of :queue, you cannot reliably compare two queues using ==/2. Use FIFO.equal?/2 instead.

Examples

iex> queue1 = FIFO.new([1, 2, 3])
iex> queue2 = FIFO.new([1, 2, 3])
iex> FIFO.equal?(queue1, queue2)
true

iex> queue1 = FIFO.new([1, 2, 3])
iex> queue2 = FIFO.new([1, 2])
iex> FIFO.equal?(queue1, queue2)
false

filter(fifo, func)

Specs

filter(t(), (term() -> boolean())) :: t()

Filters a queue.

Examples

iex> queue = FIFO.from_list([1,2,3,4])
iex> FIFO.filter(queue, fn item -> rem(item, 2) != 0 end)
#FIFO<[1, 3]>

from_list(list)

Specs

from_list(list()) :: t()

Creates a queue from a list.

Examples

iex> FIFO.from_list([1, 2, 3])
#FIFO<[1, 2, 3]>

join(fifo1, fifo2)

Specs

join(t(), t()) :: t()

Returns a new queue which is a combination of queue1 and queue2. queue1 is in front of queue2.

Examples

iex> queue1 = FIFO.from_list([1, 2])
iex> queue2 = FIFO.from_list([3, 4])
iex> FIFO.join(queue1, queue2)
#FIFO<[1, 2, 3, 4]>

length(fifo)

Specs

length(t()) :: non_neg_integer()

Returns the length of the queue.

Examples

iex> queue = FIFO.new
iex> FIFO.length(queue)
0

iex> queue = FIFO.from_list([1, 2, 3])
iex> FIFO.length(queue)
3

member?(fifo, item)

Specs

member?(t(), term()) :: boolean()

Returns true if item matches a value in queue. Returns false if not.

Examples

iex> queue = FIFO.from_list([1, 2, 3])
iex> FIFO.member?(queue, 2)
true

iex> queue = FIFO.from_list([1, 2, 3])
iex> FIFO.member?(queue, 7)
false

new()

Specs

new() :: t()

Returns an empty queue.

Examples

iex> FIFO.new()
#FIFO<[]>

new(enumerable)

Specs

new(Enum.t()) :: t()

Creates a queue from an enumerable.

Examples

iex> FIFO.new([1, 2, 3])
#FIFO<[1, 2, 3]>

new(enumerable, transform)

Specs

new(Enum.t(), (term() -> term())) :: t()

Creates a queue from an enumerable via the transformation function.

Examples

iex> FIFO.new([1, 2, 3], fn n -> n * n end)
#FIFO<[1, 4, 9]>

pop(fifo)

Specs

pop(t()) :: value_out() | empty_out()

Removes item from the front of the queue.

Examples

iex> queue = FIFO.from_list([1, 2])
iex> {{:value, 1}, queue} = FIFO.pop(queue)
iex> queue
#FIFO<[2]>

iex> queue = FIFO.new
iex> {:empty, queue} = FIFO.pop(queue)
iex> queue
#FIFO<[]>

pop_r(fifo)

Specs

pop_r(t()) :: value_out() | empty_out()

Returns an item from the end of the queue.

Examples

iex> queue = FIFO.from_list([1, 2, 3])
iex> {{:value, 3}, queue} = FIFO.pop_r(queue)
iex> queue
#FIFO<[1, 2]>

iex> queue = FIFO.new
iex> {:empty, queue} = FIFO.pop_r(queue)
iex> queue
#FIFO<[]>

push(fifo, item)

Specs

push(t(), term()) :: t()

Enqueues an item at the end of the queue.

Examples

iex> queue = FIFO.from_list([1, 2])
iex> FIFO.push(queue, 3)
#FIFO<[1, 2, 3]>

push_r(fifo, item)

Specs

push_r(t(), term()) :: t()

Enqueues an item at the front of the queue.

Examples

iex> queue = FIFO.from_list([1, 2])
iex> FIFO.push_r(queue, 3)
#FIFO<[3, 1, 2]>

queue?(arg1)

Specs

queue?(t()) :: boolean()

Returns true if the given value is a queue. Returns false if not.

Examples

iex> FIFO.queue?(FIFO.new)
true

iex> FIFO.queue?([])
false

reverse(fifo)

Specs

reverse(t()) :: t()

Reverses a queue.

Examples

iex> queue = FIFO.from_list([1, 2, 3])
iex> FIFO.reverse(queue)
#FIFO<[3, 2, 1]>

split(fifo, n)

Specs

split(t(), integer()) :: {t(), t()}

Splits a queue into two queues, starting from the given position n.

Examples

iex> queue = FIFO.from_list([1, 2, 3])
iex> {queue2, queue3} = FIFO.split(queue, 1)
iex> queue2
#FIFO<[1]>
iex> queue3
#FIFO<[2, 3]>

to_list(fifo)

Specs

to_list(t()) :: list()

Returns a list of items in a queue.

Examples

iex> queue = FIFO.from_list([1, 2, 3, 4])
iex> FIFO.to_list(queue)
[1, 2, 3, 4]