Queue data type

4 files changed, 341 insertions, 8 deletions

diff --git a/src/gleam/queue.gleam b/src/gleam/queue.gleam
new file mode 100644
index 0000000..b3278b1
--- /dev/null
+++ b/src/gleam/queue.gleam
@@ -0,0 +1,105 @@
+import gleam/list
+
+// TODO: document
+pub opaque type Queue(element) {
+  Queue(in: List(element), out: List(element))
+}
+
+// TODO: document
+pub fn new() -> Queue(a) {
+  Queue(in: [], out: [])
+}
+
+// TODO: document
+pub fn from_list(list: List(a)) -> Queue(a) {
+  Queue(in: list, out: [])
+}
+
+// TODO: document
+pub fn to_list(queue: Queue(a)) -> List(a) {
+  queue.in
+  |> list.append(list.reverse(queue.out))
+}
+
+// TODO: document
+pub fn is_empty(queue: Queue(a)) -> Bool {
+  queue.in == [] && queue.out == []
+}
+
+// TODO: document
+pub fn length(queue: Queue(a)) -> Int {
+  list.length(queue.in) + list.length(queue.out)
+}
+
+// TODO: document
+pub fn push_back(onto queue: Queue(a), this item: a) -> Queue(a) {
+  Queue(in: [item, ..queue.in], out: queue.out)
+}
+
+// TODO: document
+pub fn push_front(onto queue: Queue(a), this item: a) -> Queue(a) {
+  Queue(in: queue.in, out: [item, ..queue.out])
+}
+
+// TODO: document
+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)
+      Ok(tuple(first, queue))
+    }
+  }
+}
+
+// TODO: document
+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)
+      Ok(tuple(first, queue))
+    }
+  }
+}
+
+// TODO: document
+// O(1)
+pub fn reverse(queue: Queue(a)) -> Queue(a) {
+  Queue(in: queue.out, out: queue.in)
+}
+
+fn check_equal(
+  xs: List(t),
+  x_tail: List(t),
+  ys: List(t),
+  y_tail: List(t),
+  eq: fn(t, t) -> Bool,
+) -> Bool {
+  case xs, x_tail, ys, y_tail {
+    [], [], [], [] -> True
+    [x, ..xs], _, [y, ..ys], _ -> case eq(x, y) {
+      False -> False
+      True -> check_equal(xs, x_tail, ys, y_tail, eq)
+    }
+    [], [_, ..], _, _ -> check_equal(list.reverse(x_tail), [], ys, y_tail, eq)
+    _, _, [], [_, ..] -> check_equal(xs, x_tail, list.reverse(y_tail), [], eq)
+    _, _, _, _ -> False
+  }
+}
+
+// TODO: document
+pub fn is_logically_equal(
+  a: Queue(t),
+  to b: Queue(t),
+  checking element_is_equal: fn(t, t) -> Bool,
+) -> Bool {
+  check_equal(a.out, a.in, b.out, b.in, element_is_equal)
+}
+
+// TODO: document
+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/src/gleam/should.gleam b/src/gleam/should.gleam
index de07f10..9f88314 100644
--- a/src/gleam/should.gleam
+++ b/src/gleam/should.gleam
@@ -14,11 +14,15 @@ pub external fn equal(a, a) -> Expectation =
 pub external fn not_equal(a, a) -> Expectation =
   "gleam_stdlib" "should_not_equal"
 
-pub external fn be_true(Bool) -> Expectation =
-  "gleam_stdlib" "should_be_true"
+pub fn be_true(actual: Bool) -> Expectation {
+  actual
+  |> equal(True)
+}
 
-pub external fn be_false(Bool) -> Expectation =
-  "gleam_stdlib" "should_be_false"
+pub fn be_false(actual: Bool) -> Expectation {
+  actual
+  |> equal(False)
+}
 
 pub external fn be_ok(Result(a, b)) -> Expectation =
   "gleam_stdlib" "should_be_ok"
diff --git a/src/gleam_stdlib.erl b/src/gleam_stdlib.erl
index fc5499c..1b33126 100644
--- a/src/gleam_stdlib.erl
+++ b/src/gleam_stdlib.erl
@@ -1,8 +1,7 @@
 -module(gleam_stdlib).
 -include_lib("eunit/include/eunit.hrl").
 
--export([should_equal/2, should_not_equal/2, should_be_true/1,
-         should_be_false/1, should_be_ok/1, should_be_error/1,
+-export([should_equal/2, should_not_equal/2, should_be_ok/1, should_be_error/1,
          atom_from_string/1, atom_create_from_string/1, atom_to_string/1,
          map_get/2, iodata_append/2, iodata_prepend/2, identity/1,
          decode_int/1, decode_string/1, decode_bool/1, decode_float/1,
@@ -13,8 +12,6 @@
 
 should_equal(Actual, Expected) -> ?assertEqual(Expected, Actual).
 should_not_equal(Actual, Expected) -> ?assertNotEqual(Expected, Actual).
-should_be_true(A) -> ?assert(A).
-should_be_false(A) -> ?assertNot(A).
 should_be_ok(A) -> ?assertMatch({ok, _}, A).
 should_be_error(A) -> ?assertMatch({error, _}, A).
 
diff --git a/test/gleam/queue_test.gleam b/test/gleam/queue_test.gleam
new file mode 100644
index 0000000..128dab0
--- /dev/null
+++ b/test/gleam/queue_test.gleam
@@ -0,0 +1,227 @@
+import gleam/queue
+import gleam/int
+import gleam/list
+import gleam/should
+
+pub fn from_and_to_list_test() {
+  queue.from_list([])
+  |> should.equal(queue.new())
+
+  let test = fn(input) {
+    queue.from_list(input)
+    |> queue.to_list
+    |> 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 is_empty_test() {
+  queue.new()
+  |> queue.is_empty
+  |> should.be_true
+
+  queue.from_list([""])
+  |> queue.is_empty
+  |> should.be_false
+}
+
+pub fn length_test() {
+  let test = fn(input) {
+    queue.from_list(input)
+    |> queue.length
+    |> should.equal(list.length(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_test() {
+  queue.new()
+  |> queue.push_back(7)
+  |> queue.push_back(8)
+  |> queue.push_back(2)
+  |> queue.to_list
+  |> should.equal([2, 8, 7])
+}
+
+pub fn push_front_test() {
+  queue.new()
+  |> queue.push_back(7)
+  |> queue.push_back(8)
+  |> queue.push_back(2)
+  |> queue.push_front(4)
+  |> queue.push_front(3)
+  |> queue.to_list
+  |> should.equal([2, 8, 7, 4, 3])
+}
+
+pub fn pop_back_test() {
+  // We cannot construct the expected remainaing queue with from_list because
+  // it has different internal representation.
+  let expected_rest = 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.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]))))
+
+  queue.from_list([])
+  |> queue.pop_front
+  |> should.equal(Error(Nil))
+}
+
+pub fn reverse_test() {
+  queue.from_list([1, 2, 3])
+  |> queue.reverse
+  |> queue.to_list
+  |> should.equal([3, 2, 1])
+}
+
+pub fn is_equal_test() {
+  let should_equal = fn(a, b) {
+    a
+    |> queue.is_equal(to: b)
+    |> should.be_true
+  }
+
+  let should_not_equal = fn(a, b) {
+    a
+    |> queue.is_equal(to: b)
+    |> should.be_false
+  }
+
+  should_equal(queue.new(), queue.new())
+
+  queue.new()
+  |> queue.push_front(1)
+  |> should_equal(
+    queue.new()
+    |> queue.push_back(1),
+  )
+
+  queue.new()
+  |> queue.push_front(1)
+  |> should_equal(
+    queue.new()
+    |> queue.push_front(1),
+  )
+
+  queue.new()
+  |> queue.push_back(1)
+  |> queue.push_back(2)
+  |> should_equal(
+    queue.new()
+    |> queue.push_front(2)
+    |> queue.push_front(1),
+  )
+
+  queue.new()
+  |> queue.push_back(1)
+  |> should_not_equal(
+    queue.new()
+    |> queue.push_front(2)
+    |> queue.push_front(1),
+  )
+
+  queue.new()
+  |> queue.push_back(2)
+  |> queue.push_back(1)
+  |> should_not_equal(
+    queue.new()
+    |> queue.push_front(2)
+    |> queue.push_front(1),
+  )
+}
+
+pub fn is_logically_equal_test() {
+  let both_even_or_odd = fn(a, b) { int.is_even(a) == int.is_even(b) }
+
+  let should_equal = fn(a, b) {
+    a
+    |> queue.is_logically_equal(to: b, checking: both_even_or_odd)
+    |> should.be_true
+  }
+
+  let should_not_equal = fn(a, b) {
+    a
+    |> queue.is_logically_equal(to: b, checking: both_even_or_odd)
+    |> should.be_false
+  }
+
+  should_equal(queue.new(), queue.new())
+
+  queue.new()
+  |> queue.push_front(3)
+  |> should_equal(
+    queue.new()
+    |> queue.push_back(1),
+  )
+
+  queue.new()
+  |> queue.push_front(4)
+  |> should_equal(
+    queue.new()
+    |> queue.push_back(2),
+  )
+
+  queue.new()
+  |> queue.push_front(3)
+  |> should_equal(
+    queue.new()
+    |> queue.push_front(1),
+  )
+
+  queue.new()
+  |> queue.push_back(3)
+  |> queue.push_back(4)
+  |> should_equal(
+    queue.new()
+    |> queue.push_front(2)
+    |> queue.push_front(1),
+  )
+
+  queue.new()
+  |> queue.push_back(1)
+  |> should_not_equal(
+    queue.new()
+    |> queue.push_front(2)
+    |> queue.push_front(1),
+  )
+
+  queue.new()
+  |> queue.push_back(2)
+  |> queue.push_back(1)
+  |> should_not_equal(
+    queue.new()
+    |> queue.push_front(2)
+    |> queue.push_front(1),
+  )
+
+  queue.new()
+  |> queue.push_back(4)
+  |> queue.push_back(3)
+  |> should_not_equal(
+    queue.new()
+    |> queue.push_front(2)
+    |> queue.push_front(1),
+  )
+}