const std = @import("std");

const DynamicArray = struct {
	allocator: *std.mem.Allocator,
	data: []i32,
	len: usize,
	cap: usize,

	fn init(allocator: *std.mem.Allocator, initial_cap: usize) !DynamicArray {
		const data = try allocator.alloc(i32, initial_cap);
		return DynamicArray {
			.allocator = allocator,
			.data = data,
			.len = 0,
			.cap = initial_cap,
		};
	}

	fn add(self: *DynamicArray, value: i32) !void {
		if (self.len >= self.cap) {
			const new_cap = if (self.cap == 0) 1 else self.cap * 2;
			self.data = try self.allocator.realloc(self.data, new_cap);
			self.cap = new_cap;
		}
		self.data[self.len] = value;
		self.len += 1;
	}

	fn insert(self: *DynamicArray, index: usize, value: i32) !void {
		if (self.len == 0 and index == 0)
			return try self.add(value);
		else if (index >= self.len) 
			return error.InvalidIndex;

		if ((self.len + 1) >= self.cap) {
			const new_cap = self.cap * 2;
			self.data = try self.allocator.realloc(self.data, new_cap);
			self.cap = new_cap;
		}

		self.len += 1;
		for (index..self.len) |i| {
			const j = self.len - 1 - i;
			self.data[j + 1] = self.data[j];
		}
		self.data[index] = value;
	}

	fn remove(self: *DynamicArray, index: usize) !void {
		if (self.len == 0) return error.EmptyArray;
		if (index >= self.len) return error.InvalidIndex;

		for (index..(self.len - 1)) |i| {
			self.data[i] = self.data[i + 1];
		}
		self.data[self.len - 1] = undefined;
		self.len -= 1;

		if (self.len < (self.cap / 2)) {
			const new_cap = self.cap / 2;
			self.data = try self.allocator.realloc(self.data, new_cap);
			self.cap = new_cap;
		}
	}

	fn deinit(self: *DynamicArray) void {
		self.allocator.free(self.data);
	}
};

pub fn main() !void {
	var allocator = std.heap.page_allocator;
	var arr = try DynamicArray.init(&allocator, 2);
	defer arr.deinit();

	try arr.add(10);
	try arr.add(20);
	try arr.add(30);
	try arr.insert(1, 100);
	try arr.remove(1);

	for (arr.data[0..arr.len]) |num| {
		std.debug.print("{d}\n", .{num});
	}
}