diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/gleam/queue.gleam | 472 |
1 files changed, 234 insertions, 238 deletions
diff --git a/src/gleam/queue.gleam b/src/gleam/queue.gleam index 80cea16..6b12cfb 100644 --- a/src/gleam/queue.gleam +++ b/src/gleam/queue.gleam @@ -1,258 +1,254 @@ -if erlang { - import gleam/list +import gleam/list - /// 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)) - } +/// 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)) +} - /// Creates a fresh queue that contains no values. - /// - pub fn new() -> Queue(a) { - Queue(in: [], out: []) - } +/// Creates a fresh queue that contains no values. +/// +pub fn new() -> Queue(a) { + Queue(in: [], out: []) +} - /// Converts a list of elements into a queue of the same elements in the same - /// order. The head element in the list becomes the front element in the queue. - /// - /// 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: [], out: list) - } +/// Converts a list of elements into a queue of the same elements in the same +/// order. The head element in the list becomes the front element in the queue. +/// +/// 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: [], out: list) +} - /// Converts a queue of elements into a list of the same elements in the same - /// order. The front element in the queue becomes the head element in the list. - /// - /// 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.out - |> list.append(list.reverse(queue.in)) - } +/// Converts a queue of elements into a list of the same elements in the same +/// order. The front element in the queue becomes the head element in the list. +/// +/// 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.out + |> list.append(list.reverse(queue.in)) +} - /// Determines 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 == [] - } +/// Determines 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 == [] +} - /// Counts 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) - } +/// Counts 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) +} - /// Pushes an element onto the back of the queue. - /// - /// # Examples - /// - /// > [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) - } +/// Pushes an element onto the back of the queue. +/// +/// # Examples +/// +/// > [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) +} - /// Pushes 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]) - } +/// Pushes 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]) +} - /// Gets 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 - /// linear time. - /// - /// # Examples - /// - /// > queue.new() - /// > |> queue.push_back(0) - /// > |> queue.push_back(1) - /// > |> queue.pop_back() - /// Ok(#(1, queue.push_front(queue.new(), 0))) - /// - /// > queue.new() - /// > |> queue.push_front(0) - /// > |> queue.pop_back() - /// Ok(#(0, queue.new())) - /// - /// > queue.new() - /// > |> queue.pop_back() - /// Error(Nil) - /// - pub fn pop_back(from queue: Queue(a)) -> Result(#(a, Queue(a)), Nil) { - case queue { - Queue(in: [], out: []) -> Error(Nil) - 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(#(first, queue)) - } +/// Gets 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 +/// linear time. +/// +/// # Examples +/// +/// > queue.new() +/// > |> queue.push_back(0) +/// > |> queue.push_back(1) +/// > |> queue.pop_back() +/// Ok(#(1, queue.push_front(queue.new(), 0))) +/// +/// > queue.new() +/// > |> queue.push_front(0) +/// > |> queue.pop_back() +/// Ok(#(0, queue.new())) +/// +/// > queue.new() +/// > |> queue.pop_back() +/// Error(Nil) +/// +pub fn pop_back(from queue: Queue(a)) -> Result(#(a, Queue(a)), Nil) { + case queue { + Queue(in: [], out: []) -> Error(Nil) + 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(#(first, queue)) } } +} - /// Gets 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 - /// linear time. - /// - /// # Examples - /// - /// > queue.new() - /// > |> queue.push_front(1) - /// > |> queue.push_front(0) - /// > |> queue.pop_front() - /// Ok(#(0, queue.push_back(queue.new(), 1))) - /// - /// > queue.new() - /// > |> queue.push_back(0) - /// > |> queue.pop_front() - /// Ok(#(0, queue.new())) - /// - /// > queue.new() - /// > |> queue.pop_back() - /// Error(Nil) - /// - pub fn pop_front(from queue: Queue(a)) -> Result(#(a, Queue(a)), Nil) { - case queue { - Queue(in: [], out: []) -> Error(Nil) - 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(#(first, queue)) - } +/// Gets 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 +/// linear time. +/// +/// # Examples +/// +/// > queue.new() +/// > |> queue.push_front(1) +/// > |> queue.push_front(0) +/// > |> queue.pop_front() +/// Ok(#(0, queue.push_back(queue.new(), 1))) +/// +/// > queue.new() +/// > |> queue.push_back(0) +/// > |> queue.pop_front() +/// Ok(#(0, queue.new())) +/// +/// > queue.new() +/// > |> queue.pop_back() +/// Error(Nil) +/// +pub fn pop_front(from queue: Queue(a)) -> Result(#(a, Queue(a)), Nil) { + case queue { + Queue(in: [], out: []) -> Error(Nil) + 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(#(first, queue)) } } +} - /// Creates 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) - } +/// Creates 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) +} - 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 - } +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 } +} - /// Checks 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), - checking element_is_equal: fn(t, t) -> Bool, - ) -> Bool { - check_equal(a.out, a.in, b.out, b.in, element_is_equal) - } +/// Checks 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), + checking element_is_equal: fn(t, t) -> Bool, +) -> Bool { + check_equal(a.out, a.in, b.out, b.in, element_is_equal) +} - /// Checks 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 }) - } +/// Checks 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 }) } |