🥮 mooncakes.io

    moonstl

    Data structures and algorithms the MoonBit core library leaves out.

    data-structures
    algorithms
    collections
    containers
    stl
    moonbit
    index-map
    index-set
    multimap
    bimap
    counter
    flat-map
    sorted-map
    range-map
    trie
    radix-tree
    lru-cache
    lfu-cache
    arc-cache
    expiring-cache
    memoize
    sorting
    selection
    bisect
    binary-search
    permutations
    combinations
    powerset
    partition
    merge
    ring-buffer
    slotmap
    gap-buffer
    bit-vector
    bit-set
    linked-list
    binary-heap
    fibonacci-heap
    pairing-heap
    min-max-heap
    radix-heap
    disjoint-set
    union-find
    segment-tree
    fenwick-tree
    interval-tree
    skip-list
    treap
    bloom-filter
    cuckoo-filter
    count-min-sketch
    hyperloglog
    theta-sketch
    t-digest
    string-search
    suffix-array
    suffix-automaton
    diff
    rope
    perfect-hash
    Download zip
    Version
    0.1.2
    License
    Apache-2.0
    Repository
    Last updated
    4 hours ago
    Downloads
    102

    #moonstl

    Data structures and algorithms for MoonBit: the containers, caches and sequence algorithms that the core library leaves out, in one module with one package per family.

    Live showcase — a workbench of twenty-three structures running this module compiled to WebAssembly, the ten package families, and an API reference generated from the interfaces: https://moonbitstack.github.io/moonstl.

    Live showcase — a workbench of twenty-three structures running this module compiled to WebAssembly, the ten package families, and an API reference generated from the interfaces: https://moonbitstack.github.io/moonstl.

    ///|
    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(1), Some(("b", 2)))
      @test.assert_eq(map.get_index_of("a"), Some(0))
    }

    #Packages

    PackageCarries
    specRefused, the one error type; hash_seed, the per-process seed
    seqRingBuffer, Slab, SlotMap, DenseSlotMap, SecondaryMap, GapBuffer, BitVec, BitSet, SparseSet, LinkedList
    mapIndexMap, IndexSet, MultiMap, SortedMultiMap, BiMap, Counter, DefaultMap, ChainMap, FlatMap, FlatSet, FlatMultiMap, FlatMultiSet, RangeMap, RangeSet, Trie, RadixTree
    heapDaryHeap, IndexHeap, PairingHeap, FibonacciHeap, MinMaxHeap, RadixHeap
    treeDisjointSet, DisjointSetMap, SegmentTree, LazySegmentTree, Fenwick, IntervalTree, OrderStatisticTree, SkipList, Treap, ArenaTree
    cacheLruCache, LfuCache, ArcCache, ExpiringCache, memoize, CacheStats
    sketchBloomFilter, CuckooFilter, CountMinSketch, HyperLogLog, ThetaSketch, TDigest
    textKmp, BoyerMoore, AhoCorasick, SuffixArray, SuffixAutomaton, SequenceMatcher, the diff formats, Rope
    phfPhfMap, PhfSet, PhfOrderedMap, PhfOrderedSet, PhfBuilder
    cmd/phfgenthe generator behind #phf.map and its three siblings
    algosearching, selection, partitioning, merging and lazy adaptors over ArrayView and Iter, plus the combinatoric generators

    The module root re-exports the types of these packages, so one import is enough to name them.

    #Index maps: order and position

    IndexMap keeps insertion order and gives every entry a position. A lookup is a hash lookup; a position lookup is an array index.

    ///|
    test {
      let map : @map.IndexMap[Int32, String] = @map.IndexMap::new()
      let _ = map.set(3, "three")
      let _ = map.set(1, "one")
      @test.assert_eq(map.keys().to_array(), [3, 1])
      map.sort_keys()
      @test.assert_eq(map.keys().to_array(), [1, 3])
      let _ = map.swap_remove(1)
      @test.assert_eq(map.to_array(), [(3, "three")])
    }

    remove is swap_remove: the last entry moves into the hole and the container stays dense in O(1). A caller that needs the remaining positions to stay contiguous calls shift_remove, which is O(n).

    #Caches

    A cache owns a policy, not a data structure: the entries live in one slab of slots and the policy decides which slot is handed back when the capacity is reached.

    ///|
    test {
      let cache : @cache.LruCache[String, Int32] = @cache.LruCache::new(capacity=2)
      let _ = cache.set("a", 1)
      let _ = cache.set("b", 2)
      let _ = cache.get("a")
      @test.assert_eq(cache.set("c", 3), Some(("b", 2)))
      @test.assert_eq(cache.stats().hit_rate(), 1.0)
    }

    set returns what the insert displaced — the pair it replaced when the key was already there, the pair the policy dropped otherwise. on_evict sees evictions only: a remove is the caller's own doing and is not reported.

    ArcCache moves the share of the cache given to frequent entries as it sees repeats, and lists reports the four list sizes so the adaptation can be watched. ExpiringCache reads no clock of its own: it takes now, and every deadline is in that clock's units, which is what lets a test move time without waiting.

    #Algorithms

    Functions that leave the run alone take ArrayView[T]; functions that change it take Array[T] and say so with _in_place; everything lazy takes and returns an Iter[T].

    ///|
    test {
      let run : Array[Int32] = [5, 1, 4, 2]
      @test.assert_eq(@algo.bisect_left(@algo.sorted(run[:]), 4), 2)
      @algo.nth_element_in_place(run, 1)
      @test.assert_eq(run[1], 2)
      @test.assert_eq(@algo.chunks(run.iter(), 2).to_array().length(), 2)
    }

    The combinatoric generators are structs with next() and iter(), and they enumerate in the order Python's itertools produces, so a reader can check one against the other.

    ///|
    test {
      let pairs : @algo.Permutations[Int32] = @algo.Permutations::new([1, 2, 3], length=2)
      @test.assert_eq(pairs.iter().to_array(), [
        [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2],
      ])
    }

    #Handles, heaps and trees

    A SlotMap hands out SlotKeys that carry the generation of the slot they were issued for, so a key to a removed entry reads as absent instead of reaching the next occupant; a Slab hands out plain indices and makes the opposite trade.

    ///|
    test {
      let slots : @seq.SlotMap[String] = @seq.SlotMap::new()
      let first = slots.insert("a")
      let _ = slots.remove(first)
      let _ = slots.insert("b")
      @test.assert_eq(slots.get(first), None)
      @test.assert_eq(slots.length(), 1)
    }

    The heaps cover the two shapes an array can take and the two that need nodes: a d-ary heap and an index heap where every entry carries a handle, then a pairing heap and a Fibonacci heap whose decrease_key costs nothing to undo. MinMaxHeap answers from both ends and RadixHeap refuses a key below the last one popped rather than reordering.

    ///|
    test {
      let heap : @heap.IndexHeap[Int32] = @heap.IndexHeap::new()
      let handle = heap.insert(9)
      let _ = heap.insert(4)
      let _ = heap.update(handle, 1)
      @test.assert_eq(heap.pop(), Some(1))
    }

    The trees are the range structures an index needs: a segment tree combines an associative operation over a range, a lazy one takes a range update, a Fenwick tree keeps prefix sums that grow at a point, and an interval tree answers which spans cover a point. OrderStatisticTree and SkipList answer by position as well as by key.

    ///|
    test {
      let tree : @tree.SegmentTree[Int32] = @tree.SegmentTree::from_array(
        [3, 1, 4, 1, 5], op=(a : Int32, b : Int32) => a + b, identity=0,
      )
      @test.assert_eq(tree.query(1, 4), 6)
    }

    #Sketches, strings and perfect hashes

    When an exact answer costs more than it is worth, the sketch package trades accuracy for a fixed amount of memory: a Bloom filter with no false negatives, a Count-Min that never under-estimates, a HyperLogLog for a distinct count, and a t-digest for quantiles. Each round-trips through its own byte format.

    ///|
    test {
      let log : @sketch.HyperLogLog[Int32] = @sketch.HyperLogLog::new(precision=12)
      for i in 0..<1000 {
        log.add(i)
      }
      let estimate = log.estimate()
      @test.assert_eq(estimate > 900.0 && estimate < 1100.0, true)
    }

    text answers the string questions a matcher asks — one pattern, many patterns, every occurrence, the longest repeated substring — and SequenceMatcher follows the algorithm Python's difflib uses, so the diffs line up with the ones Python prints.

    ///|
    test {
      let automaton : @text.SuffixAutomaton = @text.SuffixAutomaton::new("banana")
      @test.assert_eq(automaton.count_occurrences("ana"), 2)
    }

    A phf table hashes its keys once, while it is built, so a lookup is a single comparison; the layout is a plain value, which is what lets a generated module carry one as a literal.

    #phf.map, #phf.ordered_map, #phf.set and #phf.ordered_set go on a top-level let holding a written-out list. The generator lays the table out while the program is built; the list stays as it is and the table reads it.

    #phf.ordered_map
    let keywords : Array[(String, Token)] = [("fn", Fn), ("let", Let), ("match", Match)]

    fn token(word : String) -> Token? {
      keywords_phf.get(word)
    }

    The keys are literal String, Int, Int64 or UInt64 values; the values are any expressions. The table is keywords_phf, public when the list is. name="..." renames it, and build="search", "quick" or "minimal" with seed="N" set the layout as PhfOptions does. A list changed without running the generator again either still fits its layout or stops the program at start-up with the reason; --check catches it in CI.

    The generator wires in as a dev_build rule, in moon.mod:

    rule(name: "phf", command: "moonx moonbitstack/moonstl/cmd/phfgen -C \"$mod_dir\" \"$input\" -o \"$output\"")

    and in the moon.pkg of the package, which imports moonbitstack/moonstl/phf:

    dev_build(rule: "phf", input: "keywords.mbt", output: "keywords.g.mbt")
formatter(ignore: [ "keywords.g.mbt" ])

    src/examples/keywords is a working copy of both files.

    #Names, order and failure

    Method names follow the core library: new, from_array, from_iter, length, is_empty, clear, copy, iter, get returning Option, at aborting.

    Ordered containers take Compare and also a _by form that takes a comparator; hashed containers take Hash + Eq and a hash_seed. The seed is drawn once per process from the platform's entropy, so a table cannot be laid out for a key set an attacker chose; pin it with hash_seed=0 when a run has to be reproducible.

    Input that cannot be used is refused with one type, Refused: a capacity of zero, a rate outside (0, 1), a branching factor below 2, two sketches of different shape asked to combine, a range inserted where the overlap policy forbids it. A lookup that finds nothing returns None instead, and an out-of-range index aborts as Array does.

    ///|
    test {
      let built : Result[Unit, Int32] = try {
        let cache : @cache.LruCache[String, Int32] = @cache.LruCache::new(capacity=0)
        let _ = cache
        Ok(())
      } catch {
        @spec.Refused::Capacity(got~) => Err(got)
        _ => Err(-1)
      }
      @test.assert_eq(built, Err(0))
    }

    #Conformance

    The behaviour of the structures is pinned to the result two independent reference implementations produce for the same inputs. The values are computed once and replayed, so a change that drifts from the reference fails the suite rather than passing quietly. Probabilistic structures are held to the bound their construction promises instead of to one implementation's bits.

    PackageWhat the reference pins
    seqring-buffer overwrite, bit-vector rank and select, gap-buffer edits, list splices
    mapcounter counts and most_common, flat-set order and index, index-map positions, range-set gaps
    heappop order of the d-ary, pairing and fibonacci heaps, min-max alternation, radix pop order
    treefenwick and segment range sums, disjoint-set components, treap in-order
    cachelru and lfu eviction, the deadline an entry drops at
    sketchcount-min within its error, hyperloglog within three standard errors, t-digest near the true quantile, bloom free of false negatives
    textkmp and aho-corasick occurrences, the z-function, suffix order, the matcher ratio
    phfthe map answers its key set, the ordered map gives each key its index
    algobisect on every probe, the generators in enumeration order, selection, merge, prefix and rotate

    Every check passes. The vectors and the two generators that agree on them live in scripts/.

    #Checks

    moon check --target all --deny-warn
moon build --target all
moon test --target all

    #Licence

    Apache-2.0.

    AhoCorasick

    source

    Many patterns matched in one pass: a trie whose nodes also carry failure links, so the text is read once and every occurrence is reported as soon as its last code unit is read. Overlapping matches all appear, including suffixes of longer ones, which the output chain walks without visiting nodes that match nothing. Build is O(total pattern length), search O(n + matches).

    Matches come out in text order of their last code unit, longest first among those that end at the same place. A zero-length pattern is reported at every offset, before the matches ending at that offset.

    test {
      let ac = @text.AhoCorasick::new(["he", "she", "his", "hers"])
      @test.assert_eq(ac.search_all("ushers").to_array(), [(1, 1), (0, 2), (3, 2)])
      assert_true(ac.is_match("ushers"))
      assert_false(ac.is_match("us"))
    }

    ArcCache

    source

    A cache that keeps the recency and the frequency of what it sees in balance, in the manner of ARC: a hit on a re-requested key raises the share of the cache given to frequent entries (recent_target moves up), a key that falls back into the ghost lists takes that share down. lists reports the four list sizes, which is how the adaptation is observed.

    test {
      let cache : @cache.ArcCache[String, Int32] = @cache.ArcCache::new(capacity=2)
      let _ = cache.set("a", 1)
      let _ = cache.set("b", 2)
      let _ = cache.get("a")
      let _ = cache.set("c", 3)
      let (t1, t2, b1, b2) = cache.lists()
      @test.assert_eq(t1 + t2, 2)
      @test.assert_eq(b1 + b2 <= 2, true)
    }

    ArenaTree

    source

    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)
    }

    BiMap

    source

    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)
    }

    BitSet

    source

    A set of non-negative integers stored as bits: membership is a bit test, and the set operations run word by word. length counts the elements, not the range, because the range has no ceiling.

    test {
      let set : @seq.BitSet = @seq.BitSet::new()
      @test.assert_eq(set.insert(3), true)
      @test.assert_eq(set.insert(3), false)
      @test.assert_eq(set.contains(3), true)
      @test.assert_eq(set.length(), 1)
      @test.assert_eq(set.select(0), Some(3))
      @test.assert_eq(set.rank(4), 1)
    }

    BitVec

    source

    A vector of bits with a length: bit i lives in word i / 64 at bit i % 64, and the bits past the length are always zero.

    test {
      let bits : @seq.BitVec = @seq.BitVec::new()
      bits.push(true)
      bits.push(false)
      bits.push(true)
      @test.assert_eq(bits.length(), 3)
      @test.assert_eq(bits.get(2), Some(true))
      @test.assert_eq(bits.count_ones(), 2)
    }

    BloomFilter

    source

    A Bloom filter answers membership with no false negatives: an item it has taken in is always reported as possibly present. Absent items are reported as present at most at the requested rate, and the bit count follows from the expected item count and that rate, so no caller picks a size by hand.

    The item type is hashed with the filter's seed, which is stored with the bits so that a decoded filter answers exactly as the one that wrote it.

    BloomOptions

    source

    The two knobs of a Bloom filter. A record rather than two parameters, because callers change one of them far more often than both.

    BoyerMoore

    source

    One pattern matched with the Boyer-Moore scan: it compares the pattern from its last character backwards and skips ahead with the bad-character and good-suffix rules, so a mismatch usually costs less than one comparison per text position. Worst case is still O(n), build is O(m + sigma).

    test {
      let bm = @text.BoyerMoore::new("needle")
      assert_eq(bm.search("a needle in a haystack"), Some(2))
      assert_eq(bm.search("haystack"), None)
    }

    CacheStats

    source

    Counters every cache keeps. hits and misses count lookups, evictions counts the entries a policy dropped to make room — a remove is not an eviction, and neither is a replacement.

    ChainMap

    source

    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))
    }

    Combinations

    source

    The k-element subsets, in lexicographic order of positions.

    test {
      let combinations : @algo.Combinations[Int32] = @algo.Combinations::new(
        [1, 2, 3, 4],
        k=2,
      )
      @test.assert_eq(combinations.iter().to_array(), [
        [1, 2],
        [1, 3],
        [1, 4],
        [2, 3],
        [2, 4],
        [3, 4],
      ])
    }

    CombinationsWithReplacement

    source

    The k-element selections that may repeat an element, in lexicographic order of positions.

    test {
      let with_repeats : @algo.CombinationsWithReplacement[Int32] = @algo.CombinationsWithReplacement::new(
        [1, 2],
        k=2,
      )
      @test.assert_eq(with_repeats.iter().to_array(), [[1, 1], [1, 2], [2, 2]])
    }

    CountMinSketch

    source

    A sketch that counts: the estimate for an item is the smallest counter its probes land on, which never underestimates because every counter it reads was incremented by that item too. The width and depth come from the error the caller tolerates, so nobody picks them by hand.

    test {
      let sketch : @sketch.CountMinSketch[String] = @sketch.CountMinSketch::new(
        epsilon=0.01,
        confidence=0.99,
      )
      for _ in 0..<5 {
        sketch.insert("a")
      }
      assert_true(sketch.estimate("a") >= 5)
      assert_true(sketch.estimate("b") == 0)
      assert_true(sketch.total() == 5L)
    }

    Counter

    source

    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)
    }

    CuckooFilter

    source

    A filter that can forget: every item lives as a short fingerprint in one of two buckets, and the second bucket is computed from the fingerprint alone, so a removal does not have to remember where the item went. An insert that cannot place its fingerprint after a bounded number of kicks reports failure instead of looping, which is the one thing a Cuckoo filter trades away: its false-positive rate, unlike a Bloom filter's, stays flat as it fills.

    test {
      let filter : @sketch.CuckooFilter[String] = @sketch.CuckooFilter::new(
        expected_items=100,
      )
      assert_true(filter.insert("a"))
      assert_true(filter.may_contain("a"))
      assert_true(filter.remove("a"))
      assert_true(!filter.may_contain("a"))
    }

    CuckooOptions

    source

    The shape of a Cuckoo filter. A fingerprint of fingerprint_bits is short enough that the whole table fits in cache and long enough that a false positive stays rare; four slots per bucket is the number the paper measured.

    DaryHeap

    source

    A d-ary heap: a heap laid out in a contiguous array where every node has up to arity children.

    A binary heap does one comparison per level; a 4-ary heap does three but halves the number of levels, and the children of one node sit next to each other in memory, so a wider heap usually wins on modern caches. arity: 4 is Boost.Heap's default for d_ary_heap.

    The heap is a multiset: it does not remove duplicates, and its iteration order is the internal array order, which is only partially ordered. Use into_sorted_array when the order matters.

    test {
      let heap : @heap.DaryHeap[Int32] = try! @heap.DaryHeap::new()
      heap.push(3)
      heap.push(1)
      heap.push(2)
      assert_true(heap.peek() == Some(1))
      assert_true(heap.pop() == Some(1))
      assert_true(heap.length() == 2)
    }

    DefaultMap

    source

    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))
    }

    DenseSlotMap

    source

    A slot map that also keeps the entries in a dense array, so iteration follows insertion order and a removal moves the last entry into the hole. The keys are the same SlotKeys a SlotMap hands out; what changes is that the entries are contiguous while they live, which is what a caller who walks the whole container wants.

    DisjointSet

    source

    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)
    }

    DisjointSetMap

    source

    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"))
    }

    ExpiringCache

    source

    A cache whose entries expire: an entry is dropped when it is read after its deadline, when a purge finds it, and by the least-recently-used rule when the capacity is full. Expiry is lazy, so a purge is the only thing that walks the expired entries in bulk.

    The cache never reads a clock of its own — now is the caller's, which is what lets a test move time without waiting. ttl and every deadline are in the units of that clock.

    test {
      let mut clock : Int64 = 0L
      let cache : @cache.ExpiringCache[String, Int32] = @cache.ExpiringCache::new(
        ttl=10L,
        capacity=2,
        now=() => clock,
      )
      let _ = cache.set("a", 1)
      @test.assert_eq(cache.get("a"), Some(1))
      clock = 11L
      @test.assert_eq(cache.get("a"), None)
    }

    Fenwick

    source

    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))
    }

    FibonacciHeap

    source

    A Fibonacci heap: roots and children sit in circular doubly linked lists, so an insert only splices one node in, a meld only joins two lists, and a decrease_key only cuts one subtree loose — each of them constant amortised time. The price is paid on pop, which consolidates the roots by degree.

    test {
      let heap : @heap.FibonacciHeap[Int32] = @heap.FibonacciHeap::new()
      let a = heap.insert(5)
      let _ = heap.insert(2)
      let _ = heap.insert(8)
      assert_true(heap.peek() == Some(2))
      assert_true(heap.decrease_key(a, 1))
      assert_true(heap.pop() == Some(1))
    }

    FlatMap

    source

    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))
    }

    FlatMultiMap

    source

    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)
    }

    FlatMultiSet

    source

    A flat multiset keeps repeats in sorted order and counts them.

    FlatSet

    source

    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))
    }

    GapBuffer

    source

    An array with a hole in it: the elements before the hole are kept in order, the ones after it are kept reversed, and moving the hole is the only operation that shifts more than one element. Typing at the hole is therefore constant time, which is what a text editor's buffer wants.

    test {
      let buffer : @seq.GapBuffer[Int32] = @seq.GapBuffer::new()
      buffer.insert(0, 1)
      buffer.insert(1, 3)
      buffer.insert(1, 2)
      @test.assert_eq(buffer.to_array(), [1, 2, 3])
      @test.assert_eq(buffer.remove(1), Some(2))
      @test.assert_eq(buffer.to_array(), [1, 3])
    }

    GrayCode

    source

    The reflected binary code over bits positions: consecutive words differ in exactly one bit, and the first is all zeroes.

    test {
      let code : @algo.GrayCode = @algo.GrayCode::new(2)
      @test.assert_eq(code.iter().take(4).to_array(), [
        [false, false],
        [false, true],
        [true, true],
        [true, false],
      ])
    }

    Growth

    source

    How a Bloom filter behaves once it holds more items than it was sized for.

    HeapKey

    source

    A stable handle to one entry of an addressable heap.

    index names the entry's slot and generation the state that slot was in when the handle was issued. A slot is reused after its entry is removed and the generation is then bumped, so a handle kept past a removal names nothing and every method taking one reports a miss instead of reaching the element that took the slot. The type parameter names the element type the handle came from, which keeps a handle from one heap type from being passed to another; it holds no data.

    HyperLogLog

    source

    An estimate of how many distinct items were added, from one small register per bucket: each item sets its bucket to the longest run of leading zeroes its hash produced, and the harmonic mean of the registers is the estimate. The error is about 1.04 / sqrt(m), so a thousand registers buy three percent, and neither the memory nor the insert cost depends on the count.

    test {
      let log : @sketch.HyperLogLog[Int32] = @sketch.HyperLogLog::new(precision=12)
      for i in 0..<1000 {
        log.add(i)
      }
      let estimate = log.estimate()
      assert_true(estimate > 900.0)
      assert_true(estimate < 1100.0)
    }

    IndexHeap

    source

    A binary heap whose entries are addressed by HeapKey: an update or a remove_at reaches one element without searching, because every slot knows its position in the heap array and every position knows its slot.

    test {
      let heap : @heap.IndexHeap[Int32] = @heap.IndexHeap::new()
      let a = heap.insert(5)
      let b = heap.insert(1)
      assert_true(heap.update(a, 0))
      assert_true(heap.peek() == Some(0))
      assert_true(heap.remove_at(b) == Some(1))
      assert_true(heap.length() == 1)
    }

    IndexMap

    source

    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)))
    }

    IndexSet

    source

    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))
    }

    IntervalKey

    source

    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.

    IntervalTree

    source

    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)
    }

    JoinEntry

    source

    The result of stepping two ordered runs side by side: an element of the first run only, of the second only, or a pair of equal elements.

    Kmp

    source

    One pattern matched with the Knuth-Morris-Pratt scan: O(n + m) time with a worst-case guarantee, because the failure table never lets the text pointer move backwards. Offsets are UTF-16 code units, the indices String uses.

    test {
      let kmp = @text.Kmp::new("ab")
      assert_eq(kmp.search("cababc"), Some(1))
      assert_eq(kmp.search_all("abab").to_array(), [0, 2])
    }

    LazySegmentTree

    source

    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)
    }

    LfuCache

    source

    A least-frequently-used cache: an insert past the capacity drops the entry with the smallest access count, and among equals the one that has gone untouched the longest. A hit moves the entry into the list of the next frequency, which is what keeps both operations O(1).

    test {
      let cache : @cache.LfuCache[String, Int32] = @cache.LfuCache::new(capacity=2)
      let _ = cache.set("a", 1)
      let _ = cache.set("b", 2)
      let _ = cache.get("a")
      let _ = cache.set("c", 3)
      @test.assert_eq(cache.get("b"), None)
      @test.assert_eq(cache.frequency("a"), Some(2))
    }

    LinkedList

    source

    A doubly linked list: splicing one list onto another and splitting a list in two are constant time, because neither moves an element — they only relink nodes. Indexing walks, which is the price of that.

    test {
      let list : @seq.LinkedList[Int32] = @seq.LinkedList::new()
      list.push_back(1)
      list.push_back(2)
      list.push_front(0)
      @test.assert_eq(list.to_array(), [0, 1, 2])
      @test.assert_eq(list.pop_front(), Some(0))
      @test.assert_eq(list.length(), 2)
    }

    LruCache

    source

    A least-recently-used cache with a fixed capacity: get marks an entry as the most recent, and an insert past the capacity drops the entry that has gone untouched the longest.

    test {
      let cache : @cache.LruCache[String, Int32] = @cache.LruCache::new(capacity=2)
      let _ = cache.set("a", 1)
      let _ = cache.set("b", 2)
      let _ = cache.get("a")
      let _ = cache.set("c", 3)
      @test.assert_eq(cache.get("b"), None)
      @test.assert_eq(cache.get("a"), Some(1))
    }

    Match

    source

    One block the two runs share: where it starts in each and how long it is.

    MinMaxHeap

    source

    A double-ended priority queue: both the smallest and the largest element are one comparison away, and both can be popped in logarithmic time. The array alternates min levels and max levels, so the smallest is at the root and the largest is one of its two children.

    test {
      let heap : @heap.MinMaxHeap[Int32] = @heap.MinMaxHeap::new()
      for value in [5, 1, 9, 3, 7] {
        heap.push(value)
      }
      assert_true(heap.peek_min() == Some(1))
      assert_true(heap.peek_max() == Some(9))
      assert_true(heap.pop_min() == Some(1))
      assert_true(heap.pop_max() == Some(9))
    }

    MultiMap

    source

    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)
    }

    MultiSet

    source
    type MultiSet[K] = 
    MultiMap    [K, Unit]

    A multiset is a multimap whose values carry no information.

    Opcode

    source

    One step of a diff: what happened to a[i1..i2] and b[j1..j2].

    Order

    source

    Which end of the order a heap pops from.

    Min pops the element that compares smallest and is what Python's heapq and Java's PriorityQueue do; Max pops the largest and is what C++ and core's PriorityQueue do. The two are one comparator apart, so the direction is a value rather than a second type.

    OrderStatisticTree

    source

    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)
    }

    Overflow

    source

    What a full RingBuffer does with the element it cannot keep. Overwrite drops the element at the opposite end, which is how a fixed-size buffer of recent samples is usually written; Refuse leaves the buffer untouched and hands the new element back, so a caller that must not lose data sees the refusal in the return value instead of an exception.

    Overlap

    source

    What an insert does when the new range meets one that is already there.

    PairingHeap

    source

    A heap of linked nodes: every node keeps its children in a list and a meld only links two roots, so insert and meld are constant time and a pop pays for the pairwise merging of the children it uncovers. Its update and remove_at reach a node through a HeapKey and detach it without a search, which is what a scheduler that cancels timers needs.

    test {
      let heap : @heap.PairingHeap[Int32] = @heap.PairingHeap::new()
      let a = heap.insert(5)
      let b = heap.insert(2)
      let _ = heap.insert(9)
      assert_true(heap.peek() == Some(2))
      assert_true(heap.update(a, 1))
      assert_true(heap.peek() == Some(1))
      assert_true(heap.remove_at(b) == Some(2))
      assert_true(heap.pop() == Some(1))
    }

    Permutations

    source

    The k-permutations of a run, in the order Python's itertools.permutations produces them: the positions advance like an odometer, so the first element changes slowest.

    test {
      let permutations : @algo.Permutations[Int32] = @algo.Permutations::new(
        [1, 2, 3],
        length=2,
      )
      @test.assert_eq(permutations.iter().to_array(), [
        [1, 2],
        [1, 3],
        [2, 1],
        [2, 3],
        [3, 1],
        [3, 2],
      ])
    }

    PhfBuild

    source

    The trade PhfBuilder makes between build time, table size and stored index.

    Search is the phf crate's default: a displacement table over a table of about 10/9 slots per key, found by searching each bucket's displacement. Quick follows quickphf: the table holds about two slots per key, so almost every bucket is placed at displacement zero and the search disappears. Minimal follows entropy-map: the entries are kept dense and the slot is turned into an entry index by a rank structure over the occupied slots.

    PhfBuilder

    source

    Builds a perfect hash table from the entries it is given. A key may appear once: the second entry for the same key is refused, because a table with two entries in one bucket would have no displacement that places both.

    test {
      let builder : @phf.PhfBuilder[String, Int32] = @phf.PhfBuilder::new()
      builder.entry("x", 1)
      let refused = try {
        builder.entry("x", 2)
        Ok(())
      } catch {
        @spec.Refused::DuplicateValue => Err(true)
        _ => Err(false)
      }
      assert_true(refused == Err(true))
    }

    PhfLayout

    source

    A perfect hash layout: everything a lookup needs that does not depend on the key or the value type.

    A key in bucket b with hash h sits in slot ((h & 0xFFFFFFFF) + disps[b]) % table_len. With build set to Minimal that slot is an intermediate value only: the map keeps a rank structure over the occupied slots and stores the entries densely.

    The fields are public because a generated module embeds one of these as a plain struct literal instead of running the builder at start-up. Nothing trusts such a literal: PhfMap::from_layout re-derives the slots from the keys it is given and refuses a layout that does not fit them.

    PhfMap

    source

    A table whose hash was computed while it was built, so a lookup is one hash, one displacement table read and one comparison — there is no probe sequence to walk and no cluster to fall into. The layout is a value, which is what lets a generated module carry one as a literal; from_layout re-derives every slot from the keys and refuses a layout that does not fit them.

    test {
      let builder : @phf.PhfBuilder[String, Int32] = @phf.PhfBuilder::new()
      builder.entry("a", 1)
      builder.entry("b", 2)
      let table = builder.build()
      assert_true(table.get("a") == Some(1))
      assert_true(table.get("b") == Some(2))
      assert_true(table.get("c") == None)
      assert_true(table.length() == 2)
    }

    PhfOptions

    source

    How a table is laid out. seed is fixed rather than drawn from the process entropy on purpose: the generated source is checked in and compared byte for byte, so the search has to start from the same place on every machine.

    PhfOrderedMap

    source

    A map that also reports the position its key was declared in, which is what a generated table wants when the order in the source is the order a reader should see.

    test {
      let builder : @phf.PhfBuilder[String, Int32] = @phf.PhfBuilder::new()
      builder.entry("b", 2)
      builder.entry("a", 1)
      let table = builder.build_ordered()
      assert_true(table.index("b") == Some(0))
      assert_true(table.index("a") == Some(1))
      assert_true(table.get("a") == Some(1))
    }

    PhfOrderedSet

    source

    A set whose elements keep the order they were declared in.

    PhfSet

    source

    A set with the same layout as PhfMap, holding only the keys.

    test {
      let builder : @phf.PhfBuilder[String, Unit] = @phf.PhfBuilder::new()
      builder.entry("in", ())
      let set = builder.build_set()
      assert_true(set.contains("in"))
      assert_true(!set.contains("out"))
    }

    Position

    source

    Where an element sits in a sequence that is being consumed.

    Powerset

    source

    Every subset, shortest first: the order chain.from_iterable(combinations(s, r) for r in range(len(s) + 1)) gives.

    test {
      let powerset : @algo.Powerset[Int32] = @algo.Powerset::new([1, 2])
      @test.assert_eq(powerset.iter().to_array(), [[], [1], [2], [1, 2]])
    }

    Product

    source

    The cartesian product of several runs, rightmost pool varying fastest, the order itertools.product uses.

    test {
      let pools : Array[ArrayView[Int32]] = [[1, 2][:], [3, 4][:]]
      let product : @algo.Product[Int32] = @algo.Product::new(pools)
      @test.assert_eq(product.iter().to_array(), [[1, 3], [1, 4], [2, 3], [2, 4]])
    }

    RadixHeap

    source

    A monotone heap over UInt64 keys: the key of a pushed entry may not be smaller than the key of the last one popped. Under that rule a pop costs O(log C) where C is the width of the key space, and it never compares two keys of different buckets — the bucket a key falls in already says which is smaller. That is what makes it a step faster than a comparison heap on integer keys, and why a key below the last pop is refused rather than reordered.

    test {
      let heap : @heap.RadixHeap[String] = @heap.RadixHeap::new()
      heap.push(5UL, "five")
      heap.push(1UL, "one")
      heap.push(9UL, "nine")
      assert_true(heap.pop_min() == Some((1UL, "one")))
      assert_true(heap.pop_min() == Some((5UL, "five")))
    }

    RadixTree

    source

    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)
    }

    RangeMap

    source

    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)
    }

    RangeSet

    source

    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)
    }

    Refused

    source

    The one error type, so a caller can catch it without naming the package.

    RingBuffer

    source

    A fixed-ceiling ring of elements. The storage is a plain array with the live elements starting at head and wrapping around, so every operation that touches an end is constant time whatever the length.

    capacity is a ceiling, not a reservation: the array starts empty and is doubled — up to the ceiling — as the buffer fills, and empty slots beyond len hold copies of an element already in the buffer. Those stale copies are outside every view the buffer hands out.

    Rope

    source

    A rope keeps its text in chunks and remembers where each chunk starts, so an offset can be found without flattening the whole document. Offsets are UTF-16 code units, as String counts them, and an edit that would split a surrogate pair is refused.

    test {
      let rope : @text.Rope = @text.Rope::from_string("hello world")
      rope.insert(5, ",")
      assert_true(rope.to_string() == "hello, world")
      rope.edit(start=0, end=5, "goodbye")
      assert_true(rope.to_string() == "goodbye, world")
      assert_true(rope.length() == 14)
    }

    RopeBuilder

    source

    Builds a rope by appending, which is what a reader or a parser wants: one chunk per append, and one reindex at the end.

    test {
      let builder : @text.RopeBuilder = @text.RopeBuilder::new()
      builder.append("one ")
      builder.append("two")
      let rope = builder.finish()
      assert_true(rope.to_string() == "one two")
    }

    RopeView

    source

    A window into a rope. It holds its own copy of the rope's chunk list, so an edit to the rope does not move the text under the window.

    test {
      let rope : @text.Rope = @text.Rope::from_string("abcdef")
      let window = rope.slice(start=2, end=4)
      assert_true(window.to_string() == "cd")
      assert_true(window.length() == 2)
    }

    SecondaryMap

    source

    A side table keyed by the slots of another map: it holds a value per slot and never invents a slot of its own. resize tells it how many slots the owner has; a key outside that range is refused, which is how a side table stays in step with the store it describes instead of quietly growing past it.

    SegmentTree

    source

    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))
    }

    SequenceMatcher

    source

    A matcher over two runs: it indexes the second one, finds the longest block the two share, and reports the matching blocks and the steps between them.

    test {
      let left : Array[Char] = "abcd".iter().to_array()
      let right : Array[Char] = "bcde".iter().to_array()
      let matcher : @text.SequenceMatcher[Char] = @text.SequenceMatcher::new(
        left[:],
        right[:],
      )
      @test.assert_eq(matcher.ratio() > 0.7, true)
      let blocks = matcher.get_matching_blocks()
      @test.assert_eq(blocks.length(), 2)
    }

    SequenceMatcherOptions

    source

    What counts as junk, and whether the popular-element heuristic runs.

    autojunk is difflib's defence against a diff of a run with hundreds of identical lines: an element of a run of two hundred or more that appears in more than one percent of it is treated as junk, because matching on it would produce a diff no reader can use.

    SkipList

    source

    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))
    }

    SkipListOptions

    source

    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.

    Slab

    source

    An index-addressed store that reuses the indices it frees. An index carries no generation, so a caller that keeps one past a remove and a later insert reaches the new occupant: that is the trade a Slab makes for handing out plain integers, and the reason SlotMap exists beside it.

    SlotKey

    source

    A handle to a slot of a SlotMap or a DenseSlotMap. The index says which slot, the generation says which occupant of that slot: a slot that is freed and reused raises its generation, so a key handed out earlier can never reach the new occupant. The type parameter exists only to stop a key of one map from being passed to another; it carries no value.

    SlotMap

    source

    A store whose handles stay valid only while their slot keeps its occupant: every slot carries a generation, a key carries the generation it was handed out under, and a freed slot raises its generation when it is reused. A stale key therefore reads as absent instead of reaching a stranger.

    SortedMultiMap

    source

    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"])
    }

    SortedMultiSet

    source

    A sorted multiset is a sorted multimap whose values carry no information.

    SparseSet

    source

    A set whose elements are kept densely, one array for the elements and one index from element to its position. Membership is a lookup and iteration walks contiguous memory, which is what a caller who filters a dense collection wants; the price is a hash index beside the array.

    test {
      let set : @seq.SparseSet[String] = @seq.SparseSet::new()
      @test.assert_eq(set.insert("a"), true)
      @test.assert_eq(set.insert("a"), false)
      @test.assert_eq(set.contains("a"), true)
      @test.assert_eq(set.to_array(), ["a"])
    }

    SuffixArray

    source

    The suffixes of a text in sorted order, built by doubling: after round k every suffix is ranked by its first 2^k units, and a round ranks the pairs of ranks it already has. Two rounds of comparison sort per doubling give O(n log^2 n), which is what a text of any ordinary size needs.

    test {
      let array : @text.SuffixArray = @text.SuffixArray::new("banana")
      @test.assert_eq(array.search("ana"), [1, 3])
      @test.assert_eq(array.length(), 6)
    }

    SuffixAutomaton

    source

    A suffix automaton: every substring of the text is a path from the start state, and each state remembers how many times the substring it stands for occurs. The build is one pass and the state count is at most twice the text length, which is what makes "how often does this appear" a lookup.

    test {
      let automaton : @text.SuffixAutomaton = @text.SuffixAutomaton::new("banana")
      @test.assert_eq(automaton.contains("ana"), true)
      @test.assert_eq(automaton.count_occurrences("ana"), 2)
      @test.assert_eq(automaton.contains("band"), false)
    }

    TDigest

    source

    A digest of a distribution: the values are grouped into centroids, each a mean with a weight, and the groups are kept small where the quantiles are dense — near the ends — so a quantile costs the same whether the digest has seen a thousand values or a million. The compression parameter is how many groups the digest is willing to keep; a hundred is the usual choice for a relative error of about one percent at the tails.

    test {
      let digest : @sketch.TDigest = @sketch.TDigest::new()
      for i in 0..<1000 {
        digest.add(i.to_double())
      }
      let median = digest.quantile(0.5)
      assert_true(median > 450.0)
      assert_true(median < 550.0)
      assert_true(digest.count() == 1000.0)
    }

    ThetaSketch

    source

    A sketch that keeps the k smallest hashes it has seen and reports a count from the largest one it kept: if the threshold sits at theta, then k / theta scales a sample of k hashes to the whole set. Because the kept hashes are exactly the ones below the threshold, the estimate is a maximum-likelihood one, and two sketches combine by keeping the union's k smallest.

    test {
      let sketch : @sketch.ThetaSketch[Int32] = @sketch.ThetaSketch::new(
        nominal_entries=1024,
      )
      for i in 0..<500 {
        sketch.add(i)
      }
      assert_true(sketch.estimate() > 450.0)
      assert_true(sketch.estimate() < 550.0)
    }

    Treap

    source

    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"))
    }

    TreeId

    source

    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.

    Trie

    source

    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)))
    }

    Source Files

    Powered by MoonBit

    Site sourceReport issueModulesSkillsCLIBuild queueStatistics

    © 2026 mooncakes.io