///|
fn validate_blocking_algorithms(
  algorithms : Array[Algorithm],
) -> Result[Unit, IndexError] {
  if algorithms.length() == 0 {
    return Err(NoBlockingAlgorithms)
  }
  for index = 0; index < algorithms.length(); index = index + 1 {
    for earlier = 0; earlier < index; earlier = earlier + 1 {
      if algorithms[index] == algorithms[earlier] {
        return Err(DuplicateBlockingAlgorithm(algorithms[index]))
      }
    }
  }
  Ok(())
}

///|
fn blocking_bucket_keys(
  normalized : String,
  algorithms : Array[Algorithm],
) -> Array[String] {
  let bucket_keys : Array[String] = []
  for algorithm in algorithms {
    let encoded = encode_normalized_keys(normalized, algorithm)
    for key in encoded.all_non_empty_keys() {
      let bucket_key = algorithm_label(algorithm) + ":" + key
      if !bucket_keys.contains(bucket_key) {
        bucket_keys.push(bucket_key)
      }
    }
  }
  bucket_keys
}

///|
fn prepare_index_name(
  name : String,
  config : MatchConfig,
  algorithms : Array[Algorithm],
) -> Result[(String, Array[String]), IndexError] {
  let normalized = match normalize_name(name, config.normalization) {
    Err(error) => return Err(IndexNormalizationFailed(error))
    Ok(result) => result.normalized
  }
  let keys = blocking_bucket_keys(normalized, algorithms)
  if keys.length() == 0 {
    Err(NoBlockingKeys(name))
  } else {
    Ok((normalized, keys))
  }
}

///|
fn add_record_to_buckets(
  buckets : Map[String, Array[String]],
  id : String,
  keys : Array[String],
) -> Unit {
  for key in keys {
    match buckets.get(key) {
      Some(bucket) => if !bucket.contains(id) { bucket.push(id) }
      None => buckets.set(key, [id])
    }
  }
}

///|
fn remove_record_from_buckets(
  buckets : Map[String, Array[String]],
  id : String,
  keys : Array[String],
) -> Unit {
  for key in keys {
    match buckets.get(key) {
      None => ()
      Some(bucket) => {
        let mut index = bucket.length() - 1
        while index >= 0 {
          if bucket[index] == id {
            ignore(bucket.remove(index))
          }
          index = index - 1
        }
        if bucket.length() == 0 {
          buckets.remove(key)
        }
      }
    }
  }
}

///|
/// Creates an empty index after validating matching and blocking settings.
pub fn NameIndex::new(
  config : MatchConfig,
  blocking_algorithms : Array[Algorithm],
) -> Result[NameIndex, IndexError] {
  match validate_match_config(config) {
    Err(error) => return Err(InvalidIndexMatchConfig(error))
    Ok(_) => ()
  }
  match validate_blocking_algorithms(blocking_algorithms) {
    Err(error) => return Err(error)
    Ok(_) => ()
  }
  Ok({
    config,
    blocking_algorithms,
    records: Map([]),
    normalized: Map([]),
    record_bucket_keys: Map([]),
    buckets: Map([]),
  })
}

///|
/// Inserts one new record and its derived blocking keys.
pub fn NameIndex::insert(
  self : NameIndex,
  id : String,
  name : String,
) -> Result[Unit, IndexError] {
  if id.length() == 0 {
    return Err(EmptyRecordId)
  }
  if self.records.contains(id) {
    return Err(DuplicateRecord(id))
  }
  let (normalized, keys) = match
    prepare_index_name(name, self.config, self.blocking_algorithms) {
    Err(error) => return Err(error)
    Ok(value) => value
  }
  add_record_to_buckets(self.buckets, id, keys)
  self.records.set(id, { id, name })
  self.normalized.set(id, normalized)
  self.record_bucket_keys.set(id, keys)
  Ok(())
}

///|
/// Replaces a record name and atomically refreshes its derived keys.
pub fn NameIndex::update(
  self : NameIndex,
  id : String,
  name : String,
) -> Result[Unit, IndexError] {
  if !self.records.contains(id) {
    return Err(MissingRecord(id))
  }
  let (normalized, keys) = match
    prepare_index_name(name, self.config, self.blocking_algorithms) {
    Err(error) => return Err(error)
    Ok(value) => value
  }
  match self.record_bucket_keys.get(id) {
    Some(old_keys) => remove_record_from_buckets(self.buckets, id, old_keys)
    None => ()
  }
  add_record_to_buckets(self.buckets, id, keys)
  self.records.set(id, { id, name })
  self.normalized.set(id, normalized)
  self.record_bucket_keys.set(id, keys)
  Ok(())
}

///|
/// Removes a record and deletes buckets that become empty.
pub fn NameIndex::remove(
  self : NameIndex,
  id : String,
) -> Result[Unit, IndexError] {
  if !self.records.contains(id) {
    return Err(MissingRecord(id))
  }
  match self.record_bucket_keys.get(id) {
    Some(keys) => remove_record_from_buckets(self.buckets, id, keys)
    None => ()
  }
  self.records.remove(id)
  self.normalized.remove(id)
  self.record_bucket_keys.remove(id)
  Ok(())
}

///|
/// Returns the original record for an identifier.
pub fn NameIndex::get(
  self : NameIndex,
  id : String,
) -> Result[NameRecord, IndexError] {
  match self.records.get(id) {
    Some(record) => Ok(record)
    None => Err(MissingRecord(id))
  }
}

///|
/// Returns the number of indexed records.
pub fn NameIndex::length(self : NameIndex) -> Int {
  self.records.length()
}