///|
priv struct BItem {
  value : Int
}

///|
impl @rle.HasLength for BItem with length(_self) {
  1
}

///|
impl @rle.Spanning for BItem with span(_self) {
  1
}

///|
impl @rle.Mergeable for BItem with can_merge(_self, _other) -> Bool {
  false
}

///|
impl @rle.Mergeable for BItem with merge(_self, _other) -> BItem {
  abort("unreachable")
}

///|
impl @rle.Sliceable for BItem with slice(self, start~ : Int, end~ : Int) -> Result[
  BItem,
  @rle.RleError,
] {
  if start == 0 && end == 1 {
    Ok({ value: self.value })
  } else {
    Err(@rle.RleError::InvalidSlice(reason=@rle.SliceError::InvalidIndex))
  }
}

///|
impl BTreeElem for BItem

///|
fn bi(v : Int) -> BItem {
  { value: v }
}

///|
/// Build tree via repeated inserts (O(n log n) baseline)
fn build_via_inserts(n : Int, min_degree : Int) -> BTree[BItem] {
  let t : BTree[BItem] = BTree::new(min_degree~)
  if n == 0 {
    return t
  }
  t.init_root(bi(0), 1)
  for i in 1.. BTree[BItem] {
  let items : Array[(BItem, Int)] = []
  for i in 0..