A contiguous, growable, double-ended queue.
Pushing/popping items from either end of the queue is O(1).
pub fn Deque(comptime T: type) typepub 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;
}
}
};
}