primitive _MapEmpty
primitive _MapDeleted
type Map[K: (Hashable #read & Equatable[K] #read), V] is
HashMap[K, V, HashEq[K]]
"""
This is a map that uses structural equality on the key.
"""
type MapIs[K, V] is HashMap[K, V, HashIs[K]]
"""
This is a map that uses identity comparison on the key.
"""
class HashMap[K, V, H: HashFunction[K] val]
"""
A quadratic probing hash map. Resize occurs at a load factor of 0.75. A
resized map has 2 times the space. The hash function can be plugged in to the
type to create different kinds of maps.
"""
var _size: USize = 0
var _array: Array[((K, V) | _MapEmpty | _MapDeleted)]
new create(prealloc: USize = 6) =>
"""
Create an array with space for prealloc elements without triggering a
resize. Defaults to 6.
"""
let len = (prealloc * 4) / 3
let n = len.max(8).next_pow2()
_array = _array.init(_MapEmpty, n)
fun size(): USize =>
"""
The number of items in the map.
"""
_size
fun space(): USize =>
"""
The available space in the map. Resize will happen when
size / space >= 0.75.
"""
_array.space()
fun apply(key: box->K!): this->V ? =>
"""
Gets a value from the map. Raises an error if no such item exists.
"""
(let i, let found) = _search(key)
if found then
_array(i)? as (_, this->V)
else
error
end
fun ref update(key: K, value: V): (V^ | None) =>
"""
Sets a value in the map. Returns the old value if there was one, otherwise
returns None. If there was no previous value, this may trigger a resize.
"""
try
(let i, let found) = _search(key)
match _array(i)? = (consume key, consume value)
| (_, let v: V) =>
return consume v
else
_size = _size + 1
if (_size * 4) > (_array.size() * 3) then
_resize(_array.size() * 2)
end
end
end
fun ref upsert(key: K, value: V, f: {(V, V): V^} box): V! =>
"""
Combines a provided value with the current value for the provided key
using the provided function. If the provided key has not been added to
the map yet, it sets its value to the provided value and ignores the
provided function.
As a simple example, say we had a map with I64 values and we wanted to
add 4 to the current value for key "test", which let's say is currently 2.
We call
m.upsert("test", 4, {(current, provided) => current + provided })
This changes the value associated with "test" to 6.
If we have not yet added the key "new-key" to the map and we call
m.upsert("new-key", 4, {(current, provided) => current + provided })
then "new-key" is added to the map with a value of 4.
Returns the value that we set the key to
"""
(let i, let found) = _search(key)
let value' = value
try
if found then
(let pkey, let pvalue) = (_array(i)? = _MapEmpty) as (K^, V^)
let new_value = f(consume pvalue, consume value)
let new_value' = new_value
_array(i)? = (consume pkey, consume new_value)
return _array(i)? as (_, V)
else
let key' = key
_array(i)? = (consume key, consume value)
_size = _size + 1
if (_size * 4) > (_array.size() * 3) then
_resize(_array.size() * 2)
end
end
value'
else
// This is unreachable, since index will never be out-of-bounds
value'
end
fun ref insert(key: K, value: V): V! =>
"""
Set a value in the map. Returns the new value, allowing reuse.
"""
let value' = value
try
(let i, let found) = _search(key)
let key' = key
_array(i)? = (consume key, consume value)
if not found then
_size = _size + 1
if (_size * 4) > (_array.size() * 3) then
_resize(_array.size() * 2)
end
end
value'
else
// This is unreachable, since index will never be out-of-bounds.
value'
end
fun ref insert_if_absent(key: K, value: V): V! =>
"""
Set a value in the map if the key doesn't already exist in the Map.
Saves an extra lookup when doing a pattern like:
```pony
if not my_map.contains(my_key) then
my_map(my_key) = my_value
end
```
Returns the value, the same as `insert`, allowing 'insert_if_absent'
to be used as a drop-in replacement for `insert`.
"""
let value' = value
try
(let i, let found) = _search(key)
let key' = key
if not found then
_array(i)? = (consume key, consume value)
_size = _size + 1
if (_size * 4) > (_array.size() * 3) then
_resize(_array.size() * 2)
end
end
_array(i)? as (_, V)
else
// This is unreachable, since index will never be out-of-bounds.
value'
end
fun ref remove(key: box->K!): (K^, V^) ? =>
"""
Delete a value from the map and return it. Raises an error if there was no
value for the given key.
"""
try
(let i, let found) = _search(key)
if found then
_size = _size - 1
match _array(i)? = _MapDeleted
| (let k: K, let v: V) =>
return (consume k, consume v)
end
end
end
error
fun get_or_else(key: box->K!, alt: this->V): this->V =>
"""
Get the value associated with provided key if present. Otherwise,
return the provided alternate value.
"""
(let i, let found) = _search(key)
if found then
try
_array(i)? as (_, this->V)
else
// This should never happen as we have already
// proven that _array(i) exists
consume alt
end
else
consume alt
end
fun contains(k: box->K!): Bool =>
"""
Checks whether the map contains the key k
"""
(_, let found) = _search(k)
found
fun ref concat(iter: Iterator[(K^, V^)]) =>
"""
Add K, V pairs from the iterator to the map.
"""
for (k, v) in iter do
this(consume k) = consume v
end
fun add[H2: HashFunction[this->K!] val = H](
key: this->K!,
value: this->V!)
: HashMap[this->K!, this->V!, H2]^
=>
"""
This with the new (key, value) mapping.
"""
let r = clone[H2]()
r(key) = value
r
fun sub[H2: HashFunction[this->K!] val = H](key: this->K!)
: HashMap[this->K!, this->V!, H2]^
=>
"""
This without the given key.
"""
let r = clone[H2]()
try r.remove(key)? end
r
fun next_index(prev: USize = -1): USize ? =>
"""
Given an index, return the next index that has a populated key and value.
Raise an error if there is no next populated index.
"""
for i in Range(prev + 1, _array.size()) do
match _array(i)?
| (_, _) => return i
end
end
error
fun index(i: USize): (this->K, this->V) ? =>
"""
Returns the key and value at a given index.
Raise an error if the index is not populated.
"""
_array(i)? as (this->K, this->V)
fun ref compact() =>
"""
Minimise the memory used for the map.
"""
_resize(((_size * 4) / 3).next_pow2().max(8))
fun clone[H2: HashFunction[this->K!] val = H]()
: HashMap[this->K!, this->V!, H2]^
=>
"""
Create a clone. The key and value types may be different due to aliasing
and viewpoint adaptation.
"""
let r = HashMap[this->K!, this->V!, H2](_size)
for (k, v) in pairs() do
r(k) = v
end
r
fun ref clear() =>
"""
Remove all entries.
"""
_size = 0
// Our default prealloc of 6 corresponds to an array alloc size of 8.
let n: USize = 8
_array = _array.init(_MapEmpty, n)
fun _search(key: box->K!): (USize, Bool) =>
"""
Return a slot number and whether or not it's currently occupied.
"""
var idx_del = _array.size()
let mask = idx_del - 1
let h = H.hash(key).usize()
var idx = h and mask
try
for i in Range(0, _array.size()) do
let entry = _array(idx)?
match entry
| (let k: this->K!, _) =>
if H.eq(k, key) then
return (idx, true)
end
| _MapEmpty =>
if idx_del <= mask then
return (idx_del, false)
else
return (idx, false)
end
| _MapDeleted =>
if idx_del > mask then
idx_del = idx
end
end
idx = (h + ((i + (i * i)) / 2)) and mask
end
end
(idx_del, false)
fun ref _resize(len: USize) =>
"""
Change the available space.
"""
let old = _array
let old_len = old.size()
_array = _array.init(_MapEmpty, len)
_size = 0
try
for i in Range(0, old_len) do
match old(i)? = _MapDeleted
| (let k: K, let v: V) =>
this(consume k) = consume v
end
end
end
fun keys(): MapKeys[K, V, H, this->HashMap[K, V, H]]^ =>
"""
Return an iterator over the keys.
"""
MapKeys[K, V, H, this->HashMap[K, V, H]](this)
fun values(): MapValues[K, V, H, this->HashMap[K, V, H]]^ =>
"""
Return an iterator over the values.
"""
MapValues[K, V, H, this->HashMap[K, V, H]](this)
fun pairs(): MapPairs[K, V, H, this->HashMap[K, V, H]]^ =>
"""
Return an iterator over the keys and values.
"""
MapPairs[K, V, H, this->HashMap[K, V, H]](this)
class MapKeys[K, V, H: HashFunction[K] val, M: HashMap[K, V, H] #read] is
Iterator[M->K]
"""
An iterator over the keys in a map.
"""
let _map: M
var _i: USize = -1
var _count: USize = 0
new create(map: M) =>
"""
Creates an iterator for the given map.
"""
_map = map
fun has_next(): Bool =>
"""
True if it believes there are remaining entries. May not be right if values
were added or removed from the map.
"""
_count < _map.size()
fun ref next(): M->K ? =>
"""
Returns the next key, or raises an error if there isn't one. If keys are
added during iteration, this may not return all keys.
"""
_i = _map.next_index(_i)?
_count = _count + 1
_map.index(_i)?._1
class MapValues[K, V, H: HashFunction[K] val, M: HashMap[K, V, H] #read] is
Iterator[M->V]
"""
An iterator over the values in a map.
"""
let _map: M
var _i: USize = -1
var _count: USize = 0
new create(map: M) =>
"""
Creates an iterator for the given map.
"""
_map = map
fun has_next(): Bool =>
"""
True if it believes there are remaining entries. May not be right if values
were added or removed from the map.
"""
_count < _map.size()
fun ref next(): M->V ? =>
"""
Returns the next value, or raises an error if there isn't one. If values
are added during iteration, this may not return all values.
"""
_i = _map.next_index(_i)?
_count = _count + 1
_map.index(_i)?._2
class MapPairs[K, V, H: HashFunction[K] val, M: HashMap[K, V, H] #read] is
Iterator[(M->K, M->V)]
"""
An iterator over the keys and values in a map.
"""
let _map: M
var _i: USize = -1
var _count: USize = 0
new create(map: M) =>
"""
Creates an iterator for the given map.
"""
_map = map
fun has_next(): Bool =>
"""
True if it believes there are remaining entries. May not be right if values
were added or removed from the map.
"""
_count < _map.size()
fun ref next(): (M->K, M->V) ? =>
"""
Returns the next entry, or raises an error if there isn't one. If entries
are added during iteration, this may not return all entries.
"""
_i = _map.next_index(_i)?
_count = _count + 1
_map.index(_i)?