///|
priv struct BTreeV1ChunkRecord {
  address : UInt64
  size : UInt64
  mask : UInt32
  offsets : Array[UInt64]
}

///|
priv struct WriterBTreeV1Node {
  level : Int32
  keys : Array[Bytes]
  child_addresses : Array[UInt64]
  child_nodes : Array[Int32]
  first_key : Bytes
  final_key : Bytes
  mut address : UInt64
  mut left_sibling : UInt64
  mut right_sibling : UInt64
}

///|
fn btree_v1_undefined_address(offset_size : Int32) -> UInt64 {
  if offset_size == 8 {
    0xFFFFFFFFFFFFFFFFUL
  } else {
    (1UL << (offset_size * 8)) - 1UL
  }
}

///|
fn encode_btree_v1_chunk_key(
  size : UInt64,
  mask : UInt32,
  offsets : Array[UInt64],
  storage_offset : UInt64,
) -> Bytes raise Hdf5Error {
  guard offsets.length() > 0 && size <= 0xFFFFFFFFUL else {
    raise InvalidField("invalid v1 B-tree chunk key")
  }
  let buffer = @buffer.Buffer::Buffer(size_hint=16 + 8 * offsets.length())
  writer_write_uint_width(buffer, size, 4)
  writer_write_uint_width(buffer, mask.to_uint64(), 4)
  for offset in offsets {
    buffer.write_uint64_le(offset)
  }
  buffer.write_uint64_le(storage_offset)
  buffer.to_bytes()
}

///|
fn btree_v1_final_key(
  record : BTreeV1ChunkRecord,
  chunk_widths : Array[Int64],
  element_size : Int32,
) -> Bytes raise Hdf5Error {
  guard record.offsets.length() == chunk_widths.length() && element_size > 0 else {
    raise InvalidField("v1 B-tree chunk key rank does not match the grid")
  }
  let offsets : Array[UInt64] = Array::make(record.offsets.length(), 0UL)
  for axis in 0.. 0L &&
      record.offsets[axis] <=
      0xFFFFFFFFFFFFFFFFUL - width.reinterpret_as_uint64() else {
      raise InvalidField("v1 B-tree final chunk key overflows")
    }
    offsets[axis] = record.offsets[axis] + width.reinterpret_as_uint64()
  }
  encode_btree_v1_chunk_key(
    0UL,
    0U,
    offsets,
    element_size.to_int64().reinterpret_as_uint64(),
  )
}

///|
fn btree_v1_chunk_offsets(
  index : Int32,
  grid : Array[Int64],
  chunk_widths : Array[Int64],
) -> Array[UInt64] raise Hdf5Error {
  guard grid.length() == chunk_widths.length() else {
    raise InvalidField("v1 B-tree chunk grid rank mismatch")
  }
  let offsets : Array[UInt64] = Array::make(grid.length(), 0UL)
  let mut remaining = index.to_int64()
  let mut axis = grid.length()
  while axis > 0 {
    axis = axis - 1
    let width = grid[axis]
    guard width > 0L && chunk_widths[axis] > 0L else {
      raise InvalidField("invalid v1 B-tree chunk grid")
    }
    offsets[axis] = (remaining % width * chunk_widths[axis]).reinterpret_as_uint64()
    remaining = remaining / width
  }
  guard remaining == 0L else {
    raise InvalidField("v1 B-tree chunk index is outside the grid")
  }
  offsets
}

///|
fn btree_v1_node_size(
  rank : Int32,
  offset_size : Int32,
  capacity : Int32,
) -> Int32 raise Hdf5Error {
  guard capacity > 0 &&
    capacity <= 65535 &&
    offset_size >= 1 &&
    offset_size <= 8 &&
    rank > 0 else {
    raise InvalidField("invalid v1 B-tree geometry")
  }
  let key_size = 8L + 8L * (rank.to_int64() + 1L)
  let header_size = 8L + 2L * offset_size.to_int64()
  let node_size = header_size +
    capacity.to_int64() * offset_size.to_int64() +
    (capacity.to_int64() + 1L) * key_size
  guard node_size <= 0x7FFFFFFFL else {
    raise UnsupportedFeature("v1 B-tree node is too large")
  }
  node_size.to_int()
}

///|
fn btree_v1_group_sizes(
  count : Int32,
  capacity : Int32,
) -> Array[Int32] raise Hdf5Error {
  guard count > 0 && capacity > 0 else {
    raise InvalidField("invalid v1 B-tree group geometry")
  }
  let count64 = count.to_int64()
  let capacity64 = capacity.to_int64()
  let group_count = (count64 + capacity64 - 1L) / capacity64
  guard group_count > 0 && group_count <= 0x7FFFFFFFL else {
    raise InvalidField("v1 B-tree group count is out of range")
  }
  let base = count64 / group_count
  let remainder = (count64 % group_count).to_int()
  let sizes : Array[Int32] = []
  for group in 0.. Bytes raise Hdf5Error {
  let undefined = btree_v1_undefined_address(offset_size)
  guard node.keys.length() <= 65535 else {
    raise InvalidField("v1 B-tree node has too many entries")
  }
  if node.level == 0 {
    guard node.child_addresses.length() == node.keys.length() &&
      node.child_nodes.length() == 0 else {
      raise InvalidField("invalid v1 B-tree leaf children")
    }
  } else {
    guard node.child_nodes.length() == node.keys.length() &&
      node.child_addresses.length() == 0 else {
      raise InvalidField("invalid v1 B-tree internal children")
    }
  }
  guard node.final_key.length() == key_size else {
    raise InvalidField("v1 B-tree final key size changed")
  }
  let buffer = @buffer.Buffer::Buffer(size_hint=node_size)
  writer_write_bytes(buffer, b"TREE")
  buffer.write_byte(b'\x01')
  buffer.write_byte(node.level.to_byte())
  buffer.write_uint16_le(node.keys.length().to_uint16())
  writer_write_uint_width(
    buffer,
    if node.left_sibling == 0UL {
      undefined
    } else {
      node.left_sibling
    },
    offset_size,
  )
  writer_write_uint_width(
    buffer,
    if node.right_sibling == 0UL {
      undefined
    } else {
      node.right_sibling
    },
    offset_size,
  )
  for entry in 0.. Bytes raise Hdf5Error {
  guard records.length() > 0 else {
    raise InvalidField("cannot encode an empty v1 B-tree chunk tree")
  }
  let rank = chunk_widths.length()
  guard element_size > 0 else {
    raise InvalidField("v1 B-tree element size must be positive")
  }
  let node_size = btree_v1_node_size(rank, offset_size, capacity)
  let key_size = 8 + 8 * (rank + 1)
  let nodes : Array[WriterBTreeV1Node] = []
  let leaf_sizes = btree_v1_group_sizes(records.length(), capacity)
  let mut cursor = 0
  for group_size in leaf_sizes {
    let keys : Array[Bytes] = []
    let addresses : Array[UInt64] = []
    let end = cursor + group_size
    guard end <= records.length() else {
      raise InvalidField("v1 B-tree leaf grouping exceeds the record count")
    }
    for record_index in cursor.. 1 {
    let parent_sizes = btree_v1_group_sizes(current.length(), capacity)
    let parents : Array[Int32] = []
    let mut child_cursor = 0
    for group_size in parent_sizes {
      let keys : Array[Bytes] = []
      let children : Array[Int32] = []
      let end = child_cursor + group_size
      guard end <= current.length() else {
        raise InvalidField("v1 B-tree parent grouping exceeds the node count")
      }
      for child_offset in child_cursor..= 0 {
      nodes[index].left_sibling = nodes[previous].address
      nodes[previous].right_sibling = nodes[index].address
    }
    previous_at_level[node_level] = index
  }
  let output = @buffer.Buffer::Buffer(size_hint=node_count * node_size)
  for node in nodes {
    writer_write_bytes(
      output,
      encode_btree_v1_node(node, nodes, node_size, key_size, offset_size),
    )
  }
  guard output.length() == node_count * node_size else {
    raise InvalidField("v1 B-tree image size changed during encoding")
  }
  output.to_bytes()
}