Skip to content
Standard libraryZig 0.17.1Official documentation
Sourcestd/deque.zig

Source line 1

std.deque.addOrOom

function

Source line 368

Integer addition returning error.OutOfMemory on overflow.

fn addOrOom(a: usize, b: usize) error{OutOfMemory}!usize

Parameters

a: usize
b: usize

Errors

OutOfMemory

std.deque.Allocator

alias

Source line 3

Alias of std.mem.Allocator

std.deque.assert

alias

Source line 2

Alias of std.debug.assert

std.deque.Deque

type-function

Source line 8

A contiguous, growable, double-ended queue.

Pushing/popping items from either end of the queue is O(1).

pub fn Deque(comptime T: type) type

Parameters

T: type

Fields

buffer: []T

A ring buffer.

head: usize

The index in buffer where the first item in the logical deque is stored.

len: usize

The number of items stored in the logical deque.

std.deque.Deque.at

function

Source line 291

Return the item at the given index in the deque.

The first item in the queue is at index 0.

Asserts that the index is in-bounds.

pub fn at(deque: *const Self, index: usize) T

Parameters

deque: *const Self
index: usize

std.deque.Deque.atPtr

function

Source line 301

Return pointer to the item at the given index in the deque.

The first item in the queue is at index 0.

Asserts that the index is in-bounds.

pub fn atPtr(deque: *const Self, index: usize) *T

Parameters

deque: *const Self
index: usize

std.deque.Deque.back

function

Source line 275

Return the last item in the deque or null if empty.

pub fn back(deque: *const Self) ?T

Parameters

deque: *const Self

std.deque.Deque.backPtr

function

Source line 281

Return the last item in the deque or null if empty.

pub fn backPtr(deque: *const Self) ?*T

Parameters

deque: *const Self

std.deque.Deque.bufferIndex

function

Source line 354

Returns the index in buffer where the element at the given index in the logical deque is stored.

fn bufferIndex(deque: *const Self, index: usize) usize

Parameters

deque: *const Self
index: usize

std.deque.Deque.deinit

function

Source line 49

Release all allocated memory.

pub fn deinit(deque: *Self, gpa: Allocator) void

Parameters

deque: *Self
gpa: Allocator

std.deque.Deque.empty

constant

Source line 20

A Deque containing no elements.

Self

std.deque.Deque.ensureTotalCapacity

function

Source line 57

Modify the deque so that it can hold at least new_capacity items. Implements super-linear growth to achieve amortized O(1) push/pop operations. Invalidates element pointers if additional memory is needed.

pub fn ensureTotalCapacity(deque: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void

Parameters

deque: *Self
gpa: Allocator
new_capacity: usize

Errors

OutOfMemory

std.deque.Deque.ensureTotalCapacityPrecise

function

Source line 65

If the current capacity is less than new_capacity, this function will modify the deque so that it can hold exactly new_capacity items. Invalidates element pointers if additional memory is needed.

pub fn ensureTotalCapacityPrecise(deque: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void

Parameters

deque: *Self
gpa: Allocator
new_capacity: usize

Errors

OutOfMemory

std.deque.Deque.ensureUnusedCapacity

function

Source line 104

Modify the deque so that it can hold at least additional_count more items. Invalidates element pointers if additional memory is needed.

pub fn ensureUnusedCapacity( deque: *Self, gpa: Allocator, additional_count: usize, ) Allocator.Error!void

Parameters

deque: *Self
gpa: Allocator
additional_count: usize

Errors

OutOfMemory

std.deque.Deque.front

function

Source line 263

Return the first item in the deque or null if empty.

pub fn front(deque: *const Self) ?T

Parameters

deque: *const Self

std.deque.Deque.frontPtr

function

Source line 269

Return pointer to the first item in the deque or null if empty.

pub fn frontPtr(deque: *const Self) ?*T

Parameters

deque: *const Self

std.deque.Deque.initBuffer

function

Source line 40

Initialize with externally-managed memory. The buffer determines the capacity and the deque is initially empty.

When initialized this way, all functions that accept an Allocator argument cause illegal behavior.

pub fn initBuffer(buffer: []T) Self

Parameters

buffer: []T

std.deque.Deque.initCapacity

function

Source line 29

Initialize with capacity to hold capacity elements. The resulting capacity will equal capacity exactly. Deinitialize with deinit.

pub fn initCapacity(gpa: Allocator, capacity: usize) Allocator.Error!Self

Parameters

gpa: Allocator
capacity: usize

Errors

OutOfMemory

std.deque.Deque.iterator

function

Source line 348

Iterates over all items in the deque in order from front to back.

pub fn iterator(deque: *const Self) Iterator

Parameters

deque: *const Self

std.deque.Deque.Iterator

container

Source line 322

Fields

deque: *const Self
index: usize

std.deque.Deque.Iterator.next

function

Source line 330

pub fn next(it: *Iterator) ?T

Parameters

it: *Iterator

std.deque.Deque.Iterator.nextPtr

function

Source line 340

pub fn nextPtr(it: *Iterator) ?*T

Parameters

it: *Iterator

std.deque.Deque.Iterator.peek

function

Source line 326

pub fn peek(it: Iterator) ?T

Parameters

it: Iterator

std.deque.Deque.Iterator.peekPtr

function

Source line 336

pub fn peekPtr(it: Iterator) ?*T

Parameters

it: Iterator

std.deque.Deque.popBack

function

Source line 316

Remove and return the last item in the deque or null if empty.

pub fn popBack(deque: *Self) ?T

Parameters

deque: *Self

std.deque.Deque.popFront

function

Source line 307

Remove and return the first item in the deque or null if empty.

pub fn popFront(deque: *Self) ?T

Parameters

deque: *Self

std.deque.Deque.pushBack

function

Source line 149

Add one item to the back of the deque.

Invalidates element pointers if additional memory is needed.

pub fn pushBack(deque: *Self, gpa: Allocator, item: T) error{OutOfMemory}!void

Parameters

deque: *Self
gpa: Allocator
item: T

Errors

OutOfMemory

std.deque.Deque.pushBackAssumeCapacity

function

Source line 170

Add one item to the back of the deque.

Never invalidates element pointers.

Asserts that the deque can hold one additional item.

pub fn pushBackAssumeCapacity(deque: *Self, item: T) void

Parameters

deque: *Self
item: T

std.deque.Deque.pushBackBounded

function

Source line 160

Add one item to the back of the deque.

Never invalidates element pointers.

If the deque lacks unused capacity for the additional item, returns error.OutOfMemory.

pub fn pushBackBounded(deque: *Self, item: T) error{OutOfMemory}!void

Parameters

deque: *Self
item: T

Errors

OutOfMemory

std.deque.Deque.pushBackSlice

function

Source line 225

Add items to the back of the deque. This is equivalent to iterating items in order and calling pushBack on every single entry.

Invalidates element pointers if additional memory is needed.

pub fn pushBackSlice(deque: *Self, gpa: Allocator, items: []const T) error{OutOfMemory}!void

Parameters

deque: *Self
gpa: Allocator
items: []const T

Errors

OutOfMemory

std.deque.Deque.pushBackSliceAssumeCapacity

function

Source line 250

Add items to the back of the deque. This is equivalent to iterating items in order and calling pushBack on every single entry.

Never invalidates element pointers.

Asserts that the deque can hold the additional items.

pub fn pushBackSliceAssumeCapacity(deque: *Self, items: []const T) void

Parameters

deque: *Self
items: []const T

std.deque.Deque.pushBackSliceBounded

function

Source line 238

Add items to the back of the deque. This is equivalent to iterating items in order and calling pushBack on every single entry.

Never invalidates element pointers.

If the deque lacks unused capacity for the additional items, returns error.OutOfMemory.

pub fn pushBackSliceBounded(deque: *Self, items: []const T) error{OutOfMemory}!void

Parameters

deque: *Self
items: []const T

Errors

OutOfMemory

std.deque.Deque.pushFront

function

Source line 115

Add one item to the front of the deque.

Invalidates element pointers if additional memory is needed.

pub fn pushFront(deque: *Self, gpa: Allocator, item: T) error{OutOfMemory}!void

Parameters

deque: *Self
gpa: Allocator
item: T

Errors

OutOfMemory

std.deque.Deque.pushFrontAssumeCapacity

function

Source line 136

Add one item to the front of the deque.

Never invalidates element pointers.

Asserts that the deque can hold one additional item.

pub fn pushFrontAssumeCapacity(deque: *Self, item: T) void

Parameters

deque: *Self
item: T

std.deque.Deque.pushFrontBounded

function

Source line 126

Add one item to the front of the deque.

Never invalidates element pointers.

If the deque lacks unused capacity for the additional item, returns error.OutOfMemory.

pub fn pushFrontBounded(deque: *Self, item: T) error{OutOfMemory}!void

Parameters

deque: *Self
item: T

Errors

OutOfMemory

std.deque.Deque.pushFrontSlice

function

Source line 182

Add items to the front of the deque. This is equivalent to iterating items in reverse and calling pushFront on every single entry.

Invalidates element pointers if additional memory is needed.

pub fn pushFrontSlice(deque: *Self, gpa: Allocator, items: []const T) error{OutOfMemory}!void

Parameters

deque: *Self
gpa: Allocator
items: []const T

Errors

OutOfMemory

std.deque.Deque.pushFrontSliceAssumeCapacity

function

Source line 207

Add items to the front of the deque. This is equivalent to iterating items in reverse and calling pushFront on every single entry.

Never invalidates element pointers.

Asserts that the deque can hold the additional items.

pub fn pushFrontSliceAssumeCapacity(deque: *Self, items: []const T) void

Parameters

deque: *Self
items: []const T

std.deque.Deque.pushFrontSliceBounded

function

Source line 195

Add items to the front of the deque. This is equivalent to iterating items in reverse and calling pushFront on every single entry.

Never invalidates element pointers.

If the deque lacks unused capacity for the additional items, returns error.OutOfMemory.

pub fn pushFrontSliceBounded(deque: *Self, items: []const T) error{OutOfMemory}!void

Parameters

deque: *Self
items: []const T

Errors

OutOfMemory

std.deque.Deque.Self

alias

Source line 10

Alias of std.deque.Deque

std.deque.fuzzAgainstArrayList

function

Source line 619

fn fuzzAgainstArrayList(_: void, smith: *std.testing.Smith) anyerror!void

Parameters

_: void
smith: *std.testing.Smith

std.deque.FuzzAllocator

container

Source line 521

Fields

smith: *std.testing.Smith
bufs: [2][256 * 4]u8 align(4)
used_bitmap: u2
used_len: [2]usize

std.deque.FuzzAllocator.alloc

function

Source line 552

fn alloc(ctx: *anyopaque, len: usize, a: std.mem.Alignment, _: usize) ?[*]u8

Parameters

ctx: *anyopaque
len: usize
a: std.mem.Alignment
_: usize

std.deque.FuzzAllocator.allocator

function

Source line 536

pub fn allocator(f: *FuzzAllocator) std.mem.Allocator

Parameters

std.deque.FuzzAllocator.allocCount

function

Source line 548

pub fn allocCount(f: *FuzzAllocator) u2

Parameters

std.deque.FuzzAllocator.free

function

Source line 612

fn free(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, _: usize) void

Parameters

ctx: *anyopaque
mem: []u8
a: std.mem.Alignment
_: usize

std.deque.FuzzAllocator.init

function

Source line 527

pub fn init(smith: *std.testing.Smith) FuzzAllocator

Parameters

smith: *std.testing.Smith

std.deque.FuzzAllocator.memSlot

function

Source line 565

fn memSlot(f: *FuzzAllocator, mem: []u8) u1

Parameters

f: *FuzzAllocator
mem: []u8

std.deque.FuzzAllocator.remap

function

Source line 588

fn remap(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, new_len: usize, _: usize) ?[*]u8

Parameters

ctx: *anyopaque
mem: []u8
a: std.mem.Alignment
new_len: usize
_: usize

std.deque.FuzzAllocator.resize

function

Source line 577

fn resize(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, new_len: usize, _: usize) bool

Parameters

ctx: *anyopaque
mem: []u8
a: std.mem.Alignment
new_len: usize
_: usize

std.deque.std

alias

Source line 1

Alias of std

Source code

std/deque.zig

const std = @import("std");
const assert = std.debug.assert;
const Allocator = std.mem.Allocator;

/// A contiguous, growable, double-ended queue.
///
/// Pushing/popping items from either end of the queue is O(1).
pub fn Deque(comptime T: type) type {
    return struct {
        const Self = @This();

        /// A ring buffer.
        buffer: []T,
        /// The index in buffer where the first item in the logical deque is stored.
        head: usize,
        /// The number of items stored in the logical deque.
        len: usize,

        /// A Deque containing no elements.
        pub const empty: Self = .{
            .buffer = &.{},
            .head = 0,
            .len = 0,
        };

        /// Initialize with capacity to hold `capacity` elements.
        /// The resulting capacity will equal `capacity` exactly.
        /// Deinitialize with `deinit`.
        pub fn initCapacity(gpa: Allocator, capacity: usize) Allocator.Error!Self {
            var deque: Self = .empty;
            try deque.ensureTotalCapacityPrecise(gpa, capacity);
            return deque;
        }

        /// Initialize with externally-managed memory. The buffer determines the
        /// capacity and the deque is initially empty.
        ///
        /// When initialized this way, all functions that accept an Allocator
        /// argument cause illegal behavior.
        pub fn initBuffer(buffer: []T) Self {
            return .{
                .buffer = buffer,
                .head = 0,
                .len = 0,
            };
        }

        /// Release all allocated memory.
        pub fn deinit(deque: *Self, gpa: Allocator) void {
            gpa.free(deque.buffer);
            deque.* = undefined;
        }

        /// Modify the deque so that it can hold at least `new_capacity` items.
        /// Implements super-linear growth to achieve amortized O(1) push/pop operations.
        /// Invalidates element pointers if additional memory is needed.
        pub fn ensureTotalCapacity(deque: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void {
            if (deque.buffer.len >= new_capacity) return;
            return deque.ensureTotalCapacityPrecise(gpa, std.ArrayList(T).growCapacity(new_capacity));
        }

        /// If the current capacity is less than `new_capacity`, this function will
        /// modify the deque so that it can hold exactly `new_capacity` items.
        /// Invalidates element pointers if additional memory is needed.
        pub fn ensureTotalCapacityPrecise(deque: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void {
            if (deque.buffer.len >= new_capacity) return;
            const old_buffer = deque.buffer;
            if (gpa.remap(old_buffer, new_capacity)) |new_buffer| {
                // If the items wrap around the end of the buffer we need to do
                // a memcpy to prevent a gap after resizing the buffer.
                if (deque.head > old_buffer.len - deque.len) {
                    // The gap splits the items in the deque into head and tail parts.
                    // Choose the shorter part to copy.
                    const head = new_buffer[deque.head..old_buffer.len];
                    const tail = new_buffer[0 .. deque.len - head.len];
                    if (head.len > tail.len and new_buffer.len - old_buffer.len > tail.len) {
                        @memcpy(new_buffer[old_buffer.len..][0..tail.len], tail);
                    } else {
                        // In this case overlap is possible if e.g. the capacity increase is 1
                        // and head.len is greater than 1.
                        deque.head = new_buffer.len - head.len;
                        @memmove(new_buffer[deque.head..][0..head.len], head);
                    }
                }
                deque.buffer = new_buffer;
            } else {
                const new_buffer = try gpa.alloc(T, new_capacity);
                if (deque.head < old_buffer.len - deque.len) {
                    @memcpy(new_buffer[0..deque.len], old_buffer[deque.head..][0..deque.len]);
                } else {
                    const head = old_buffer[deque.head..];
                    const tail = old_buffer[0 .. deque.len - head.len];
                    @memcpy(new_buffer[0..head.len], head);
                    @memcpy(new_buffer[head.len..][0..tail.len], tail);
                }
                deque.head = 0;
                deque.buffer = new_buffer;
                gpa.free(old_buffer);
            }
        }

        /// Modify the deque so that it can hold at least `additional_count` **more** items.
        /// Invalidates element pointers if additional memory is needed.
        pub fn ensureUnusedCapacity(
            deque: *Self,
            gpa: Allocator,
            additional_count: usize,
        ) Allocator.Error!void {
            return deque.ensureTotalCapacity(gpa, try addOrOom(deque.len, additional_count));
        }

        /// Add one item to the front of the deque.
        ///
        /// Invalidates element pointers if additional memory is needed.
        pub fn pushFront(deque: *Self, gpa: Allocator, item: T) error{OutOfMemory}!void {
            try deque.ensureUnusedCapacity(gpa, 1);
            deque.pushFrontAssumeCapacity(item);
        }

        /// Add one item to the front of the deque.
        ///
        /// Never invalidates element pointers.
        ///
        /// If the deque lacks unused capacity for the additional item, returns
        /// `error.OutOfMemory`.
        pub fn pushFrontBounded(deque: *Self, item: T) error{OutOfMemory}!void {
            if (deque.buffer.len - deque.len == 0) return error.OutOfMemory;
            return deque.pushFrontAssumeCapacity(item);
        }

        /// Add one item to the front of the deque.
        ///
        /// Never invalidates element pointers.
        ///
        /// Asserts that the deque can hold one additional item.
        pub fn pushFrontAssumeCapacity(deque: *Self, item: T) void {
            assert(deque.len < deque.buffer.len);
            if (deque.head == 0) {
                deque.head = deque.buffer.len;
            }
            deque.head -= 1;
            deque.buffer[deque.head] = item;
            deque.len += 1;
        }

        /// Add one item to the back of the deque.
        ///
        /// Invalidates element pointers if additional memory is needed.
        pub fn pushBack(deque: *Self, gpa: Allocator, item: T) error{OutOfMemory}!void {
            try deque.ensureUnusedCapacity(gpa, 1);
            deque.pushBackAssumeCapacity(item);
        }

        /// Add one item to the back of the deque.
        ///
        /// Never invalidates element pointers.
        ///
        /// If the deque lacks unused capacity for the additional item, returns
        /// `error.OutOfMemory`.
        pub fn pushBackBounded(deque: *Self, item: T) error{OutOfMemory}!void {
            if (deque.buffer.len - deque.len == 0) return error.OutOfMemory;
            deque.pushBackAssumeCapacity(item);
        }

        /// Add one item to the back of the deque.
        ///
        /// Never invalidates element pointers.
        ///
        /// Asserts that the deque can hold one additional item.
        pub fn pushBackAssumeCapacity(deque: *Self, item: T) void {
            assert(deque.len < deque.buffer.len);
            const buffer_index = deque.bufferIndex(deque.len);
            deque.buffer[buffer_index] = item;
            deque.len += 1;
        }

        /// Add `items` to the front of the deque.
        /// This is equivalent to iterating `items` in reverse and calling
        /// `pushFront` on every single entry.
        ///
        /// Invalidates element pointers if additional memory is needed.
        pub fn pushFrontSlice(deque: *Self, gpa: Allocator, items: []const T) error{OutOfMemory}!void {
            try deque.ensureUnusedCapacity(gpa, items.len);
            return deque.pushFrontSliceAssumeCapacity(items);
        }

        /// Add `items` to the front of the deque.
        /// This is equivalent to iterating `items` in reverse and calling
        /// `pushFront` on every single entry.
        ///
        /// Never invalidates element pointers.
        ///
        /// If the deque lacks unused capacity for the additional items, returns
        /// `error.OutOfMemory`.
        pub fn pushFrontSliceBounded(deque: *Self, items: []const T) error{OutOfMemory}!void {
            if (deque.buffer.len - deque.len < items.len) return error.OutOfMemory;
            return deque.pushFrontSliceAssumeCapacity(items);
        }

        /// Add `items` to the front of the deque.
        /// This is equivalent to iterating `items` in reverse and calling
        /// `pushFront` on every single entry.
        ///
        /// Never invalidates element pointers.
        ///
        /// Asserts that the deque can hold the additional items.
        pub fn pushFrontSliceAssumeCapacity(deque: *Self, items: []const T) void {
            assert(deque.buffer.len - deque.len >= items.len);
            if (deque.head < items.len) {
                @memcpy(deque.buffer[0..deque.head], items[items.len - deque.head ..]);
                deque.head = deque.buffer.len - items.len + deque.head;
                @memcpy(deque.buffer[deque.head..], items.ptr);
            } else {
                deque.head -= items.len;
                @memcpy(deque.buffer[deque.head..][0..items.len], items);
            }
            deque.len += items.len;
        }

        /// Add `items` to the back of the deque.
        /// This is equivalent to iterating `items` in order and calling
        /// `pushBack` on every single entry.
        ///
        /// Invalidates element pointers if additional memory is needed.
        pub fn pushBackSlice(deque: *Self, gpa: Allocator, items: []const T) error{OutOfMemory}!void {
            try deque.ensureUnusedCapacity(gpa, items.len);
            return deque.pushBackSliceAssumeCapacity(items);
        }

        /// Add `items` to the back of the deque.
        /// This is equivalent to iterating `items` in order and calling
        /// `pushBack` on every single entry.
        ///
        /// Never invalidates element pointers.
        ///
        /// If the deque lacks unused capacity for the additional items, returns
        /// `error.OutOfMemory`.
        pub fn pushBackSliceBounded(deque: *Self, items: []const T) error{OutOfMemory}!void {
            if (deque.buffer.len - deque.len < items.len) return error.OutOfMemory;
            return deque.pushBackSliceAssumeCapacity(items);
        }

        /// Add `items` to the back of the deque.
        /// This is equivalent to iterating `items` in order and calling
        /// `pushBack` on every single entry.
        ///
        /// Never invalidates element pointers.
        ///
        /// Asserts that the deque can hold the additional items.
        pub fn pushBackSliceAssumeCapacity(deque: *Self, items: []const T) void {
            assert(deque.buffer.len - deque.len >= items.len);
            const trailing_buffer = deque.buffer[deque.bufferIndex(deque.len)..];
            if (trailing_buffer.len < items.len) {
                @memcpy(trailing_buffer, items[0..trailing_buffer.len]);
                @memcpy(deque.buffer.ptr, items[trailing_buffer.len..]);
            } else {
                @memcpy(trailing_buffer[0..items.len], items);
            }
            deque.len += items.len;
        }

        /// Return the first item in the deque or null if empty.
        pub fn front(deque: *const Self) ?T {
            if (deque.len == 0) return null;
            return deque.buffer[deque.head];
        }

        /// Return pointer to the first item in the deque or null if empty.
        pub fn frontPtr(deque: *const Self) ?*T {
            if (deque.len == 0) return null;
            return &deque.buffer[deque.head];
        }

        /// Return the last item in the deque or null if empty.
        pub fn back(deque: *const Self) ?T {
            if (deque.len == 0) return null;
            return deque.buffer[deque.bufferIndex(deque.len - 1)];
        }

        /// Return the last item in the deque or null if empty.
        pub fn backPtr(deque: *const Self) ?*T {
            if (deque.len == 0) return null;
            return &deque.buffer[deque.bufferIndex(deque.len - 1)];
        }

        /// Return the item at the given index in the deque.
        ///
        /// The first item in the queue is at index 0.
        ///
        /// Asserts that the index is in-bounds.
        pub fn at(deque: *const Self, index: usize) T {
            assert(index < deque.len);
            return deque.buffer[deque.bufferIndex(index)];
        }

        /// Return pointer to the item at the given index in the deque.
        ///
        /// The first item in the queue is at index 0.
        ///
        /// Asserts that the index is in-bounds.
        pub fn atPtr(deque: *const Self, index: usize) *T {
            assert(index < deque.len);
            return &deque.buffer[deque.bufferIndex(index)];
        }

        /// Remove and return the first item in the deque or null if empty.
        pub fn popFront(deque: *Self) ?T {
            if (deque.len == 0) return null;
            const pop_index = deque.head;
            deque.head = deque.bufferIndex(1);
            deque.len -= 1;
            return deque.buffer[pop_index];
        }

        /// Remove and return the last item in the deque or null if empty.
        pub fn popBack(deque: *Self) ?T {
            if (deque.len == 0) return null;
            deque.len -= 1;
            return deque.buffer[deque.bufferIndex(deque.len)];
        }

        pub const Iterator = struct {
            deque: *const Self,
            index: usize,

            pub fn peek(it: Iterator) ?T {
                if (it.index >= it.deque.len) return null;
                return it.deque.at(it.index);
            }
            pub fn next(it: *Iterator) ?T {
                const item = it.peek() orelse return null;
                it.index += 1;
                return item;
            }

            pub fn peekPtr(it: Iterator) ?*T {
                if (it.index >= it.deque.len) return null;
                return it.deque.atPtr(it.index);
            }
            pub fn nextPtr(it: *Iterator) ?*T {
                const item_ptr = it.peekPtr() orelse return null;
                it.index += 1;
                return item_ptr;
            }
        };

        /// Iterates over all items in the deque in order from front to back.
        pub fn iterator(deque: *const Self) Iterator {
            return .{ .deque = deque, .index = 0 };
        }

        /// Returns the index in `buffer` where the element at the given
        /// index in the logical deque is stored.
        fn bufferIndex(deque: *const Self, index: usize) usize {
            // This function is written in this way to avoid overflow and
            // expensive division.
            const head_len = deque.buffer.len - deque.head;
            if (index < head_len) {
                return deque.head + index;
            } else {
                return index - head_len;
            }
        }
    };
}

/// Integer addition returning `error.OutOfMemory` on overflow.
fn addOrOom(a: usize, b: usize) error{OutOfMemory}!usize {
    const result, const overflow = @addWithOverflow(a, b);
    if (overflow != 0) return error.OutOfMemory;
    return result;
}

test "basic" {
    const testing = std.testing;
    const gpa = testing.allocator;

    var q: Deque(u32) = .empty;
    defer q.deinit(gpa);

    try testing.expectEqual(null, q.popFront());
    try testing.expectEqual(null, q.popBack());

    try q.pushBack(gpa, 1);
    try q.pushBack(gpa, 2);
    try q.pushBack(gpa, 3);
    try q.pushFront(gpa, 0);

    try testing.expectEqual(0, q.popFront());
    try testing.expectEqual(1, q.popFront());
    try testing.expectEqual(3, q.popBack());
    try testing.expectEqual(2, q.popFront());
    try testing.expectEqual(null, q.popFront());
    try testing.expectEqual(null, q.popBack());
}

test "buffer" {
    const testing = std.testing;

    var buffer: [4]u32 = undefined;
    var q: Deque(u32) = .initBuffer(&buffer);

    try testing.expectEqual(null, q.popFront());
    try testing.expectEqual(null, q.popBack());

    try q.pushBackBounded(1);
    try q.pushBackBounded(2);
    try q.pushBackBounded(3);
    try q.pushFrontBounded(0);
    try testing.expectError(error.OutOfMemory, q.pushBackBounded(4));

    try testing.expectEqual(0, q.popFront());
    try testing.expectEqual(1, q.popFront());
    try testing.expectEqual(3, q.popBack());
    try testing.expectEqual(2, q.popFront());
    try testing.expectEqual(null, q.popFront());
    try testing.expectEqual(null, q.popBack());
}

test "slow growth" {
    const testing = std.testing;
    const gpa = testing.allocator;

    var q: Deque(i32) = .empty;
    defer q.deinit(gpa);

    try q.ensureTotalCapacityPrecise(gpa, 1);
    q.pushBackAssumeCapacity(1);
    try q.ensureTotalCapacityPrecise(gpa, 2);
    q.pushFrontAssumeCapacity(0);
    try q.ensureTotalCapacityPrecise(gpa, 3);
    q.pushBackAssumeCapacity(2);
    try q.ensureTotalCapacityPrecise(gpa, 5);
    q.pushBackAssumeCapacity(3);
    q.pushFrontAssumeCapacity(-1);
    try q.ensureTotalCapacityPrecise(gpa, 6);
    q.pushFrontAssumeCapacity(-2);

    try testing.expectEqual(-2, q.popFront());
    try testing.expectEqual(-1, q.popFront());
    try testing.expectEqual(3, q.popBack());
    try testing.expectEqual(0, q.popFront());
    try testing.expectEqual(2, q.popBack());
    try testing.expectEqual(1, q.popBack());
    try testing.expectEqual(null, q.popFront());
    try testing.expectEqual(null, q.popBack());
}

test "slice" {
    const testing = std.testing;
    const gpa = testing.allocator;

    var q: Deque(i32) = .empty;
    defer q.deinit(gpa);

    try q.pushBackSlice(gpa, &.{ 3, 4, 5 });
    try q.pushBackSlice(gpa, &.{ 6, 7 });
    try q.pushFrontSlice(gpa, &.{2});
    try q.pushBackSlice(gpa, &.{});
    try q.pushFrontSlice(gpa, &.{ 0, 1 });
    try q.pushFrontSlice(gpa, &.{});

    try testing.expectEqual(0, q.popFront());
    try testing.expectEqual(1, q.popFront());
    try testing.expectEqual(7, q.popBack());
    try testing.expectEqual(6, q.popBack());

    try q.pushFrontSlice(gpa, &.{ 0, 1 });
    try q.pushBackSlice(gpa, &.{ 6, 7 });

    try testing.expectEqual(0, q.popFront());
    try testing.expectEqual(1, q.popFront());
    try testing.expectEqual(2, q.popFront());
    try testing.expectEqual(7, q.popBack());
    try testing.expectEqual(6, q.popBack());
    try testing.expectEqual(3, q.popFront());
    try testing.expectEqual(4, q.popFront());
    try testing.expectEqual(5, q.popBack());
    try testing.expectEqual(null, q.popFront());
    try testing.expectEqual(null, q.popBack());
}

test "iterator" {
    const testing = std.testing;
    const gpa = testing.allocator;

    var q: Deque(i32) = .empty;
    defer q.deinit(gpa);

    const items: []const i32 = &.{ 0, 1, 2, 3, 4, 5 };
    try q.pushFrontSlice(gpa, items);

    {
        var it = q.iterator();
        for (items) |item| {
            try testing.expectEqual(item, it.peek());
            try testing.expectEqual(item, it.next());
        }
        try testing.expectEqual(null, it.peek());
        try testing.expectEqual(null, it.next());
    }
    {
        var it = q.iterator();
        for (items) |item| {
            if (it.peekPtr()) |ptr| {
                try testing.expectEqual(item, ptr.*);
            } else return error.TestExpectedNonNull;
            if (it.nextPtr()) |ptr| {
                try testing.expectEqual(item, ptr.*);
            } else return error.TestExpectedNonNull;
        }
        try testing.expectEqual(null, it.peekPtr());
        try testing.expectEqual(null, it.nextPtr());
    }
}

test "fuzz against ArrayList oracle" {
    try std.testing.fuzz({}, fuzzAgainstArrayList, .{});
}

const FuzzAllocator = struct {
    smith: *std.testing.Smith,
    bufs: [2][256 * 4]u8 align(4),
    used_bitmap: u2,
    used_len: [2]usize,

    pub fn init(smith: *std.testing.Smith) FuzzAllocator {
        return .{
            .smith = smith,
            .bufs = undefined,
            .used_len = undefined,
            .used_bitmap = 0,
        };
    }

    pub fn allocator(f: *FuzzAllocator) std.mem.Allocator {
        return .{
            .ptr = f,
            .vtable = &.{
                .alloc = alloc,
                .resize = resize,
                .remap = remap,
                .free = free,
            },
        };
    }

    pub fn allocCount(f: *FuzzAllocator) u2 {
        return @popCount(f.used_bitmap);
    }

    fn alloc(ctx: *anyopaque, len: usize, a: std.mem.Alignment, _: usize) ?[*]u8 {
        const f: *FuzzAllocator = @ptrCast(@alignCast(ctx));
        assert(a == .@"4");
        assert(len % 4 == 0);

        const slot: u1 = @intCast(@ctz(~f.used_bitmap));
        const buf: []u8 = &f.bufs[slot];
        if (len > buf.len) return null;
        f.used_bitmap |= @as(u2, 1) << slot;
        f.used_len[slot] = len;
        return buf.ptr;
    }

    fn memSlot(f: *FuzzAllocator, mem: []u8) u1 {
        const slot: u1 = if (&mem[0] == &f.bufs[0][0])
            0
        else if (&mem[0] == &f.bufs[1][0])
            1
        else
            unreachable;
        assert((f.used_bitmap >> slot) & 1 == 1);
        assert(mem.len == f.used_len[slot]);
        return slot;
    }

    fn resize(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, new_len: usize, _: usize) bool {
        const f: *FuzzAllocator = @ptrCast(@alignCast(ctx));
        assert(a == .@"4");
        assert(f.allocCount() == 1);

        const slot = f.memSlot(mem);
        if (new_len > f.bufs[slot].len or f.smith.value(bool)) return false;
        f.used_len[slot] = new_len;
        return true;
    }

    fn remap(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, new_len: usize, _: usize) ?[*]u8 {
        const f: *FuzzAllocator = @ptrCast(@alignCast(ctx));
        assert(a == .@"4");
        assert(f.allocCount() == 1);

        const slot = f.memSlot(mem);
        if (new_len > f.bufs[slot].len or f.smith.value(bool)) return null;

        if (f.smith.value(bool)) {
            f.used_len[slot] = new_len;
            // remap in place
            return mem.ptr;
        } else {
            // moving remap
            const new_slot = ~slot;
            f.used_bitmap = ~f.used_bitmap;
            f.used_len[new_slot] = new_len;

            const new_buf = &f.bufs[new_slot];
            @memcpy(new_buf[0..mem.len], mem);
            return new_buf.ptr;
        }
    }

    fn free(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, _: usize) void {
        const f: *FuzzAllocator = @ptrCast(@alignCast(ctx));
        assert(a == .@"4");
        f.used_bitmap ^= @as(u2, 1) << f.memSlot(mem);
    }
};

fn fuzzAgainstArrayList(_: void, smith: *std.testing.Smith) anyerror!void {
    const testing = std.testing;

    var q_gpa_inst: FuzzAllocator = .init(smith);
    var l_gpa_buf: [q_gpa_inst.bufs[0].len]u8 align(4) = undefined;
    var l_gpa_inst: std.heap.FixedBufferAllocator = .init(&l_gpa_buf);
    const q_gpa = q_gpa_inst.allocator();
    const l_gpa = l_gpa_inst.allocator();

    var q: Deque(u32) = .empty;
    var l: std.ArrayList(u32) = .empty;

    const Action = enum(u8) {
        grow,
        push_back,
        push_front,
        push_back_slice,
        push_front_slice,
        pop_back,
        pop_front,
    };

    while (!smith.eosWeightedSimple(15, 1)) {
        const baseline = testing.Smith.baselineWeights(Action);
        const grow_weight: testing.Smith.Weight = .value(Action, .grow, 3);
        switch (smith.valueWeighted(Action, baseline ++ .{grow_weight})) {
            .push_back => {
                const item = smith.value(u32);
                try testing.expectEqual(
                    l.appendBounded(item),
                    q.pushBackBounded(item),
                );
            },
            .push_front => {
                const item = smith.value(u32);
                try testing.expectEqual(
                    l.insertBounded(0, item),
                    q.pushFrontBounded(item),
                );
            },
            .push_back_slice => {
                var buffer: [std.math.maxInt(u3)]u32 = undefined;
                const items = buffer[0..smith.value(u3)];
                for (items) |*item| {
                    item.* = smith.value(u32);
                }
                try testing.expectEqual(
                    l.appendSliceBounded(items),
                    q.pushBackSliceBounded(items),
                );
            },
            .push_front_slice => {
                var buffer: [std.math.maxInt(u3)]u32 = undefined;
                const items = buffer[0..smith.value(u3)];
                for (items) |*item| {
                    item.* = smith.value(u32);
                }
                try testing.expectEqual(
                    l.insertSliceBounded(0, items),
                    q.pushFrontSliceBounded(items),
                );
            },
            .pop_back => {
                try testing.expectEqual(l.pop(), q.popBack());
            },
            .pop_front => {
                try testing.expectEqual(
                    if (l.items.len > 0) l.orderedRemove(0) else null,
                    q.popFront(),
                );
            },
            // Growing by small, random, linear amounts seems to better test
            // ensureTotalCapacityPrecise(), which is the most complex part
            // of the Deque implementation.
            .grow => {
                const growth = smith.value(u3);
                try l.ensureTotalCapacityPrecise(l_gpa, l.items.len + growth);
                try q.ensureTotalCapacityPrecise(q_gpa, q.len + growth);
            },
        }
        try testing.expectEqual(l.last(), q.back());
        try testing.expectEqual(
            if (l.items.len > 0) l.items[0] else null,
            q.front(),
        );
        try testing.expectEqual(l.items.len, q.len);
        try testing.expectEqual(l.capacity, q.buffer.len);
        {
            var it = q.iterator();
            for (l.items) |item| {
                try testing.expectEqual(item, it.next());
            }
            try testing.expectEqual(null, it.next());
        }
        try testing.expectEqual(@intFromBool(q.buffer.len != 0), q_gpa_inst.allocCount());
    }
    q.deinit(q_gpa);
    try testing.expectEqual(0, q_gpa_inst.allocCount());
}