diff options
| -rw-r--r-- | src/gleam/queue.gleam | 180 | ||||
| -rw-r--r-- | test/gleam/queue_test.gleam | 50 |
2 files changed, 212 insertions, 18 deletions
diff --git a/src/gleam/queue.gleam b/src/gleam/queue.gleam index b3278b1..dc85f89 100644 --- a/src/gleam/queue.gleam +++ b/src/gleam/queue.gleam @@ -1,47 +1,141 @@ import gleam/list -// TODO: document +/// A queue is an order collection of elements. It is similar to a list, but +/// unlike a list elements can be added to or removed from either the front or +/// the back in a performant fashion. +/// +/// The internal representation may be different for two queues with the same +/// elements in the same order if the queues were constructed in different +/// ways. This is the price paid for a queue's fast access at both the front +/// and the back. +/// +/// Because of unpredictable internal representation the equality operator `==` +/// may return surprising results, and the `is_equal` and `is_logically_equal` +/// functions are the recommended way to test queues for equality. +/// pub opaque type Queue(element) { Queue(in: List(element), out: List(element)) } -// TODO: document +/// Create a fresh queue that contains no values. +/// pub fn new() -> Queue(a) { Queue(in: [], out: []) } -// TODO: document +/// Convert a list of elements into a queue of the same elements in the same +/// order. +/// +/// This function runs in constant time. +/// +/// # Examples +/// +/// > [1, 2, 3] |> from_list |> length +/// 3 +/// pub fn from_list(list: List(a)) -> Queue(a) { Queue(in: list, out: []) } -// TODO: document +/// Convert a queue of elements into a list of the same elements in the same +/// order. +/// +/// This function runs in linear time. +/// +/// # Examples +/// +/// > new() |> push_back(1) |> push_back(2) |> to_list +/// [1, 2] +/// pub fn to_list(queue: Queue(a)) -> List(a) { - queue.in - |> list.append(list.reverse(queue.out)) + queue.out + |> list.append(list.reverse(queue.in)) } -// TODO: document +/// Determine whether or not the queue is empty. +/// +/// This function runs in constant time. +/// +/// ## Examples +/// +/// > [] |> from_list |> is_empty +/// True +/// +/// > [1] |> from_list |> is_empty +/// False +/// +/// > [1, 2] |> from_list |> is_empty +/// False +/// pub fn is_empty(queue: Queue(a)) -> Bool { queue.in == [] && queue.out == [] } -// TODO: document +/// Count the number of elements in a given queue. +/// +/// This function has to traverse the queue to determine the number of elements, +/// so it runs in linear time. +/// +/// ## Examples +/// +/// > length(from_list([])) +/// 0 +/// +/// > length(from_list([1])) +/// 1 +/// +/// > length(from_list([1, 2])) +/// 2 +/// pub fn length(queue: Queue(a)) -> Int { list.length(queue.in) + list.length(queue.out) } -// TODO: document +/// Push an element onto the back of the queue. +/// +/// # Examples +/// +/// > [0, 0] |> from_list |> push_back(1) |> to_list +/// [0, 0, 1] +/// pub fn push_back(onto queue: Queue(a), this item: a) -> Queue(a) { Queue(in: [item, ..queue.in], out: queue.out) } -// TODO: document +/// Push an element onto the front of the queue. +/// +/// # Examples +/// +/// > [0, 0] |> from_list |> push_front(1) |> to_list +/// [1, 0, 0] +/// pub fn push_front(onto queue: Queue(a), this item: a) -> Queue(a) { Queue(in: queue.in, out: [item, ..queue.out]) } -// TODO: document +/// Get the first element from the back of the of the queue, returning the +/// element and a new queue without that element. +/// +/// This function typically runs in constant time, but will occasionally run in +/// linear time. +/// +/// # Examples +/// +/// > queue.new() +/// > |> queue.push_front(0) +/// > |> queue.push_back(1) +/// > |> queue.pop_back() +/// Ok(tuple(1, queue.push_front(queue.new(), 0))) +/// +/// > queue.new() +/// > |> queue.push_front(0) +/// > |> queue.pop_back() +/// Ok(tuple(0, queue.new())) +/// +/// > queue.new() +/// > |> queue.pop_back() +/// Error(Nil) +/// pub fn pop_back(from queue: Queue(a)) -> Result(tuple(a, Queue(a)), Nil) { case queue { Queue(in: [], out: []) -> Error(Nil) @@ -53,7 +147,29 @@ pub fn pop_back(from queue: Queue(a)) -> Result(tuple(a, Queue(a)), Nil) { } } -// TODO: document +/// Get the first element from the front of the of the queue, returning the +/// element and a new queue without that element. +/// +/// This function typically runs in constant time, but will occasionally run in +/// linear time. +/// +/// # Examples +/// +/// > queue.new() +/// > |> queue.push_front(0) +/// > |> queue.push_back(1) +/// > |> queue.pop_front() +/// Ok(tuple(0, queue.push_back(queue.new(), 1))) +/// +/// > queue.new() +/// > |> queue.push_back(0) +/// > |> queue.pop_front() +/// Ok(tuple(0, queue.new())) +/// +/// > queue.new() +/// > |> queue.pop_back() +/// Error(Nil) +/// pub fn pop_front(from queue: Queue(a)) -> Result(tuple(a, Queue(a)), Nil) { case queue { Queue(in: [], out: []) -> Error(Nil) @@ -65,8 +181,22 @@ pub fn pop_front(from queue: Queue(a)) -> Result(tuple(a, Queue(a)), Nil) { } } -// TODO: document -// O(1) +/// Create a new queue from a given queue containing the same elements, but in +/// the opposite order. +/// +/// This function runs in constant time. +/// +/// ## Examples +/// +/// > reverse(from_list([])) +/// [] +/// +/// > reverse(from_list([1])) +/// [1] +/// +/// > reverse(from_list([1, 2])) +/// [2, 1] +/// pub fn reverse(queue: Queue(a)) -> Queue(a) { Queue(in: queue.out, out: queue.in) } @@ -90,7 +220,17 @@ fn check_equal( } } -// TODO: document +/// Check whether two queues have equal elements in the same order, where the +/// equality of elements is determined by a given equality checking function. +/// +/// This function is useful as the internal representation may be different for +/// two queues with the same elements in the same order depending on how they +/// were constructed, so the equality operator `==` may return surprising +/// results. +/// +/// This function runs in linear time multiplied by the time taken by the +/// element equality checking function. +/// pub fn is_logically_equal( a: Queue(t), to b: Queue(t), @@ -99,7 +239,15 @@ pub fn is_logically_equal( check_equal(a.out, a.in, b.out, b.in, element_is_equal) } -// TODO: document +/// Check whether two queues have the same elements in the same order. +/// +/// This function is useful as the internal representation may be different for +/// two queues with the same elements in the same order depending on how they +/// were constructed, so the equality operator `==` may return surprising +/// results. +/// +/// This function runs in linear time. +/// pub fn is_equal(a: Queue(t), to b: Queue(t)) -> Bool { check_equal(a.out, a.in, b.out, b.in, fn(a, b) { a == b }) } diff --git a/test/gleam/queue_test.gleam b/test/gleam/queue_test.gleam index 128dab0..e0e7378 100644 --- a/test/gleam/queue_test.gleam +++ b/test/gleam/queue_test.gleam @@ -7,9 +7,16 @@ pub fn from_and_to_list_test() { queue.from_list([]) |> should.equal(queue.new()) + [0, 0] + |> queue.from_list + |> queue.push_back(1) + |> queue.to_list + |> should.equal([0, 0, 1]) + let test = fn(input) { queue.from_list(input) |> queue.to_list + |> list.reverse |> should.equal(input) } @@ -20,6 +27,14 @@ pub fn from_and_to_list_test() { test([1, 2, 1, 5, 2, 7, 2, 7, 8, 4, 545]) } +pub fn push_back_test() { + [0, 0] + |> queue.from_list + |> queue.push_back(1) + |> queue.to_list + |> should.equal([0, 0, 1]) +} + pub fn is_empty_test() { queue.new() |> queue.is_empty @@ -50,7 +65,7 @@ pub fn push_test() { |> queue.push_back(8) |> queue.push_back(2) |> queue.to_list - |> should.equal([2, 8, 7]) + |> should.equal([7, 8, 2]) } pub fn push_front_test() { @@ -61,7 +76,13 @@ pub fn push_front_test() { |> queue.push_front(4) |> queue.push_front(3) |> queue.to_list - |> should.equal([2, 8, 7, 4, 3]) + |> should.equal([3, 4, 7, 8, 2]) + + [0, 0] + |> queue.from_list + |> queue.push_front(1) + |> queue.to_list + |> should.equal([1, 0, 0]) } pub fn pop_back_test() { @@ -93,7 +114,32 @@ pub fn reverse_test() { queue.from_list([1, 2, 3]) |> queue.reverse |> queue.to_list + |> should.equal([1, 2, 3]) + + queue.new() + |> queue.push_back(1) + |> queue.push_back(2) + |> queue.push_back(3) + |> queue.reverse + |> queue.to_list |> should.equal([3, 2, 1]) + + queue.new() + |> queue.push_front(1) + |> queue.push_front(2) + |> queue.push_front(3) + |> queue.reverse + |> queue.to_list + |> should.equal([1, 2, 3]) + + queue.new() + |> queue.push_front(1) + |> queue.push_front(2) + |> queue.push_back(3) + |> queue.push_back(4) + |> queue.reverse + |> queue.to_list + |> should.equal([4, 3, 1, 2]) } pub fn is_equal_test() { |