//! 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;

    list.free += 1;

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

    list.pool[idx].next = list.head;

    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;

    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 {

        count += 1;

        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;

        }

        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;

        }

        cur = list.pool[idx].next;

        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;

        list.pool[idx].next = prev;

        prev = idx;

        cur = next;

    }

    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 {

        total += list.pool[idx].value;

        cur = list.pool[idx].next;

    }

    return total;

}

/// Reset the list to empty.

fn reset(list: *mut List) {

    list.head = nil;

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

        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;

        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;

}