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/tree does not have a README file
ArenaTree
A tree whose nodes live in one arena and are reached by id: a node knows its
parent, its first and last child, and its two siblings, so every step of a
walk is a field read and no pointer chases the allocator. Children are kept
in insertion order, and sort_children reorders them by their own values.
test {
let tree : @tree.ArenaTree[String] = @tree.ArenaTree::new()
let root = tree.add("root")
let a = tree.add_child(root, "a")
let _ = tree.add_child(root, "b")
let _ = tree.add_child(a, "a1")
assert_true(tree.length() == 4)
assert_true(tree.children(root).length() == 2)
assert_true(tree.descendants(root).to_array().length() == 3)
assert_true(tree.remove(a) == Some("a"))
assert_true(tree.length() == 2)
}ArenaTree::add
Adds a detached node, which becomes a root of its own.
ArenaTree::add_child
Adds a child at the end of parent's children and returns its id; a parent that is no longer in the tree yields the null id.
ArenaTree::ancestors
The root first, then each ancestor up to it.
ArenaTree::children
The ids of the children, in order.
ArenaTree::clear
Removes every node; the ids issued before it name nothing afterwards.
ArenaTree::contains
Whether id names a node.
ArenaTree::copy
A copy that owns its arrays: an edit to either tree leaves the other alone, and an id names the same node in both.
ArenaTree::descendants
The children of a node, and their children, depth first and left to right.
ArenaTree::detach
Cuts a subtree loose and returns it as a tree of its own. The copy owns its
nodes, so the ids of the returned tree are its own; the original keeps its
ids. The cost is the size of the subtree, because the nodes are rebuilt.
ArenaTree::first_child
The first child of id, or None when it has none.
ArenaTree::get
The value behind id, or None when the id names nothing.
ArenaTree::insert_after
Adds a sibling just after sibling and returns its id; a sibling that is no longer in the tree yields the null id.
ArenaTree::insert_before
Adds a sibling just before sibling and returns its id; a sibling that is no longer in the tree yields the null id.
ArenaTree::is_empty
Whether the tree holds no node.
ArenaTree::next_sibling
The sibling after id, or None when it is the last child.
ArenaTree::parent
The parent of id, or None when it is the root or names nothing.
ArenaTree::postorder
The subtree in postorder: every child before its parent.
ArenaTree::preorder
The whole tree in preorder, the node itself first.
ArenaTree::prepend_child
Adds a child at the front of parent's children and returns its id; a parent that is no longer in the tree yields the null id.
ArenaTree::previous_sibling
The sibling before id, or None when it is the first child.
ArenaTree::remove
Removes the node and everything below it, returning the value that was on it.
ArenaTree::set
Replaces the value behind id and reports whether the id named a node.
ArenaTree::siblings
The siblings of a node, the node itself included, in order.
DisjointSet
Union-find over 0 ..< n: every set is a tree whose root carries its size,
and find halves the path on the way up so repeated queries flatten the
structure without a second pass. Union by size keeps the trees shallow, which
together with path halving makes the amortised cost of an operation inverse
Ackermann — effectively constant.
test {
let sets : @tree.DisjointSet = @tree.DisjointSet::new()
let a = sets.add()
let b = sets.add()
let c = sets.add()
assert_true(sets.union(a, b))
assert_true(sets.connected(a, b))
assert_true(!sets.connected(a, c))
assert_true(sets.set_count() == 2)
}DisjointSet::add
Adds a singleton set and returns its index.
DisjointSet::clear
Removes every element, leaving a union-find with none.
DisjointSet::component_size
The size of the set that holds element.
DisjointSet::connected
Whether two elements are in the same set; an element that was never added is in no set.
DisjointSet::copy
An independent copy. Both sides own their own arrays, so a union or an added
element in one leaves the other as it was, and the path that find flattens
is flattened in one of them only.
DisjointSet::find
The representative of the set that holds element, with the path halved on
the way.
DisjointSet::is_empty
Whether no element has been added.
DisjointSet::length
The number of elements, not of sets.
DisjointSet::set_count
How many sets the elements are split into.
DisjointSet::set_size
The size of the set whose representative is root, which is what a caller
that already holds a root avoids a second find with.
DisjointSet::to_sets
Every set as the array of its members, representatives first.
DisjointSet::union
Joins the sets of two elements and reports whether they were apart.
DisjointSetMap
Union-find over keys of any type: the key is interned to an index on first
use, and the union-find runs on the indices.
test {
let sets : @tree.DisjointSetMap[String] = @tree.DisjointSetMap::new()
assert_true(sets.union("a", "b"))
assert_true(sets.connected("a", "b"))
assert_true(!sets.connected("a", "c"))
}DisjointSetMap::clear
Removes every key, leaving a union-find with none.
DisjointSetMap::component_size
The size of the set that holds key, zero when the key was never seen.
DisjointSetMap::connected
Whether two keys are in the same set; a key that was never interned is in no set.
DisjointSetMap::copy
An independent copy: the keys and the union-find under them are both new, so
a union on either side leaves the other as it was.
DisjointSetMap::find
The key that represents the set holding key, or None when the key was never interned.
DisjointSetMap::intern
The index of a key, adding it as a singleton the first time it is seen.
DisjointSetMap::is_empty
Whether no key has been interned.
DisjointSetMap::length
How many keys have been interned.
DisjointSetMap::new
A union-find over keys, with no key interned yet.
DisjointSetMap::set_count
How many sets the keys are split into.
DisjointSetMap::to_sets
Every set as the array of its members.
DisjointSetMap::union
Joins the sets of two keys, interning either if it is new, and reports whether they were apart.
Fenwick
A Fenwick tree: tree[i] holds the sum of the i & -i elements that end at
i, so a prefix sum reads one path to zero and an update writes one path to
the end. Both are O(log n) with small constants, which is why it beats a
segment tree for sums that only ever grow at a point.
test {
let fenwick : @tree.Fenwick[Int32] = @tree.Fenwick::new(length=5)
fenwick.add(0, 3)
fenwick.add(2, 4)
assert_true(fenwick.prefix_sum(3) == 7)
assert_true(fenwick.range_sum(1, 3) == 4)
let _ = fenwick.set(0, 10)
assert_true(fenwick.get(0) == Some(10))
assert_true(fenwick.lower_bound(5) == Some(0))
}Fenwick::add
Adds delta at index, which is the one point update a Fenwick tree supports.
Fenwick::from_array
A Fenwick tree over the values written out, with the prefix sums ready.
Fenwick::get
The value at index, or None past the last one.
Fenwick::length
How many positions the tree covers.
Fenwick::lower_bound
The first index whose prefix sum is strictly greater than target, which is
how a Fenwick tree answers "where does this weight get spent" while every
value stays non-negative. None when the whole tree does not reach it.
Fenwick::new
A Fenwick tree of length zeros.
Fenwick::prefix_sum
The sum of the first end elements.
Fenwick::range_sum
The sum of [start, end).
IntervalKey
A handle to one interval of an IntervalTree. Like a slot key, it carries
the generation of the slot it was handed out for, so a handle to a removed
interval reads as absent instead of reaching a later one.
IntervalKey::hash_combine
IntervalKey::not_equal
IntervalTree
Intervals over a key type, kept sorted by start with a running maximum of the
ends. That prefix maximum is what a point query walks back through: once a
prefix can no longer reach the point, no interval before it can either, so
the scan stops. Intervals are half-open, [start, end).
test {
let tree : @tree.IntervalTree[Int32, String] = @tree.IntervalTree::new()
let _ = tree.insert(start=0, end=10, "a")
let _ = tree.insert(start=5, end=15, "b")
assert_true(tree.query_point(7).length() == 2)
assert_true(tree.query_point(12).length() == 1)
assert_true(tree.query_point(20).length() == 0)
}IntervalTree::clear
Removes every interval; the keys issued before it name nothing afterwards.
IntervalTree::copy
A copy that owns its arrays: a change to either tree leaves the other alone, and a key names the same interval in both.
IntervalTree::get
The interval key names — its start, its end and its value — or None when the key names nothing.
IntervalTree::insert
fn[K, V] IntervalTree::insert(self : IntervalTree[K, V], start~ : K, end~ : K, value : V) -> IntervalKey[K]Adds the interval from start up to end, holding value, and returns the key that names it.
IntervalTree::is_empty
Whether the tree holds no interval.
IntervalTree::iter
The intervals in start order.
IntervalTree::length
How many intervals the tree holds.
IntervalTree::new
An empty tree of intervals ordered by start.
IntervalTree::new_by
An empty tree of intervals ordered by cmp over their starts.
IntervalTree::query_overlap
fn[K, V] IntervalTree::query_overlap(self : IntervalTree[K, V], start~ : K, end~ : K) -> Array[(K, K, V)]Every interval that meets [start, end).
IntervalTree::query_point
Every interval that covers point.
IntervalTree::remove
Removes the interval key names and returns it.
LazySegmentTree
A segment tree that also accepts a range update: a tag is applied to a whole
cover of a range and pushed down only when a later query or a partial update
has to look inside. apply says what a tag does to an aggregate, compose
merges an older tag into a newer one, and none is the tag that does
nothing.
test {
let tree : @tree.LazySegmentTree[Int32, Int32] = @tree.LazySegmentTree::from_array(
[1, 1, 1, 1],
op=(a, b) => a + b,
identity=0,
apply=(tag, value, span) => value + tag * span,
compose=(older, newer) => older + newer,
none=0,
)
tree.range_update(1, 3, 5)
assert_true(tree.query(0, 4) == 14)
assert_true(tree.query(1, 2) == 6)
}LazySegmentTree::from_array
fn[T, F] LazySegmentTree::from_array(values : ArrayView[T], op~ : (T, T) -> T, identity~ : T, apply~ : (F, T, Int) -> T, compose~ : (F, F) -> F, none~ : F) -> LazySegmentTree[T, F]A tree over the values written out, with the range update the other arguments describe.
LazySegmentTree::get
The value at index after the updates that cover it, or None past the last leaf.
LazySegmentTree::new
fn[T, F] LazySegmentTree::new(length~ : Int, op~ : (T, T) -> T, identity~ : T, apply~ : (F, T, Int) -> T, compose~ : (F, F) -> F, none~ : F) -> LazySegmentTree[T, F]An empty tree of length leaves, each holding identity, ready for range updates.
LazySegmentTree::query
The combination of the leaves from start up to end, with the updates that cover them already applied.
LazySegmentTree::range_update
fn[T, F] LazySegmentTree::range_update(self : LazySegmentTree[T, F], start : Int, end : Int, tag : F) -> UnitApplies update to every leaf from start up to end, leaving the answer to any later query correct.
LazySegmentTree::set
Replaces the value at index, keeping the updates that cover it.
OrderStatisticTree
A search tree that also answers by position: every node carries the size of
its subtree, so select and rank walk one path instead of counting.
Duplicates are not stored. The shape is that of a treap, which is what keeps
the depth logarithmic without rebalancing after every insert.
test {
let tree : @tree.OrderStatisticTree[Int32] = @tree.OrderStatisticTree::new()
for value in [5, 1, 9, 3] {
let _ = tree.insert(value)
}
assert_true(tree.select(0) == Some(1))
assert_true(tree.select(3) == Some(9))
assert_true(tree.rank(5) == 2)
assert_true(tree.count_range(2, 9) == 2)
}OrderStatisticTree::clear
Removes every key.
OrderStatisticTree::contains
Whether key is in the tree.
OrderStatisticTree::copy
A copy that owns its arrays: a change to either tree leaves the other alone.
OrderStatisticTree::count_less
How many keys in the tree are smaller than key.
OrderStatisticTree::count_range
The number of elements in [start, end), both ends compared by the tree's
own comparator.
OrderStatisticTree::first
The smallest key, or None when the tree is empty.
OrderStatisticTree::insert
Adds key and reports whether it was new; a key already in the tree is left alone.
OrderStatisticTree::is_empty
Whether the tree holds no key.
OrderStatisticTree::iter
The keys ascending.
OrderStatisticTree::last
The largest key, or None when the tree is empty.
OrderStatisticTree::length
How many keys the tree holds.
OrderStatisticTree::new
An empty tree ordered ascending by the element's own order.
OrderStatisticTree::new_by
An empty tree ordered by cmp, which reports the smaller of two elements as negative.
OrderStatisticTree::range
The keys from start up to end, ascending.
OrderStatisticTree::rank
The number of elements smaller than key.
OrderStatisticTree::remove
Removes key and reports whether it was there.
OrderStatisticTree::select
The element at position index, counting from zero.
OrderStatisticTree::to_array
The keys ascending, as a new array.
SegmentTree
A range aggregate over a fixed array: the leaves are the elements, an inner
node is op of its two children, and a query combines the O(log n) nodes
that cover a half-open range. The operation has to be associative, and
identity has to leave the other operand alone, which is what lets a query
start from nothing.
test {
let tree : @tree.SegmentTree[Int32] = @tree.SegmentTree::from_array(
[3, 1, 4, 1, 5],
op=(a, b) => a + b,
identity=0,
)
assert_true(tree.query(0, 3) == 8)
assert_true(tree.query_all() == 14)
let _ = tree.set(1, 10)
assert_true(tree.query(0, 3) == 17)
assert_true(tree.first_where(x => x >= 17) == Some(2))
}SegmentTree::copy
A copy that owns its nodes and the combining function: a change to either tree leaves the other alone.
SegmentTree::first_where
The first position whose prefix aggregate satisfies predicate, or None.
The descent relies on the predicate holding for a prefix once it holds for a
smaller one, which is what makes a segment tree able to answer "where does
this threshold get crossed" in O(log n).
SegmentTree::from_array
fn[T] SegmentTree::from_array(values : ArrayView[T], op~ : (T, T) -> T, identity~ : T) -> SegmentTree[T]A tree over the values written out, combining them with op at construction.
SegmentTree::get
The value at index, or None past the last leaf.
SegmentTree::length
How many leaves the tree covers.
SegmentTree::new
A tree over length positions, every one of them identity.
SegmentTree::query
The aggregate over [start, end), identity when the range is empty.
SegmentTree::query_all
The combination of every leaf, which is the answer to query(0, length).
SegmentTree::set
Replaces the value at index and brings the nodes above it up to date; reports whether the index was in range.
SegmentTree::to_array
The leaves in order, as a new array.
SkipList
A probabilistic ordered set. A node takes part in one level with probability
p and in the next with p again, so a search skips most of the list at the
top and refines as it descends; every level also stores how many nodes it
spans, which is what makes rank and select a single descent. The shape is
drawn from the seed, so a run replays exactly.
test {
let list : @tree.SkipList[Int32] = @tree.SkipList::new()
for value in [5, 1, 9, 3] {
let _ = list.insert(value)
}
assert_true(list.to_array() == [1, 3, 5, 9])
assert_true(list.rank(5) == 2)
assert_true(list.select(2) == Some(5))
}SkipList::clear
Removes every element, leaving the list at its initial height.
SkipList::contains
Whether value is in the list.
SkipList::first
The smallest element, or None when the list is empty.
SkipList::insert
Adds value and reports whether it was new.
SkipList::is_empty
Whether the list holds no element.
SkipList::last
The largest element, or None when the list is empty.
SkipList::length
How many elements the list holds.
SkipList::new
An empty list ordered ascending by the element's own order, with the level and density skip_list_options sets.
SkipList::new_by
An empty list ordered by cmp, with the level and density skip_list_options sets.
SkipList::range
The elements between start and end, both included by the list's own
comparator.
SkipList::rank
The number of elements smaller than value.
SkipList::remove
Removes value and reports whether it was there.
SkipList::select
The element at position index, counting from zero.
SkipListOptions
The shape of a skip list: how often a node is promoted to the next level, the
highest level it may reach, and the seed its coin flips come from. The
probability of 0.25 is what Redis uses, which keeps the level count low while
keeping the paths short.
SkipListOptions::not_equal
Treap
A map held as a treap: the keys are kept in order, each node carries a random
priority that keeps the tree balanced, and split and merge cut and join
in one path. range walks the keys in order between two bounds.
test {
let tree : @tree.Treap[Int32, String] = @tree.Treap::new()
let _ = tree.set(2, "b")
let _ = tree.set(1, "a")
let _ = tree.set(3, "c")
assert_true(tree.get(2) == Some("b"))
assert_true(tree.to_array() == [(1, "a"), (2, "b"), (3, "c")])
assert_true(tree.remove(2) == Some("b"))
}Treap::contains
Whether key has a value.
Treap::first
The entry with the smallest key, or None when the tree is empty.
Treap::is_empty
Whether the tree holds no entry.
Treap::last
The entry with the largest key, or None when the tree is empty.
Treap::length
How many entries the tree holds.
Treap::merge
Joins two trees whose key ranges do not interleave.
Treap::new
An empty tree ordered ascending by the key's own order.
Treap::new_by
An empty tree ordered by cmp, which reports the smaller of two keys as negative.
Treap::range
The entries whose key is from start up to end, in key order.
Treap::remove
Removes key and returns the value it held.
Treap::set
Stores value under key and returns the value it replaced.
Treap::split
Splits the tree at key into the part below it and the part at or above it.
TreeId
A handle to one node of an ArenaTree: the slot the node occupies and the
generation of that slot when the handle was handed out, so a handle to a
removed node reads as absent rather than reaching whoever took the slot.
skip_list_options
The preset: a quarter of the nodes climb to the next level, and thirty-two
levels cover 4^32 entries.
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