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
ArenaTree::ancestors
The root first, then each ancestor up to it.
ArenaTree::children
The ids of the children, in order.
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
ArenaTree::insert_after
ArenaTree::insert_before
ArenaTree::next_sibling
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
ArenaTree::previous_sibling
ArenaTree::remove
Removes the node and everything below it, returning the value that was on it.
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::component_size
The size of the set that holds element.
DisjointSet::find
The representative of the set that holds element, with the path halved on
the way.
DisjointSet::length
The number of elements, not of sets.
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::component_size
The size of the set that holds key, zero when the key was never seen.
DisjointSetMap::connected
DisjointSetMap::find
DisjointSetMap::intern
The index of a key, adding it as a singleton the first time it is seen.
DisjointSetMap::to_sets
Every set as the array of its members.
DisjointSetMap::union
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::from_array
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::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::copy
IntervalTree::get
IntervalTree::insert
fn[K, V] IntervalTree::insert(self : IntervalTree[K, V], start~ : K, end~ : K, value : V) -> IntervalKey[K]IntervalTree::iter
The intervals in start order.
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
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]LazySegmentTree::get
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]LazySegmentTree::query
LazySegmentTree::range_update
fn[T, F] LazySegmentTree::range_update(self : LazySegmentTree[T, F], start : Int, end : Int, tag : F) -> UnitLazySegmentTree::set
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
OrderStatisticTree::contains
OrderStatisticTree::copy
OrderStatisticTree::count_less
OrderStatisticTree::count_range
The number of elements in [start, end), both ends compared by the tree's
own comparator.
OrderStatisticTree::insert
OrderStatisticTree::is_empty
OrderStatisticTree::iter
OrderStatisticTree::length
OrderStatisticTree::new
OrderStatisticTree::new_by
OrderStatisticTree::range
OrderStatisticTree::rank
The number of elements smaller than key.
OrderStatisticTree::remove
OrderStatisticTree::select
The element at position index, counting from zero.
OrderStatisticTree::to_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::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]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.
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::insert
Adds value and reports whether it was new.
SkipList::new
SkipList::new_by
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::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::merge
Joins two trees whose key ranges do not interleave.
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 9 hours ago
102 downloads