Module `collections/deque`

collections/deque

Stability: stable — changes additively from here.

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

Deque type-function

fn(T : Type) -> Type

Circular buffer supporting efficient push/pop at both front and back.

Type Parameters

Name	Type	Notes
`T`	Type	comptime

Trait Implementations

Drop IntoIterator BorrowedWalk BorrowedWalkMut Index IndexMut Trace FromIterator Default

impl(generic(T : Type), Deque(T), ...)

new : (fn() -> Self)

Empty deque on the global allocator. Allocates nothing — the first push buys an 8-slot ring. new_in(a) places the ring in a instead.

Returns: Self

new_in : (fn(alloc : Allocator) -> Self)

Empty deque whose ring lives in alloc. Every growth and the final release go through alloc. Takes one allocation right away — a block holding only the owner prefix, which is how the deque remembers its allocator. 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))

The allocator the ring lives in, or .None for the global one.

Returns: 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, body : &Impl(Fn(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().

{ 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 : T

IntoIter : 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), BorrowedWalk(...))

WalkCursor : usize

WalkElem : T

walk_start : (fn(self : &Self) -> usize)

The first position (equal to the end for an empty collection).

Returns: usize

walk_valid : (fn(self : &Self, cur : &usize) -> bool)

Whether cur names an element.

Parameters

Name	Type	Notes
`cur`	&usize

Returns: bool

walk_ref : (fn(self : &Self, cur : &usize) -> &T)

The element at cur, read in place (a read projection). Panics if cur names no element.

Parameters

Name	Type	Notes
`cur`	&usize

Returns: &T

walk_next : (fn(self : &Self, cur : &usize) -> usize)

The position after cur.

Parameters

Name	Type	Notes
`cur`	&usize

Returns: usize

impl(generic(T : Type), Deque(T), BorrowedWalkMut(...))

walk_elem : (fn(self : &mut Self, cur : &usize) -> &mut T)

The element at cur, written in place (a mutable projection). Panics if cur names no element.

Parameters

Name	Type	Notes
`cur`	&usize

Returns: &mut T

impl(generic(T : Type), Deque(T), Index(usize)(...))

Output : T

index : (fn(self : &Self, idx : usize) -> &Self.Output)

Parameters

Name	Type	Notes
`idx`	usize

Returns: &Self.Output

impl(generic(T : Type), Deque(T), IndexMut(usize)(...))

Output : T

index_mut : (fn(self : &mut Self, idx : usize) -> &mut Self.Output)

Parameters

Name	Type	Notes
`idx`	usize

Returns: &mut 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 : T

from_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

DequeIter type-function

fn(T : Type) -> Type

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

Iterator DoubleEndedIterator

impl(generic(T : Type), DequeIter(T), Iterator(...))

Item : T

next : (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 : T

next_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)

DequeIterPtr type-function

fn(T : Type) -> Type

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

Iterator

impl(generic(T : Type), DequeIterPtr(T), Iterator(...))

Item : *T

next : (fn(self : &mut Self) -> Option(*T))

Advance the iterator and return the next value, or None when exhausted.

Returns: Option(*T)

Module collections/deque

Example

Stability

Types

Type Parameters

Trait Implementations

Parameters

Parameters

Parameters

Parameters

Parameters

Parameters

Parameters

Parameters

Type Parameters

Trait Implementations

Type Parameters

Trait Implementations

Module `collections/deque`