Dict

Builtin.Dict(k, v) :: # (opaque)

parser_for : _

encoder_for : _

is_eq : Dict(k, v), Dict(k, v) -> Bool
    where [
        k.is_eq : k, k -> Bool,
        k.to_hash : k, Hasher -> Hasher,
        v.is_eq : v, v -> Bool,
    ]

Returns True if the two dictionaries contain the same key-value pairs, and False otherwise.

to_hash : Dict(k, v), Hasher -> Hasher
    where [
        k.to_hash : k, Hasher -> Hasher,
        v.to_hash : v, Hasher -> Hasher,
    ]

Feed a Dict into a Hasher. The hash is independent of insertion order.

empty : () -> Dict(_k, _v)

Returns an empty Dict.

empty_dict = Dict.empty()

with_capacity : U64 -> Dict(_k, _v)

Returns an empty Dict with room for at least the requested number of entries.

capacity : Dict(_k, _v) -> U64

Returns the number of entries the dictionary can hold before growing.

reserve : Dict(k, v), U64 -> Dict(k, v) where [k.to_hash : k, Hasher -> Hasher]

Ensure this dictionary has room for at least this many additional entries.

Like List.reserve, this aims for the exact size requested rather than rounding up, so call it once with the total number of entries you expect to add rather than repeatedly inside a loop.

release_excess_capacity : Dict(k, v) -> Dict(k, v) where [k.to_hash : k, Hasher -> Hasher]

Reduce unused dictionary capacity.

clear : Dict(k, v) -> Dict(k, v)

Remove every entry while preserving the current capacity.

single : k, v -> Dict(k, v) where [k.is_eq : k, k -> Bool, k.to_hash : k, Hasher -> Hasher]

Returns a Dict containing the key and value provided as input.

expect Dict.single("A", "B") == Dict.empty().insert("A", "B")

len : Dict(_k, _v) -> U64

Returns the number of key-value pairs in the dictionary.

expect Dict.empty()
           .insert("One", "A Song")
           .insert("Two", "Candy Canes")
           .insert("Three", "Boughs of Holly")
           .len() == 3

is_empty : Dict(_k, _v) -> Bool

Check if the dictionary is empty.

expect !Dict.empty().insert("key", 42).is_empty()

expect Dict.empty().is_empty()

get : Dict(k, v), k -> Try(v, [KeyNotFound, ..]) where [k.is_eq : k, k -> Bool, k.to_hash : k, Hasher -> Hasher]

Get the value for a given key. If there is a value for the specified key it will return Ok(value), otherwise return Err(KeyNotFound).

dictionary = Dict.empty()
                 .insert(1, "Apple")
                 .insert(2, "Orange")

expect dictionary.get(1) == Ok("Apple")
expect dictionary.get(2000) == Err(KeyNotFound)

subscript : Dict(k, v), k -> Try(v, [KeyNotFound, ..]) where [k.is_eq : k, k -> Bool, k.to_hash : k, Hasher -> Hasher]

Alias for Dict.get, enabling the future dict[key] subscript operator. Returns the value for a given key.

Returns Err KeyNotFound if the dictionary has no value for the key.

expect Dict.empty()
           .insert("Apples", 12.U64)
           .subscript("Apples") == Ok(12)

expect Dict.empty()
           .insert("Apples", 12.U64)
           .subscript("Oranges") == Err(KeyNotFound)

contains : Dict(k, _v), k -> Bool where [k.is_eq : k, k -> Bool, k.to_hash : k, Hasher -> Hasher]

Check if the dictionary has a value for a specified key.

expect Dict.empty().insert(1234, "5678").contains(1234)

insert : Dict(k, v), k, v -> Dict(k, v) where [k.is_eq : k, k -> Bool, k.to_hash : k, Hasher -> Hasher]

Insert a value into the dictionary at a specified key. If the key already exists, the existing value is replaced.

expect Dict.empty()
           .insert("Apples", 12)
           .get("Apples") == Ok(12)

remove : Dict(k, v), k -> Dict(k, v) where [k.is_eq : k, k -> Bool, k.to_hash : k, Hasher -> Hasher]

Remove a value from the dictionary for a specified key. Removal may change the iteration order of the remaining key-value pairs because the last pair can be moved into the removed pair's position.

expect Dict.empty()
           .insert("Some", "Value")
           .remove("Some")
           .len() == 0

to_list : Dict(k, v) -> List((k, v))

Returns the key-value pairs of a dictionary as a List.

expect Dict.single(1, "One")
           .insert(2, "Two")
           .to_list() == [(1, "One"), (2, "Two")]

iter : Dict(k, v) -> Iter((k, v))

Iterate over the dictionary's key-value pairs in their current internal order. This matches insertion order until an entry is removed; Dict.remove may reorder the remaining pairs.

expect Iter.fold(Dict.single(1, "One").insert(2, "Two").iter(), [], |acc, pair| acc.append(pair)) == [(1, "One"), (2, "Two")]

iter_rev : Dict(k, v) -> Iter((k, v))

Iterate over the dictionary's key-value pairs in reverse current internal order. This is reverse insertion order until an entry is removed; Dict.remove may reorder the remaining pairs. Like List.iter_rev, this reads the entries in place rather than building a reversed copy.

expect Iter.fold(Dict.single(1, "One").insert(2, "Two").iter_rev(), [], |acc, pair| acc.append(pair)) == [(2, "Two"), (1, "One")]

from_list : List((k, v)) -> Dict(k, v) where [k.is_eq : k, k -> Bool, k.to_hash : k, Hasher -> Hasher]

Create a Dict from a List of key-value pairs. If the list contains duplicate keys, later values overwrite earlier ones.

expect Dict.from_list([(1, "One"), (2, "Two")]) ==
	Dict.single(1, "One").insert(2, "Two")

from_iter : Iter((k, v)) -> Dict(k, v) where [k.is_eq : k, k -> Bool, k.to_hash : k, Hasher -> Hasher]

Create a Dict from an Iter of key-value pairs. If the iterator yields duplicate keys, later values overwrite earlier ones.

expect Dict.from_iter([(1, "One"), (2, "Two")].iter()) ==
	Dict.single(1, "One").insert(2, "Two")

keys : Dict(k, _v) -> List(k)

Returns the keys of a dictionary as a List.

expect Dict.single(1, "One")
           .insert(2, "Two")
           .keys() == [1, 2]

values : Dict(_k, v) -> List(v)

Returns the values of a dictionary as a List.

expect Dict.single(1, "One")
           .insert(2, "Two")
           .values() == ["One", "Two"]

fold : Dict(k, v), state, (state, k, v -> state) -> state

Build a value by folding through each key-value pair in the dictionary. Starting with a given state value, this runs the given step function on each pair, using its return value as the new state. It returns the final state at the end.

expect Dict.empty()
           .insert("Apples", 12.U64)
           .insert("Oranges", 24)
           .fold(0, |count, _key, qty| count + qty) == 36

fold_until : Dict(k, v), state, (state, k, v -> [Continue(state), Break(state)]) -> state

Same as Dict.fold, except you can stop folding early.

expect Dict.empty()
           .insert("Apples", 12.U64)
           .insert("Oranges", 24)
           .fold_until(0, |count, _key, qty| if count + qty >= 30 {
               Break(count + qty)
           } else {
               Continue(count + qty)
           }) == 36

keep_if : Dict(k, v), ((k, v) -> Bool) -> Dict(k, v) where [k.to_hash : k, Hasher -> Hasher]

Run the given function on each key-value pair of a dictionary, and return a dictionary with just the pairs for which the function returned Bool.True.

expect Dict.empty()
           .insert("Alice", 17.U64)
           .insert("Bob", 18)
           .insert("Charlie", 19)
           .keep_if(|(_k, v)| v >= 18)
           .len() == 2

drop_if : Dict(k, v), ((k, v) -> Bool) -> Dict(k, v) where [k.to_hash : k, Hasher -> Hasher]

Run the given function on each key-value pair of a dictionary, and return a dictionary with just the pairs for which the function returned Bool.False.

expect Dict.empty()
           .insert("Alice", 17.U64)
           .insert("Bob", 18)
           .insert("Charlie", 19)
           .drop_if(|(_k, v)| v >= 18)
           .len() == 1

map : Dict(k, a), (k, a -> b) -> Dict(k, b)

Convert each value in the dictionary to something new, by calling a conversion function on each of them which receives both the key and the old value. Then return a new dictionary containing the same keys and the converted values.

expect Dict.empty()
           .insert("a", 1.I64)
           .insert("b", 2)
           .map(|_k, v| v * 10)
           == Dict.empty()
                  .insert("a", 10)
                  .insert("b", 20)

join_map : Dict(a, b), (a, b -> Dict(x, y)) -> Dict(x, y) where [x.is_eq : x, x -> Bool, x.to_hash : x, Hasher -> Hasher]

Like Dict.map, except the transformation function returns a dictionary. At the end, all the dictionaries are joined together (using Dict.insert_all) into one dictionary.

You may know a similar function named concat_map in other languages.

insert_all : Dict(k, v), Dict(k, v) -> Dict(k, v) where [k.is_eq : k, k -> Bool, k.to_hash : k, Hasher -> Hasher]

Combine two dictionaries by keeping the union of all the key-value pairs. Where the same key is present in both dictionaries, the value from the second input is kept.

expect {
	first = Dict.single(1, "Not Me").insert(2, "And Me")
	second = Dict.single(1, "Keep Me").insert(3, "Me Too")
	expected = Dict.single(1, "Keep Me").insert(2, "And Me").insert(3, "Me Too")
	Dict.is_eq(Dict.insert_all(first, second), expected)
}

keep_shared : Dict(k, v), Dict(k, v) -> Dict(k, v)
    where [
        k.is_eq : k, k -> Bool,
        k.to_hash : k, Hasher -> Hasher,
        v.is_eq : v, v -> Bool,
    ]

Combine two dictionaries by keeping the intersection of all the key-value pairs. Only pairs where the key exists in both dictionaries and the values are equal are kept.

expect {
	first = Dict.single(1, "Keep Me").insert(2, "And Me").insert(3, "Not this one")
	second = Dict.single(1, "Keep Me").insert(2, "And Me").insert(3, "Different")
	expected = Dict.single(1, "Keep Me").insert(2, "And Me")

	Dict.is_eq(Dict.keep_shared(first, second), expected)
}

remove_all : Dict(k, v), Dict(k, _w) -> Dict(k, v) where [k.is_eq : k, k -> Bool, k.to_hash : k, Hasher -> Hasher]

Remove the key-value pairs in the first input whose keys are also in the second using the set difference.

expect {
	first = Dict.single(1, "Keep Me").insert(2, "And Me").insert(3, "Remove Me")
	second = Dict.single(3, "Remove Me").insert(4, "I do nothing...")
	expected = Dict.single(1, "Keep Me").insert(2, "And Me")

	Dict.is_eq(Dict.remove_all(first, second), expected)
}

update : Dict(k, v), k, (Try(v, [Missing]) -> Try(v, [Missing])) -> Dict(k, v) where [k.is_eq : k, k -> Bool, k.to_hash : k, Hasher -> Hasher]

Insert, update or remove a value for a specified key. This is more efficient than doing a Dict.get and then a Dict.insert call.

The provided function receives: - Ok(value) if the key is currently in the dictionary. - Err(Missing) if the key is not currently in the dictionary.

It should return: - Ok(new_value) to insert or update the value at the key. - Err(Missing) to remove the key (or leave it absent).

alter = |possible_value| match possible_value {
	Err(Missing) => Ok(Bool.False)
	Ok(value) => if value Err(Missing) else Ok(Bool.True)
}

expect Dict.is_eq(
	Dict.update(Dict.empty(), "a", alter),
	Dict.single("a", Bool.False),
)

DictBucket : { dist_and_fingerprint : U32, entry_index : U32 }

DictData : {
    entries : List((k, v)),
    buckets : List(DictBucket),
    max_entries_before_grow : U64,
    shifts : U8,
}

DictMetadata : {
    buckets : List(DictBucket),
    max_entries_before_grow : U64,
    shifts : U8,
}