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::clear
Removes every pair from both sides.
BiMap::contains_key
Whether key is on the key side.
BiMap::contains_value
Whether value is on the value side.
BiMap::copy
A copy that owns both tables: a change to either bijection is invisible to the other.
BiMap::get
The value key is mapped to, or None.
BiMap::get_key
The key a value belongs to, which is the reverse of get.
BiMap::is_empty
Whether the bijection holds no pair.
BiMap::iter
The pairs in insertion order.
BiMap::length
How many pairs the bijection holds.
BiMap::new
An empty bijection, with room for capacity pairs and its tables laid out from hash_seed.
BiMap::output
BiMap::remove_key
Removes the pair whose key is key from both sides and returns it.
BiMap::remove_value
Removes the pair whose value is value from both sides and returns it.
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
Whether any map in the chain holds key.
ChainMap::copy
A copy whose maps are copies: a write through it leaves the original chain alone.
ChainMap::flatten
Copies the chain into one map, which is what a child does when it has to
stop following its parent.
ChainMap::get
The value of key from the first map in the chain that holds it.
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::copy
A copy that owns its table: a change to either counter is invisible to the other.
Counter::decr
Subtracts one from key's count and drops the key once its count reaches zero, returning the count it holds afterwards.
Counter::decr_by
Subtracts amount from key's count and drops the key once its count reaches zero or below, returning the count it holds afterwards.
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::iter
The keys and their counts in insertion order.
Counter::length
The number of distinct keys counted.
Counter::most_common
The n keys with the largest counts, ties in insertion order. n below
zero means every key.
Counter::new
A counter with room for capacity keys, laid out from hash_seed.
Counter::retain
Keeps the keys f accepts with their counts and drops the rest.
Counter::subtract_in_place
Subtracts other from this counter in place, dropping keys that reach zero.
Counter::to_array
The keys and their counts in insertion order, as a new array.
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::clear
Removes every entry, keeping the factory.
DefaultMap::contains
Whether key has an entry; a key the factory would answer still reads as absent until it is stored.
DefaultMap::copy
A copy that owns its table and shares the factory: a change to either map is invisible to the other.
DefaultMap::equal
DefaultMap::get
The value under key, or None; unlike get_or_init this does not call the factory and stores nothing.
DefaultMap::get_or_init
The value under key, inserting factory(key) when the key is new.
DefaultMap::is_empty
Whether the map holds no entry.
DefaultMap::iter
The entries in insertion order.
DefaultMap::keys
The keys in insertion order.
DefaultMap::length
How many entries the map holds.
DefaultMap::new
fn[K, V] DefaultMap::new(factory~ : (K) -> V, capacity? : Int, hash_seed? : Int) -> DefaultMap[K, V]A map that answers a missing key with factory(key). The factory runs only when get_or_init asks, so a lookup through get still reports the absence.
DefaultMap::not_equal
DefaultMap::output
DefaultMap::remove
Removes key and returns the value it held.
DefaultMap::set
Stores value under key and returns what was there.
DefaultMap::to_string
DefaultMap::values
The values in insertion order.
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::capacity
How many entries the run has room for before it grows.
FlatMap::clear
Removes every entry, keeping the room the run has.
FlatMap::contains
Whether key has an entry.
FlatMap::copy
A copy that owns its arrays: a change to either map is invisible to the other.
FlatMap::equal
FlatMap::first
The entry with the smallest key, or None when the map is empty.
FlatMap::from_array
Sorts the pairs by key; when a key repeats, the last pair in the array wins.
FlatMap::get
The value under key, or None; the lookup is a binary search over the sorted keys.
FlatMap::get_index
The entry at position index in key order, or None when the position is past the last one.
FlatMap::index_of
Where key is, or where it would be inserted.
FlatMap::is_empty
Whether the map holds no entry.
FlatMap::iter
The entries in key order.
FlatMap::last
The entry with the largest key, or None when the map is empty.
FlatMap::length
How many entries the map holds.
FlatMap::new
An empty map whose entries live in one sorted run, with room for capacity of them.
FlatMap::not_equal
FlatMap::output
FlatMap::pop_first
Removes and returns the entry with the smallest key.
FlatMap::pop_last
Removes and returns the entry with the largest key.
FlatMap::range
The pairs whose keys fall between start and end, both included.
FlatMap::remove
Removes key and returns the value it held, closing the gap in the run.
FlatMap::reserve_capacity
Makes room for capacity entries in one allocation, so the inserts that follow do not grow the run again.
FlatMap::set
Stores value under key, inserting the key in order, and returns the value it replaced.
FlatMap::shrink_to_fit
Releases the room past the last entry.
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::clear
Removes every entry, keeping the room the run has.
FlatMultiMap::contains
Whether key has at least one value.
FlatMultiMap::copy
A copy that owns its array: a change to either multimap is invisible to the other.
FlatMultiMap::count
How many values are stored under key.
FlatMultiMap::equal
fn[K : Eq, V : Eq] FlatMultiMap::equal(self : FlatMultiMap[K, V], other : FlatMultiMap[K, V]) -> BoolFlatMultiMap::first
The smallest entry, or None when the map is empty.
FlatMultiMap::get
The values under key, ascending.
FlatMultiMap::insert
fn[K : Compare + Eq, V : Compare + Eq] FlatMultiMap::insert(self : FlatMultiMap[K, V], key : K, value : V) -> UnitAdds value under key in sorted position; a pair that is already there is not added twice.
FlatMultiMap::is_empty
Whether no value is stored under any key.
FlatMultiMap::iter
Every entry in key order, and within one key in value order.
FlatMultiMap::key_count
The number of distinct keys.
FlatMultiMap::last
The largest entry, or None when the map is empty.
FlatMultiMap::length
How many entries, counting one per value, the map holds.
FlatMultiMap::new
An empty multimap whose entries live in one run sorted by key and then by value, with room for capacity of them.
FlatMultiMap::not_equal
FlatMultiMap::output
FlatMultiMap::pop_first
Removes and returns the smallest entry.
FlatMultiMap::pop_last
Removes and returns the largest entry.
FlatMultiMap::range
fn[K : Compare + Eq, V] FlatMultiMap::range(self : FlatMultiMap[K, V], start~ : K, end~ : K) -> Iter[(K, V)]Every entry whose key is from start up to end, in order.
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
Every entry in key order, as a new 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::capacity
How many values the run has room for before it grows.
FlatSet::clear
Removes every value, keeping the room the run has.
FlatSet::contains
Whether value is in the set; the lookup is a binary search over the sorted run.
FlatSet::copy
A copy that owns its array: a change to either set is invisible to the other.
FlatSet::first
The smallest value, or None when the set is empty.
FlatSet::from_array
A set holding the values written out, in order and without repeats.
FlatSet::get_index
The value at position index in order, or None when the position is past the last one.
FlatSet::index_of
Where key is, or where it would be inserted.
FlatSet::insert
Adds the element and reports whether it was new.
FlatSet::is_empty
Whether the set holds no value.
FlatSet::last
The largest value, or None when the set is empty.
FlatSet::new
An empty set whose values live in one sorted run, with room for capacity of them.
FlatSet::pop_first
Removes and returns the smallest value.
FlatSet::pop_last
Removes and returns the largest value.
FlatSet::range
The values from start up to end, in order.
FlatSet::remove
Removes value, closing the gap in the run, and reports whether it was there.
FlatSet::reserve_capacity
Makes room for capacity values in one allocation.
FlatSet::shrink_to_fit
Releases the room past the last value.
FlatSet::to_array
The values in order, as a new array.
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::clear
Removes every entry, keeping the seed the map was made with.
IndexMap::contains
Whether key has an entry.
IndexMap::copy
A copy that owns its arrays: a change to either map is invisible to the other.
IndexMap::equal
IndexMap::from_array
A map holding the entries written out, in the order given. A key that appears twice keeps its first position and takes the last value.
IndexMap::from_iter
A map holding the entries the iterator yields, in the order they arrive.
IndexMap::from_json
IndexMap::get
The value under key, or None when no entry has it.
IndexMap::get_full
The position, key and value of key, read in one lookup.
IndexMap::get_index
The entry at position index, or None when the position is past the last one.
IndexMap::get_index_of
The position key sits at, or None when it has no entry.
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::is_empty
Whether the map holds no entry.
IndexMap::iter
The entries in position order.
IndexMap::iter2
The keys and the values in position order, as a two-part iterator.
IndexMap::keys
The keys in position order.
IndexMap::length
How many entries the map holds.
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::remove
Removes key the way swap_remove does and hands back the value it held.
IndexMap::reserve_capacity
Lays the table out again with room for capacity entries, so the inserts that follow do not rehash.
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
Removes key by shifting every later entry down one position, so the positions that remain are the ones they were; O(n).
IndexMap::shift_remove_index
Removes the entry at index and closes the gap, so every entry after it
moves down one position.
IndexMap::shrink_to_fit
Lays the table out again at the smallest size that holds the entries, dropping the slots removals left behind.
IndexMap::sort_by
Reorders the entries by cmp, which sees the whole entry rather than only its key, and renumbers the positions.
IndexMap::sort_by_key
Reorders the entries by a projection of the key and renumbers the positions.
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
Exchanges the entries at two positions. Both keys keep their slots in the table, so this costs a swap and not a rehash; an index that is out of range leaves the map as it was.
IndexMap::swap_remove
Removes key by moving the last entry into its position, so the entries stay dense and the cost is O(1). The positions of the entries after the hole therefore change.
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_array
The entries in position order, as a new array.
IndexMap::to_string
IndexMap::truncate
Keeps the first length entries and drops the rest; a length past the end leaves the map alone.
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::capacity
How many values the table behind the set has room for before it is laid out again.
IndexSet::clear
Removes every value, keeping the seed the set was made with.
IndexSet::contains
Whether value is in the set.
IndexSet::copy
A copy that owns its arrays: a change to either set is invisible to the other.
IndexSet::difference
The elements of this set that are not in other, in this set's order.
IndexSet::first
The value at position 0, or None when the set is empty.
IndexSet::from_array
A set holding the values written out, in the order given.
IndexSet::from_iter
A set holding the values the iterator yields, in the order they arrive.
IndexSet::get_index
The value at position index, or None when the position is past the last one.
IndexSet::get_index_of
The position value sits at, or None when it is not in the set.
IndexSet::hash_combine
IndexSet::insert
The position of the element and whether it was new.
IndexSet::intersection
A new set holding the values in both, in the order this one holds them.
IndexSet::is_disjoint
Whether the two sets share no value.
IndexSet::is_empty
Whether the set holds no value.
IndexSet::is_subset
Whether every value of this set is in other.
IndexSet::is_superset
Whether every value of other is in this set.
IndexSet::iter
The values in position order.
IndexSet::last
The value at the last position, or None when the set is empty.
IndexSet::length
How many values the set holds.
IndexSet::move_index
Moves the value at one position to another and closes the gap, so no position is skipped.
IndexSet::new
A set with room for capacity values, laid out from hash_seed.
IndexSet::range
The elements from start for len positions.
IndexSet::remove
Removes value the way swap_remove does and reports whether it was there.
IndexSet::retain
Keeps the values f accepts and removes the rest, holding their order.
IndexSet::shift_remove
Removes value by shifting every later value down one position, so the positions that remain are the ones they were; O(n).
IndexSet::sort_by
Reorders the values by cmp.
IndexSet::sort_keys
Reorders the values ascending by their own order.
IndexSet::swap_indices
Exchanges the values at two positions, leaving the set's contents alone.
IndexSet::swap_remove
Removes value by moving the last value into its position, so the values stay dense and the cost is O(1).
IndexSet::symmetric_difference
A new set holding the values in exactly one of the two.
IndexSet::to_array
The values in position order, as a new array.
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::clear
Removes every key and every value.
MultiMap::contains
Whether key has at least one value.
MultiMap::contains_entry
Whether value is one of the values under key.
MultiMap::copy
A copy that owns its arrays: a change to either multimap is invisible to the other.
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
Adds value under key, keeping the values of a key in the order they were added.
MultiMap::is_empty
Whether no value is stored under any key.
MultiMap::iter
Every pair, key by key, the values of a key in insertion order.
MultiMap::iter2
Every value paired with its key, in key order and then in the order the values were added.
MultiMap::iter_values
The values under key, in the order they were added; a key that is absent yields nothing.
MultiMap::key_count
The number of distinct keys.
MultiMap::keys
The keys in the order they were first added.
MultiMap::length
The number of values held, counting repeats.
MultiMap::new
A multimap with room for capacity values, its key table laid out from hash_seed.
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::clear
Removes every key, leaving the root.
RadixTree::contains
Whether key is stored.
RadixTree::contains_prefix
Whether some stored key begins with prefix.
RadixTree::copy
A copy that shares nothing with the original: a write to either is invisible to the other.
RadixTree::get
The value stored under key, or None.
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::is_empty
Whether no key is stored.
RadixTree::iter
Every stored key and its value, in tree order.
RadixTree::iter_prefix
The keys under prefix, in character order.
RadixTree::keys_with_prefix
Every stored key that begins with prefix, in tree order.
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.
RadixTree::to_array
Every stored key and its value, in tree order, as a new array.
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::clear
Removes every range, keeping the overlap policy.
RangeMap::copy
A copy that owns its array: a change to either map is invisible to the other.
RangeMap::equal
RangeMap::gaps
The spans no range covers, in start order.
RangeMap::get
The value covering key, or None when no range does.
RangeMap::get_range
The range covering key — its start, its end and its value — or None.
RangeMap::insert
Stores value over [start, end), applying the overlap policy and folding
the result into its neighbours.
RangeMap::is_empty
Whether the map holds no range.
RangeMap::length
How many ranges the map holds.
RangeMap::new
An empty range map whose policy for an overlapping insert is overlap: Overwrite cuts the existing ranges back, Refuse raises Refused::Overlap, KeepFirst drops the incoming one.
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::clear
Removes every range, keeping the overlap policy.
RangeSet::contains
Whether key is covered by a range.
RangeSet::copy
A copy that owns its array: a change to either set is invisible to the other.
RangeSet::gaps
The spans between one range and the next, in order.
RangeSet::insert
Adds the range from start up to end, merging it with the ranges it touches.
RangeSet::is_empty
Whether the set holds no range.
RangeSet::length
How many ranges the set holds.
RangeSet::new
An empty range set whose policy for an overlapping insert is overlap.
RangeSet::overlapping
The ranges that meet the span from start up to end, in order.
RangeSet::ranges
The ranges, in order.
RangeSet::remove
Removes the span from start up to end, cutting the ranges that cover it.
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::clear
Removes every entry.
SortedMultiMap::contains
Whether key has at least one value.
SortedMultiMap::copy
A copy that owns its array: a change to either multimap is invisible to the other.
SortedMultiMap::equal
fn[K : Eq, V : Eq] SortedMultiMap::equal(self : SortedMultiMap[K, V], other : SortedMultiMap[K, V]) -> BoolSortedMultiMap::first
The smallest entry, or None when the map is empty.
SortedMultiMap::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) -> UnitAdds value under key; the entry goes where key order puts it, and equal keys keep the values in the order they were added.
SortedMultiMap::is_empty
Whether no value is stored under any key.
SortedMultiMap::iter
Every entry in key order, and within one key in the order the values were added.
SortedMultiMap::key_count
The number of distinct keys.
SortedMultiMap::last
The largest entry, or None when the map is empty.
SortedMultiMap::length
How many entries, counting one per value, the map holds.
SortedMultiMap::new
An empty multimap that keeps its entries in key order.
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
Removes and returns the smallest entry.
SortedMultiMap::pop_last
Removes and returns the largest entry.
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
Every entry in key order, as a new 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
Whether key is a stored word; a prefix of one is not.
Trie::contains_prefix
Whether any key stored here starts with prefix.
Trie::copy
A copy that shares nothing with the original: a write to either is invisible to the other.
Trie::get
The value stored under key, or None when key is not a stored word.
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.
Trie::to_array
Every stored word and its value, in the depth-first order the trie walks.
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 10 hours ago
297 downloads