tiny.preserves.containers

1//! A hash map and a hash set keyed by the package's values. A lookup has to find a key whenever the2//! key it is given is an equal value, including a set or dictionary that stores its items in3//! another order. Two equal sets can store their items in different orders, and so can two equal4//! dictionaries. A hash over the stored order would put such equal keys in different buckets.5//!6//! `ValueContext` gives the standard hash map the value's own hash and equality, which ignore the7//! order in which a set or dictionary stores its items. `ValueHashMap` and `ValueSet` are the8//! standard unmanaged hash map with that context, so every call that allocates takes the allocator9//! as an argument. The map stores each key and value as given and frees only its own table, so the10//! caller keeps every value's memory alive while it sits in the map.11const std = @import("std");12const value_mod = @import("value.zig");1314/// Returns the hashing context for `Value(D)` that the standard hash map expects. `ValueHashMap`15/// and `ValueSet` pass it to Zig's standard hash map, so the map finds keys by value equality. The16/// context holds no state, so every instance behaves the same.17pub fn ValueContext(comptime D: type) type {18    return struct {19        /// Returns the hash of `v`, the same number `v.hash()` returns. Equal values get equal20        /// hashes, whatever order a set or dictionary stores its items in.21        pub fn hash(_: @This(), v: value_mod.Value(D)) u64 {22            return v.hash();23        }2425        /// Returns true when `a` and `b` are equal values, the same answer `a.eql(b)` gives.26        pub fn eql(_: @This(), a: value_mod.Value(D), b: value_mod.Value(D)) bool {27            return a.eql(b);28        }29    };30}3132/// Returns the standard unmanaged hash map type from `Value(D)` keys to `Value(D)` values, keyed33/// through `ValueContext(D)`. Code that maps one Preserves value to another declares one, for34/// lookups by value equality. The map grows once it is 80 percent full. A lookup with a set key35/// finds an entry stored under an equal set in another order, and the same holds for dictionaries.36/// The map copies no value memory, and `deinit` frees only the map's table.37pub fn ValueHashMap(comptime D: type) type {38    return std.HashMapUnmanaged(value_mod.Value(D), value_mod.Value(D), ValueContext(D), 80);39}4041/// Returns the standard unmanaged hash map type with `Value(D)` keys and `void` values, keyed42/// through `ValueContext(D)`. Code that tracks which values it has seen declares one of these. The43/// set grows once it is 80 percent full. Adding an equal value a second time leaves the count44/// unchanged. The set copies no value memory, and `deinit` frees only its table.45pub fn ValueSet(comptime D: type) type {46    return std.HashMapUnmanaged(value_mod.Value(D), void, ValueContext(D), 80);47}4849/// Returns true when `a` and `b` are equal values, the same answer `a.eql(b)` gives. Generic code50/// that passes equality as a function value calls it, for the method's answer in function form. The51/// package root's `valueEqual` is a separate function with the same answer for values whose52/// embedded values hold any pointer.53pub fn valueEqual(comptime D: type, a: value_mod.Value(D), b: value_mod.Value(D)) bool {54    return a.eql(b);55}5657test "ValueHashMap stores and looks up by value" {58    const NoEmbedded = @import("domain.zig").NoEmbedded;59    const V = value_mod.Value(NoEmbedded);60    const Map = ValueHashMap(NoEmbedded);6162    const allocator = std.testing.allocator;63    var map: Map = .{};64    defer map.deinit(allocator);6566    const k1 = V.initI128(1);67    const k2 = V.initI128(2);68    const v1 = V.initBoolean(true);69    const v2 = V.initBoolean(false);7071    try map.put(allocator, k1, v1);72    try map.put(allocator, k2, v2);73    try std.testing.expectEqual(@as(usize, 2), map.count());7475    const got1 = map.get(V.initI128(1)).?;76    try std.testing.expect(got1.eql(v1));77    const got2 = map.get(V.initI128(2)).?;78    try std.testing.expect(got2.eql(v2));79    try std.testing.expect(map.get(V.initI128(99)) == null);80}8182test "ValueHashMap finds permutation-equivalent unordered keys" {83    const NoEmbedded = @import("domain.zig").NoEmbedded;84    const V = value_mod.Value(NoEmbedded);85    const Map = ValueHashMap(NoEmbedded);8687    const allocator = std.testing.allocator;88    var map: Map = .{};89    defer map.deinit(allocator);9091    var set_items_a = [_]V{ V.initI128(1), V.initI128(2) };92    var set_items_b = [_]V{ V.initI128(2), V.initI128(1) };93    const set_a = V.initSet(&set_items_a);94    const set_b = V.initSet(&set_items_b);95    try std.testing.expect(set_a.eql(set_b));96    try std.testing.expectEqual(std.math.Order.eq, set_a.compare(set_b));97    try std.testing.expectEqual(set_a.hash(), set_b.hash());98    try map.put(allocator, set_a, V.initBoolean(true));99    try std.testing.expect(map.get(set_b) != null);100101    var entries_a = [_]V.DictionaryEntry{102        .{ .key = V.initI128(1), .value = V.initBoolean(true) },103        .{ .key = V.initI128(2), .value = V.initBoolean(false) },104    };105    var entries_b = [_]V.DictionaryEntry{106        .{ .key = V.initI128(2), .value = V.initBoolean(false) },107        .{ .key = V.initI128(1), .value = V.initBoolean(true) },108    };109    const dictionary_a = V.initDictionary(&entries_a);110    const dictionary_b = V.initDictionary(&entries_b);111    try std.testing.expect(dictionary_a.eql(dictionary_b));112    try std.testing.expectEqual(std.math.Order.eq, dictionary_a.compare(dictionary_b));113    try std.testing.expectEqual(dictionary_a.hash(), dictionary_b.hash());114    try map.put(allocator, dictionary_a, V.initBoolean(false));115    try std.testing.expect(map.get(dictionary_b) != null);116}117118test "ValueSet tracks presence" {119    const NoEmbedded = @import("domain.zig").NoEmbedded;120    const V = value_mod.Value(NoEmbedded);121    const Set = ValueSet(NoEmbedded);122123    const allocator = std.testing.allocator;124    var set: Set = .{};125    defer set.deinit(allocator);126127    try set.put(allocator, V.initI128(1), {});128    try set.put(allocator, V.initI128(2), {});129    try set.put(allocator, V.initI128(1), {});130    try std.testing.expectEqual(@as(usize, 2), set.count());131    try std.testing.expect(set.contains(V.initI128(1)));132    try std.testing.expect(!set.contains(V.initI128(7)));133}134135test "valueEqual freestanding wrapper matches method form" {136    const NoEmbedded = @import("domain.zig").NoEmbedded;137    const V = value_mod.Value(NoEmbedded);138    try std.testing.expect(valueEqual(NoEmbedded, V.initI128(1), V.initI128(1)));139    try std.testing.expect(!valueEqual(NoEmbedded, V.initI128(1), V.initI128(2)));140}

1pub const containers = @import("containers.zig");