aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/gleam/queue.gleam105
-rw-r--r--src/gleam/should.gleam12
-rw-r--r--src/gleam_stdlib.erl5
-rw-r--r--test/gleam/queue_test.gleam227
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),
+ )
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-27 18:52:49 +0000