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/archive/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), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unitWrite a clone of self into the uninitialized slot dst, which has
room for size_of_val(self) bytes at align_of_val(self).
Parameters
| Name | Type | Notes |
|---|---|---|
self | Self | |
dst | *(Self) |
Returns: unit
impl(generic(T : Type), where(T <: Send), Deque(T), Send())
impl(generic(T : Type), where(T <: Sync), Deque(T), Sync())
impl(generic(T : Type), where(T <: Clone), Deque(T), ...)
_clone_placed : (fn(self : &Self, alloc : Option(Allocator)) -> Self)Returns: Self
impl(generic(T : Type), where(T <: Clone), Deque(T), Clone(...))
clone : (fn(self : &Self) -> Self)Create an independent clone of self.
Returns: Self
impl(generic(T : Type), Deque(T), ...)
new : (fn((alloc : Option(Allocator)) ?= .None) -> Self)Empty deque. alloc : .None, the default, puts the ring on the global
allocator and allocates nothing: the first push buys an 8-slot ring.
alloc : .Some(a) places the ring in a, and every growth and the
final release go through a. A placed deque takes one allocation right
away, a block holding only the owner prefix, which is how it remembers
its allocator; it PANICS when that allocation fails.
Returns: Self
_cap : (fn(self : &Self) -> usize)Returns: usize
_owned : (fn(self : &Self) -> bool)Returns: bool
allocator : (fn(self : &Self) -> Option(Allocator))_free_buf : (fn(self : &Self, p : &*T) -> unit)Returns: unit
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 : &mut Self, min_cap : usize) -> unit)Returns: unit
push_back : (fn(self : &mut 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 : &mut 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 : &mut 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 : &mut 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) reads the element in place and asserts
the bound instead; get_cloned(i) clones an element that is not copied
implicitly, and with(i, body) writes one in place
(plans/VALUES_BY_DEFAULT.md decision 20).
Returns: Option(T)
with : (fn(generic(R : Type), self : &mut Self, index : usize, sink(body) : Impl(FnOnce(v : &mut T) -> R)) -> R)Run body on the element at logical index index, borrowed in place,
and return its result — decision 20's non-copying access. Asserts
index < len(). The body runs once, so it is an FnOnce moved in
(decision 37) and may move its captures into the element.
{ Deque } :: import("std/collections/deque");
(mut(d) : Deque(i32)) = Deque(i32).new();
d.push_back(i32(1));
d.with(usize(0), v => {
v = (v + i32(10));
});
assert(d(usize(0)) == i32(11), "written in place");
Returns: R
take : (fn(self : &mut Self, index : usize, where(T <: Default)) -> T)Move the element at logical index index out and leave T's default
in its slot — std/mem's take(&mut d(i)). Asserts index < len().
Returns: T
swap : (fn(self : &mut Self, i : usize, j : usize) -> unit)Exchange the elements at logical indices i and j — Rust's
VecDeque::swap. The slots move bitwise: no element is copied or
dropped, so a move-only T swaps too. Asserts both indices are
< len().
Returns: unit
impl(generic(T : Type), where(T <: Clone), Deque(T), ...)
get_cloned : (fn(self : &Self, index : usize) -> Option(T))A clone of the element at logical index index, or .None when out of
range — get for an element that is not copied implicitly (decision
20). The element is cloned in place, never copied out first.
Returns: Option(T)
front_cloned : (fn(self : &Self) -> Option(T))A clone of the front element, or .None when empty.
Returns: Option(T)
back_cloned : (fn(self : &Self) -> Option(T))A clone of the back element, or .None when empty.
Returns: Option(T)
impl(generic(T : Type), Deque(T), Drop(...))
drop : (fn(self : &mut Self) -> unit)One ArcWeak fewer; the cell is freed when its payload is gone and
this was the last handle. A zeroed handle names no cell.
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))Raw walk from the front: yields a *(T) into the ring and leaves the
deque intact (D14). Safe code reads elements with for(&dq, x => ...);
this is the pragma(Pragma.AllowUnsafe) form, whose iterator holds the
buffer, not the deque (decision 39, B7b).
Returns: DequeIterPtr(T)
indices : (fn(self : &Self) -> Range(usize))The logical positions 0 .. len() (front first), a Range(usize) that
holds no handle to the deque: decision 39's index cursor
(plans/VALUES_BY_DEFAULT.md). Read each element as dq(i), which
re-derives it from the current ring.
Returns: Range(usize)
impl(generic(T : Type), Deque(T), Index(usize)(...))
Output : Tindex : (fn(self : &Self, idx : usize) -> &Self.Output)impl(generic(T : Type), Deque(T), IndexMut(usize)(...))
Output : Tindex_mut : (fn(self : &mut Self, idx : usize) -> &mut Self.Output)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(sink(acc) : Self, item : &T) -> Self)Add one element to a partially-built collection and return it.
Parameters
| Name | Type | Notes |
|---|---|---|
item | &T |
Returns: Self
impl(generic(T : Type), Deque(T), Default(...))
default : (fn() -> Self)The default value of the type.
Returns: Self
impl(generic(T : Type, p : Origin), &(Deque(T), p), IntoIterator(...))
Item : &(T, p)IntoIter : DequeCursor(T, p)into_iter : (fn(self : Self) -> DequeIter(T))Returns: DequeIter(T)
impl(generic(T : Type, p : Origin), &mut(Deque(T), p), IntoIterator(...))
Item : &mut(T, p)IntoIter : DequeCursorMut(T, p)into_iter : (fn(self : Self) -> DequeIter(T))Returns: DequeIter(T)
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), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unitWrite a clone of self into the uninitialized slot dst, which has
room for size_of_val(self) bytes at align_of_val(self).
Parameters
| Name | Type | Notes |
|---|---|---|
self | Self | |
dst | *(Self) |
Returns: unit
impl(generic(T : Type), DequeIter(T), Iterator(...))
Item : Tnext : (fn(self : &mut 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(self : &mut 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 raw view (decision 39, B7b): it holds the ring's buffer pointer, its
capacity and the head and length iter() saw, NOT the deque, so it keeps
nothing alive and is meant for pragma(Pragma.AllowUnsafe) code. A
yielded pointer dies with the buffer, so the deque must outlive the walk,
and a push, pop or growth during it leaves the walk reading stale slots.
Type Parameters
| Name | Type | Notes |
|---|---|---|
T | Type | comptime |
Trait Implementations
impl(generic(T : Type), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unitWrite a clone of self into the uninitialized slot dst, which has
room for size_of_val(self) bytes at align_of_val(self).
Parameters
| Name | Type | Notes |
|---|---|---|
self | Self | |
dst | *(Self) |
Returns: unit
impl(generic(T : Type), DequeIterPtr(T), Iterator(...))
Item : *Tnext : (fn(self : &mut Self) -> Option(*T))Advance the iterator and return the next value, or None when exhausted.
Returns: Option(*T)
The shared walk over a Deque (Rust's Iter<'a, T>): a &(Deque(T), p) lend and a
position, yielding each element as a &(T, p). Binding the cursor freezes the
collection for its life (E0911 on a write), which is what makes the borrowed
for(&xs, x => body) lower to the value form over (&xs).into_iter().
Type Parameters
| Name | Type | Notes |
|---|---|---|
T | Type | comptime |
p | Origin | comptime |
Trait Implementations
impl(generic(T : Type), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unitWrite a clone of self into the uninitialized slot dst, which has
room for size_of_val(self) bytes at align_of_val(self).
Parameters
| Name | Type | Notes |
|---|---|---|
self | Self | |
dst | *(Self) |
Returns: unit
impl(generic(T : Type, p : Origin), DequeCursor(T, p), Iterator(...))
Item : &(T, p)next : (fn(self : &mut Self) -> Option(&(T, p)))Advance the iterator and return the next value, or None when exhausted.
Returns: Option(&(T, p))
The write walk over a Deque (Rust's IterMut<'a, T>): a &mut(Deque(T), p) lend and a
position, yielding each element as a &mut(T, p). The collection is frozen
exclusively while the cursor lives (a read of it is E0911 too). The body
reaches each element through the raw buffer pointer; the position only moves
forward, so no two yielded references alias.
Type Parameters
| Name | Type | Notes |
|---|---|---|
T | Type | comptime |
p | Origin | comptime |
Trait Implementations
impl(generic(T : Type), where(T <: Clone), T : (Clone))
impl(generic(T : Type), where(T <: Clone), T : (Clone), CloneInto)
clone_into : fn(self : &Self, dst : *(Self)) -> unitWrite a clone of self into the uninitialized slot dst, which has
room for size_of_val(self) bytes at align_of_val(self).
Parameters
| Name | Type | Notes |
|---|---|---|
self | Self | |
dst | *(Self) |
Returns: unit
impl(generic(T : Type, p : Origin), DequeCursorMut(T, p), Iterator(...))
Item : &mut(T, p)next : (fn(self : &mut Self) -> Option(&mut(T, p)))Advance the iterator and return the next value, or None when exhausted.
Returns: Option(&mut(T, p))