// list — the dynamic array, in pure Flash.
//
// `List(T)` mirrors Zig's unmanaged ArrayList surface — `.empty`, `deinit`,
// `append`, `appendSlice`, `toOwnedSlice`, `.items` — so a facade can
// re-route between the two implementations without touching a call site.
// The allocation is carried as a second slice (`buf`) rather than a raw
// capacity count, so the implementation needs nothing beyond the language's
// slice surface. Growth doubles the capacity (floor 4) and jumps straight
// to the requested length when a bulk append outruns the double.

use "base"
use "mem"

pub fn List(comptime T type) type {
    return struct {
        // The live elements, always a prefix of `buf`; the length is the
        // list length. Index, slice, and write through freely.
        items []mut T,
        // The full allocation. `items.len <= buf.len` holds at all times.
        buf []mut T,

        const Self = #This()

        // The canonical initializer: no allocation until the first append.
        pub const empty Self = .{ .items = &.{}, .buf = &.{} }

        // Release the allocation. The list is `.empty` afterwards and may
        // be reused.
        pub fn deinit(self *mut Self, alloc base.Allocator) void {
            alloc.free(self.buf)
            self.* = .empty
        }

        // Append one element, growing if needed.
        pub fn append(self *mut Self, alloc base.Allocator, item T) !void {
            try self.grow(alloc, self.items.len + 1)
            n := self.items.len
            self.buf[n] = item
            self.items = self.buf[0 .. n + 1]
        }

        // Append every element of `source`, growing at most once.
        pub fn appendSlice(self *mut Self, alloc base.Allocator, source []T) !void {
            try self.grow(alloc, self.items.len + source.len)
            n := self.items.len
            mem.copy(T, self.buf[n .. n + source.len], source)
            self.items = self.buf[0 .. n + source.len]
        }

        // Hand the elements to the caller as an exactly-sized allocation
        // the caller owns. The list is `.empty` afterwards and may be
        // reused.
        pub fn toOwnedSlice(self *mut Self, alloc base.Allocator) ![]mut T {
            owned := try alloc.alloc(T, self.items.len)
            mem.copy(T, owned, self.items)
            alloc.free(self.buf)
            self.* = .empty
            return owned
        }

        // Remove and return the element at `index` in O(1) by moving the
        // last element into its place. Order is not preserved.
        pub fn swapRemove(self *mut Self, index usize) T {
            n := self.items.len
            removed := self.items[index]
            self.items[index] = self.items[n - 1]
            self.items = self.buf[0 .. n - 1]
            return removed
        }

        // Ensure the allocation holds at least `needed` elements. On
        // failure the list is untouched — the old allocation is released
        // only after the new one exists.
        fn grow(self *mut Self, alloc base.Allocator, needed usize) !void {
            if needed <= self.buf.len {
                return
            }
            var cap usize = self.buf.len * 2
            if cap < 4 {
                cap = 4
            }
            if cap < needed {
                cap = needed
            }
            grown := try alloc.alloc(T, cap)
            mem.copy(T, grown, self.items)
            alloc.free(self.buf)
            self.buf = grown
            self.items = grown[0..self.items.len]
        }
    }
}

const Pair = struct {
    key i32,
    tag u8,
}

test "append grows past the initial capacity" {
    var xs List(i32) = .empty
    defer xs.deinit(base.testAlloc)
    var v i32 = 0
    while v < 9 {
        try xs.append(base.testAlloc, v)
        v += 1
    }
    try base.expectEqual(9, xs.items.len)
    try base.expectEqual(0, xs.items[0])
    try base.expectEqual(8, xs.items[8])
    try base.expect(xs.buf.len >= 9)
}

test "appendSlice appends in bulk" {
    var s List(u8) = .empty
    defer s.deinit(base.testAlloc)
    try s.appendSlice(base.testAlloc, "flash")
    try s.append(base.testAlloc, '!')
    try base.expect(mem.eql(u8, s.items, "flash!"))
}

test "toOwnedSlice hands off the elements and resets the list" {
    var s List(u8) = .empty
    defer s.deinit(base.testAlloc)
    try s.appendSlice(base.testAlloc, "ab")
    owned := try s.toOwnedSlice(base.testAlloc)
    defer base.testAlloc.free(owned)
    try base.expect(mem.eql(u8, owned, "ab"))
    try base.expectEqual(0, s.items.len)
    try s.append(base.testAlloc, 'c')
    try base.expectEqual('c', s.items[0])
}

test "toOwnedSlice on an empty list returns an empty slice" {
    var s List(u8) = .empty
    owned := try s.toOwnedSlice(base.testAlloc)
    defer base.testAlloc.free(owned)
    try base.expectEqual(0, owned.len)
}

test "swapRemove takes from the middle and the end" {
    var xs List(u8) = .empty
    defer xs.deinit(base.testAlloc)
    try xs.appendSlice(base.testAlloc, "abcd")
    try base.expectEqual('b', xs.swapRemove(1))
    try base.expect(mem.eql(u8, xs.items, "adc"))
    try base.expectEqual('c', xs.swapRemove(2))
    try base.expect(mem.eql(u8, xs.items, "ad"))
    try base.expectEqual('a', xs.swapRemove(0))
    try base.expectEqual('d', xs.swapRemove(0))
    try base.expectEqual(0, xs.items.len)
}

test "deinit releases and the list is reusable" {
    var s List(u8) = .empty
    try s.append(base.testAlloc, 'x')
    s.deinit(base.testAlloc)
    try base.expectEqual(0, s.items.len)
    try s.append(base.testAlloc, 'y')
    try base.expectEqual('y', s.items[0])
    s.deinit(base.testAlloc)
}

// The failing-allocator sweep bodies. `checkAllAllocationFailures` re-runs
// each one, failing a different allocation per run: every induced OOM must
// propagate as an error with nothing leaked, and the final unfailed run
// must pass the assertions.
fn growthSweep(alloc base.Allocator) !void {
    var xs List(i32) = .empty
    defer xs.deinit(alloc)
    var v i32 = 0
    while v < 40 {
        try xs.append(alloc, v)
        v += 1
    }
    try base.expectEqual(40, xs.items.len)
}

fn appendSliceSweep(alloc base.Allocator) !void {
    var s List(u8) = .empty
    defer s.deinit(alloc)
    try s.appendSlice(alloc, "ab")
    try s.appendSlice(alloc, "0123456789abcdef")
    try base.expect(mem.eql(u8, s.items, "ab0123456789abcdef"))
}

fn toOwnedSliceSweep(alloc base.Allocator) !void {
    var s List(u8) = .empty
    defer s.deinit(alloc)
    try s.appendSlice(alloc, "flash")
    owned := try s.toOwnedSlice(alloc)
    defer alloc.free(owned)
    try base.expect(mem.eql(u8, owned, "flash"))
}

test "append survives failure at every allocation point" {
    try base.checkAllAllocationFailures(base.testAlloc, growthSweep, .{})
}

test "appendSlice survives failure at every allocation point" {
    try base.checkAllAllocationFailures(base.testAlloc, appendSliceSweep, .{})
}

test "toOwnedSlice survives failure at every allocation point" {
    try base.checkAllAllocationFailures(base.testAlloc, toOwnedSliceSweep, .{})
}

test "a failed grow leaves the list untouched" {
    var failing = base.FailingAllocator.init(base.testAlloc, .{ .fail_index = 1 })
    fa := failing.allocator()
    var xs List(u8) = .empty
    defer xs.deinit(base.testAlloc)
    try xs.appendSlice(fa, "abcd")
    try base.expectError(error.OutOfMemory, xs.append(fa, 'e'))
    try base.expect(mem.eql(u8, xs.items, "abcd"))
    try base.expectEqual(4, xs.buf.len)
    try xs.append(base.testAlloc, 'e')
    try base.expect(mem.eql(u8, xs.items, "abcde"))
}

test "struct and optional element types instantiate" {
    var ps List(Pair) = .empty
    defer ps.deinit(base.testAlloc)
    try ps.append(base.testAlloc, .{ .key = 1, .tag = 'a' })
    try ps.append(base.testAlloc, .{ .key = 2, .tag = 'b' })
    try base.expectEqual(2, ps.items.len)
    try base.expectEqual('b', ps.items[1].tag)
    ps.items[0].key = 9
    try base.expectEqual(9, ps.items[0].key)

    var os List(?[]u8) = .empty
    defer os.deinit(base.testAlloc)
    try os.append(base.testAlloc, null)
    try os.append(base.testAlloc, "s")
    try base.expect(os.items[0] == null)
    try base.expect(os.items[1] != null)
}