///|
/// A mutable binary min-heap for `(priority, node_index)` pairs.
///
/// Priorities are ordered first and node indices break ties, which keeps
/// path selection deterministic across runs.
priv struct MinHeap {
  data : Array[(Double, Int)]
}

///|
fn MinHeap::new() -> MinHeap {
  { data: [] }
}

///|
fn MinHeap::is_empty(self : MinHeap) -> Bool {
  self.data.length() == 0
}

///|
fn heap_entry_less(a : (Double, Int), b : (Double, Int)) -> Bool {
  let (a_priority, a_node) = a
  let (b_priority, b_node) = b
  a_priority < b_priority || (a_priority == b_priority && a_node < b_node)
}

///|
fn MinHeap::push(self : MinHeap, priority : Double, node : Int) -> Unit {
  self.data.push((priority, node))
  MinHeap::sift_up(self.data, self.data.length() - 1)
}

///|
fn MinHeap::pop(self : MinHeap) -> (Double, Int)? {
  if self.data.length() == 0 {
    return None
  }

  let result = self.data[0]
  match self.data.pop() {
    None => None
    Some(last) => {
      if self.data.length() > 0 {
        self.data[0] = last
        MinHeap::sift_down(self.data, 0)
      }
      Some(result)
    }
  }
}

///|
fn MinHeap::sift_up(data : Array[(Double, Int)], start : Int) -> Unit {
  let mut index = start
  while index > 0 {
    let parent = (index - 1) / 2
    if !heap_entry_less(data[index], data[parent]) {
      break
    }
    let temporary = data[parent]
    data[parent] = data[index]
    data[index] = temporary
    index = parent
  }
}

///|
fn MinHeap::sift_down(data : Array[(Double, Int)], start : Int) -> Unit {
  let mut index = start
  while true {
    let mut smallest = index
    let left = 2 * index + 1
    let right = left + 1

    if left < data.length() && heap_entry_less(data[left], data[smallest]) {
      smallest = left
    }
    if right < data.length() && heap_entry_less(data[right], data[smallest]) {
      smallest = right
    }
    if smallest == index {
      break
    }

    let temporary = data[index]
    data[index] = data[smallest]
    data[smallest] = temporary
    index = smallest
  }
}