// Ported from Draco 1.5.7 (compression/point_cloud/algorithms/dynamic_integer_points_kd_tree_decoder.h,
// compression/bit_coders/direct_bit_decoder.cc, folded_integer_bit_decoder.h, rans_bit_decoder.cc):
// Apache License 2.0, Copyright 2016 The Draco Authors. See NOTICE.

///|
/// The most dimensions (components of the attributes one kd-tree decoder holds) a kd-tree may
/// have; Draco allocates `32 × dimensions + 1` stack levels of that many words up front.
pub const MAX_KD_DIMENSIONS : Int32 = 1024

///|
/// The most work (tree nodes times dimensions) one kd-tree may take, which Draco leaves unbounded.
const MAX_KD_WORK : Int64 = 0x40000000L

///|
/// `DirectBitDecoder`: 32-bit words read from their most significant bit. `value` holds what
/// `bits` decoded.
priv struct DirectBits {
  words : FixedArray[UInt32]
  mut pos : Int32
  mut used : Int32
  mut value : UInt32
}

///|
/// `StartDecoding`.
fn DirectBits::start(b : Buffer) -> DirectBits? {
  let size = b.u32()
  guard !b.failed else { return None }
  guard size != 0 && (size & 3) == 0 else { return None }
  guard b.fits(size.reinterpret_as_uint().to_uint64()) else { return None }
  let words = FixedArray::makei(size / 4, fn(_) {
    b.u32().reinterpret_as_uint()
  })
  Some({ words, pos: 0, used: 0, value: 0, })
}

///|
/// `DecodeNextBit`: false past the end.
fn DirectBits::next_bit(self : DirectBits) -> Bool {
  guard self.pos < self.words.length() else { return false }
  let bit = (self.words[self.pos] >> (31 - self.used)) & 1
  self.used += 1
  if self.used == 32 {
    self.pos += 1
    self.used = 0
  }
  bit != 0
}

///|
/// `DecodeLeastSignificantBits32` of 1 to 32 bits into `value`; false (leaving `value`) past the
/// end.
fn DirectBits::bits(self : DirectBits, nbits : Int32) -> Bool {
  let remaining = 32 - self.used
  if nbits <= remaining {
    guard self.pos < self.words.length() else { return false }
    self.value = self.words[self.pos] << self.used >> (32 - nbits)
    self.used += nbits
    if self.used == 32 {
      self.pos += 1
      self.used = 0
    }
  } else {
    guard self.pos + 1 < self.words.length() else { return false }
    let left = self.words[self.pos] << self.used
    self.used = nbits - remaining
    self.pos += 1
    let right = self.words[self.pos] >> (32 - self.used)
    self.value = (left >> (32 - self.used - remaining)) | right
  }
  true
}

///|
/// The numbers decoder of a compression level: `DirectBitDecoder` (levels 0 and 1),
/// `RAnsBitDecoder` (2 and 3) or `FoldedBit32Decoder` (4 to 6, its 32 folded
/// decoders then its bit decoder).
priv enum KdNumbers {
  Direct(DirectBits)
  RAns(BitDecoder)
  Folded(FixedArray[BitDecoder])
}

///|
fn KdNumbers::start(level : Int32, b : Buffer) -> KdNumbers? {
  if level < 2 {
    return DirectBits::start(b).map(d => Direct(d))
  }
  let count = if level < 4 { 1 } else { 33 }
  let decoders = FixedArray::makei(count, fn(_) { BitDecoder::new(b.data) })
  for d in decoders {
    guard d.start(b) else { return None }
  }
  Some(if level < 4 { RAns(decoders[0]) } else { Folded(decoders) })
}

///|
/// `DecodeLeastSignificantBits32` of 1 to 32 bits; 0 when a direct decoder runs out, as the
/// kd-tree decoder's zeroed number stays.
fn KdNumbers::decode(self : KdNumbers, nbits : Int32) -> UInt32 {
  match self {
    Direct(d) => if d.bits(nbits) { d.value } else { 0 }
    RAns(d) => {
      let mut v : UInt32 = 0
      for _ in 0.. {
      let mut v : UInt32 = 0
      for i in 0.. KdOut {
  { targets, collected: [], collect: false, limit: 0, count: 0, over: false, }
}

///|
fn KdOut::collecting(limit : Int64) -> KdOut {
  { targets: [], collected: [], collect: true, limit, count: 0, over: false, }
}

///|
/// `*oit = p; ++oit;` repeated `n` times; false (and `over`) when collecting past `limit`.
fn KdOut::put(self : KdOut, p : FixedArray[UInt32], n : Int64) -> Bool {
  if self.collect {
    guard self.count + n <= self.limit else {
      self.over = true
      return false
    }
    for _ in 0..> (8 * k)).to_byte()
          }
        }
      }
    }
  }
  self.count += n
  true
}

///|
/// The `remaining`, `axis` and `half` decoders and the stacks of one kd-tree.
priv struct KdTree {
  dim : Int32
  select_axis : Bool
  bit_length : Int32
  numbers : KdNumbers
  remaining : DirectBits
  axis : DirectBits
  half : DirectBits
  bases : Array[FixedArray[UInt32]]
  levels : Array[FixedArray[Int32]]
}

///|
/// `GetAxis`.
fn KdTree::get_axis(
  self : KdTree,
  num_remaining : UInt32,
  levels : FixedArray[Int32],
  last_axis : Int32,
) -> Int32 {
  if !self.select_axis {
    return if last_axis == self.dim - 1 { 0 } else { last_axis + 1 }
  }
  let mut best = 0
  if num_remaining < 64 {
    for axis in 1.. levels[axis] {
        best = axis
      }
    }
  } else if self.axis.bits(4) {
    best = self.axis.value.reinterpret_as_int()
  }
  best
}

///|
/// Makes stack level `at` exist (Draco allocates all `32 × dim + 1` up front).
fn KdTree::level(self : KdTree, at : Int32) -> Unit {
  while self.bases.length() <= at {
    self.bases.push(FixedArray::make(self.dim, 0))
    self.levels.push(FixedArray::make(self.dim, 0))
  }
}

///|
/// `DynamicIntegerPointsKdTreeDecoder(dim).DecodePoints(buffer, out, max_points)`: false
/// where Draco fails, and past `MAX_KD_DIMENSIONS` or `MAX_KD_WORK`. `out.count` is then the
/// number of points decoded.
fn decode_kd_points(
  b : Buffer,
  level : Int32,
  dim : Int32,
  max_points : UInt32,
  out : KdOut,
) -> Bool {
  let bit_length = b.u32()
  guard !b.failed && bit_length.reinterpret_as_uint() <= 32 else {
    return false
  }
  let num_points = b.u32().reinterpret_as_uint()
  guard !b.failed else { return false }
  guard num_points != 0 else { return true }
  guard num_points <= max_points else { return false }
  guard dim >= 1 && dim <= MAX_KD_DIMENSIONS else { return false }
  guard KdNumbers::start(level, b) is Some(numbers) else { return false }
  guard DirectBits::start(b) is Some(remaining) else { return false }
  guard DirectBits::start(b) is Some(axis) else { return false }
  guard DirectBits::start(b) is Some(half) else { return false }
  let tree : KdTree = {
    dim,
    select_axis: level == 6,
    bit_length,
    numbers,
    remaining,
    axis,
    half,
    bases: [],
    levels: [],
  }
  tree.level(0)
  tree.decode(num_points, out)
}

///|
/// `DecodeInternal`.
fn KdTree::decode(self : KdTree, num_points : UInt32, out : KdOut) -> Bool {
  let dim = self.dim
  let stack_points : Array[UInt32] = [num_points]
  let stack_axis : Array[Int32] = [0]
  let stack_pos : Array[Int32] = [0]
  let p : FixedArray[UInt32] = FixedArray::make(dim, 0)
  let axes = FixedArray::make(dim, 0)
  let mut work = 0L
  while stack_points.length() > 0 {
    let n = stack_points.unsafe_pop()
    let last_axis = stack_axis.unsafe_pop()
    let pos = stack_pos.unsafe_pop()
    work += dim.to_int64()
    guard work <= MAX_KD_WORK else { return false }
    guard n <= num_points else { return false }
    let old_base = self.bases[pos]
    let levels = self.levels[pos]
    let axis = self.get_axis(n, levels, last_axis)
    guard axis >= 0 && axis < dim else { return false }
    let level = levels[axis]
    if self.bit_length == level {
      guard out.put(old_base, n.to_uint64().reinterpret_as_int64()) else {
        return false
      }
      continue
    }
    if n <= 2 {
      axes[0] = axis
      for i in 1..= number else { return false }
    first = first - number
    let mut second = n - first
    if first != second && !self.half.next_bit() {
      let t = first
      first = second
      second = t
    }
    levels[axis] += 1
    let next_levels = self.levels[pos + 1]
    for i in 0..