Module collections/deque
Double-ended queue (ring buffer) with O(1) push/pop at both ends.
Example
{ Deque } :: import "std/collections/deque";
d := Deque(i32).new();
d.push_back(1);
d.push_front(0);
x := d.pop_front().unwrap(); // 0
Elements live in one heap block used as a ring: _head is the front slot
and the logical index k sits at (_head + k) % capacity, so both ends
are O(1) and nothing shifts. Growth doubles the block (8 slots first) and
LINEARISES the contents, which invalidates every pointer into the old
buffer. Rust's counterpart is VecDeque.
Stability
stable — the surface mirrors VecDeque
(push_front/push_back/pop_front/pop_back/front/back/get,
iter/into_iter, FromIterator, Default), allocation failure panics
like every other collection (D9), and plans/STD_API_STABILIZATION.md §4
lists nothing open against this module.
tests/collections/deque.test.yo covers the surface, including the
wrap-around cases. Missing pieces such as Debug or a retain would be
additive.
Types
Circular buffer supporting efficient push/pop at both front and back.
Type Parameters
| Name | Type | Notes |
|---|---|---|
T | Type | comptime |
Trait Implementations
impl(generic(T : Type), Deque(T), ...)
new : (fn() -> Self)Empty deque. Allocates nothing — the first push buys an 8-slot ring.
Returns: Self
len : (fn(self : Self) -> usize)Number of elements. O(1); not the ring's capacity.
Returns: usize
is_empty : (fn(self : Self) -> bool)True when the deque holds no elements.
Returns: bool
_grow : (fn(self : Self, min_cap : usize) -> unit)Returns: unit
push_back : (fn(self : Self, val : T) -> unit)Add an element at the back — amortized O(1). Rust's push_back.
A full ring grows (doubling and linearising), which PANICS on allocation failure or capacity overflow rather than reporting it (D9), and invalidates every pointer into the buffer.
Returns: unit
push_front : (fn(self : Self, val : T) -> unit)Add an element at the front — amortized O(1) and no shifting, which is
the whole reason to use a deque over an ArrayList. Rust's
push_front.
Grows exactly like push_back when the ring is full.
Returns: unit
pop_front : (fn(self : Self) -> Option(T))Remove and return the front element, or .None when empty — O(1). The
capacity is kept.
Returns: Option(T)
pop_back : (fn(self : Self) -> Option(T))Remove and return the back element, or .None when empty — O(1).
Returns: Option(T)
front : (fn(self : Self) -> Option(T))First element, or .None when empty — Rust's VecDeque::front.
Returns: Option(T)
back : (fn(self : Self) -> Option(T))Last element, or .None when empty — Rust's VecDeque::back.
Returns: Option(T)
get : (fn(self : Self, index : usize) -> Option(T))Copy of the element at LOGICAL index index (0 = front), or .None
when out of range — O(1) through the ring's modulo, not a walk.
self(index) (the Index impl) hands back a pointer into the ring and
asserts the bound instead.
Returns: Option(T)
impl(generic(T : Type), Deque(T), Dispose(...))
dispose : (fn(self : Self) -> unit)Release the resources self owns — a file descriptor, a socket, a lock,
a buffer the allocator handed out. Called automatically when the last
reference to the value goes away, so an implementor never calls it
directly and must tolerate being the only one who ever does.
It must be safe to run exactly once: the runtime calls it at refcount
zero, and a type that also exposes an explicit close/release is
responsible for making the second call a no-op.
Returns: unit
impl(generic(T : Type), Deque(T), IntoIterator(...))
Item : TIntoIter : DequeIter(T)into_iter : (fn(self : Self) -> DequeIter(T))Returns: DequeIter(T)
impl(generic(T : Type), Deque(T), ...)
iter : (fn(self : Self) -> DequeIterPtr(T))Borrowing walk from the front: yields a *(T) into the ring and
leaves the deque intact (D14).
Returns: DequeIterPtr(T)
impl(generic(T : Type), Deque(T), Index(usize)(...))
Output : Tindex : (fn(inout(self) : Self, idx : usize) -> *Self.Output)impl(generic(T : Type), Deque(T), Trace(...))
trace : (fn(self : Self, tracer : GcTracer) -> unit)Cycle-GC tracing. The elements live in a malloc'd ring buffer the
compiler's auto-derived field walk cannot reach, so trace each live
element's buffer slot. Logical element k (0 = front) sits at
physical slot (_head + k) % _capacity. tracer.visit takes the slot
POINTER and reads it WITHOUT touching the element's reference count (a
by-value managed handle would be dup'd then dropped, freeing a live
element mid-collection). Mirrors the ArrayList Trace impl.
Parameters
| Name | Type | Notes |
|---|---|---|
tracer | GcTracer |
Returns: unit
impl(generic(T : Type), Deque(T), FromIterator(...))
Elem : Tfrom_iter_new : (fn() -> Self)The empty collection collect starts from.
Returns: Self
from_iter_add : (fn(acc : Self, item : T) -> Self)Add one element to a partially-built collection and return it.
Parameters
| Name | Type | Notes |
|---|---|---|
acc | Self | |
item | T |
Returns: Self
impl(generic(T : Type), Deque(T), Default(...))
default : (fn() -> Self)The default value of the type.
Returns: Self
Value iterator over a Deque — walks the ring in logical order (front
first) and yields each element BY VALUE, dup'ing a refcounted T. This is
what into_iter(), and therefore for(deque, ...), returns; iter()
yields pointers.
The element count is captured when the iterator is made, so pushes during
the walk are not seen — and a pop is worse than unseen: it moves _head,
which shifts every remaining position. Double-ended: next_back takes
from the far end of the same window.
Type Parameters
| Name | Type | Notes |
|---|---|---|
T | Type | comptime |
Trait Implementations
impl(generic(T : Type), DequeIter(T), Iterator(...))
Item : Tnext : (fn(inout(self) : Self) -> Option(T))Advance the iterator and return the next value, or None when exhausted.
Returns: Option(T)
impl(generic(T : Type), DequeIter(T), DoubleEndedIterator(...))
Item : Tnext_back : (fn(inout(self) : Self) -> Option(T))Advance the iterator from the back and return the previous value, or
None when the two ends have met.
Returns: Option(T)
Pointer iterator over a Deque — yields *(T) into the ring itself, in
logical order. This is what iter() returns (D14): nothing is dup'd and
writing through the pointer updates the element in place.
A yielded pointer dies with the buffer, so a push that grows the ring (or
a dispose) during the walk leaves it dangling.
Type Parameters
| Name | Type | Notes |
|---|---|---|
T | Type | comptime |
Trait Implementations
impl(generic(T : Type), DequeIterPtr(T), Iterator(...))
Item : *Tnext : (fn(inout(self) : Self) -> Option(*T))Advance the iterator and return the next value, or None when exhausted.
Returns: Option(*T)