Change queue.from_list. Fix queue.pop_back and queue.pop_front

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)