Queue

Queue module: functional double-ended queue (deque) using two lists.

Representation: Queue(front, back) The sequence from front to back is: front ++ reverse(back)

This gives amortised O(1) push and pop at both ends: push_front / push_back O(1) worst case pop_front / pop_back O(1) amortised (O(n) worst case on rebalance) peek_front / peek_back O(1) amortised size O(n) to_list O(n)

Rebalancing: when the "consume" end is empty we reverse the other list.

Types

typeQueueQueue(a) = Queue(List(a), List(a))#

Functions

fnemptyempty() : Queue(a)#

Returns an empty queue.

Examples

march> Queue.to_list(Queue.empty())
[]
march> Queue.is_empty(Queue.empty())
true

fnfrom_listfrom_list(xs : List(a)) : Queue(a)#

Build a queue from a list. The first element of the list becomes the front. O(n).

Examples

march> Queue.peek_front(Queue.from_list([1, 2, 3]))
Some(1)
march> Queue.to_list(Queue.from_list([]))
[]

fnis_emptyis_empty(q : Queue(a)) : Bool#

Returns true if the queue contains no elements. O(1).

Examples

march> Queue.is_empty(Queue.empty())
true
march> Queue.is_empty(Queue.push_back(Queue.empty(), 1))
false

fnpeek_backpeek_back(q : Queue(a)) : Option(a)#

Return the back element without removing it, or None if empty. O(1) amortised (O(n) when the back list is empty; the reversal is not kept).

Examples

march> Queue.peek_back(Queue.from_list([1, 2, 3]))
Some(3)
march> Queue.peek_back(Queue.push_front(Queue.empty(), 9))
Some(9)

fnpeek_frontpeek_front(q : Queue(a)) : Option(a)#

Return the front element without removing it, or None if empty. O(1) amortised (O(n) when the front list is empty; the reversal is not kept).

Examples

march> Queue.peek_front(Queue.from_list([1, 2, 3]))
Some(1)
march> Queue.peek_front(Queue.empty())
None

fnpop_backpop_back(q : Queue(a)) : Option((a, Queue(a)))#

Remove and return the back element. Returns Some((element, new_queue)) if non-empty, or None if empty. O(1) amortised: when the back list is exhausted the front list is reversed once into the back.

Examples

march> Option.map(Queue.pop_back(Queue.from_list([1, 2, 3])), fn p -> match p do (x, q) -> (x, Queue.to_list(q)) end)
Some((3, [1, 2]))
march> Queue.pop_back(Queue.empty())
None

fnpop_frontpop_front(q : Queue(a)) : Option((a, Queue(a)))#

Remove and return the front element. Returns Some((element, new_queue)) if non-empty, or None if empty. O(1) amortised: when the front list is exhausted the back list is reversed once into the front.

Examples

march> Option.map(Queue.pop_front(Queue.from_list([1, 2, 3])), fn p -> match p do (x, q) -> (x, Queue.to_list(q)) end)
Some((1, [2, 3]))
march> Queue.pop_front(Queue.empty())
None

fnpush_backpush_back(q : Queue(a), x : a) : Queue(a)#

Add an element to the back of the queue. O(1).

Examples

march> Queue.to_list(Queue.push_back(Queue.from_list([1, 2]), 3))
[1, 2, 3]

fnpush_frontpush_front(q : Queue(a), x : a) : Queue(a)#

Add an element to the front of the queue. O(1).

Examples

march> Queue.to_list(Queue.push_front(Queue.from_list([2, 3]), 1))
[1, 2, 3]

fnsizesize(q : Queue(a)) : Int#

Return the number of elements in the queue. O(n): both internal lists are counted.

Examples

march> Queue.size(Queue.from_list([1, 2, 3]))
3
march> Queue.size(Queue.empty())
0

fnto_listto_list(q : Queue(a)) : List(a)#

Convert the queue to a list ordered from front to back. O(n).

Examples

march> Queue.to_list(Queue.push_front(Queue.push_back(Queue.empty(), 2), 1))
[1, 2]