//
// 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 math = std.math;
const meta = std.meta;
const hash = std.hash;
const mem = std.mem;
const assert = std.debug.assert;
const io = std.io;
const fmt = std.fmt;
pub const SequenceCount = u32;
pub const Loading = math.IntFittingRange(0, 100);
pub fn HashedArrayIndex(
    comptime T: type,
    comptime capacity: SequenceCount,
    comptime identifier: []const []const u8,
    comptime load_factor: Loading,
) type {
    if (@typeInfo(T) != .Struct)
        @compileError("index can only be created on a structure");

    if (identifier.len == 0)
        @compileError("no fields names supplied as an identifier");

    inline for (identifier) |id_field| {
        const id_trait = meta.trait.hasField(id_field);
        if (!id_trait(T)) @compileError("missing identifier field: " ++ id_field);
    }

    if (load_factor > 100)
        @compileError("load factor must be less than or equal to 100%");
    if (load_factor == 0)
        @compileError("load factor cannot be 0%");

    return struct {
        const Self = @This();

        const bucket_count = math.divCeil(SequenceCount, capacity * 100, load_factor)
            catch |err| @compileError("failed to calculate bucket count: " ++ @errorName(err));
        const Bucket = struct {
            sequence: SequenceCount = 0,
            value: ?*T = null,
        };
        buckets: [bucket_count]Bucket = [_]Bucket{.{}} ** bucket_count,
        occupied: SequenceCount = 0,
        const hash_function = struct {
            fn hash_identifier(
                value: *const T,
            ) u32 {
                var hasher = hash.Fnv1a_32.init();
                inline for (identifier) |id_field| {
                    hasher.update(mem.asBytes(&@field(value, id_field)));
                }
                return hasher.final();
            }
        }.hash_identifier;
        const compare_function = struct {
            fn compare_identifier(
                a: *const T,
                b: *const T,
            ) bool {
                inline for (identifier) |id_field| {
                    if (!meta.eql(@field(a, id_field), @field(b, id_field))) return false;
                }
                return true;
            }
        }.compare_identifier;
        const ProbeStatus = enum {
            empty,
            found,
            end,
        };
        const ProbeResult = struct {
            status: ProbeStatus,            // which status the probe found
            bucket_index: SequenceCount,    // the index of the bucket where probing stopped
            probe_count: SequenceCount,     // the number of probe attempts required to determine
                                            //      the status, equivalent to the number of key
        				    //      comparisons required
        };
        pub fn insert(
            self: *Self,
            value: *T,
        ) bool {
            if (self.occupied >= self.buckets.len) {
                return false;
            }
            
            var insert_value: *T = value;
            var probe_result = self.probe(null, 0, insert_value);
            
            while (true) {
                const bucket = &self.buckets[probe_result.bucket_index];
                switch (probe_result.status) {
                    .empty => {
                        bucket.sequence = probe_result.probe_count;
                        bucket.value = insert_value;
                        self.occupied += 1;
                        return true;
                    },
                    .found => return false,
                    .end => {
                        // The bucket is stolen by swapping out the value we are trying to insert
                        // for the one in the bucket.
                        const occupant_value = bucket.value.?;
                        bucket.value = insert_value;
                        insert_value = occupant_value;
            
                        // The steal is completed by swapping the bucket sequence count with the
                        // probe count.
                        const occupant_sequence = bucket.sequence;
                        bucket.sequence = probe_result.probe_count;
                            // +1 as we are moving the occupant to the next slot
                            //  from is initial placement
                        const next_probe = occupant_sequence + 1;
            
                        // Continue probing at the next bucket with the stolen value and
                        // probe count.
                        const next_bucket = Self.nextBucket(probe_result.bucket_index);
                        probe_result = self.probe(next_bucket, next_probe, insert_value);
                    },
                }
            }
        }
        pub fn search(
            self: Self,
            key: *const T,
        ) ?*T {
            const probe_result = self.probe(null, 0, key);
            return if (probe_result.status == .found) self.buckets[probe_result.bucket_index].value
                   else null;
        }
        pub fn remove(
            self: *Self,
            key: *const T,
        ) ?*T {
            const probe_result = self.probe(null, 0, key);
            
            var removed: ?*T = null;
            
            if (probe_result.status == .found) {
                var bucket_index = probe_result.bucket_index;
                removed = self.buckets[bucket_index].value;
                self.occupied -= 1;
            
                var done = false;
                while (!done) {
                    var bucket = &self.buckets[bucket_index];
                    var next_index = Self.nextBucket(bucket_index);
                    var next_bucket = &self.buckets[next_index];
            
                    if (next_bucket.value == null or next_bucket.sequence == 0) {
                        bucket.value = null;
                        bucket.sequence = 0;
                        done = true;
                    } else {
                        bucket.value = next_bucket.value;
                        bucket.sequence = next_bucket.sequence - 1;	// <1>
                    }
            
                    bucket_index = next_index;
                }
            }
            
            return removed;
        }
        pub fn stats(
            self: Self,
            stream: ?*io.StreamSource,
            optional_bin: ?[]SequenceCount,
        ) void {
            const writer = if (stream) |supplied_stream| supplied_stream.writer()
                            else blk: {
                                var err_stream = io.StreamSource{.file = io.getStdErr()};
                                break :blk err_stream.writer();
                            };
            
            fmt.format(writer, "total buckets: {d}\n", .{Self.bucket_count}) catch return;
            fmt.format(writer, "occupied buckets: {d}\n", .{self.occupied}) catch return;
            
            if (optional_bin) |bin| {
                assert(bin.len > 0);
                @memset(bin, 0);
            
                for (&self.buckets, 0..) |*bucket, b_index| {
                    fmt.format(writer, "{d}: seq: {d}, value: {any}\n",
                            .{b_index, bucket.sequence, bucket.value}) catch return;
                    if (bucket.value != null) {
                        const bin_index = @min(bucket.sequence, bin.len - 1);
                        bin[bin_index] += 1;
                    }
                }
                for (bin, 0..) |bin_value, bin_index| {
                    fmt.format(writer, "probes: {d}, frequency: {d}\n",
                            .{bin_index, bin_value}) catch return;
                }
            } else {
                for (&self.buckets, 0..) |*bucket, b_index| {
                    fmt.format(writer, "{d}: seq: {d}, value: {any}\n",
                            .{b_index, bucket.sequence, bucket.value}) catch return;
                }
            }
        }
        inline fn nextBucket(
            bucket_index: SequenceCount,
        ) SequenceCount {
            return (bucket_index +% 1) % bucket_count;
        }
        fn probe(
            self: Self,
            index_start: ?SequenceCount,
            probe_start: SequenceCount,
            key: *const T,
        ) ProbeResult {
            var result = ProbeResult{
                .status = undefined,
                .bucket_index = index_start orelse Self.hash_function(key) % bucket_count, // <1>
                .probe_count = probe_start,
            };
            
            if (index_start == null) {
                assert(probe_start == 0);
                result.probe_count = 0;
            }
            var bucket = &self.buckets[result.bucket_index];
            
            assert(result.probe_count < self.buckets.len);
            
            while (result.probe_count < self.buckets.len) {
                if (bucket.value == null) {
                    result.status = .empty;
                    break;
                } else if (compare_function(bucket.value.?, key)) {
                    result.status = .found;
                    break;
                } else if (result.probe_count > bucket.sequence) {
                    result.status = .end;
                    break;
                }
            
                // N.B. no else clause. Continue looking for one of the
                // three conditions that terminates the probe.
                result.probe_count += 1;
                result.bucket_index = Self.nextBucket(result.bucket_index);
                bucket = &self.buckets[result.bucket_index];
            }
            
            return result;
        }
    };
}
const testing = std.testing;
test "simple insertion" {
    const Person = struct {
        name: []const u8,
        age: u8,
        height: u18,            // in some unknown units
    };

    var people = [_]Person{
        .{.name = "Betty", .age = 42, .height = 27},
        .{.name = "John", .age = 37, .height = 29},
    };

    const people_id = [_][]const u8{
        "name",
    };

    const PersonIndex = HashedArrayIndex(Person, people.len, &people_id, 80);
    var people_index: PersonIndex = .{};

    var result = people_index.insert(&people[0]);
    try testing.expect(result);

    result = people_index.insert(&people[0]);
    try testing.expect(!result);

    result = people_index.insert(&people[1]);
    try testing.expect(result);
}
test "searching" {
    const Person = struct {
        name: []const u8,
        age: u8,		// in standard birthday terms
        height: u18,            // in some unknown units of length
    };

    var people = [_]Person{
        .{.name = "A", .age = 42, .height = 27},
        .{.name = "B", .age = 37, .height = 29},
        .{.name = "C", .age = 47, .height = 30},
        .{.name = "D", .age = 32, .height = 31},
        .{.name = "E", .age = 67, .height = 32},
        .{.name = "F", .age = 31, .height = 25},
        .{.name = "G", .age = 33, .height = 26},
    };

    const people_id = [_][]const u8{
        "name",
    };

    const PersonIndex = HashedArrayIndex(Person, people.len, &people_id, 100);
    var people_index: PersonIndex = .{};

    for (&people) |*a_person| {
        var result = people_index.insert(a_person);
        try testing.expect(result);
    }

    people_index.stats(null, null);

    for (&people, 0..) |*a_person, p_index| {
        var result = people_index.search(a_person);
        try testing.expect(result != null);
        try testing.expect(mem.eql(u8, a_person.name, people[p_index].name));
    }

    const Part = struct {
        num: u16,
        sub_num: u16,
        name: []const u8,
    };
    var parts = [_]Part{
        .{.num = 1, .sub_num = 1, .name = "A"},
        .{.num = 1, .sub_num = 2, .name = "B"},
        .{.num = 1, .sub_num = 3, .name = "C"},
        .{.num = 1, .sub_num = 4, .name = "D"},
        .{.num = 2, .sub_num = 1, .name = "E"},
        .{.num = 2, .sub_num = 2, .name = "F"},
        .{.num = 2, .sub_num = 3, .name = "G"},
        .{.num = 2, .sub_num = 4, .name = "H"},
    };

    const part_id = [_][]const u8{
        "num", "sub_num",
    };
    const PartIndex = HashedArrayIndex(Part, parts.len, &part_id, 90);
    var part_index: PartIndex = .{};

    for (&parts) |*a_part| {
        var result = part_index.insert(a_part);
        try testing.expect(result);
    }
    var bin: [5]SequenceCount = undefined;
    part_index.stats(null, &bin);

    for (&parts, 0..) |*a_part, p_index| {
        var result = part_index.search(a_part);
        try testing.expect(result != null);
        try testing.expect(a_part.num == parts[p_index].num);
        try testing.expect(a_part.sub_num == parts[p_index].sub_num);
    }
}
test "removal" {
    const Part = struct {
        num: u16,
        sub_num: u16,
        name: []const u8,
    };
    var parts = [_]Part{
        .{.num = 1, .sub_num = 5, .name = "A"},
        .{.num = 1, .sub_num = 6, .name = "B"},
        .{.num = 1, .sub_num = 7, .name = "C"},
        .{.num = 1, .sub_num = 8, .name = "D"},
        .{.num = 2, .sub_num = 9, .name = "E"},
        .{.num = 2, .sub_num = 10, .name = "F"},
        .{.num = 2, .sub_num = 11, .name = "G"},
        .{.num = 2, .sub_num = 12, .name = "H"},
    };

    const part_id = [_][]const u8{
        "num", "sub_num",
    };
    const PartIndex = HashedArrayIndex(Part, parts.len, &part_id, 80);
    var part_index: PartIndex = .{};

    for (&parts) |*a_part| {
        var result = part_index.insert(a_part);
        try testing.expect(result);
    }

    var bin: [5]SequenceCount = undefined;
    part_index.stats(null, &bin);

    for (&parts, 0..) |*a_part, p_index| {
        var result = part_index.search(a_part);
        try testing.expect(result != null);
        try testing.expect(a_part.num == parts[p_index].num);
        try testing.expect(a_part.sub_num == parts[p_index].sub_num);
    }

    for (&parts, 0..) |*a_part, p_index| {
        var removed = part_index.remove(a_part);
        try testing.expect(removed != null);
        var removed_part = removed.?;
        try testing.expect(removed_part.num == parts[p_index].num);
        try testing.expect(removed_part.sub_num == parts[p_index].sub_num);
    }

    part_index.stats(null, null);
}
