diff options
| -rw-r--r-- | CHANGELOG.md | 2 | ||||
| -rw-r--r-- | src/gleam/queue.gleam | 30 | ||||
| -rw-r--r-- | test/gleam/queue_test.gleam | 160 |
3 files changed, 126 insertions, 66 deletions
diff --git a/CHANGELOG.md b/CHANGELOG.md index 36ef33d..a6fdafa 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -8,6 +8,8 @@ - The `bool` module gains the `nand`, `nor`, `exclusive_nor`, and `exclusive_or` functions. - The `bit_builder` module gains the `from_string_builder` function. - The `list` modules gains the `permutations` function. +- Breaking change in `queue.from_list`. The head element in the list becomes the first element in the queue. +- Fix `queue.pop_back` and `queue.pop_front` ## v0.12.0 - 2020-11-04 diff --git a/src/gleam/queue.gleam b/src/gleam/queue.gleam index 1df8d12..bab4b48 100644 --- a/src/gleam/queue.gleam +++ b/src/gleam/queue.gleam @@ -24,7 +24,7 @@ pub fn new() -> Queue(a) { } /// Convert a list of elements into a queue of the same elements in the same -/// order. +/// order. The head element in the list becomes the front element in the queue. /// /// This function runs in constant time. /// @@ -34,11 +34,11 @@ pub fn new() -> Queue(a) { /// 3 /// pub fn from_list(list: List(a)) -> Queue(a) { - Queue(in: list, out: []) + Queue(in: [], out: list) } /// Convert a queue of elements into a list of the same elements in the same -/// order. +/// order. The front element in the queue becomes the head element in the list. /// /// This function runs in linear time. /// @@ -95,8 +95,8 @@ pub fn length(queue: Queue(a)) -> Int { /// /// # Examples /// -/// > [0, 0] |> from_list |> push_back(1) |> to_list -/// [0, 0, 1] +/// > [1, 2] |> from_list |> push_back(3) |> to_list +/// [1, 2, 3] /// pub fn push_back(onto queue: Queue(a), this item: a) -> Queue(a) { Queue(in: [item, ..queue.in], out: queue.out) @@ -113,7 +113,7 @@ pub fn push_front(onto queue: Queue(a), this item: a) -> Queue(a) { Queue(in: queue.in, out: [item, ..queue.out]) } -/// Get the first element from the back of the of the queue, returning the +/// Get the last element from the queue, returning the /// element and a new queue without that element. /// /// This function typically runs in constant time, but will occasionally run in @@ -122,7 +122,7 @@ pub fn push_front(onto queue: Queue(a), this item: a) -> Queue(a) { /// # Examples /// /// > queue.new() -/// > |> queue.push_front(0) +/// > |> queue.push_back(0) /// > |> queue.push_back(1) /// > |> queue.pop_back() /// Ok(tuple(1, queue.push_front(queue.new(), 0))) @@ -139,15 +139,15 @@ pub fn push_front(onto queue: Queue(a), this item: a) -> Queue(a) { pub fn pop_back(from queue: Queue(a)) -> Result(tuple(a, Queue(a)), Nil) { case queue { Queue(in: [], out: []) -> Error(Nil) - Queue(in: in, out: []) -> pop_back(Queue(in: [], out: list.reverse(in))) - Queue(in: in, out: [first, ..rest]) -> { - let queue = Queue(in: in, out: rest) + Queue(in: [], out: out) -> pop_back(Queue(in: list.reverse(out), out: [])) + Queue(in: [first, ..rest], out: out) -> { + let queue = Queue(in: rest, out: out) Ok(tuple(first, queue)) } } } -/// Get the first element from the front of the of the queue, returning the +/// Get the first element from the queue, returning the /// element and a new queue without that element. /// /// This function typically runs in constant time, but will occasionally run in @@ -156,8 +156,8 @@ pub fn pop_back(from queue: Queue(a)) -> Result(tuple(a, Queue(a)), Nil) { /// # Examples /// /// > queue.new() +/// > |> queue.push_front(1) /// > |> queue.push_front(0) -/// > |> queue.push_back(1) /// > |> queue.pop_front() /// Ok(tuple(0, queue.push_back(queue.new(), 1))) /// @@ -173,9 +173,9 @@ pub fn pop_back(from queue: Queue(a)) -> Result(tuple(a, Queue(a)), Nil) { pub fn pop_front(from queue: Queue(a)) -> Result(tuple(a, Queue(a)), Nil) { case queue { Queue(in: [], out: []) -> Error(Nil) - Queue(in: [], out: out) -> pop_front(Queue(in: list.reverse(out), out: [])) - Queue(in: [first, ..rest], out: out) -> { - let queue = Queue(in: rest, out: out) + Queue(in: in, out: []) -> pop_front(Queue(in: [], out: list.reverse(in))) + Queue(in: in, out: [first, ..rest]) -> { + let queue = Queue(in: in, out: rest) Ok(tuple(first, queue)) } } diff --git a/test/gleam/queue_test.gleam b/test/gleam/queue_test.gleam index ea38ed3..ae5dfeb 100644 --- a/test/gleam/queue_test.gleam +++ b/test/gleam/queue_test.gleam @@ -2,37 +2,16 @@ import gleam/queue import gleam/int import gleam/list import gleam/should +import gleam/pair pub fn from_and_to_list_test() { queue.from_list([]) |> should.equal(queue.new()) - [0, 0] + [1, 2, 3] |> 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) - } - - test([]) - test([1]) - test([1, 2]) - test([1, 2, 1]) - 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]) + |> should.equal([1, 2, 3]) } pub fn is_empty_test() { @@ -59,53 +38,132 @@ pub fn length_test() { test([1, 2, 1, 5, 2, 7, 2, 7, 8, 4, 545]) } -pub fn push_test() { - queue.new() - |> queue.push_back(7) - |> queue.push_back(8) - |> queue.push_back(2) +pub fn push_back_test() { + [1, 2] + |> queue.from_list + |> queue.push_back(3) |> queue.to_list - |> should.equal([7, 8, 2]) -} + |> should.equal([1, 2, 3]) -pub fn push_front_test() { queue.new() - |> queue.push_back(7) - |> queue.push_back(8) + |> queue.push_back(1) |> queue.push_back(2) - |> queue.push_front(4) - |> queue.push_front(3) + |> queue.push_back(3) |> queue.to_list - |> should.equal([3, 4, 7, 8, 2]) + |> should.equal([1, 2, 3]) +} - [0, 0] +pub fn push_front_test() { + [2, 3] |> queue.from_list |> queue.push_front(1) + |> queue.push_front(0) + |> queue.to_list + |> should.equal([0, 1, 2, 3]) +} + +pub fn push_test() { + queue.new() + |> queue.push_front("b") + |> queue.push_back("x") + |> queue.push_front("a") + |> queue.push_back("y") |> queue.to_list - |> should.equal([1, 0, 0]) + |> should.equal(["a", "b", "x", "y"]) } pub fn pop_back_test() { - // We cannot construct the expected remainaing queue with from_list because - // it has different internal representation. - let expected_rest = + assert Ok(tup) = + [1, 2, 3] + |> queue.from_list + |> queue.pop_back + + tup + |> pair.first + |> should.equal(3) + + tup + |> pair.second + |> queue.is_equal(queue.from_list([1, 2])) + |> should.be_true +} + +pub fn pop_back_after_push_back_test() { + assert Ok(tup) = queue.new() - |> queue.push_front(1) - |> queue.push_front(2) - queue.from_list([1, 2, 3]) - |> queue.pop_back - |> should.equal(Ok(tuple(3, expected_rest))) + |> queue.push_back(1) + |> queue.push_back(2) + |> queue.push_back(3) + |> queue.pop_back + + tup + |> pair.first + |> should.equal(3) +} + +pub fn pop_back_after_push_test() { + assert Ok(tup) = + queue.new() + |> queue.push_front("b") + |> queue.push_back("x") + |> queue.push_front("a") + |> queue.push_back("y") + |> queue.pop_back + + tup + |> pair.first + |> should.equal("y") +} +pub fn pop_back_empty_test() { queue.from_list([]) |> queue.pop_back |> should.equal(Error(Nil)) } pub fn pop_front_test() { - queue.from_list([1, 2, 3]) - |> queue.pop_front - |> should.equal(Ok(tuple(1, queue.from_list([2, 3])))) + assert Ok(tup) = + [1, 2, 3] + |> queue.from_list + |> queue.pop_front + + tup + |> pair.first + |> should.equal(1) + + tup + |> pair.second + |> queue.is_equal(queue.from_list([2, 3])) + |> should.be_true +} + +pub fn pop_front_after_push_front_test() { + assert Ok(tup) = + queue.new() + |> queue.push_front(3) + |> queue.push_front(2) + |> queue.push_front(1) + |> queue.pop_front + + tup + |> pair.first + |> should.equal(1) +} + +pub fn pop_front_after_push_test() { + assert Ok(tup) = + queue.new() + |> queue.push_front("b") + |> queue.push_back("x") + |> queue.push_front("a") + |> queue.pop_front + + tup + |> pair.first + |> should.equal("a") +} +pub fn pop_front_empty_test() { queue.from_list([]) |> queue.pop_front |> should.equal(Error(Nil)) @@ -115,7 +173,7 @@ pub fn reverse_test() { queue.from_list([1, 2, 3]) |> queue.reverse |> queue.to_list - |> should.equal([1, 2, 3]) + |> should.equal([3, 2, 1]) queue.new() |> queue.push_back(1) |