//! Tree prefix rendering for the utilization table, vendored from
//! kubectl-view-allocations (CC0-1.0) after its 3.0 release made the
//! `tree` module private.

#[derive(Debug, Clone)]
struct TreeNode {
  parent: Option<usize>,
  level: Vec<bool>,
  children: Vec<usize>,
}

fn level_to_string(level: &[bool]) -> String {
  const EMPTY: &str = "   ";
  const EDGE: &str = " └─";
  const PIPE: &str = " │ ";
  const BRANCH: &str = " ├─";

  let mut prefix = String::new();
  if !level.is_empty() {
    let last_col = level.len() - 1;
    for (col, is_last_child) in level.iter().enumerate() {
      let is_last_col = col == last_col;
      let s = match (*is_last_child, is_last_col) {
        (true, false) => EMPTY,
        (true, true) => EDGE,
        (false, false) => PIPE,
        (false, true) => BRANCH,
      };
      prefix.push_str(s);
    }
  }
  prefix
}

fn write_tree_level_of_children(nodes: &mut [TreeNode], idx: usize) {
  if let Some(node) = nodes.get(idx) {
    let treenode = node.clone();
    let mut d = treenode.children.len();
    for s in treenode.children.iter() {
      if let Some(child) = nodes.get_mut(*s) {
        let mut lnext = treenode.level.clone();
        lnext.push(d == 1);
        d -= 1;
        child.level = lnext;
      }
    }
  }
}

fn make_tree_by_reverse_depth_first<I, F>(items: &[I], is_parent_of: F) -> Vec<TreeNode>
where
  F: Fn(&I, &I) -> bool,
{
  let mut current: Option<usize> = None;
  let mut nodes: Vec<TreeNode> = vec![];
  for (i, item) in items.iter().enumerate() {
    while current.is_some() && !is_parent_of(&items[current.unwrap()], item) {
      current = nodes.get_mut(current.unwrap()).and_then(|n| n.parent);
    }
    let treenode = TreeNode {
      parent: current,
      level: vec![],
      children: vec![],
    };
    if let Some(parent) = current {
      if let Some(node) = nodes.get_mut(parent) {
        node.children.push(i);
      }
    }
    nodes.push(treenode);
    current = Some(i);
  }
  nodes
}

/// Generate a list of prefix to display items as a tree (multi-root)
/// - the input should be sorted in the target display order
/// - the input order of items is preserved into output
/// - the input order is used to ask for parent of item (parent should be before child)
/// - output has the same number of elements as input `items`
/// - output can be zipped with input `items`
/// - is_parent_of(maybe_parent, item)
pub fn provide_prefix<I, F>(items: &[I], is_parent_of: F) -> Vec<String>
where
  F: Fn(&I, &I) -> bool,
{
  let mut nodes: Vec<TreeNode> = make_tree_by_reverse_depth_first(items, is_parent_of);
  for i in 0..nodes.len() {
    write_tree_level_of_children(&mut nodes, i);
  }
  nodes.iter().map(|n| level_to_string(&n.level)).collect()
}

#[cfg(test)]
mod tests {
  use super::*;

  #[test]
  fn test_provide_prefix() {
    let items = vec!["1/2", "1/2/3", "1/2/3/4", "1/2/5", "6", "7", "7/8", "7/9"];

    let prefixes = provide_prefix(&items, |parent, item| {
      let pi = item.split('/');
      let pp = parent.split('/');
      (pi.count() == pp.count() + 1) && item.starts_with(parent)
    });

    let mut actual = String::new();
    prefixes
      .iter()
      .zip(items)
      .for_each(|(p, i)| actual.push_str(&format!("{} {}\n", p, i)));

    let expected = " 1/2\n ├─ 1/2/3\n │  └─ 1/2/3/4\n └─ 1/2/5\n 6\n 7\n ├─ 7/8\n └─ 7/9\n";
    assert_eq!(actual, expected);
  }
}
