///|
/// Direct children of a word (by 1-based index); the root's children are
/// returned for `head == 0`.
pub fn children(sentence : Sentence, head : Int32) -> Array[Int32] {
  let out : Array[Int32] = []
  for row in sentence.words() {
    match row.head() {
      Some(h) => if h == head { out.push(row.start) }
      None => ()
    }
  }
  out
}

///|
/// All words whose HEAD chain passes through `ancestor`.
pub fn descendants(sentence : Sentence, ancestor : Int32) -> Array[Int32] {
  let out : Array[Int32] = []
  for row in sentence.words() {
    if row.start == ancestor {
      continue
    }
    if is_ancestor(sentence, ancestor, row.start) {
      out.push(row.start)
    }
  }
  out
}

///|
/// True when following HEAD links from `node` reaches `ancestor`.
pub fn is_ancestor(sentence : Sentence, ancestor : Int32, node : Int32) -> Bool {
  let n = sentence.word_count()
  let mut cur = node
  let mut steps : Int32 = 0
  while steps <= n {
    match sentence.word(cur) {
      Some(row) =>
        match row.head() {
          Some(h) =>
            if h == ancestor {
              return true
            } else if h == 0 || h == cur {
              return false
            } else {
              cur = h
            }
          None => return false
        }
      None => return false
    }
    steps = steps + 1
  }
  false
}

///|
/// Depth of a word in its tree: root children have depth 1.
pub fn depth(sentence : Sentence, index : Int32) -> Int32 {
  let n = sentence.word_count()
  let mut cur = index
  let mut d : Int32 = 0
  let mut steps : Int32 = 0
  while steps <= n {
    match sentence.word(cur) {
      Some(row) =>
        match row.head() {
          Some(0) => return d + 1
          Some(h) =>
            if h == cur {
              return d
            } else {
              cur = h
              d = d + 1
            }
          None => return d
        }
      None => return d
    }
    steps = steps + 1
  }
  d
}

///|
/// Longest root-to-leaf distance in the sentence.
pub fn max_depth(sentence : Sentence) -> Int32 {
  let mut best : Int32 = 0
  for row in sentence.words() {
    let d = depth(sentence, row.start)
    if d > best {
      best = d
    }
  }
  best
}

///|
/// A sentence is projective when no two dependency arcs cross. An arc
/// `head -> dep` is projective iff every word strictly between them is a
/// descendant of `head`.
pub fn is_projective(sentence : Sentence) -> Bool {
  let mut ok = true
  for row in sentence.words() {
    match row.head() {
      Some(h) =>
        if h != 0 {
          let lo = if h < row.start { h } else { row.start }
          let hi = if h < row.start { row.start } else { h }
          let mut k = lo + 1
          while k < hi {
            if !is_ancestor(sentence, h, k) {
              ok = false
            }
            k = k + 1
          }
        }
      None => ()
    }
  }
  ok
}

///|
/// Root words of a sentence (HEAD == 0).
pub fn roots(sentence : Sentence) -> Array[Int32] {
  children(sentence, 0)
}

///|
/// True when the sentence has exactly one word attached to the root. A
/// well-formed CoNLL-U sentence is single-rooted by definition; this is the
/// cheap check for tooling that only needs that one property.
pub fn is_single_rooted(sentence : Sentence) -> Bool {
  roots(sentence).length() == 1
}

///|
/// Dependency path from `from` up to `to`, both inclusive, in the order
/// `from, ..., to`. Returns `None` when `to` is not an ancestor of `from` or an
/// index is out of range. `to = 0` walks all the way up to the artificial root.
pub fn path(sentence : Sentence, from : Int32, to : Int32) -> Array[Int32]? {
  let n = sentence.word_count()
  if from < 1 || from > n || to < 0 || to > n {
    return None
  }
  let out : Array[Int32] = []
  let mut cur = from
  let mut steps : Int32 = 0
  while steps <= n {
    out.push(cur)
    if cur == to {
      return Some(out)
    }
    if cur == 0 {
      return None
    }
    match sentence.word(cur) {
      Some(row) =>
        match row.head() {
          Some(h) => if h == cur { return None } else { cur = h }
          None => return None
        }
      None => return None
    }
    steps = steps + 1
  }
  None
}