#Immutable VectorMap
A persistent map that iterates in insertion order — the immutable counterpart of the built-in insertion-ordered Map. Updates return a map and never disturb the receiver: a new one when anything changed, and the receiver itself for a handful of no-ops spelled out below.
Reach for it over @immut/hashmap when the order in which entries were added is part of what you are storing: rendering a list, replaying a log, or anything whose output a reader would notice being shuffled. Reach for @immut/sorted_map instead when you want entries in key order, and for @immut/hashmap when order does not matter at all — it is the leaner structure.
#Create
///|
test "create" {
let empty : @vector_map.VectorMap[String, Int] = @vector_map.new()
inspect(empty.is_empty(), content="true")
let one = @vector_map.singleton("a", 1)
inspect(one.length(), content="1")
// The array keeps its order — this is not sorted by key.
let m = @vector_map.VectorMap([("c", 3), ("a", 1), ("b", 2)])
debug_inspect(
m.keys().to_array(),
content=(
#|["c", "a", "b"]
),
)
}#Order
A key already in the map keeps its position when its value is replaced; a key that is new goes to the end. Removing a key and adding it back therefore moves it.
///|
test "order" {
let m = @vector_map.VectorMap([("a", 1), ("b", 2), ("c", 3)])
// replacing in place: "a" stays first
debug_inspect(
m.add("a", 10).keys().to_array(),
content=(
#|["a", "b", "c"]
),
)
// a fresh key is appended
debug_inspect(
m.add("d", 4).keys().to_array(),
content=(
#|["a", "b", "c", "d"]
),
)
// remove-then-add moves it to the end
debug_inspect(
m.remove("a").add("a", 1).keys().to_array(),
content=(
#|["b", "c", "a"]
),
)
}#Add, get, remove
///|
test "add_get_remove" {
let m = @vector_map.new().add("a", 1).add("b", 2)
debug_inspect(m.get("a"), content="Some(1)")
inspect(m["b"], content="2")
inspect(m.contains("z"), content="false")
let smaller = m.remove("a")
debug_inspect(smaller.get("a"), content="None")
// the original is unchanged
debug_inspect(m.get("a"), content="Some(1)")
}update covers insert, replace and remove in one call, which is convenient when folding a change into existing state:
///|
test "update" {
let m = @vector_map.VectorMap([("hits", 1)])
let bumped = m.update("hits", n => Some(n.unwrap_or(0) + 1))
debug_inspect(bumped.get("hits"), content="Some(2)")
let fresh = m.update("misses", n => Some(n.unwrap_or(0) + 1))
debug_inspect(fresh.get("misses"), content="Some(1)")
// returning None removes the key
inspect(m.update("hits", _ => None).is_empty(), content="true")
}#Traverse
Every traversal yields entries in insertion order.
///|
test "traverse" {
let m = @vector_map.VectorMap([("c", 3), ("a", 1), ("b", 2)])
debug_inspect(
m.to_array(),
content=(
#|[("c", 3), ("a", 1), ("b", 2)]
),
)
inspect(m.fold(init=0, (acc, _, v) => acc + v), content="6")
let labelled = []
m.eachi((i, k, _) => labelled.push("\{i}:\{k}"))
debug_inspect(
labelled,
content=(
#|["0:c", "1:a", "2:b"]
),
)
for k, v in m {
ignore((k, v))
}
}#Transform
map rewrites values, keeping every key where it is. filter keeps the entries you select, in their existing relative order.
///|
test "transform" {
let m = @vector_map.VectorMap([("c", 3), ("a", 1), ("b", 2)])
debug_inspect(
m.map((_, v) => v * 10).to_array(),
content=(
#|[("c", 30), ("a", 10), ("b", 20)]
),
)
debug_inspect(
m.filter((_, v) => v > 1).to_array(),
content=(
#|[("c", 3), ("b", 2)]
),
)
}#Equality, hashing and JSON
Order is part of the content: two maps holding the same entries in different orders are not equal, and generally do not hash alike. That is what you want when a reordering is a visible change.
///|
test "equality" {
let ab = @vector_map.VectorMap([("a", 1), ("b", 2)])
let ba = @vector_map.VectorMap([("b", 2), ("a", 1)])
inspect(ab == ba, content="false")
inspect(ab == @vector_map.new().add("a", 1).add("b", 2), content="true")
}JSON is an array of [key, value] pairs rather than an object, so that the order survives the round trip and keys keep their type.
///|
test "json" {
let m = @vector_map.VectorMap([(30, "c"), (10, "a")])
json_inspect(m, content=[[30, "c"], [10, "a"]])
let back : @vector_map.VectorMap[Int, String] = @json.from_json(Json(m))
inspect(back == m, content="true")
}#Skipping work on an unchanged map
Two operations are guaranteed to hand back the receiver itself rather than an equal copy: removing a key that is not there, and filtering with a predicate that rejects nothing. update inherits the first, since returning None for a key that is absent goes through remove. A caller that memoises on physical identity — re-rendering only when the map is a different object — is therefore not woken by any of them.
///|
test "no_op" {
let m = @vector_map.VectorMap([("a", 1)])
inspect(physical_equal(m.remove("absent"), m), content="true")
inspect(physical_equal(m.filter((_, _) => true), m), content="true")
}No such promise is made beyond those, and in particular add always builds a new map even when the value it stores equals the one already there. Deciding otherwise would mean comparing values, and the only generic way to do that cheaply — physical_equal — is explicitly not something to hang semantics on. Check get yourself first if you need to skip a redundant write.
#How it works, and what it costs
Entries live in a persistent vector — the spine — in insertion order, and a persistent hash map — the index — maps each key to its slot. Iteration reads the spine straight through and never descends the hash trie, which is what makes traversing the whole map cheap; a lookup pays for both structures.
| Operation | Cost |
|---|---|
| contains | one trie descent |
| get | one trie descent, then one vector descent |
| add on an existing key | one trie descent, one vector descent to recover the stored key, then one vector path copied |
| add on a new key | one trie descent, one trie insertion, and usually only the vector's tail rewritten |
| remove | one trie descent, one trie removal, one vector write — plus the trimming or rebuild described below |
| length, is_empty | O(1) |
| iteration, map, filter, to_array | O(n) |
A trie descent is O(log n) for keys whose hashes are reasonably distributed. Keys that collide on the full hash share a bucket that is searched linearly, so an adversarial or badly written Hash degrades lookup, add and remove towards O(n) — this map inherits that from @immut/hashmap and does nothing to make it worse.
Removal punches a hole in the spine rather than shifting the entries after it, since shifting would invalidate the index entry for every one of them. Under continued removal, holes are reclaimed two ways:
- Trimming. A hole at the end of the spine is dropped at once, and dropping it can uncover more. Trimming k holes costs k vector pops, each of which may copy a tree path, so a single remove can cost O(k log n).
- Rebuilding. Holes in the middle accumulate until the spine is both at least 32 slots long and holding more holes than live entries. Below that length the ratio is not worth acting on, so a small map really can sit on nine holes and one entry. When it does fire, the spine is rebuilt dense and the index renumbered onto the new slots, at O(n).
Outside that cycle, a filter that rejects anything rebuilds the spine dense whatever its length, clearing every hole as a side effect; a filter that rejects nothing returns the receiver untouched, holes included.
Both reclamation paths above are amortised only along a single line of descent. Every hole trimmed or reclaimed was paid for by the removal that made it, but a program that repeatedly returns to a version from just before a trim or a rebuild and removes again will pay the same cost each time. This is a good trade when a map's history moves mostly forward — state that is updated, occasionally rewound — and a poor one under heavy branching with heavy deletion in each branch.
There is deliberately no positional lookup by rank. A slot is a physical position, holes and all, so exposing one would be either misleading or O(n); iterate instead.
The design follows Immutable.js's OrderedMap, and answers the same problem as Scala's VectorMap.
VectorMap
type VectorMap[K, V]A persistent map that iterates in insertion order, the immutable
counterpart of the built-in insertion-ordered Map.
Entries live in a persistent vector — the spine — in the order they were
first inserted, and a persistent hash map — the index — maps each key to
its slot in that spine. Iteration therefore reads the spine straight
through, without descending the hash trie, which is what makes it suited to
rendering a collection on every state change.
Removal punches a hole in the spine rather than shifting the entries after
it, since shifting would invalidate every index entry to their right. Those
holes go two ways as removals continue. A hole left at the end of the spine
is trimmed at once, on the removal that made it, and trimming one can
uncover more. A hole in the middle waits for compact, which runs only when
the spine is both at least MIN_COMPACT_LENGTH slots long and holding more
holes than live entries — a spine too short to be worth rebuilding is left
alone however holey it gets. Beyond that, a filter that rejects anything
rebuilds the spine dense whatever its length, so it clears every hole as a
side effect.
Invariants
- index holds exactly the live keys, and spine[index[k]] is Some((k, _)) for every one of them.
- size is the number of Some slots in spine.
- The last slot of a non-empty spine is never a tombstone, so an empty map always has an empty spine.
- Tombstones never outnumber live entries once the spine reaches MIN_COMPACT_LENGTH.
Note that the representation is deliberately not canonical: two equal maps
may hold different tombstone layouts, so Eq compares the live entry
sequence rather than the underlying structure.
Complexity
Each operation carries its own cost below. Two conventions run through them:
n is the number of live entries — never the number of pairs an operation
consumes, which is written m where the two differ — and a descent, of
the hash trie or of the spine, is O(log n) for keys whose hashes are
reasonably distributed. Keys that collide on the whole hash share a bucket
searched linearly, so a bad Hash degrades every keyed operation towards
O(n); that is inherited from @immut/hashmap rather than added here.
Traversals are linear in the spine, whose length the reclamation rules
bound at max(MIN_COMPACT_LENGTH - 1, 2n): a spine too short to be worth
rebuilding is left alone however holey it gets, and above that length the
trigger is a strict majority of holes, so an even split survives. Traversals
are therefore O(n), with a constant factor that rises as holes accumulate
and, for a map that has shrunk to almost nothing, a floor set by the
exemption rather than by the entry count.
Two maps are equal when they hold the same entries in the same order.
Order is part of the content here, so maps built from the same pairs in
different orders are not equal — which is what a consumer rendering the
entries needs, since a reordering is a visible change. The comparison reads
the live entries only: tombstone layout is representation, and two equal
maps reached by different histories may well have different spines.
O(1) when the two are physically identical or differ in length, O(n)
otherwise — and it stops at the first entry that differs.
Hash the entries in insertion order, so that two maps that compare equal
hash equally and two orderings of the same entries generally do not.
The length is not folded in separately: the hasher is fed one key and one
value per entry in sequence, so a map and a proper prefix of it already feed
it different sequences. That is not a guarantee of different hashes — only
equal maps hashing equally is promised, and unequal ones may always collide.
O(n).
Serialise as an array of [key, value] pairs.
An array rather than an object, because the point of this type is the order
of its entries and JSON object member order is not something a reader is
obliged to preserve. It also keeps non-string keys intact. O(n).
VectorMap::VectorMap
Create a map from an array of key-value pairs, in the array's order.
A repeated key keeps the position of its first occurrence and the value
of its last, matching what repeated adds would produce.
One trie descent per input pair, plus a second for each pair that introduces
a key, so O(m log n) for m pairs — repeated keys cost the lookup only.
Example
test {
let m = @vector_map.VectorMap([(3, "c"), (1, "a"), (3, "z")])
debug_inspect(
m.to_array(),
content=(
#|[(3, "z"), (1, "a")]
),
)
}VectorMap::add
Add an entry, returning a new map.
A key already present keeps its position and only its value is replaced; a
new key is appended after every existing entry. Removing a key and adding it
back therefore moves it to the end.
O(log n) for a key already present. For a new key O(log n) amortised,
but O(n) on the call that carries the spine over the rebuild threshold.
Example
test {
let m = @vector_map.VectorMap([("a", 1), ("b", 2)])
// updating in place keeps "a" first
debug_inspect(
m.add("a", 10).keys().to_array(),
content=(
#|["a", "b"]
),
)
// re-adding after a removal appends
debug_inspect(
m.remove("a").add("a", 10).keys().to_array(),
content=(
#|["b", "a"]
),
)
}VectorMap::at
Look up a key, aborting when it is absent. O(log n), as for get.
VectorMap::contains
Whether the map holds an entry for key. One trie descent and no spine
access at all, so O(log n) and cheaper than get.
VectorMap::each
Apply f to every entry, in insertion order. O(n).
VectorMap::eachi
Apply f to every entry along with its position, in insertion order.
The position is the entry's rank among the live entries, so it always runs
from 0 to length() - 1 with no gaps, whatever the spine looks like
underneath. O(n).
VectorMap::equal
VectorMap::filter
Keep the entries satisfying pred, in their existing relative order.
A predicate that rejects nothing returns the receiver itself, holes and all;
any other result is rebuilt dense, so filtering never introduces a hole.
O(n): one spine pass, then the index is filtered and renumbered in place
of being rebuilt from the keys, so again nothing is hashed.
VectorMap::fold
Fold over the entries, in insertion order. O(n).
VectorMap::from_iter
Create a map from an iterator of key-value pairs, in the iterator's order.
A repeated key keeps the position of its first occurrence and the value of
its last. One trie descent per pair, plus a second for each pair that
introduces a key, so O(m log n) for m pairs.
VectorMap::get
Look up a key. One trie descent and one spine descent, so O(log n).
VectorMap::is_empty
Whether the map holds no entries. O(1).
VectorMap::iter
Iterate over the entries, in insertion order. O(1) to build, O(n) to
drain.
VectorMap::iter2
Iterate over the entries as key/value pairs, in insertion order. O(1) to
build, O(n) to drain.
VectorMap::keys
Iterate over the keys, in insertion order. O(1) to build, O(n) to drain.
VectorMap::length
The number of entries in the map. O(1) — the count is stored, unlike
@immut/hashmap.HashMap::length which walks the whole trie.
VectorMap::map
Transform every value, keeping the keys and their order.
The index is shared with the receiver rather than rebuilt: no slot moves, so
the mapping from keys to positions is unchanged. O(n), and no key is
hashed.
VectorMap::new
Create an empty map. O(1).
VectorMap::remove
Remove a key, returning a new map. A key that is absent returns the receiver
itself.
O(log n) amortised. The worst case is a call that reclaims: trimming k
uncovered holes costs k spine pops, each of which may copy a path, so
O(k log n); a rebuild costs O(n). The amortisation holds along one line
of descent only — repeatedly removing from a version taken just before a
trim or a rebuild pays for it each time.
VectorMap::singleton
Create a map holding a single entry. O(1).
VectorMap::to_array
Collect the entries into an array, in insertion order. O(n).
VectorMap::update
Replace, insert, or remove the entry for key in one step: f sees the
current value if there is one, and its result becomes the new value, or
removes the key when it is None.
A lookup followed by an add or a remove, so O(log n) amortised, with
the reclamation worst cases those two carry.
Example
test {
let m = @vector_map.VectorMap([("a", 1)])
let bumped = m.update("a", v => Some(v.unwrap_or(0) + 1))
debug_inspect(bumped.get("a"), content="Some(2)")
let cleared = m.update("a", _ => None)
inspect(cleared.is_empty(), content="true")
}Install
Installed by default
corestandard library
Apache-2.0
Updated 10 days ago