🥮 mooncakes.io

    order-tree

    Order-statistic B-tree with O(log n) position-indexed operations

    btree
    order-statistic
    data-structure
    Download zip
    Author
    Version
    0.1.0
    License
    Apache-2.0
    Repository
    Last updated
    6 months ago
    Downloads
    31K

    #order-tree

    Position-indexed sequence for MoonBit with O(log n) insert, delete, and lookup by index.

    Built on dowdiness/btree (a counted B+ tree). OrderTree adds a high-level API for common sequence operations — insert at position, delete at position, bulk construction from arrays, and operator overloads.

    #Install

    moon add dowdiness/order-tree

    #Quick Start

    // Build from array
    let tree = @order_tree.OrderTree::from_array(["a", "b", "c", "d"])

    // Positional access
    tree[0]       //=> Some("a")
    tree[2]       //=> Some("c")

    // Range view
    tree[1:3]     //=> ["b", "c"]

    // Insert and delete
    tree.insert_at(2, "x")    // ["a", "b", "x", "c", "d"]
    tree.delete_at(0)          //=> Some("a"), tree is ["b", "x", "c", "d"]

    // Range delete
    tree.delete_range(1, 3)    // ["b", "d"]

    #API

    MethodDescriptionComplexity
    OrderTree::new(min_degree?)Create empty treeO(1)
    OrderTree::from_array(items, min_degree?)Bulk build from arrayO(n)
    get_at(pos) / tree[pos]Element at positionO(log n)
    find(pos)Element + offset within elementO(log n)
    insert_at(pos, elem)Insert element at positionO(log n)
    delete_at(pos)Delete element at positionO(log n)
    delete_range(start, end)Delete span range [start, end)O(log n)*
    set_at(pos, elem) / tree[pos] = elemReplace elementO(log n)
    view(start?, end?) / tree[start:end]Slice elements in rangeO(k + log n)
    iter()Lazy iterator over all elementsO(n) total
    span()Total spanO(1)
    size()Number of RLE runs (≤ logical length when adjacent items merge)O(1)

    *Falls back to O(n) rebuild for some boundary cases.

    #When to Use OrderTree vs BTree

    NeedUse
    Insert/delete by positionOrderTree — insert_at, delete_at
    Bulk construction from arrayOrderTree — from_array (O(n) bottom-up)
    Operator syntax (tree[i], tree[i:j])OrderTree — has #alias overloads
    Custom splice logic (split/merge neighbors)BTree — mutate_for_insert/delete callbacks
    Embedding in another data structureBTree — OrderTree is a thin wrapper

    OrderTree is a single-field wrapper: { tree: @btree.BTree[T] }. It delegates all operations to the underlying BTree and adds convenience methods.

    #Element Requirements

    Trait bounds scale with the operation:

    • Pure queries (get_at / tree[pos], find, size, span, each, to_array, iter, length, is_empty): no bound on T.
    • Bulk construction (from_array): @rle.Spanning + @rle.Mergeable.
    • Positional mutation and slicing (insert_at, delete_at, delete_range, set_at / tree[pos] = item, view / tree[start:end]): @btree.BTreeElem, the super trait @rle.Spanning + @rle.Mergeable + @rle.Sliceable.

    view needs Sliceable because it may split an element at a span boundary when materializing the slice — not because it mutates.

    Traits:
    • @rle.Spanning — how much span an element occupies
    • @rle.Mergeable — when adjacent elements can merge (RLE compression)
    • @rle.Sliceable — how to split an element at a position

    See dowdiness/rle for trait details.

    #Architecture

    dowdiness/rle          Element traits (Spanning, Mergeable, Sliceable)
    ↑
dowdiness/btree        Counted B+ tree engine
    ↑                  - Navigation by span position (not keys)
    |                  - All data in leaves, internal nodes are navigational
    |                  - Automatic RLE merge of adjacent leaves
    |
dowdiness/order-tree   High-level sequence API (this library)
                       - insert_at, delete_at, from_array
                       - Operator overloads
                       - Used by the CRDT layer (event-graph-walker)

    #Design Notes

    The underlying B+ tree uses span counts instead of keys for navigation. Each internal node stores a counts array where counts[i] is the total span of child i. This gives O(log n) positional access without key comparison — ideal for sequence editors where position is the natural index.

    Adjacent elements with the same identity merge automatically (RLE compression). This keeps the tree compact when consecutive elements share properties (e.g., same author, same formatting).

    OrderTree

    source
    pub struct OrderTree[T] {
      tree : 
    BTree    [T]
    } derive(Eq, 
    Debug    )

    Order-statistic B-tree: a position-indexed sequence with O(log n) operations. Items are ordered by insertion position, not by key comparison. Wraps a generic @btree.BTree[T] and adds RLE-specific merge semantics.
    impl HasLength for OrderTree[T]
    impl Spanning for OrderTree[T]

    OrderTree::delete_at

    source

    Delete the element at the given span position from the tree. Returns a single-unit slice of the deleted element.

    OrderTree::delete_range

    source

    Delete all elements in the span range [start, end_).

    OrderTree::each

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

    Call f for each element in the tree in order.

    OrderTree::find

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

    OrderTree::from_array

    source

    Build an OrderTree from an array of elements in O(n) time. Filters zero-span items, pre-merges adjacent mergeable elements, then builds bottom-up.

    OrderTree::get_at

    source
    #alias("_[_]")
    fn[T] OrderTree::get_at(self : OrderTree[T], pos : Int) -> T?

    Get the element at span position. Aliased as tree[pos].

    OrderTree::insert_at

    source

    Insert an element at the given position in the tree. Position is clamped to [0, span()]. Element must have span > 0.

    OrderTree::iter

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

    Return a lazy iterator over elements in order.

    OrderTree::new

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

    OrderTree::op_set

    source

    Index setter: tree[pos] = elem. Discards the old value.

    OrderTree::set_at

    source

    Replace the element at the given span position. Returns the old single-unit slice, or None if out of bounds. Implemented as delete_at + insert_at to ensure neighbor merging.

    OrderTree::size

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

    Total leaf entries (number of runs).

    OrderTree::to_array

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

    Collect all elements into an array in order.

    OrderTree::view

    source

    View operator: tree[start:end] returns elements in span range [start, end). Slices at boundaries.

    Source Files

    Powered by MoonBit

    Site sourceReport issueModulesSkillsCLIBuild queueStatistics

    © 2026 mooncakes.io