//! returns: 0
//! Linked list via array pool.
//! Implement a singly-linked list using an array of node records
//! (pool allocator pattern). Operations: push, pop, find, reverse, length.

/// A node in the linked list.
record Node {
    value: i32,
    next: ?u32,
}

/// A linked list backed by a pool of pre-allocated nodes.
record List {
    pool: [Node; 64],
    free: u32,
    head: ?u32,
}

/// Allocate a node from the pool. Returns its index.
fn alloc(list: &mut List, value: i32) -> u32 {
    let idx = list.free;
    set list.free += 1;
    set list.pool[idx] = Node { value, next: nil };
    return idx;
}

/// Push a value onto the front of the list.
fn push(list: &mut List, value: i32) {
    let idx = alloc(list, value);
    set list.pool[idx].next = list.head;
    set list.head = idx;
}

/// Pop a value from the front of the list. Returns nil if empty.
fn pop(list: &mut List) -> ?i32 {
    let idx = list.head else {
        return nil;
    };
    let value = list.pool[idx].value;
    set list.head = list.pool[idx].next;
    return value;
}

/// Get the length of the list.
fn length(list: &List) -> u32 {
    let mut count: u32 = 0;
    let mut cur = list.head;
    while let idx = cur {
        set count += 1;
        set cur = list.pool[idx].next;
    }
    return count;
}

/// Find a value in the list. Returns the node index if found, or nil.
fn find(list: &List, value: i32) -> ?u32 {
    let mut cur = list.head;
    while let idx = cur {
        if list.pool[idx].value == value {
            return idx;
        }
        set cur = list.pool[idx].next;
    }
    return nil;
}

/// Get the value at a given index (0-based from head).
fn valueAt(list: &List, index: u32) -> ?i32 {
    let mut cur = list.head;
    let mut i: u32 = 0;
    while let idx = cur {
        if i == index {
            return list.pool[idx].value;
        }
        set cur = list.pool[idx].next;
        set i += 1;
    }
    return nil;
}

/// Reverse the linked list in-place.
fn reverse(list: &mut List) {
    let mut prev: ?u32 = nil;
    let mut cur = list.head;
    while let idx = cur {
        let next = list.pool[idx].next;
        set list.pool[idx].next = prev;
        set prev = idx;
        set cur = next;
    }
    set list.head = prev;
}

/// Compute the sum of all values in the list.
fn sum(list: &List) -> i32 {
    let mut total: i32 = 0;
    let mut cur = list.head;
    while let idx = cur {
        set total += list.pool[idx].value;
        set cur = list.pool[idx].next;
    }
    return total;
}

/// Reset the list to empty.
fn reset(list: &mut List) {
    set list.head = nil;
    set list.free = 0;
}

/// Test basic push and length.
fn testPushLength(list: &mut List) -> i32 {
    push(list, 10);
    push(list, 20);
    push(list, 30);

    assert length(list) == 3;
    // Head should be most recently pushed.
    let v0 = valueAt(list, 0) else {
        return 2;
    };
    assert v0 == 30;
    let v1 = valueAt(list, 1) else {
        return 3;
    };
    assert v1 == 20;
    let v2 = valueAt(list, 2) else {
        return 4;
    };
    assert v2 == 10;
    return 0;
}

/// Test pop.
fn testPop(list: &mut List) -> i32 {
    let v = pop(list) else {
        return 1;
    };
    assert v == 30;
    assert length(list) == 2;
    let v0 = valueAt(list, 0) else {
        return 3;
    };
    assert v0 == 20;
    return 0;
}

/// Test find.
fn testFind(list: &mut List) -> i32 {
    // 20 should be found.
    assert find(list, 20) <> nil;
    // 10 should be found.
    assert find(list, 10) <> nil;
    // 30 was popped, should not be found.
    assert find(list, 30) == nil;
    // 99 never inserted.
    assert find(list, 99) == nil;
    return 0;
}

/// Test reverse.
fn testReverse(list: &mut List) -> i32 {
    // Current list: 20 -> 10
    // Add more elements.
    push(list, 40);
    push(list, 50);
    // List: 50 -> 40 -> 20 -> 10

    let sumBefore = sum(list);

    reverse(list);
    // List should be: 10 -> 20 -> 40 -> 50

    assert length(list) == 4;

    let v0 = valueAt(list, 0) else {
        return 2;
    };
    assert v0 == 10;
    let v1 = valueAt(list, 1) else {
        return 3;
    };
    assert v1 == 20;
    let v2 = valueAt(list, 2) else {
        return 4;
    };
    assert v2 == 40;
    let v3 = valueAt(list, 3) else {
        return 5;
    };
    assert v3 == 50;

    assert sum(list) == sumBefore;
    return 0;
}

/// Test building a larger list.
fn testLargerList(list: &mut List) -> i32 {
    reset(list);

    // Push 32 elements.
    let mut i: u32 = 0;
    while i < 32 {
        push(list, i as i32 * 3);
        set i += 1;
    }

    assert length(list) == 32;

    // Sum should be 3 * (0 + 1 + ... + 31) = 3 * 496 = 1488
    assert sum(list) == 1488;

    // Reverse and verify sum is preserved.
    reverse(list);
    assert sum(list) == 1488;

    // After reverse, head should be 0 (first pushed), tail should be 93 (last pushed).
    let head = valueAt(list, 0) else {
        return 4;
    };
    assert head == 0;
    let tail = valueAt(list, 31) else {
        return 5;
    };
    assert tail == 93;

    // Pop all and verify decreasing original order.
    let mut j: u32 = 0;
    while j < 32 {
        let v = pop(list) else {
            return 6;
        };
        let expected = j as i32 * 3;
        assert v == expected;
        set j += 1;
    }

    assert length(list) == 0;

    // Pop from empty list should return nil.
    assert pop(list) == nil;
    return 0;
}

@default fn main() -> i32 {
    let mut list: List = List {
        pool: [Node { value: 0, next: nil }; 64],
        free: 0,
        head: nil,
    };

    let r1 = testPushLength(&mut list);
    if r1 <> 0 {
        return 10 + r1;
    }

    let r2 = testPop(&mut list);
    if r2 <> 0 {
        return 20 + r2;
    }

    let r3 = testFind(&mut list);
    if r3 <> 0 {
        return 30 + r3;
    }

    let r4 = testReverse(&mut list);
    if r4 <> 0 {
        return 40 + r4;
    }

    let r5 = testLargerList(&mut list);
    if r5 <> 0 {
        return 50 + r5;
    }
    return 0;
}