///|
pub fn StaticIntMap::build(
  entries : Array[FuseValue],
) -> Result[StaticIntMap, FuseError] {
  if entries.length() == 0 {
    return Err(EmptyInput)
  }
  let sorted = entries.copy()
  sorted.sort_by((left, right) => left.hash.compare(right.hash))
  let hashes : Array[Int] = []
  let values : Array[Int] = []
  for entry in sorted {
    hashes.push(entry.hash)
    values.push(entry.value)
  }
  match VerifiedFuseFilter::build(hashes) {
    Ok(index) => Ok({ index, values })
    Err(error) => Err(error)
  }
}

///|
pub fn StaticIntMap::get(self : StaticIntMap, hash : Int) -> Int? {
  if !self.index.may_contain(hash) {
    return None
  }
  match self.find_index(hash) {
    Some(index) => Some(self.values[index])
    None => None
  }
}

///|
pub fn StaticIntMap::contains_key(self : StaticIntMap, hash : Int) -> Bool {
  self.get(hash) is Some(_)
}

///|
pub fn StaticIntMap::len(self : StaticIntMap) -> Int {
  self.values.length()
}

///|
pub fn StaticIntMap::entries(self : StaticIntMap) -> Array[FuseValue] {
  let entries : Array[FuseValue] = []
  for index in 0.. Array[Int?] {
  let results : Array[Int?] = []
  for hash in hashes {
    results.push(self.get(hash))
  }
  results
}

///|
pub fn StaticIntMap::with_updates(
  self : StaticIntMap,
  updates : Array[FuseValue],
) -> Result[StaticIntMap, FuseError] {
  if updates.length() == 0 {
    return Ok({ index: self.index, values: self.values.copy() })
  }
  let sorted_updates = updates.copy()
  sorted_updates.sort_by((left, right) => left.hash.compare(right.hash))
  for index in 1.. Result[StaticIntMap, FuseError] {
  let removals = hashes.copy()
  removals.sort()
  let kept : Array[FuseValue] = []
  for entry in self.entries() {
    if !sorted_contains(removals, entry.hash) {
      kept.push(entry)
    }
  }
  StaticIntMap::build(kept)
}

///|
pub fn StaticIntMap::stats(self : StaticIntMap) -> MapStats {
  {
    entry_count: self.len(),
    smallest_key: self.index.sorted_hashes[0],
    largest_key: self.index.sorted_hashes[self.len() - 1],
  }
}

///|
pub fn StaticIntMap::validate(self : StaticIntMap) -> Bool {
  if self.values.length() == 0 ||
    self.values.length() != self.index.len() ||
    !self.index.validate() {
    return false
  }
  for index in 1..= self.index.sorted_hashes[index] {
      return false
    }
  }
  true
}

///|
fn StaticIntMap::find_index(self : StaticIntMap, hash : Int) -> Int? {
  let mut low = 0
  let mut high = self.index.sorted_hashes.length()
  while low < high {
    let middle = low + (high - low) / 2
    let candidate = self.index.sorted_hashes[middle]
    if candidate == hash {
      return Some(middle)
    }
    if candidate < hash {
      low = middle + 1
    } else {
      high = middle
    }
  }
  None
}