hashmap
Flat open-addressing hash map from Int keys to V, salted with splitmix64.
Generated from spec/std/hashmap.cp by cpl doc --format json.
FlatMap
pub struct FlatMap<V>Flat open-addressing hash map from Int keys to V, salted with splitmix64.
get, contains, set, remove, and get_or_insert are O(1) expected.
FlatMap.new
fn new(default_val: V, cap: Int = 16) -> FlatMap<V>[rename] Create an empty FlatMap<V> sized for at least cap entries (replaces with_capacity).
default_val fills the value slots that hold no entry; no method returns it, so any
value of V works. The table is a power of two at least twice cap, so cap entries
fit without a rehash; a cap below 1 gives the smallest table.
- cost: O(cap)
- traps: never
Examples:
var m: FlatMap<Int> = FlatMap(0); m.len == 0
FlatMap.len
fn len(self) -> IntNumber of live key-value pairs.
- cost: O(1)
- traps: never
Examples:
var m = FlatMap(0); m.set(1, 5); m.set(1, 6); m.len == 1
FlatMap.is_empty
fn is_empty(self) -> BoolWhether the map has no live entries.
- cost: O(1)
- traps: never
Examples:
FlatMap(0).is_empty == true
FlatMap.clear
fn clear(mut self)Remove all entries while keeping allocated capacity.
- cost: O(capacity)
- traps: never
Examples:
var m = FlatMap(0); m.set(1, 5); m.clear(); m.get(1) == None
FlatMap.slot
fn slot(self, k: Int) -> IntFlatMap.rehash
fn rehash(mut self, new_cap: Int)FlatMap.get
fn get(self, k: Int) -> ?VLook up k, returning None if absent.
- cost: O(1) expected
- traps: never
Examples:
var m = FlatMap(0); m.set(5, 50); m.get(5) == Some(50) and m.get(6) == None
FlatMap.contains
fn contains(self, k: Int) -> BoolWhether k is currently present.
- cost: O(1) expected
- traps: never
Examples:
var m = FlatMap(0); m.set(-3, 1); m.contains(-3) and not m.contains(3)
FlatMap.set
fn set(mut self, k: Int, v: V)Insert or overwrite k -> v.
When the table would pass half full it doubles and every entry is rehashed.
- cost: O(1) expected amortized
- traps: never
Examples:
var m = FlatMap(0); m.set(1, 5); m.set(1, 6); m.get(1) == Some(6)
FlatMap.get_or_insert
fn get_or_insert(mut self, k: Int, v: V) -> VReturn the value for k, inserting v first if k is absent.
A present k keeps its value; v is then ignored.
- cost: O(1) expected amortized
- traps: never
Examples:
var m = FlatMap(0); m.get_or_insert(4, 7) == 7 and m.get_or_insert(4, 9) == 7
FlatMap.remove
fn remove(mut self, k: Int) -> ?VRemove k if present; returns its old value or None.
- cost: O(1) expected
- traps: never
Examples:
var m = FlatMap(0); m.set(2, 9); m.remove(2) == Some(9) and m.remove(2) == None
FlatMap.reserve
fn reserve(mut self, cap: Int)Reserve space for at least cap entries without rehashing.
Entries are kept; a cap the table already fits does nothing.
- cost: O(cap) when the table grows, O(1) otherwise
- traps: never
Examples:
var m = FlatMap(0); m.set(1, 2); m.reserve(1000); m.get(1) == Some(2)
FlatMap.take
fn take(mut self) -> FlatMap<V>Move the map's contents out in O(1), leaving self empty.
- cost: O(1)
- traps: never
Examples:
var m = FlatMap(0); m.set(1, 2); let t = m.take(); m.is_empty and t.get(1) == Some(2)
FlatMap.items
fn items(self) -> yields (Int, V)O(1) to make. Yields every live (key, val) pair.
The order is the table's slot order, which depends on the per-map salt: it is fixed
while the map is unchanged and agrees with keys and values, but no program should
depend on it. Sort when the order matters.
- cost: O(1) to make, O(capacity) to walk
- empty: yields nothing
- order: unspecified slot order, the same as
keysandvalueswhile unchanged - traps: never
Examples:
var m = FlatMap(0); m.set(2, 20); m.set(1, 10); m.items.sorted() == [(1, 10), (2, 20)]
FlatMap.keys
fn keys(self) -> yields Int- cost: O(1) to make, O(capacity) to walk
- empty: yields nothing
- order: unspecified slot order, the same as
items - traps: never
Examples:
var m = FlatMap(0); m.set(2, 20); m.set(1, 10); m.keys.sorted() == [1, 2]
FlatMap.values
fn values(self) -> yields V- cost: O(1) to make, O(capacity) to walk
- empty: yields nothing
- order: unspecified slot order, the same as
items - traps: never
Examples:
var m = FlatMap(0); m.set(2, 20); m.set(1, 10); m.values.sorted() == [10, 20]
FlatMap.absorb
fn absorb(mut self, mut other: FlatMap<V>, join: ?((V, V) -> V) = None)Merge all entries from other into self (emptying other), combining collisions with join or overwriting.
For a key in both maps the result is join(self's value, other's value), or other's
value when join is None. The smaller map is drained into the larger, so the
argument order of join and the overwrite rule hold whichever side is moved.
- cost: O(min(|self|, |other|)) expected
- empty: an empty
otherleavesselfunchanged - traps: never
Examples:
var a = FlatMap(0); a.set(1, 10); var b = FlatMap(0); b.set(1, 5); b.set(2, 7); a.absorb(mut b, join: (x, y) => x + y); a.get(1) == Some(15) and a.get(2) == Some(7) and b.is_emptyvar a = FlatMap(0); a.set(1, 10); var b = FlatMap(0); b.set(1, 5); a.absorb(mut b); a.get(1) == Some(5)
Counter
pub struct Counter<K, V = Int>Default-valued frequency / weight map over hashable keys K. Counter<K> counts with Int
(V = Int) and is a Track<K> (std.window): push(k) adds 1, pop(k) takes 1 away.
c[k] reads init without inserting; add, get, set, remove, and contains are O(1) expected.
Invariant: no stored entry equals init. A write that leaves a key at init (add, set,
absorb) removes it, so len is the number of keys whose value differs from init and
contains(k) is get(k) != init.
Counter.new
fn new(init: V) -> Counter<K, V>Create an empty Counter<K, V> whose missing keys read as init.
- cost: O(1)
- traps: never
Examples:
var c: Counter<Char, Int> = Counter(0); c.get('z') == 0 and c.len == 0
Counter.of
fn of(xs: List<K>) -> Counter<K, Int>Count occurrences of each element in xs.
The result has init 0, so a key that never occurs reads 0.
- cost: O(n) expected
- empty: an empty counter
- traps: never
Examples:
let c = Counter.of(['a', 'b', 'a']); c.get('a') == 2 and c.get('c') == 0
Counter.len
fn len(self) -> IntNumber of keys with a stored entry.
- cost: O(1)
- traps: never
Examples:
Counter.of([3, 1, 3]).len == 2
Counter.is_empty
fn is_empty(self) -> BoolWhether no keys are stored.
- cost: O(1)
- traps: never
Examples:
Counter.of([1]).is_empty == false
Counter.get
fn get(self, k: K) -> VValue stored for k, or init if absent (does not insert).
c[k] calls this.
- cost: O(1) expected
- traps: never
Examples:
let c = Counter.of([5, 5]); c[5] == 2 and c[6] == 0 and c.len == 1
Counter.contains
fn contains(self, k: K) -> BoolWhether k currently has a stored entry.
- cost: O(1) expected
- traps: never
Examples:
let c = Counter.of([5]); c.contains(5) and not c.contains(6)
Counter.set
fn set(mut self, k: K, v: V)Set k to v (W8 IndexSet backing c[k] = v).
Setting a key to init removes it.
- cost: O(1) expected amortized
- traps: never
Examples:
var c = Counter.of(['a']); c['a'] = 4; c['a'] == 4var c = Counter.of(['a']); c['a'] = 0; c.contains('a') == false
Counter.add
fn add(mut self, k: K, delta: V)Add delta to k's value, removing k if the result equals init.
An absent key starts from init. c[k] += d is c.add(k, d).
- cost: O(1) expected amortized
- traps: never (overflow wraps in release, traps in debug)
Examples:
var c: Counter<Char, Int> = Counter(0); c.add('x', 2); c['x'] == 2var c: Counter<Char, Int> = Counter(0); c.add('x', 2); c.add('x', -2); c.len == 0
Counter.remove
fn remove(mut self, k: K) -> ?VRemove k and return its previous value, or None if absent.
- cost: O(1) expected
- traps: never
Examples:
var c = Counter.of(['a', 'a']); c.remove('a') == Some(2) and c.remove('a') == None
Counter.reserve
fn reserve(mut self, cap: Int)Reserve space for at least cap keys.
- cost: O(cap) when the table grows, O(1) otherwise
- traps: never
Examples:
var c = Counter.of([1]); c.reserve(100); c[1] == 1
Counter.clear
fn clear(mut self)Remove all entries.
- cost: O(n)
- traps: never
Examples:
var c = Counter.of([1, 2]); c.clear(); c.len == 0 and c[1] == 0
Counter.take
fn take(mut self) -> Counter<K, V>Move contents out in O(1), leaving self empty.
The init of self is unchanged.
- cost: O(1)
- traps: never
Examples:
var c = Counter.of([1]); let d = c.take(); c.is_empty and d[1] == 1
Counter.absorb
fn absorb(mut self, mut other: Counter<K, V>)Merge all entries from other into self by adding values (emptying other).
Stored values are added: a key stored in both ends at the sum of the two, a key stored in
one keeps that value, and a sum equal to init is removed. Absent keys contribute
nothing (not init), which keeps the result the same whichever side is drained.
- cost: O(min(|self|, |other|)) expected
- empty: an empty
otherleavesselfunchanged - traps: never (overflow wraps in release, traps in debug)
Examples:
var a = Counter.of(['x', 'y']); var b = Counter.of(['y', 'z']); a.absorb(mut b); a['y'] == 2 and a.len == 3 and b.len == 0
Counter.total
fn total(self) -> VSum of all stored values.
Only stored entries count; init is not added for absent keys.
- cost: O(n)
- empty:
V.zero - traps: never (overflow wraps in release, traps in debug)
Examples:
Counter.of([1, 1, 2]).total() == 3
Counter.most_common
fn most_common(self, k: Int) -> List<(K, V)>Top k entries sorted by descending value.
A k at least len returns every entry.
- cost: O(n log n)
- empty:
[] - ties: equal values in ascending key order
- order: descending value; a new
List, keyed from 0 - traps: when
k < 0
Examples:
Counter.of([3, 1, 3, 2, 1, 3]).most_common(2) == [(3, 3), (1, 2)]Counter.of(['b', 'a']).most_common(5) == [('a', 1), ('b', 1)]
Counter.items
fn items(self) -> yields (K, V)O(1) to make. Yields every stored (key, val) pair.
- cost: O(1) to make, O(1) per step
- empty: yields nothing
- order: unspecified hash order, the same as
keysandvalueswhile unchanged - traps: never
Examples:
Counter.of([2, 1, 2]).items.sorted() == [(1, 1), (2, 2)]
Counter.keys
fn keys(self) -> yields K- cost: O(1) to make, O(1) per step
- empty: yields nothing
- order: unspecified hash order, the same as
items - traps: never
Examples:
Counter.of([2, 1, 2]).keys.sorted() == [1, 2]
Counter.values
fn values(self) -> yields V- cost: O(1) to make, O(1) per step
- empty: yields nothing
- order: unspecified hash order, the same as
items - traps: never
Examples:
Counter.of([2, 1, 2]).values.sorted() == [1, 2]