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;
        }
    };
}