///|
/// Frequency of one object member name across a document tree.
pub(all) struct KeyFrequency {
  key : String
  count : Int
}

///|
pub fn key_frequencies(value : JsonValue) -> Array[KeyFrequency] {
  let frequencies : Array[KeyFrequency] = []
  collect_key_frequencies(value, frequencies)
  sort_key_frequencies(frequencies)
  frequencies
}

///|
fn collect_key_frequencies(
  value : JsonValue,
  frequencies : Array[KeyFrequency],
) -> Unit {
  match value {
    Object(entries) =>
      for entry in entries {
        increment_frequency(frequencies, entry.0)
        collect_key_frequencies(entry.1, frequencies)
      }
    Array(values) =>
      for child in values {
        collect_key_frequencies(child, frequencies)
      }
    _ => ()
  }
}

///|
fn increment_frequency(frequencies : Array[KeyFrequency], key : String) -> Unit {
  let mut index = 0
  while index < frequencies.length() {
    if frequencies[index].key == key {
      frequencies[index] = { key, count: frequencies[index].count + 1 }
      return
    }
    index = index + 1
  }
  frequencies.push({ key, count: 1 })
}

///|
fn sort_key_frequencies(frequencies : Array[KeyFrequency]) -> Unit {
  let mut index = 1
  while index < frequencies.length() {
    let current = frequencies[index]
    let mut cursor = index
    while cursor > 0 &&
          (
            frequencies[cursor - 1].count < current.count ||
            (
              frequencies[cursor - 1].count == current.count &&
              compare_keys(frequencies[cursor - 1].key, current.key) > 0
            )
          ) {
      frequencies[cursor] = frequencies[cursor - 1]
      cursor = cursor - 1
    }
    frequencies[cursor] = current
    index = index + 1
  }
}

///|
pub fn key_frequencies_json(value : JsonValue) -> String {
  let frequencies = key_frequencies(value)
  let mut output = "["
  let mut first = true
  for frequency in frequencies {
    if !first {
      output = output + ","
    }
    first = false
    output = output +
      "{\"key\":" +
      canonical_string(frequency.key) +
      ",\"count\":" +
      frequency.count.to_string() +
      "}"
  }
  output + "]"
}