🥮 mooncakes.io

    btree

    Generic counted B-tree with O(log n) indexed access, insert, delete, and range operations

    btree
    data-structure
    counted-sequence
    moonbit
    Download zip
    Author
    Version
    0.1.0
    License
    Apache-2.0
    Repository
    Last updated
    6 months ago
    Downloads
    33K

    #btree

    Counted B+ tree for MoonBit with O(log n) position-indexed access, insert, delete, and range operations.

    All data lives in leaf nodes. Internal nodes store only child pointers and span counts for positional navigation — a B+ tree indexed by cumulative span rather than keys.

    #Install

    moon add dowdiness/btree

    #How It Works

    Internal(counts=[5, 3, 4], total=12)
├── Leaf(elem=a, span=5)     positions [0, 5)
├── Leaf(elem=b, span=3)     positions [5, 8)
└── Leaf(elem=c, span=4)     positions [8, 12)

    Navigation uses the counts array as a cumulative index. To find position 6: counts[0]=5 (skip), 6-5=1 into child 1 → Leaf(b) at offset 1.

    Elements implement BTreeElem (requires Spanning + Mergeable + Sliceable from dowdiness/rle). Adjacent leaves with the same identity merge automatically — this is RLE compression at the tree level.

    #Quick Start

    // Define your element type
    struct TextRun {
      text : String
      len : Int
    }

    // Implement BTreeElem traits (Spanning, Mergeable, Sliceable)
    impl @rle.Spanning for TextRun with span(self) { self.len }
    impl @rle.Mergeable for TextRun with can_merge(a, b) { true }
    impl @rle.Mergeable for TextRun with merge(a, b) {
      { text: a.text + b.text, len: a.len + b.len }
    }
    // ... plus Sliceable, HasLength
    impl @btree.BTreeElem for TextRun

    // Use the tree
    let tree : @btree.BTree[TextRun] = @btree.BTree::new()
    tree.init_root({ text: "hello", len: 5 }, 5)

    #API

    MethodDescriptionComplexity
    BTree::new(min_degree?)Create empty tree (default min_degree=10)O(1)
    get_at(pos)Element at span positionO(log n)
    find(pos)Element + offset within elementO(log n)
    mutate_for_insert(pos, callback)Insert via leaf splice callbackO(log n)
    mutate_for_delete(pos, callback)Delete via leaf splice callbackO(log n)
    delete_range(start, end)Delete span range [start, end)O(log n)*
    view(start?, end?)Slice elements in rangeO(k + log n)
    iter()Lazy cursor-based iteratorO(n) total
    each(f)Visit all elementsO(n)
    to_array()Collect all elementsO(n)
    span()Total span (cached)O(1)
    size()Number of leavesO(1)

    *Falls back to O(n) rebuild when boundary subtrees are underfull.

    #Relationship to Other Libraries

    dowdiness/rle          Traits: Spanning, Mergeable, Sliceable
    ↑
dowdiness/btree        Counted B+ tree (this library)
    ↑
dowdiness/order-tree   High-level API: insert_at, delete_at, from_array

    • rle defines the element contracts. Any type implementing BTreeElem can be stored.
    • btree is the engine — tree structure, navigation, rebalancing, range operations.
    • order-tree adds convenience: insert_at(pos, elem), delete_at(pos), from_array(items), operator overloads (tree[pos], tree[start:end]).

    Use btree directly when you need low-level control (custom splice callbacks). Use order-tree for standard sequence operations.

    #Design

    This is a counted B+ tree, also known as an order-statistic tree:

    • B+ tree: data only in leaves, internal nodes are navigational
    • Counted: counts array replaces keys — navigation by span position, not key comparison
    • RLE-aware: adjacent mergeable leaves auto-compress

    The tree maintains these invariants:
    • All leaves at the same depth
    • Internal nodes have between min_degree and 2 * min_degree children (root excepted)
    • counts[i] == children[i].total() and total == sum(counts)
    • No adjacent mergeable leaves (RLE invariant)

    BTreeElem

    source

    BTree

    source
    pub(all) struct BTree[T] {
      root : BTreeNode[T]?
      min_degree : Int
      size : Int
    } derive(Eq, 
    Debug    )

    BTree::delete_range

    source

    Delete all elements in the span range [start, end_). Handles all cases: single-leaf splice, multi-child LCA splice, underfull node repair, and post-splice boundary merging.

    BTree::each

    source
    fn[T] BTree::each(self : BTree[T], f : (T) -> Unit) -> Unit

    BTree::find

    source
    fn[T] BTree::find(self : BTree[T], pos : Int) -> FindResult[T]?

    BTree::from_sorted

    source
    fn[T] BTree::from_sorted(items : Array[(T, Int)], min_degree? : Int) -> BTree[T]

    Build a BTree bottom-up from a pre-sorted array of (element, span) pairs. O(n) instead of O(n log n) repeated inserts. Caller must ensure no adjacent items are mergeable (pre-merge if needed).

    BTree::get_at

    source
    fn[T] BTree::get_at(self : BTree[T], pos : Int) -> T?

    BTree::init_root

    source
    fn[T] BTree::init_root(self : BTree[T], elem : T, span : Int) -> Unit

    Initialize root with a single leaf wrapped in an internal node.

    BTree::is_empty

    source
    fn[T] BTree::is_empty(self : BTree[T]) -> Bool

    BTree::iter

    source
    fn[T] BTree::iter(self : BTree[T]) -> Iter[T]

    Lazy iterator: traverses leaves using cursor without allocating an array.

    BTree::mutate_for_delete

    source
    fn[T, R] BTree::mutate_for_delete(self : BTree[T], pos : Int, f : (LeafContext[T]) -> (Splice[T], R)) -> R?

    Descend for delete: ensures min children during descent, uses strict slot finding. Returns the callback's payload R, or None if pos is out of bounds or tree is empty. The callback returns (splice, payload) where payload is any caller-defined data (e.g., the deleted element).

    BTree::mutate_for_insert

    source
    fn[T] BTree::mutate_for_insert(self : BTree[T], pos : Int, f : (LeafContext[T]) -> Splice[T]) -> Unit

    Descend for insert: splits full nodes during descent, uses inclusive slot finding, allows leaf-end positions. Tree must be non-empty (use init_root first). Aborts if pos is out of [0, span] or tree is empty. The callback receives a LeafContext and returns a Splice describing what to replace. The tree handles rebalancing and size tracking automatically.

    BTree::new

    source
    fn[T] BTree::new(min_degree? : Int) -> BTree[T]

    BTree::size

    source
    fn[T] BTree::size(self : BTree[T]) -> Int

    BTree::span

    source
    fn[T] BTree::span(self : BTree[T]) -> Int

    BTree::to_array

    source
    fn[T] BTree::to_array(self : BTree[T]) -> Array[T]

    BTree::view

    source

    View elements in span range [start, end). Slices at boundaries.

    BTreeNode

    source
    pub(all) enum BTreeNode[T] {
      Leaf(T, Int)
      Internal(Array[BTreeNode[T]], Array[Int], Int)
    } derive(Eq, 
    Debug    )

    BTreeNode::each

    source
    fn[T] BTreeNode::each(self : BTreeNode[T], f : (T) -> Unit) -> Unit

    BTreeNode::each_slice_in_range

    source

    BTreeNode::height

    source
    fn[T] BTreeNode::height(self : BTreeNode[T]) -> Int

    BTreeNode::total

    source
    fn[T] BTreeNode::total(self : BTreeNode[T]) -> Int

    Cached span total: O(1) for both Leaf (stored span) and Internal (stored total).

    FindResult

    source
    pub(all) struct FindResult[T] {
      elem : T
      offset : Int
    } derive(Eq, 
    Debug    )

    impl Show for FindResult[T]

    LeafContext

    source
    pub(all) struct LeafContext[T] {
      elem : T
      span : Int
      offset : Int
      children : Array[BTreeNode[T]]
      child_idx : Int
    } derive(
    Debug    )

    Read-only context passed to pure leaf splice computations.

    LeafContext::left_neighbor

    source
    fn[T] LeafContext::left_neighbor(self : LeafContext[T]) -> T?

    LeafContext::right_neighbor

    source
    fn[T] LeafContext::right_neighbor(self : LeafContext[T]) -> T?

    Splice

    source
    pub(all) struct Splice[T] {
      start_idx : Int
      end_idx : Int
      new_leaves : Array[(T, Int)]
    } derive(
    Debug    )

    Source Files

    Powered by MoonBit

    Site sourceReport issueModulesSkillsCLIBuild queueStatistics

    © 2026 mooncakes.io