///|
/// Node in a Vantage Point (VP) Tree for metric space nearest neighbor search under Hamming distance.
pub(all) struct VpNode {
  codeword : Int64
  index : Int
  rotation : Int
  threshold : Int
  left : VpNode?
  right : VpNode?
} derive(Debug)

///|
/// Fast Vantage Point (VP) Tree index for sub-linear Hamming distance search.
pub(all) struct DictionaryIndex {
  root : VpNode?
  max_error : Int
} derive(Debug)

///|
/// Builds a VP-tree node recursively from an array of (codeword, index, rotation) tuples.
fn build_vp_tree(
  items : Array[(Int64, Int, Int)],
  start : Int,
  end : Int,
) -> VpNode? {
  if start >= end {
    return None
  }

  // Choose the first element as vantage point
  let vp = items[start]
  if end - start == 1 {
    return Some({
      codeword: vp.0,
      index: vp.1,
      rotation: vp.2,
      threshold: 0,
      left: None,
      right: None,
    })
  }

  // Compute distances from vantage point to all other items
  let count = end - start - 1
  let dists = Array::make(count, 0)
  for i in 0.. DictionaryIndex {
  let items : Array[(Int64, Int, Int)] = []
  for i in 0.. (Int, Int, Int)? {
  let mut best_id = -1
  let mut best_rot = 0
  let mut min_dist = self.max_error + 1

  fn search_node(node_opt : VpNode?) -> Unit {
    match node_opt {
      Some(node) => {
        let dist = compute_hamming_distance(query, node.codeword)
        if dist < min_dist {
          min_dist = dist
          best_id = node.index
          best_rot = node.rotation
        }

        if min_dist == 0 {
          return // Exact match found
        }

        let thresh = node.threshold
        if dist - min_dist <= thresh {
          search_node(node.left)
        }
        if dist + min_dist >= thresh {
          search_node(node.right)
        }
      }
      None => ()
    }
  }

  search_node(self.root)

  if min_dist <= self.max_error && best_id >= 0 {
    Some((best_id, best_rot, min_dist))
  } else {
    None
  }
}