#Queue

    Queue is a first in first out (FIFO) data structure, allowing to process their elements in the order they come.

    #Usage

    #Create and Clear

    You can create an empty queue with Queue([]), or construct one from an array with from_array.
    ///|
    test {
    let _queue : @queue.Queue[Int32] = Queue([])
    let _queue1 = @queue.from_array([1, 2, 3])
    }

    To clear the queue, you can use the clear method.
    ///|
    test {
    let queue = @queue.from_array([1, 2, 3])
    queue.clear()
    }

    #Length

    You can get the length of the queue by using the length method. The is_empty method can be used to check if the queue is empty.
    ///|
    test {
    let queue = @queue.from_array([1, 2, 3])
    @test.assert_eq(queue.length(), 3)
    @test.assert_eq(queue.is_empty(), false)
    }

    #Pop and Push

    You can add elements to the queue using the push method and remove them using the pop method.
    ///|
    test {
    let queue = @queue.Queue([])
    queue.push(1)
    queue.push(2)
    @test.assert_eq(queue.pop(), Some(1))
    @test.assert_eq(queue.pop(), Some(2))
    }

    #Peek

    You can get the first element of the queue without removing it using the peek method.
    ///|
    test {
    let queue = @queue.from_array([1, 2, 3])
    @test.assert_eq(queue.peek(), Some(1))
    }

    #From Iterator

    ///|
    test {
    let queue = @queue.from_iter([|1, 2, 3|])
    @test.assert_eq(queue.length(), 3)
    }

    #Traverse

    each() iterates over elements in FIFO order. eachi() provides the index. fold() reduces the queue to a single value.

    ///|
    test {
    let queue = @queue.from_array([1, 2, 3])
    // each
    let buf = []
    queue.each(fn(x) { buf.push(x) })
    @test.assert_eq(buf, [1, 2, 3])
    // eachi
    let pairs = []
    queue.eachi(fn(i, x) { pairs.push((i, x)) })
    @test.assert_eq(pairs, [(0, 1), (1, 2), (2, 3)])
    // fold
    let sum = queue.fold(init=0, fn(acc, x) { acc + x })
    @test.assert_eq(sum, 6)
    }

    #Iterator

    iter() returns an Iter over the queue's elements.

    ///|
    test {
    let queue = @queue.from_array([1, 2, 3])
    debug_inspect(queue.iter().to_array(), content="[1, 2, 3]")
    }

    #Copy and Transfer

    copy() creates a shallow clone. transfer() moves all elements from one queue to the end of another, emptying the source.

    ///|
    test {
    let queue = @queue.from_array([1, 2, 3])
    let cloned = queue.copy()
    @test.assert_eq(cloned.pop(), Some(1))
    @test.assert_eq(queue.length(), 3) // original unchanged
    }

    ///|
    test {
    let dst = @queue.from_array([1, 2])
    let src = @queue.from_array([3, 4])
    src.transfer(dst)
    @test.assert_eq(src.is_empty(), true)
    @test.assert_eq(dst.length(), 4)
    @test.assert_eq(dst.pop(), Some(1))
    }

    Queue

    type Queue[A]

    A FIFO queue backed by @deque.Deque (a growable circular buffer).

    push appends to the back of the deque and peek/pop operate on the front, so all queue operations are O(1) (amortized for push).
    impl Compare for Queue[A]
    impl Default for Queue[A]
    impl Eq for Queue[A]
    impl Hash for Queue[A]
    impl Show for Queue[A]
    impl FromJson for Queue[A]
    impl ToJson for Queue[A]

    Queue::Queue

    #as_free_fn(of, deprecated="Use from_array instead")
    #alias(of, deprecated="Use from_array instead")
    #as_free_fn(from_array)
    #alias(from_array)
    fn[A] Queue::Queue(arr : ArrayView[A], capacity? : Int) -> Queue[A]

    Creates a new queue holding the elements of arr, front first.

    capacity preallocates room for at least that many elements (never less than arr.length()), as in @deque.Deque(arr, capacity=...). Aborts if capacity is negative.

    Example

    test {
    let array = Array::makei(3, idx => idx + 1)
    let queue : @queue.Queue[Int32] = Queue(array)
    @test.assert_eq(queue.length(), 3)
    }

    Queue::clear

    fn[A] Queue::clear(self : Queue[A]) -> Unit

    Clears the queue.

    This keeps the memory the queue has allocated, only setting the length to 0.

    Emptying a queue is a removal like any other: the queue may keep referring to the elements that were in it until later pushes overwrite them or the queue is dropped. Call Queue::shrink_to_fit to release them at once.

    Example

    test {
    let queue : @queue.Queue[Int32] = @queue.from_array([1, 2, 3, 4])
    queue.clear()
    inspect(queue.length(), content="0")
    }

    Queue::compare

    fn[A : Compare + Eq] Queue::compare(self : Queue[A], other : Queue[A]) -> Int

    Queue::copy

    #alias(clone, deprecated="`clone` is deprecated, use `copy` instead")
    fn[A] Queue::copy(self : Queue[A]) -> Queue[A]

    Returns a copy of the queue.

    Example

    test {
    let queue : @queue.Queue[Int32] = @queue.from_array([1, 2, 3, 4])
    let queue2 : @queue.Queue[Int32] = queue.copy()
    @test.assert_eq(queue2.length(), 4)
    }

    Queue::each

    fn[A] Queue::each(self : Queue[A], f : (A) -> Unit raise?) -> Unit raise?

    Iterates over the queue.

    If f pushes, pops or clears the queue, the result is memory-safe but otherwise unspecified.

    Example

    test {
    let queue : @queue.Queue[Int32] = @queue.from_array([1, 2, 3, 4])
    let mut sum = 0
    queue.each(x => sum += x)
    inspect(sum, content="10")
    }

    Queue::eachi

    fn[A] Queue::eachi(self : Queue[A], f : (Int, A) -> Unit raise?) -> Unit raise?

    Iterates over the queue with index.

    If f pushes, pops or clears the queue, the result is memory-safe but otherwise unspecified.

    Example

    test {
    let queue : @queue.Queue[Int32] = @queue.from_array([1, 2, 3, 4])
    let mut sum = 0
    queue.eachi((i, x) => sum += i * x)
    inspect(sum, content="20")
    }

    Queue::equal

    fn[A : Eq] Queue::equal(self : Queue[A], other : Queue[A]) -> Bool

    Queue::fold

    fn[A, B] Queue::fold(self : Queue[A], init~ : B, f : (B, A) -> B raise?) -> B raise?

    Folds over the queue.

    If f pushes, pops or clears the queue, the result is memory-safe but otherwise unspecified.

    Example

    test {
    let queue : @queue.Queue[Int32] = Queue([])
    let sum = queue.fold(init=0, (acc, x) => acc + x)
    @test.assert_eq(sum, 0)
    }

    Queue::from_iter

    #as_free_fn(from_iterator, deprecated="Use Queue::from_iter instead.")
    #alias(from_iterator, deprecated="`from_iterator` is deprecated, use `from_iter` instead")
    #as_free_fn
    fn[A] Queue::from_iter(iter : Iter[A]) -> Queue[A]

    Creates a new queue from an iter.

    Example

    test {
    let queue : @queue.Queue[Int32] = @queue.from_iter([||])
    @test.assert_eq(queue.length(), 0)
    }

    Queue::hash

    fn[A : Hash] Queue::hash(self : Queue[A]) -> Int

    Queue::is_empty

    fn[A] Queue::is_empty(self : Queue[A]) -> Bool

    Checks if the queue is empty.

    Example

    test {
    let queue : @queue.Queue[Int32] = Queue([])
    assert_true(queue.is_empty())
    }

    Queue::iter

    #alias(iterator, deprecated="`iterator` is deprecated, use `iter` instead")
    fn[A] Queue::iter(self : Queue[A]) -> Iter[A]

    Creates an iter from the queue.

    Modifying the queue while the iterator is in use is memory-safe, but which elements the iterator then yields is unspecified.

    Example

    test {
    let queue : @queue.Queue[Int32] = @queue.from_array([5, 6, 7, 8])
    let sum = queue.iter().fold((x, y) => x + y, init=0)
    @test.assert_eq(sum, 26)
    }

    Queue::length

    fn[A] Queue::length(self : Queue[A]) -> Int

    Get the length of the queue.

    Example

    test {
    let queue : @queue.Queue[Int32] = Queue([])
    @test.assert_eq(queue.length(), 0)
    }

    Queue::new

    #as_free_fn(deprecated="Use `Queue([])` instead")
    #deprecated("Use `Queue([])` instead")
    fn[A] Queue::new() -> Queue[A]

    Creates a new empty queue.

    Deprecated: use Queue([]) instead.

    Queue::peek

    fn[A] Queue::peek(self : Queue[A]) -> A?

    Peeks at the first value in the queue, which returns None if the queue is empty.

    Example

    test {
    let queue : @queue.Queue[Int32] = @queue.from_array([1, 2, 3, 4])
    @test.assert_eq(queue.peek(), Some(1))
    }

    Queue::pop

    fn[A] Queue::pop(self : Queue[A]) -> A?

    Pops the first value from the queue, which returns None if the queue is empty.

    The queue may keep referring to the removed element until a later push overwrites it or the queue is dropped. Call Queue::shrink_to_fit to release it at once.

    Example

    test {
    let queue : @queue.Queue[Int32] = @queue.from_array([1, 2, 3, 4])
    @test.assert_eq(queue.pop(), Some(1))
    }

    Queue::push

    fn[A] Queue::push(self : Queue[A], x : A) -> Unit

    Adds a value to the queue.

    Example

    test {
    let queue : @queue.Queue[Int32] = Queue([])
    queue.push(1)
    }

    Queue::shrink_to_fit

    fn[A] Queue::shrink_to_fit(self : Queue[A]) -> Unit

    Releases the memory the queue holds beyond its current elements.

    Removing elements (Queue::pop, Queue::clear, or Queue::transfer on its source) does not let go of them right away: the queue may keep referring to them, so they stay reachable until later pushes overwrite them or the queue is dropped. After this call the queue refers only to the elements it currently holds, and its spare capacity is returned as well. The elements and their order are unchanged.

    This matters only for element types holding references; it costs an allocation plus a copy of the current elements, and does nothing when the queue has no spare capacity.

    Example

    test {
    let queue : @queue.Queue[String] = @queue.from_array(["a", "b", "c"])
    let _ = queue.pop()
    queue.shrink_to_fit()
    @debug.debug_inspect(
    queue,
    content=(
    #|<Queue: ["b", "c"]>
    ),
    )
    }

    Queue::to_array

    fn[A] Queue::to_array(self : Queue[A]) -> Array[A]

    Returns the elements of the queue as an array, front first.

    Example

    test {
    let queue = @queue.Queue([1, 2, 3])
    queue.push(4)
    ignore(queue.pop())
    @debug.debug_inspect(queue.to_array(), content="[2, 3, 4]")
    }

    Queue::transfer

    fn[A] Queue::transfer(self : Queue[A], dst : Queue[A]) -> Unit

    Transfers all elements from one queue to another.

    Adds all of the elements of source to the end of destination, then clears source. If source and destination are the same queue, this is a no-op.

    Like Queue::clear, emptying the source may leave it referring to the transferred elements; call Queue::shrink_to_fit on it to release them.

    Example

    test {
    let dst : @queue.Queue[Int32] = Queue([])
    let src : @queue.Queue[Int32] = @queue.from_array([5, 6, 7, 8])
    src.transfer(dst)
    }