//
// DO NOT EDIT THIS FILE!
// THIS FILE IS AUTOMATICALLY GENERATED FROM A LITERATE PROGRAM SOURCE FILE.
//
//
// This software is copyrighted 2023 by G. Andrew Mangogna.
// The following terms apply to all files associated with the software unless
// explicitly disclaimed in individual files.
// 
// The author hereby grants permission to use, copy, modify, distribute,
// and license this software and its documentation for any purpose, provided
// that existing copyright notices are retained in all copies and that this
// notice is included verbatim in any distributions. No written agreement,
// license, or royalty fee is required for any of the authorized uses.
// Modifications to this software may be copyrighted by their authors and
// need not follow the licensing terms described here, provided that the
// new terms are clearly indicated on the first page of each file where
// they apply.
// 
// IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY PARTY FOR
// DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING
// OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY DERIVATIVES
// THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE POSSIBILITY OF
// SUCH DAMAGE.
// 
// THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT.  THIS SOFTWARE
// IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE
// NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS,
// OR MODIFICATIONS.
// 
// GOVERNMENT USE: If you are acquiring this software on behalf of the
// U.S. government, the Government shall have only "Restricted Rights"
// in the software and related documentation as defined in the Federal
// Acquisition Regulations (FARs) in Clause 52.227.19 (c) (2).  If you
// are acquiring the software on behalf of the Department of Defense,
// the software shall be classified as "Commercial Computer Software"
// and the Government shall have only "Restricted Rights" as defined in
// Clause 252.227-7013 (c) (1) of DFARs.  Notwithstanding the foregoing,
// the authors grant the U.S. Government and others acting in its behalf
// permission to use and distribute the software in accordance with the
// terms specified in this license.
//

const std = @import("std");
const mem = std.mem;
const testing = std.testing;
const meta = std.meta;
pub const AllocCount = u16;
pub const GenCount = AllocCount;
const GenCounter = struct {
    counter: GenCount = 1,

    const Self = @This();

    pub fn next(
        self: *Self,
    ) void {
        self.counter +%= 1;
        if (self.counter == 0) {    // Skip the special 0 value.
            self.counter = 1;
        }
    }
};
pub const ElementStatus = enum {
    free,           // The element is not allocated.
    reserved,       // The element is allocated but not yet "active".
    allocated,      // The element is allocated and active.
};
pub const ElementId = struct {
    index: AllocCount,
    generation: GenCount,
};
pub const ArrayAllocatorError = error{
    OutOfMemory,            // All array elements are allocated or reserved.
    FreeElement,            // Operation attempted on a free element.
    UnallocatedElement,     // Operation attempted on an unallocated element.
    RefOutOfRange,          // A pointer to an array element was out of range.
    GenerationMismatch,     // The generation of the element did not match.
};
pub fn ArrayAllocator(
    comptime T: type,
    comptime capacity: AllocCount,
) type {
    return struct {
        const Self = @This();
    
        pub const AllocationSet = std.StaticBitSet(capacity);
        pub const ElementField = meta.FieldEnum(T);
        
        pub fn elementFieldName(
            comptime field: ElementField,
        ) []const u8 {
            return meta.fieldInfo(T, field).name;
        }
        
        pub fn ElementFieldType(
            comptime field: ElementField,
        ) type {
            return meta.FieldType(T, field);
        }
    
        pool: [capacity]T = undefined,
        pool_status: [capacity]ElementStatus = [_]ElementStatus{.free} ** capacity,
        generations: [capacity]GenCount = [_]GenCount{0} ** capacity,
        allocations: AllocationSet = AllocationSet.initEmpty(),
        next_generation: GenCounter = .{},
    
        pub fn validateElementIdNotFree(
            self: Self,
            id: ElementId,
        ) !void {
            if (self.pool_status[id.index] == .free) {
                return ArrayAllocatorError.FreeElement;
            }
        }
        fn validateElementIdGeneration(
            self: Self,
            id: ElementId,
        ) !void {
            if (id.generation == 0 or self.generations[id.index] != id.generation) {
                return ArrayAllocatorError.GenerationMismatch;
            }
        }
        pub fn validateElementId(
            self: Self,
            id: ElementId,
        ) !void {
            try self.validateElementIdNotFree(id);
            try self.validateElementIdGeneration(id);
        }
        pub fn allocate(
            self: *Self,
        ) ArrayAllocatorError!ElementId {
            const id = try self.reserve();      // Allocation is just reservation followed
            try self.activate(id);              // immediately by activation.
            return id;
        }
        pub fn free(
            self: *Self,
            id: ElementId,
        ) !void {
            try self.validateElementIdGeneration(id);
            self.pool_status[id.index] = .free;
            self.generations[id.index] = 0;
            self.allocations.unset(id.index);
        }
        pub fn reserve(
            self: *Self,
        ) ArrayAllocatorError!ElementId {
            var element_iter = self.allocations.iterator(.{ .kind = .unset });
            while (element_iter.next()) |element_index| {
                if (self.pool_status[element_index] == .free) {                    // <1>
                    self.pool_status[element_index] = .reserved;
                    self.generations[element_index] = self.next_generation.counter;
                    self.next_generation.next();
        
                    return ElementId{
                        .index = @truncate(element_index),
                        .generation = self.generations[element_index],
                    };
                }
            }
            return ArrayAllocatorError.OutOfMemory;
        }
        pub fn activate(
            self: *Self,
            id: ElementId,
        ) ArrayAllocatorError!void {
            try self.validateElementId(id);
            self.pool_status[id.index] = .allocated;
            self.allocations.set(id.index);
        }
        pub fn create(
            self: *Self,
            value: T,
        ) ArrayAllocatorError!ElementId {
            const elem_id = try self.allocate();
            try self.update(elem_id, value);
            return elem_id;
        }
        pub fn populate(
            self: *Self,
            population: []const T,
        ) ArrayAllocatorError!AllocationSet {
            var pop_set = AllocationSet.initEmpty();
            for (population) |element| {
                const elem_id = try self.create(element);
                pop_set.set(elem_id.index);
            }
            return pop_set;
        }
        pub fn read(
            self: Self,
            id: ElementId,
        ) ArrayAllocatorError!T {
            try self.validateElementId(id);
            return self.pool[id.index];
        }
        pub fn readField(
            self: Self,
            id: ElementId,
            comptime field: ElementField,
        ) ArrayAllocatorError!ElementFieldType(field) {
            return @field(try self.read(id), elementFieldName(field));
        }
        pub fn update(
            self: *Self,
            id: ElementId,
            value: T,
        ) ArrayAllocatorError!void {
            try self.validateElementId(id);
            self.pool[id.index] = value;
        }
        pub fn updateField(
            self: *Self,
            id: ElementId,
            comptime field: ElementField,
            value: ElementFieldType(field),
        ) ArrayAllocatorError!void {
            try self.validateElementId(id);
            @field(self.pool[id.index], elementFieldName(field)) = value;
        }
        pub fn idFromRef(
            self: *const Self, // N.B. receive by pointer. We need addresses of internal fields.
            ref: *const T,
        ) ArrayAllocatorError!ElementId {
            // Since Zig does not yet (as of 0.11.0) support pointer differences,
            // we take over the pointer subtraction and the scaling
            // of the result. This code should change when pointer
            // subtraction is available.
            const base = @intFromPtr(&self.pool[0]);
            const end = @intFromPtr(&self.pool[capacity - 1]);
            const ref_at = @intFromPtr(ref);
        
            if (!(ref_at >= base and ref_at <= end)) {
                return ArrayAllocatorError.RefOutOfRange;
            }
        
            const index = (ref_at - base) / @sizeOf(T);
            if (self.pool_status[index] != .allocated) {
                return ArrayAllocatorError.UnallocatedElement;
            }
        
            return ElementId{
                .index = @truncate(index),
                .generation = self.generations[index],
            };
        }
        pub fn idFromIndex(
            self: Self,
            index: usize,
        ) ArrayAllocatorError!ElementId {
            if (self.pool_status[index] == .free) {
                return ArrayAllocatorError.FreeElement;
            }
        
            return ElementId{
                .index = @truncate(index),
                .generation = self.generations[index],
            };
        }
        pub fn refFromId(
            self: *Self,
            id: ElementId,
        ) ArrayAllocatorError!*T {
            try self.validateElementId(id);
            return &self.pool[id.index];
        }
        pub fn status(
            self: Self,
            id: ElementId,
        ) ElementStatus {
            return self.pool_status[id.index];
        }
        pub fn iterator(
            self: *const Self,
            set: AllocationSet,
        ) Iterator() {
            return .{
                .set_iterator = set.iterator(.{}),
                .allocator = self,
            };
        }
        fn Iterator() type {
            return struct {
                const IterSelf = @This();
        
                set_iterator: @TypeOf(@as(AllocationSet, undefined).iterator(.{})),
                allocator: *const Self,
        
                pub fn next(
                    self: *IterSelf,
                ) ?ElementId {
                    while (self.set_iterator.next()) |index| {
                        return self.allocator.idFromIndex(index) catch null ;
                    }
        
                    return null;
                }
            };
        }
        pub fn iteratorAll(
            self: *const Self,
        ) Iterator() {
            return self.iterator(self.allocations);
        }
    };
}
test "allocating" {
    const Info = struct {
        name: []const u8,
        age: u8,
    };

    const info_count: AllocCount = 10;
    const InfoAllocator = ArrayAllocator(Info, info_count);
    _ = testing.refAllDecls(InfoAllocator);

    var info_storage: InfoAllocator = .{};

    const inst_id = try info_storage.create(.{ .name = "Jane", .age = 45 });
    const jane_value = try info_storage.read(inst_id);
    try testing.expectEqualStrings(jane_value.name, "Jane");
    try testing.expectEqual(try info_storage.readField(inst_id, .age), 45);
    try info_storage.updateField(inst_id, .age, 42);
    try testing.expectEqual(try info_storage.readField(inst_id, .age), 42);
    try info_storage.free(inst_id);

    // Allocate every element of the array.
    for (0..info_count) |_| {
        _ = try info_storage.allocate();
    }
    // Further allocation attempts yield an error.
    try testing.expectError(ArrayAllocatorError.OutOfMemory,
            info_storage.allocate() catch |err| err);
}
test "iterating" {
    const ShiftSpec = struct {
        spec_name: []const u8,
        max_shift: u8,          // Hours
        min_break: u8,          // Minutes
    };

    const spec_count: AllocCount = 20;
    const init_count: AllocCount = 3;
    const ShiftSpecAllocator = ArrayAllocator(ShiftSpec, spec_count);

    const init_spec: [init_count]ShiftSpec = .{
        .{.spec_name = "Morning", .max_shift = 7, .min_break = 20,},
        .{.spec_name = "Afternoon", .max_shift = 8, .min_break = 15,},
        .{.spec_name = "Night", .max_shift = 6, .min_break = 30,},
    };

    var shift_spec: ShiftSpecAllocator = .{};
    const spec_set = try shift_spec.populate(&init_spec);
    try testing.expect(spec_set.count() == init_count);

    // Count the number of allocated elements.
    var alloc_elements: usize = 0;
    var spec_iter = shift_spec.iteratorAll();
    while (spec_iter.next()) |elem_id| {
        alloc_elements += 1;
        try testing.expect(shift_spec.status(elem_id) == .allocated);
    }
    try testing.expect(init_count == alloc_elements);

    spec_iter = shift_spec.iteratorAll();
    while (spec_iter.next()) |spec_id| {
        const spec_name = shift_spec.readField(spec_id, .spec_name);
        try testing.expect(!meta.eql(spec_name, "Graveyard"));
    }

    const new_spec_1_id = try shift_spec.create(.{
        .spec_name = "Graveyard",
        .max_shift = 4,
        .min_break = 30,
    });

    spec_iter = shift_spec.iteratorAll();
    var search_spec_id: ElementId = undefined;
    while (spec_iter.next()) |elem_id| {
        const spec_name = shift_spec.readField(elem_id, .spec_name);
        if (meta.eql(spec_name, "Graveyard")) {
            search_spec_id = elem_id;
            break;
        }
    }
    try testing.expectEqual(new_spec_1_id, search_spec_id);
}
