🥮 mooncakes.io

order-tree

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

btree
order-statistic
data-structure
moon add dowdiness/order-tree@0.1.2
Download zip
Author
Version
0.1.2
License
Apache-2.0
Repository
Last updated
16 days ago
Downloads
24K

Dependencies

README

#order-tree

Position-indexed sequence for MoonBit with O(log n) lookup by index and O(log n) point mutations when boundary merges are bounded.

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 position; non-positive spans are ignoredO((m + 1) log n)¹
delete_at(pos)Delete element at positionO((m + 1) log n)¹
delete_range(start, end)Delete span range [start, end)O(log n)
set_at(pos, elem) / tree[pos] = elemReplace element; non-positive spans are rejected without mutationO((m + 1) 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)

¹ Point mutations normalize only their affected logical boundaries. Here m is the number of boundaries merged into the canonical run closure; the common bounded-merge case remains O(log n).

#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.

Elements passed to insert_at with a span of zero or less are ignored. For set_at, the same invalid replacement returns None and leaves the tree unchanged; the index setter is likewise a no-op.

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.

#Defining Your Element Type

To use mutation and slicing operations you need an element type that implements @btree.BTreeElem. Add the dependencies that contribute the traits:

moon add dowdiness/order-tree
moon add dowdiness/rle
moon add dowdiness/btree

// Each E occupies span 1 and never merges with its neighbour.
pub struct E {
  v : Int
} derive(Eq)

pub impl @rle.HasLength for E with length(_self) { 1 }

pub impl @rle.Spanning for E with span(_self) { 1 }

pub impl @rle.Mergeable for E with can_merge(_a, _b) { false }
pub impl @rle.Mergeable for E with merge(a, _b) { a }

pub impl @rle.Sliceable for E with slice(self, start~, end~) {
  let _ = start
  let _ = end
  Ok(self)
}

// BTreeElem is an empty super-trait. MoonBit emits warning [0027]
// for implicit empty-trait impls, so add an explicit one:
pub impl @btree.BTreeElem for E

For RLE-merging behaviour (adjacent runs of the same value collapse to a single leaf), make can_merge return true for compatible neighbours and have merge combine their spans. See dowdiness/rle for the full contract.

#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()]. Elements with non-positive span are ignored without mutating the tree.

#
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 and does nothing when the replacement span is non-positive.

#
OrderTree::set_at

source

Replace the element at the given span position. Returns the old single-unit slice, or None if out of bounds or the replacement span is non-positive. Invalid replacements leave the tree unchanged. 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 issuePackagesBuild queueSkillsStatistics

© 2026 mooncakes.io