class Map<+K: Hashable & Equality, +V>

A mutable, growable collection of key => value associations with O(1) key lookup/update and amortized O(1) insertion of new keys. Iteration order corresponds to the order in which keys were first added to the Map (ie updating the value of an existing key does not affect iteration order).

Notes

This uses a "Robin Hood hashing" open-addressed linear-probed hash table. Each slot knows its own hash, where its slot index comes from the high bits, which makes Robin Hood distance comparisons trivial -- just subtract. Empty slots use a hash value that looks like a "perfect" (distance 0) fit from the Robin Hood perspective, which makes them look like good candidates for "displacing" without an additional check in the inner loop.

TODO

• Make generation_PRIVATE private to the module (once that is supported in the language).
• Either use a different scheme for invalidating iterators in order to allow more than 2**32 entries, or exploit this size limit and use UInt32 for sz, used, and shift ( and possibly store just the high 32 bits of the hash after finalization).

Static Methods

Creating a Map

static fun sourcemcreate(capacity: Int): mutable this

Creates a new hash table. If specified, "size" is how many values can be added to the hash table without rehashing.

static fun sourcecreateFromItems<I: readonly Sequence<(K, V)>>(items: I): this

static fun sourcemcreateFromItems<I: readonly Sequence<(K, V)>>(items: I): mutable this

static fun sourcecreateFromIterator<I: mutable Iterator<(K, V)>>(iterator: I): this

static fun sourcemcreateFromIterator<I: mutable Iterator<(K, V)>>(iterator: I): mutable this

Methods

readonly fun sourceclone(reserveCapacity: Int): mutable this

Creates a mutable, minimally-sized clone of this table. The optional 'reserveCapacity' parameter is the number of additional values that can be added after cloning without forcing a rehash.

readonly fun sourcechill(): this

Sizing

readonly fun sourcesize(): Int

mutable fun sourcecapacity(): Int

NOTE: Making capacity observable on frozen values prevents optimizations such as shrinking to fit on freeze. By making it mutable we preserve option value to add such optimizations in the future.

readonly fun sourceisEmpty(): Bool

mutable fun sourceensureCapacity(capacity: Int): Void

mutable fun sourceclear(): Void

Accessing Items

readonly fun sourceget<K2: Hashable & Equality>(k: K2): V

readonly fun sourcemaybeGet<K2: Hashable & Equality>(k: K2): Option<V>

readonly fun sourcegetItem<K2: Hashable & Equality>(k: K2): (K, V)

Like get(), but returns both the key and the value.

readonly fun sourcemaybeGetItem<K2: Hashable & Equality>(k: K2): Option<(K, V)>

Like maybeGet(), but returns both the key and the value.

readonly fun sourcefirstItem(): (K, V)

Get the first item in the Map, throws if the container is empty.

readonly fun sourcemaybeFirstItem(): Option<(K, V)>

Get the first item in the Map as Some() if non-empty, or None() if empty.

readonly fun sourcelastItem(): (K, V)

Get the last item in the Map, throws if the container is empty.

readonly fun sourcemaybeLastItem(): Option<(K, V)>

Get the last item in the Map as Some() if non-empty, or None() if empty.

mutable fun sourcegetOrAdd(k: K, f: () -> V): V

If k exists in this map, returns its value. Else, runs f() to get a new value, inserts it, and returns that new value.

readonly fun sourcecontainsKey<K2: Hashable & Equality>(k: K2): Bool

Returns true if the Map has a value associated with the given key, else false.

Modifying Items

mutable fun sourceset(k: K, v: V): Void

Associate key with value in this Map:

• If the key already exists in this Map, associates it to the new value.
• Else add the key/value association.

mutable fun sourceadd(k: K, v: V): Void

Like mset(), but throws a Duplicate() exception if the key already exists.

mutable fun sourcemaybeSet(k: K, v: V): Bool

If the key does not already exist, inserts it and returns true. Else returns false.

mutable fun sourceextend(second: readonly KeyedSequence<K, V>): Void

Adds all of the key/value associations from the second Map to this one, replacing values for keys already present and adding key/value associations for keys not yet in this Map.

mutable fun sourcemaybeRemove(k: K): Bool

Remove the given key from this Map:

• If the key is present remove it and return true.
• Otherwise do nothing and return false.

mutable fun sourceremove(k: K): Void

Remove the key from this Map if present, otherwise throw.

Iteration

readonly fun sourceeach(f: (K, V) -> Void): Void

Aggregation

readonly fun sourcefind(p: (K, V) -> Bool): Option<V>

readonly fun sourcefindItem(p: (K, V) -> Bool): Option<(K, V)>

Composition

readonly fun sourcemap<V2>(f: (K, V) -> V2): Map<K, V2>

readonly fun sourcemapItems<K2: Hashable & Equality, V2>(s: (K, V) -> (K2, V2)): Map<K2, V2>

readonly fun sourcefilter(p: (K, V) -> Bool): Map<K, V>

readonly fun sourcefilterNone<U>(): Map<K, U>

Async

fun sourcegen<V2: frozen>(): ^Map<K, V2>

fun sourcegenMap<V2: frozen>(s: (K, V) ~> ^V2): ^Map<K, V2>

fun sourcegenFilter<V2>(p: (K, V) ~> ^Bool): ^Map<K, V>

Trait Implementations

readonly fun sourcetoString(): String

readonly fun sourceinspect(): Inspect

readonly fun sourceinspectInternal(): Inspect

For use when developing Map

readonly fun source==<K2: Hashable & Equality, V2: Equality>(other: readonly Map<K2, V2>): Bool

readonly fun source!=<K2: Hashable & Equality, V2: Equality>(other: readonly Map<K2, V2>): Bool

readonly fun sourcehash(): Int

Iterators

readonly fun sourcekeys(): mutable Map.MapKeysIterator<K, V>

readonly fun sourcevalues(): mutable Map.MapValuesIterator<K, V>

readonly fun sourceitems(): mutable Map.MapItemsIterator<K, V>

readonly fun sourceeachWhileImpl(f: (Map.MapEntry<K, V>) -> Bool): Void

Internal helper for iteration guarding against concurrent modifiction.

Inherited Methods

static fun sourcemeta<Tk: Hashable & Equality, Ck: MetaClass<Tk>, Tv, Cv: MetaClass<Tv>>(keyClass: Ck, valueClass: Cv): MapMetaClass<Tk, Ck, Tv, Cv>

static fun sourcegenerator<K2: Hashable & Equality, V2>(keyGenerator: QuickCheck.Generator<K2>, valueGenerator: QuickCheck.Generator<V2>): QuickCheck.Generator<Map<K2, V2>>

fun sourceperturb(rng: mutable Random): Void

fun sourceshrink(_firstShrink: Bool): mutable Iterator<Map<K, V>>