const libc = @cImport(@cInclude("string.h"));
const heap = @import("../heap.zig");
pub fn DynamicArray(comptime T: type) type {
return struct {
const Self = @This();
items: [*]T = undefined,
length: usize = 0,
capacity: usize = 0,
pub fn init() Self {
return .{ .items = undefined, .length = 0, .capacity = 0 };
}
pub fn deinit(self: *Self) void {
if (self.capacity > 0)
heap.free(self.items);
}
pub fn size(self: *const Self) usize {
return self.length;
}
pub fn cap(self: *const Self) usize {
return self.capacity;
}
pub fn empty(self: *const Self) bool {
return self.length == 0;
}
pub fn slice(self: *const Self) []const T {
if (self.capacity == 0) return &[_]T{};
return self.items[0..self.length];
}
pub fn sliceMut(self: *Self) []T {
if (self.capacity == 0) return &[_]T{};
return self.items[0..self.length];
}
pub fn get(self: *const Self, index: usize) *const T {
return &self.items[index];
}
pub fn getMut(self: *Self, index: usize) *T {
return &self.items[index];
}
pub fn front(self: *const Self) *const T {
return &self.items[0];
}
pub fn frontMut(self: *Self) *T {
return &self.items[0];
}
pub fn back(self: *const Self) *const T {
return &self.items[self.length - 1];
}
pub fn backMut(self: *Self) *T {
return &self.items[self.length - 1];
}
pub fn at(self: *const Self, index: usize) *const T {
if (index >= self.length) @panic("index out of bounds");
return &self.items[index];
}
pub fn atMut(self: *Self, index: usize) *T {
if (index >= self.length) @panic("index out of bounds");
return &self.items[index];
}
pub fn reserve(self: *Self, min_capacity: usize) void {
if (min_capacity <= self.capacity) return;
self.grow(min_capacity);
}
pub fn shrinkToFit(self: *Self) void {
if (self.length == self.capacity) return;
if (self.length == 0) {
heap.free(self.items);
self.items = undefined;
self.capacity = 0;
return;
}
self.items = @ptrCast(@alignCast(heap.realloc(
@ptrCast(self.items),
self.length * @sizeOf(T),
)));
self.capacity = self.length;
}
pub fn resize(self: *Self, new_size: usize) void {
if (new_size > self.capacity)
self.grow(self.recommend(new_size));
self.length = new_size;
}
pub fn resizeWith(self: *Self, new_size: usize, value: T) void {
if (new_size > self.capacity)
self.grow(self.recommend(new_size));
if (new_size > self.length)
@memset(self.items[self.length..new_size], value);
self.length = new_size;
}
pub fn append(self: *Self, item: T) void {
if (self.length == self.capacity)
self.grow(self.recommend(self.length + 1));
self.items[self.length] = item;
self.length += 1;
}
pub fn appendAll(self: *Self, other: *const Self) void {
self.reserve(self.length + other.length);
for (other.slice()) |item|
self.append(item);
}
pub fn equal(self: *const Self, other: *const Self) bool {
if (self.length != other.length) return false;
for (0..self.length) |i|
if (self.items[i] != other.items[i]) return false;
return true;
}
pub fn clear(self: *Self) void {
self.length = 0;
}
pub fn swap(self: *Self, other: *Self) void {
const tmp = self.*;
self.* = other.*;
other.* = tmp;
}
pub fn swapRemove(self: *Self, index: usize) T {
const val = self.items[index];
self.length -= 1;
if (index != self.length)
self.items[index] = self.items[self.length];
return val;
}
pub fn orderedRemove(self: *Self, index: usize) T {
const val = self.items[index];
self.orderedRemoveRange(index, index + 1);
return val;
}
pub fn orderedRemoveRange(self: *Self, first: usize, last: usize) void {
const count = last - first;
_ = libc.memmove(
@as([*]u8, @ptrCast(self.items + first)),
@as([*]const u8, @ptrCast(self.items + last)),
(self.length - last) * @sizeOf(T),
);
self.length -= count;
}
pub fn popBack(self: *Self) void {
self.length -= 1;
}
pub fn insert(self: *Self, index: usize, item: T) void {
if (self.length == self.capacity)
self.grow(self.recommend(self.length + 1));
_ = libc.memmove(
@as([*]u8, @ptrCast(self.items + index + 1)),
@as([*]const u8, @ptrCast(self.items + index)),
(self.length - index) * @sizeOf(T),
);
self.items[index] = item;
self.length += 1;
}
fn recommend(self: *const Self, new_size: usize) usize {
const ms = ~@as(usize, 0) / @sizeOf(T);
if (new_size > ms) @panic("size overflow");
if (self.capacity >= ms / 2) return ms;
return @max(@max(self.capacity * 2, new_size), 8);
}
fn grow(self: *Self, new_capacity: usize) void {
self.items = @ptrCast(@alignCast(heap.realloc(
if (self.capacity > 0) @ptrCast(self.items) else null,
new_capacity * @sizeOf(T),
)));
self.capacity = new_capacity;
}
};
}