Document queue

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() {