README- UAhoCorasick
- UArcCache
- UArenaTree
- UBiMap
- UBitSet
- UBitVec
- UBloomFilter
- UBloomOptions
- UBoyerMoore
- UCacheStats
- UChainMap
- UCombinations
- UCombinationsWithReplacement
- UCountMinSketch
- UCounter
- UCuckooFilter
- UCuckooOptions
- UDaryHeap
- UDefaultMap
- UDenseSlotMap
- UDisjointSet
- UDisjointSetMap
- UExpiringCache
- UFenwick
- UFibonacciHeap
- UFlatMap
- UFlatMultiMap
- UFlatMultiSet
- UFlatSet
- UGapBuffer
- UGrayCode
- UGrowth
- UHeapKey
- UHyperLogLog
- UIndexHeap
- UIndexMap
- UIndexSet
- UIntervalKey
- UIntervalTree
- UJoinEntry
- UKmp
- ULazySegmentTree
- ULfuCache
- ULinkedList
- ULruCache
- UMatch
- UMinMaxHeap
- UMultiMap
- UMultiSet
- UOpcode
- UOrder
- UOrderStatisticTree
- UOverflow
- UOverlap
- UPairingHeap
- UPermutations
- UPhfBuild
- UPhfBuilder
- UPhfLayout
- UPhfMap
- UPhfOptions
- UPhfOrderedMap
- UPhfOrderedSet
- UPhfSet
- UPosition
- UPowerset
- UProduct
- URadixHeap
- URadixTree
- URangeMap
- URangeSet
- URefused
- URingBuffer
- URope
- URopeBuilder
- URopeView
- USecondaryMap
- USegmentTree
- USequenceMatcher
- USequenceMatcherOptions
- USkipList
- USkipListOptions
- USlab
- USlotKey
- USlotMap
- USortedMultiMap
- USortedMultiSet
- USparseSet
- USuffixArray
- USuffixAutomaton
- UTDigest
- UThetaSketch
- UTreap
- UTreeId
- UTrie
moonbitstack/moonstl/map does not have a README file
FlatMultiSet
A flat multiset keeps repeats in sorted order and counts them.
MultiSet
A multiset is a multimap whose values carry no information.
SortedMultiSet
A sorted multiset is a sorted multimap whose values carry no information.
BiMap
A two-way map: the pair k -> v can be read from either side, and neither a
key nor a value can appear twice. set keeps the mapping total by dropping
whatever the new pair collides with, and hands it back.
test {
let bimap : @map.BiMap[Int32, String] = @map.BiMap::new()
let _ = bimap.set(1, "a")
let _ = bimap.set(2, "b")
@test.assert_eq(bimap.get_key("b"), Some(2))
@test.assert_eq(bimap.set(1, "b"), Some((1, "a")))
@test.assert_eq(bimap.get(1), Some("b"))
@test.assert_eq(bimap.get(2), None)
}BiMap::contains_key
BiMap::contains_value
BiMap::get_key
The key a value belongs to, which is the reverse of get.
BiMap::output
BiMap::remove_key
BiMap::remove_value
BiMap::set
Stores the pair, dropping the pair the key belonged to and the pair the
value belonged to, and returns one of the dropped pairs — the one the key
displaced when there is one, otherwise the one the value displaced.
BiMap::set_new
Stores the pair only when neither side is taken, and refuses otherwise.
ChainMap
A stack of maps read as one: a lookup falls through the stack from the front,
and a write always lands in the front map. That is what a layered
configuration needs — a child scope that sees its parent's settings but
shadows them without touching them.
test {
let base : Map[String, Int32] = Map([])
base.set("a", 1)
let chain : @map.ChainMap[String, Int32] = @map.ChainMap::new([base])
@test.assert_eq(chain.get("a"), Some(1))
let child = chain.new_child()
child.set("a", 2)
@test.assert_eq(child.get("a"), Some(2))
@test.assert_eq(chain.get("a"), Some(1))
}ChainMap::contains
ChainMap::flatten
Copies the chain into one map, which is what a child does when it has to
stop following its parent.
ChainMap::iter
Every pair the chain answers for: the first map that holds a key decides its
value.
ChainMap::length
The number of distinct keys the chain answers for.
ChainMap::maps
The maps of the chain, front first.
ChainMap::new
Builds a chain over maps, the first of which is written to.
ChainMap::new_child
Puts a fresh empty map in front, which is how a narrower scope is opened.
ChainMap::parent
The chain without its front map, or None when only one is left.
ChainMap::remove
Removes key from every map in the chain, so a shadowed value does not
reappear once the front one is dropped.
Counter
A multiset of counts: each key carries how many times it was seen, and a key
whose count reaches zero leaves the counter so that iteration only ever sees
keys that are present.
test {
let counter : @map.Counter[String] = @map.Counter::new()
@test.assert_eq(counter.incr("a"), 1)
@test.assert_eq(counter.incr_by("a", 2), 3)
@test.assert_eq(counter.decr("a"), 2)
@test.assert_eq(counter.total(), 2L)
}Counter::add
The sum of two counters, as a new one. The keys keep the order of self,
and keys only other has follow.
Counter::decr_by
Counter::elements
Every key repeated as many times as it was counted.
Counter::get
The count of key, zero when it has none.
Counter::incr
Adds one and returns the new count.
Counter::incr_by
Adds amount, which may be negative, and returns the new count. A count
that reaches zero or below removes the key.
Counter::most_common
The n keys with the largest counts, ties in insertion order. n below
zero means every key.
Counter::retain
Counter::subtract_in_place
Subtracts other from this counter in place, dropping keys that reach zero.
DefaultMap
A map that answers a lookup with a value it makes up on the spot: the
factory is called with the key, so a reader never has to write the
check-then-insert pair by hand.
test {
let map : @map.DefaultMap[String, Int32] = @map.DefaultMap::new(factory=key => {
key.length()
})
@test.assert_eq(map.get_or_init("abc"), 3)
@test.assert_eq(map.length(), 1)
@test.assert_eq(map.get("abc"), Some(3))
}impl Eq for DefaultMap[K, V]impl Show for DefaultMap[K, V]DefaultMap::contains
DefaultMap::equal
DefaultMap::get_or_init
The value under key, inserting factory(key) when the key is new.
DefaultMap::new
fn[K, V] DefaultMap::new(factory~ : (K) -> V, capacity? : Int, hash_seed? : Int) -> DefaultMap[K, V]DefaultMap::not_equal
DefaultMap::output
DefaultMap::remove
DefaultMap::set
DefaultMap::to_string
FlatMap
A map held as a sorted array of keys with a parallel array of values: a
lookup is a binary search over contiguous memory, which is the shape to
reach for when a table is built once and read many times.
test {
let map : @map.FlatMap[Int32, String] = @map.FlatMap::new()
let _ = map.set(2, "b")
let _ = map.set(1, "a")
@test.assert_eq(map.keys().to_array(), [1, 2])
@test.assert_eq(map.get(2), Some("b"))
@test.assert_eq(map.index_of(3), Err(2))
}FlatMap::contains
FlatMap::equal
FlatMap::from_array
Sorts the pairs by key; when a key repeats, the last pair in the array wins.
FlatMap::index_of
Where key is, or where it would be inserted.
FlatMap::not_equal
FlatMap::output
FlatMap::range
The pairs whose keys fall between start and end, both included.
FlatMap::reserve_capacity
FlatMap::set
FlatMultiMap
A multimap held as a sorted array of pairs: keys in order, and the values of
one key in order among themselves. Repeats are kept, so this is the flat
counterpart of SortedMultiMap.
test {
let map : @map.FlatMultiMap[Int32, String] = @map.FlatMultiMap::new()
map.insert(2, "b")
map.insert(1, "a")
map.insert(1, "c")
@test.assert_eq(map.get(1), ["a", "c"])
@test.assert_eq(map.length(), 3)
@test.assert_eq(map.key_count(), 2)
}impl Eq for FlatMultiMap[K, V]impl Show for FlatMultiMap[K, V]FlatMultiMap::contains
FlatMultiMap::copy
FlatMultiMap::count
FlatMultiMap::equal
fn[K : Eq, V : Eq] FlatMultiMap::equal(self : FlatMultiMap[K, V], other : FlatMultiMap[K, V]) -> BoolFlatMultiMap::get
FlatMultiMap::insert
fn[K : Compare + Eq, V : Compare + Eq] FlatMultiMap::insert(self : FlatMultiMap[K, V], key : K, value : V) -> UnitFlatMultiMap::key_count
FlatMultiMap::not_equal
FlatMultiMap::output
FlatMultiMap::range
fn[K : Compare + Eq, V] FlatMultiMap::range(self : FlatMultiMap[K, V], start~ : K, end~ : K) -> Iter[(K, V)]FlatMultiMap::remove
Drops every value of key and returns them.
FlatMultiMap::remove_entry
fn[K : Compare + Eq, V : Compare + Eq] FlatMultiMap::remove_entry(self : FlatMultiMap[K, V], key : K, value : V) -> BoolDrops one pair equal to (key, value).
FlatMultiMap::to_array
FlatMultiMap::to_string
FlatSet
A set held as a sorted array of elements, the companion of FlatMap.
test {
let set : @map.FlatSet[Int32] = @map.FlatSet::new()
@test.assert_eq(set.insert(3), true)
@test.assert_eq(set.insert(3), false)
@test.assert_eq(set.get_index(0), Some(3))
}FlatSet::from_array
FlatSet::index_of
Where key is, or where it would be inserted.
FlatSet::insert
Adds the element and reports whether it was new.
FlatSet::range
FlatSet::reserve_capacity
IndexMap
An associative container that keeps insertion order and gives every entry a
position: get_index reads by position, get_index_of reads the position of
a key, and the entries can be reordered without touching the table's
contents. swap_remove is the default removal because it is O(1); a caller
that needs the remaining positions to stay contiguous uses shift_remove.
test {
let map : @map.IndexMap[String, Int32] = @map.IndexMap::new()
let _ = map.set("a", 1)
let _ = map.set("b", 2)
@test.assert_eq(map.get_index_of("b"), Some(1))
@test.assert_eq(map.get_index(0), Some(("a", 1)))
let _ = map.swap_remove("a")
@test.assert_eq(map.get_index(0), Some(("b", 2)))
}IndexMap::capacity
The number of slots the table has, which is what reserve_capacity raises.
IndexMap::contains
IndexMap::equal
IndexMap::from_array
IndexMap::from_iter
IndexMap::from_json
IndexMap::get_full
IndexMap::get_index
IndexMap::get_index_of
IndexMap::get_key_value
The key and the value of an entry, which unlike get hands back the key the
map actually holds.
IndexMap::hash_combine
IndexMap::insert_full
The entry index of key after storing value there, and the value that was
there before. The position of an existing entry does not change.
IndexMap::move_index
Moves the entry at from to to, shifting everything between them.
IndexMap::new
A table with room for capacity entries, laid out from hash_seed. A fixed
seed makes the layout, and with it nothing visible, reproducible; the order
of the entries does not depend on it.
IndexMap::not_equal
IndexMap::output
IndexMap::range
The entries from start for len positions, clamped to the container.
IndexMap::reserve_capacity
IndexMap::retain
Keeps the entries the predicate accepts, in their order, and renumbers the
positions when any were dropped.
IndexMap::set
Stores value under key and returns the value it replaced.
IndexMap::set_default
Stores value under key only when the key is new, which is how a caller
keeps the first value written.
IndexMap::shift_remove
IndexMap::shift_remove_index
Removes the entry at index and closes the gap, so every entry after it
moves down one position.
IndexMap::sort_by
IndexMap::sort_by_key
IndexMap::sort_keys
Sorts the entries by key and renumbers the positions.
IndexMap::split_off
The entries from at on, as a new map; this map keeps the ones before it.
IndexMap::swap_indices
IndexMap::swap_remove
IndexMap::swap_remove_index
Removes the entry at index by moving the last entry into its place, and
returns it. The entry that moved keeps its key and takes the removed
position.
IndexMap::to_string
IndexMap::update
Replaces the value of an entry that is already there, and reports whether
there was one.
IndexSet
A set that keeps insertion order and gives every element a position, the
companion of IndexMap the way HashSet is the companion of HashMap.
test {
let set : @map.IndexSet[Int32] = @map.IndexSet::new()
@test.assert_eq(set.insert(7), (0, true))
@test.assert_eq(set.insert(7), (0, false))
@test.assert_eq(set.get_index(0), Some(7))
}IndexSet::difference
The elements of this set that are not in other, in this set's order.
IndexSet::from_array
IndexSet::from_iter
IndexSet::get_index_of
IndexSet::hash_combine
IndexSet::insert
The position of the element and whether it was new.
IndexSet::intersection
IndexSet::is_disjoint
IndexSet::is_subset
IndexSet::is_superset
IndexSet::move_index
IndexSet::range
The elements from start for len positions.
IndexSet::shift_remove
IndexSet::swap_indices
IndexSet::swap_remove
IndexSet::symmetric_difference
MultiMap
A map from a key to a list of values: one entry per key, and the values of a
key keep the order they were inserted in.
test {
let map : @map.MultiMap[String, Int32] = @map.MultiMap::new()
map.insert("a", 1)
map.insert("a", 2)
@test.assert_eq(map.get("a"), [1, 2])
@test.assert_eq(map.length(), 2)
@test.assert_eq(map.key_count(), 1)
}MultiMap::contains
MultiMap::contains_entry
MultiMap::equal
MultiMap::get
The values of key, in insertion order. The array is a copy, so a caller
cannot write into the map through it.
MultiMap::insert
MultiMap::iter
Every pair, key by key, the values of a key in insertion order.
MultiMap::iter_values
MultiMap::key_count
The number of distinct keys.
MultiMap::length
The number of values held, counting repeats.
MultiMap::not_equal
MultiMap::output
MultiMap::remove
Drops every value of key and returns them.
MultiMap::remove_entry
Drops one occurrence of value under key.
Overlap
What an insert does when the new range meets one that is already there.
RadixTree
A trie with its chains of single-child nodes collapsed into one edge per
label: a lookup compares whole labels instead of single characters, which is
what keeps a tree over long shared prefixes shallow. The surface is the
Trie surface, plus the queries that only make sense over a compressed tree:
the keys that are prefixes of a given key, a count of the keys under a
prefix, and a scan of that subtree.
test {
let tree : @map.RadixTree[Int32] = @map.RadixTree::new()
@test.assert_eq(tree.insert("car", 1), None)
@test.assert_eq(tree.insert("cart", 2), None)
@test.assert_eq(tree.insert("cat", 3), None)
@test.assert_eq(tree.get("cart"), Some(2))
@test.assert_eq(tree.get_ancestor_keys("cartoon"), ["car", "cart"])
@test.assert_eq(tree.prefix_count("ca"), 3)
}RadixTree::contains_prefix
RadixTree::get_ancestor_keys
The stored keys that are prefixes of key, shortest first.
RadixTree::insert
Stores value under key and returns what the key held before.
RadixTree::iter_prefix
The keys under prefix, in character order.
RadixTree::keys_with_prefix
RadixTree::longest_prefix
The longest stored key that is a prefix of text, with its value.
RadixTree::output
RadixTree::prefix_count
How many stored keys start with prefix.
RadixTree::remove
Drops the value under key, and the nodes the removal left empty.
RangeMap
A value that holds over a span of keys: the ranges are kept sorted, never
overlap each other, and two ranges that touch and hold the same value are
kept as one. A range is half-open — it covers start and stops before end
— so an insert that meets a neighbour at one endpoint does not collide with
it.
test {
let map : @map.RangeMap[Int32, String] = @map.RangeMap::new()
map.insert(start=0, end=10, "low")
map.insert(start=10, end=20, "high")
@test.assert_eq(map.get(5), Some("low"))
@test.assert_eq(map.get(10), Some("high"))
@test.assert_eq(map.get(20), None)
@test.assert_eq(map.length(), 2)
}RangeMap::equal
RangeMap::gaps
The spans no range covers, in start order.
RangeMap::get_range
RangeMap::insert
Stores value over [start, end), applying the overlap policy and folding
the result into its neighbours.
RangeMap::not_equal
RangeMap::output
RangeMap::overlapping
Every range that meets [start, end), in start order.
RangeMap::ranges
The ranges, in start order.
RangeMap::remove
Drops the part of every range that falls in [start, end), splitting a range
that straddles it.
RangeSet
A set of spans: the companion of RangeMap with no value to carry.
test {
let set : @map.RangeSet[Int32] = @map.RangeSet::new()
set.insert(start=0, end=5)
set.insert(start=5, end=9)
@test.assert_eq(set.contains(7), true)
@test.assert_eq(set.contains(9), false)
@test.assert_eq(set.length(), 1)
}RangeSet::contains
RangeSet::insert
RangeSet::overlapping
RangeSet::remove
SortedMultiMap
A multimap held as a sorted array: the keys are in order, and the values of
one key are in order among themselves as well, so range and first walk
the pairs in the order a reader expects.
test {
let map : @map.SortedMultiMap[Int32, String] = @map.SortedMultiMap::new()
map.insert(2, "b")
map.insert(1, "a")
map.insert(1, "b")
@test.assert_eq(map.first(), Some((1, "a")))
@test.assert_eq(map.get(1), ["a", "b"])
}impl Eq for SortedMultiMap[K, V]impl Show for SortedMultiMap[K, V]SortedMultiMap::contains
SortedMultiMap::copy
SortedMultiMap::equal
fn[K : Eq, V : Eq] SortedMultiMap::equal(self : SortedMultiMap[K, V], other : SortedMultiMap[K, V]) -> BoolSortedMultiMap::get
The values of key, in order.
SortedMultiMap::insert
fn[K : Compare + Eq, V : Compare + Eq] SortedMultiMap::insert(self : SortedMultiMap[K, V], key : K, value : V) -> UnitSortedMultiMap::is_empty
SortedMultiMap::iter
SortedMultiMap::key_count
The number of distinct keys.
SortedMultiMap::not_equal
fn[K : Eq, V : Eq] SortedMultiMap::not_equal(x : SortedMultiMap[K, V], y : SortedMultiMap[K, V]) -> BoolSortedMultiMap::output
fn[K : Show, V : Show] SortedMultiMap::output(self : SortedMultiMap[K, V], logger : &Logger) -> UnitSortedMultiMap::pop_first
SortedMultiMap::pop_last
SortedMultiMap::range
fn[K : Compare + Eq, V] SortedMultiMap::range(self : SortedMultiMap[K, V], start~ : K, end~ : K) -> Iter[(K, V)]The pairs whose keys fall in start up to end, both included.
SortedMultiMap::remove
Drops the values of key and returns them.
SortedMultiMap::to_array
SortedMultiMap::to_string
Trie
A map keyed by String that shares the storage of keys with a common
prefix: the walk to a key costs one step per character, whatever else is
stored.
test {
let trie : @map.Trie[Int32] = @map.Trie::new()
@test.assert_eq(trie.insert("car", 1), None)
@test.assert_eq(trie.insert("cart", 2), None)
@test.assert_eq(trie.get("car"), Some(1))
@test.assert_eq(trie.keys_with_prefix("ca"), ["car", "cart"])
@test.assert_eq(trie.longest_prefix("cartoon"), Some(("cart", 2)))
}Trie::contains_prefix
Whether any key stored here starts with prefix.
Trie::insert
Stores value under key and returns the value the key held before.
Trie::keys_with_prefix
The keys starting with prefix, in character order.
Trie::longest_prefix
The longest key stored here that is a prefix of text, with its value.
Trie::remove
Drops the value under key and returns it. The nodes stay, so a later
insert of a key with the same prefix does not walk the string again.
Install
Download zipData structures and algorithms the MoonBit core library leaves out.
data-structuresalgorithmscollectionscontainersstlmoonbitindex-mapindex-setmultimapbimapcounterflat-mapsorted-maprange-maptrieradix-treelru-cachelfu-cachearc-cacheexpiring-cachememoizesortingselectionbisectbinary-searchpermutationscombinationspowersetpartitionmergering-bufferslotmapgap-bufferbit-vectorbit-setlinked-listbinary-heapfibonacci-heappairing-heapmin-max-heapradix-heapdisjoint-setunion-findsegment-treefenwick-treeinterval-treeskip-listtreapbloom-filtercuckoo-filtercount-min-sketchhyperloglogtheta-sketcht-digeststring-searchsuffix-arraysuffix-automatondiffropeperfect-hash
Apache-2.0
Updated 9 hours ago
102 downloads