Capacidade: 4    Tamanho: 3
+---+---+---+---+
| 5 | 8 | 3 |   |  ← espaço livre
+---+---+---+---+

Após inserir 7 e 1 (capacidade dobra para 8):
+---+---+---+---+---+---+---+---+
| 5 | 8 | 3 | 7 | 1 |   |   |   |
+---+---+---+---+---+---+---+---+
Capacidade: 8    Tamanho: 5

Redimensionamento:
1. Aloca novo buffer com 2x capacidade
2. Copia elementos para novo buffer
3. Libera buffer antigo

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

/// Array dinâmico genérico.
pub fn ArrayDinamico(comptime T: type) type {
    return struct {
        const Self = @This();

        items: []T,
        capacidade: usize,
        tamanho: usize,
        allocator: Allocator,

        /// Cria um novo array dinâmico vazio.
        pub fn init(allocator: Allocator) Self {
            return .{
                .items = &.{},
                .capacidade = 0,
                .tamanho = 0,
                .allocator = allocator,
            };
        }

        /// Cria com capacidade inicial reservada.
        pub fn initCapacidade(allocator: Allocator, capacidade: usize) !Self {
            const items = try allocator.alloc(T, capacidade);
            return .{
                .items = items,
                .capacidade = capacidade,
                .tamanho = 0,
                .allocator = allocator,
            };
        }

        /// Libera a memória.
        pub fn deinit(self: *Self) void {
            if (self.capacidade > 0) {
                self.allocator.free(self.items[0..self.capacidade]);
            }
        }

        /// Adiciona um elemento ao final — O(1) amortizado.
        pub fn append(self: *Self, item: T) !void {
            if (self.tamanho == self.capacidade) {
                try self.redimensionar();
            }
            self.items[self.tamanho] = item;
            self.tamanho += 1;
        }

        /// Remove e retorna o último elemento — O(1).
        pub fn pop(self: *Self) ?T {
            if (self.tamanho == 0) return null;
            self.tamanho -= 1;
            return self.items[self.tamanho];
        }

        /// Insere em uma posição específica — O(n).
        pub fn inserir(self: *Self, indice: usize, item: T) !void {
            if (indice > self.tamanho) return error.IndiceInvalido;
            if (self.tamanho == self.capacidade) {
                try self.redimensionar();
            }

            // Desloca elementos para a direita
            var i = self.tamanho;
            while (i > indice) : (i -= 1) {
                self.items[i] = self.items[i - 1];
            }
            self.items[indice] = item;
            self.tamanho += 1;
        }

        /// Remove elemento em uma posição — O(n).
        pub fn remover(self: *Self, indice: usize) !T {
            if (indice >= self.tamanho) return error.IndiceInvalido;
            const item = self.items[indice];

            // Desloca elementos para a esquerda
            for (indice..self.tamanho - 1) |i| {
                self.items[i] = self.items[i + 1];
            }
            self.tamanho -= 1;
            return item;
        }

        /// Acessa elemento por índice — O(1).
        pub fn get(self: *const Self, indice: usize) !T {
            if (indice >= self.tamanho) return error.IndiceInvalido;
            return self.items[indice];
        }

        /// Define valor em índice — O(1).
        pub fn set(self: *Self, indice: usize, valor: T) !void {
            if (indice >= self.tamanho) return error.IndiceInvalido;
            self.items[indice] = valor;
        }

        /// Retorna slice dos elementos válidos.
        pub fn slice(self: *const Self) []const T {
            return self.items[0..self.tamanho];
        }

        /// Busca linear — O(n).
        pub fn buscar(self: *const Self, valor: T) ?usize {
            for (self.items[0..self.tamanho], 0..) |item, i| {
                if (item == valor) return i;
            }
            return null;
        }

        /// Verifica se contém o valor.
        pub fn contem(self: *const Self, valor: T) bool {
            return self.buscar(valor) != null;
        }

        /// Limpa todos os elementos sem liberar memória.
        pub fn limpar(self: *Self) void {
            self.tamanho = 0;
        }

        fn redimensionar(self: *Self) !void {
            const nova_capacidade = if (self.capacidade == 0) 4 else self.capacidade * 2;
            const novo_buffer = try self.allocator.alloc(T, nova_capacidade);

            // Copia elementos existentes
            @memcpy(novo_buffer[0..self.tamanho], self.items[0..self.tamanho]);

            if (self.capacidade > 0) {
                self.allocator.free(self.items[0..self.capacidade]);
            }

            self.items = novo_buffer;
            self.capacidade = nova_capacidade;
        }
    };
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var arr = ArrayDinamico(i32).init(allocator);
    defer arr.deinit();

    // Append
    for ([_]i32{ 10, 20, 30, 40, 50 }) |val| {
        try arr.append(val);
    }
    try stdout.print("Array: ", .{});
    for (arr.slice()) |v| try stdout.print("{d} ", .{v});
    try stdout.print("(tam={d}, cap={d})\n", .{ arr.tamanho, arr.capacidade });

    // Inserir no meio
    try arr.inserir(2, 25);
    try stdout.print("Após inserir 25 no índice 2: ", .{});
    for (arr.slice()) |v| try stdout.print("{d} ", .{v});
    try stdout.print("\n", .{});

    // Remover
    const removido = try arr.remover(0);
    try stdout.print("Removido índice 0: {d}\n", .{removido});

    // Pop
    if (arr.pop()) |ultimo| {
        try stdout.print("Pop: {d}\n", .{ultimo});
    }

    // Buscar
    try stdout.print("Contém 30? {}\n", .{arr.contem(30)});
    try stdout.print("Índice de 25: {?d}\n", .{arr.buscar(25)});

    // Estado final
    try stdout.print("Final: ", .{});
    for (arr.slice()) |v| try stdout.print("{d} ", .{v});
    try stdout.print("(tam={d})\n", .{arr.tamanho});

    // Comparação com std.ArrayList
    try stdout.print("\n=== std.ArrayList ===\n", .{});
    var lista = std.ArrayList(i32).init(allocator);
    defer lista.deinit();
    try lista.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
    try stdout.print("std.ArrayList: {any}\n", .{lista.items});
}