///|
fn graph_add_edge(
  result : Array[GraphEdge],
  from : Int,
  to : Int,
  relation : String,
  argument : Int,
) -> Unit {
  result.push({ from, to, relation, argument })
}

///|
fn graph_edges_from_value(
  result : Array[GraphEdge],
  from : Int,
  relation : String,
  argument : Int,
  value : Value,
) -> Unit {
  match value {
    Reference(to) => graph_add_edge(result, from, to, relation, argument)
    Typed(name~, value~) =>
      graph_edges_from_value(result, from, name, argument, value)
    List(values) =>
      for item in values {
        graph_edges_from_value(result, from, relation, argument, item)
      }
    _ => ()
  }
}

///|
fn graph_build_edges(index : ModelIndex) -> Array[GraphEdge] {
  let edges : Array[GraphEdge] = []
  for entity in index.all() {
    for argument, value in entity.arguments {
      graph_edges_from_value(edges, entity.id, entity.name, argument, value)
    }
  }
  edges
}

///|
fn graph_add_edge_map(
  map : Map[Int, Array[GraphEdge]],
  key : Int,
  edge : GraphEdge,
) -> Unit {
  map.update_or_default(key, [edge], values => {
    values.push(edge)
    values
  })
}

///|
pub fn EntityGraph::new(index : ModelIndex) -> EntityGraph {
  let nodes = index.all().map(entity => entity.id)
  let edges = graph_build_edges(index)
  let outgoing : Map[Int, Array[GraphEdge]] = Map([])
  let incoming : Map[Int, Array[GraphEdge]] = Map([])
  for edge in edges {
    graph_add_edge_map(outgoing, edge.from, edge)
    graph_add_edge_map(incoming, edge.to, edge)
  }
  { nodes, edges, outgoing, incoming }
}

///|
pub fn entity_graph(model : Model) -> EntityGraph {
  EntityGraph::new(model.index())
}

///|
pub fn EntityGraph::nodes(self : EntityGraph) -> Array[Int] {
  self.nodes.copy()
}

///|
pub fn EntityGraph::edges(self : EntityGraph) -> Array[GraphEdge] {
  self.edges.copy()
}

///|
pub fn EntityGraph::node_count(self : EntityGraph) -> Int {
  self.nodes.length()
}

///|
pub fn EntityGraph::edge_count(self : EntityGraph) -> Int {
  self.edges.length()
}

///|
pub fn EntityGraph::has_node(self : EntityGraph, id : Int) -> Bool {
  self.nodes.contains(id)
}

///|
pub fn EntityGraph::edges_from(
  self : EntityGraph,
  id : Int,
) -> Array[GraphEdge] {
  self.outgoing.get(id).unwrap_or([])
}

///|
pub fn EntityGraph::edges_to(self : EntityGraph, id : Int) -> Array[GraphEdge] {
  self.incoming.get(id).unwrap_or([])
}

///|
pub fn EntityGraph::outgoing_ids(self : EntityGraph, id : Int) -> Array[Int] {
  self.edges_from(id).map(edge => edge.to)
}

///|
pub fn EntityGraph::incoming_ids(self : EntityGraph, id : Int) -> Array[Int] {
  self.edges_to(id).map(edge => edge.from)
}

///|
pub fn EntityGraph::degree(self : EntityGraph, id : Int) -> GraphDegree {
  let incoming = self.edges_to(id).length()
  let outgoing = self.edges_from(id).length()
  {
    id,
    incoming,
    outgoing,
    total: incoming + outgoing,
    orphan: incoming == 0 && outgoing == 0,
  }
}

///|
pub fn EntityGraph::degrees(self : EntityGraph) -> Array[GraphDegree] {
  self.nodes.map(id => self.degree(id))
}

///|
fn graph_unique_ids(values : Array[Int]) -> Array[Int] {
  let result : Array[Int] = []
  for value in values {
    if !result.contains(value) {
      result.push(value)
    }
  }
  result
}

///|
pub fn EntityGraph::roots(self : EntityGraph) -> Array[Int] {
  self.nodes.filter(id => self.edges_to(id).length() == 0)
}

///|
pub fn EntityGraph::leaves(self : EntityGraph) -> Array[Int] {
  self.nodes.filter(id => self.edges_from(id).length() == 0)
}

///|
pub fn EntityGraph::orphans(self : EntityGraph) -> Array[Int] {
  self.nodes.filter(id => self.degree(id).orphan)
}

///|
pub fn EntityGraph::direct_dependencies(
  self : EntityGraph,
  id : Int,
) -> Array[Int] {
  graph_unique_ids(self.outgoing_ids(id))
}

///|
pub fn EntityGraph::direct_dependents(
  self : EntityGraph,
  id : Int,
) -> Array[Int] {
  graph_unique_ids(self.incoming_ids(id))
}

///|
fn graph_visit_forward(
  graph : EntityGraph,
  pending : Array[Int],
  visited : Map[Int, Bool],
) -> Array[Int] {
  let queue = pending.copy()
  let result : Array[Int] = []
  while queue.length() > 0 {
    let current = queue.remove(0)
    if visited.contains(current) {
      continue
    }
    visited[current] = true
    result.push(current)
    for next in graph.direct_dependencies(current) {
      if !visited.contains(next) {
        queue.push(next)
      }
    }
  }
  result
}

///|
fn graph_visit_backward(
  graph : EntityGraph,
  pending : Array[Int],
  visited : Map[Int, Bool],
) -> Array[Int] {
  let queue = pending.copy()
  let result : Array[Int] = []
  while queue.length() > 0 {
    let current = queue.remove(0)
    if visited.contains(current) {
      continue
    }
    visited[current] = true
    result.push(current)
    for next in graph.direct_dependents(current) {
      if !visited.contains(next) {
        queue.push(next)
      }
    }
  }
  result
}

///|
pub fn EntityGraph::reachable(
  self : EntityGraph,
  roots : Array[Int],
) -> Array[Int] {
  graph_visit_forward(self, roots, Map([]))
}

///|
pub fn EntityGraph::dependents(
  self : EntityGraph,
  roots : Array[Int],
) -> Array[Int] {
  graph_visit_backward(self, roots, Map([]))
}

///|
fn graph_edge_between(graph : EntityGraph, from : Int, to : Int) -> GraphEdge? {
  for edge in graph.edges_from(from) {
    if edge.to == to {
      return Some(edge)
    }
  }
  None
}

///|
/// Find a shortest reference path, useful for explaining why two IFC records are connected.
pub fn EntityGraph::shortest_path(
  self : EntityGraph,
  start : Int,
  goal : Int,
) -> GraphPath? {
  if start == goal {
    return Some({ ids: [start], edges: [], total_cost: 0 })
  }
  let queue : Array[Int] = [start]
  let visited : Map[Int, Bool] = Map([])
  let parents : Map[Int, Int] = Map([])
  visited[start] = true
  while queue.length() > 0 {
    let current = queue.remove(0)
    for next in self.direct_dependencies(current) {
      if visited.contains(next) {
        continue
      }
      visited[next] = true
      parents[next] = current
      if next == goal {
        queue.clear()
        break
      }
      queue.push(next)
    }
  }
  if !visited.contains(goal) {
    return None
  }
  let ids : Array[Int] = []
  let mut cursor = goal
  ids.push(cursor)
  while cursor != start {
    match parents.get(cursor) {
      Some(parent) => {
        cursor = parent
        ids.push(cursor)
      }
      None => break
    }
  }
  let ordered : Array[Int] = []
  for index in 0.. edges.push(edge)
        None => ()
      }
    }
  }
  Some({ ids: ordered, edges, total_cost: edges.length() })
}

///|
fn graph_neighbors_undirected(graph : EntityGraph, id : Int) -> Array[Int] {
  graph_unique_ids(graph.direct_dependencies(id) + graph.direct_dependents(id))
}

///|
fn graph_component(
  graph : EntityGraph,
  start : Int,
  visited : Map[Int, Bool],
) -> GraphComponent {
  let queue : Array[Int] = [start]
  let ids : Array[Int] = []
  let mut edge_count = 0
  let mut cyclic = false
  while queue.length() > 0 {
    let current = queue.remove(0)
    if visited.contains(current) {
      continue
    }
    visited[current] = true
    ids.push(current)
    let neighbors = graph_neighbors_undirected(graph, current)
    edge_count += neighbors.length()
    if graph.direct_dependencies(current).contains(current) {
      cyclic = true
    }
    for next in neighbors {
      if visited.contains(next) {
        if next != current {
          cyclic = true
        }
      } else {
        queue.push(next)
      }
    }
  }
  { root: start, entity_ids: ids, edge_count: edge_count / 2, cyclic }
}

///|
pub fn EntityGraph::components(self : EntityGraph) -> Array[GraphComponent] {
  let visited : Map[Int, Bool] = Map([])
  let result : Array[GraphComponent] = []
  for id in self.nodes {
    if !visited.contains(id) {
      result.push(graph_component(self, id, visited))
    }
  }
  result
}

///|
fn graph_path_depth(graph : EntityGraph, id : Int, stack : Array[Int]) -> Int {
  if stack.contains(id) {
    return stack.length()
  }
  let next_stack = stack.copy()
  next_stack.push(id)
  let mut maximum = next_stack.length()
  for child in graph.direct_dependencies(id) {
    let depth = graph_path_depth(graph, child, next_stack)
    if depth > maximum {
      maximum = depth
    }
  }
  maximum
}

///|
fn graph_stack_position(stack : Array[Int], wanted : Int) -> Int {
  for index, value in stack {
    if value == wanted {
      return index
    }
  }
  0
}

///|
fn graph_cycle_from(
  graph : EntityGraph,
  id : Int,
  visiting : Map[Int, Bool],
  visited : Map[Int, Bool],
  stack : Array[Int],
) -> Array[Int]? {
  if visiting.contains(id) {
    let position = graph_stack_position(stack, id)
    let cycle : Array[Int] = []
    for index in position.. return Some(cycle)
      None => ()
    }
  }
  visiting.remove(id)
  visited[id] = true
  None
}

///|
pub fn EntityGraph::cycles(self : EntityGraph) -> Array[Array[Int]] {
  let visiting : Map[Int, Bool] = Map([])
  let visited : Map[Int, Bool] = Map([])
  let result : Array[Array[Int]] = []
  for id in self.nodes {
    match graph_cycle_from(self, id, visiting, visited, []) {
      Some(cycle) if !result.any(item => item == cycle) => result.push(cycle)
      _ => ()
    }
  }
  result
}

///|
fn graph_indegrees(graph : EntityGraph) -> Map[Int, Int] {
  let result : Map[Int, Int] = Map([])
  for id in graph.nodes {
    result[id] = 0
  }
  for edge in graph.edges {
    result.update_or_default(edge.to, 1, value => value + 1)
  }
  result
}

///|
/// Return a stable topological order; cyclic nodes are appended in source order.
pub fn EntityGraph::topological_order(self : EntityGraph) -> Array[Int] {
  let indegrees = graph_indegrees(self)
  let queue : Array[Int] = self.nodes.filter(id => {
    indegrees.get(id).unwrap_or(0) == 0
  })
  let result : Array[Int] = []
  while queue.length() > 0 {
    let id = queue.remove(0)
    result.push(id)
    for child in self.direct_dependencies(id) {
      let next = indegrees.get(child).unwrap_or(0) - 1
      indegrees[child] = next
      if next == 0 {
        queue.push(child)
      }
    }
  }
  for id in self.nodes {
    if !result.contains(id) {
      result.push(id)
    }
  }
  result
}

///|
fn graph_max_depth(graph : EntityGraph) -> Int {
  graph.nodes.fold(init=0, (result, id) => {
    let depth = graph_path_depth(graph, id, [])
    if depth > result {
      depth
    } else {
      result
    }
  })
}

///|
pub fn analyze_entity_graph(graph : EntityGraph) -> GraphAnalysis {
  let components = graph.components()
  {
    nodes: graph.nodes.length(),
    edges: graph.edges.length(),
    roots: graph.roots(),
    leaves: graph.leaves(),
    components,
    cycles: graph.cycles(),
    max_depth: graph_max_depth(graph),
    orphan_ids: graph.orphans(),
  }
}

///|
pub fn graph_analysis(model : Model) -> GraphAnalysis {
  analyze_entity_graph(entity_graph(model))
}

///|
pub fn GraphAnalysis::is_acyclic(self : GraphAnalysis) -> Bool {
  self.cycles.length() == 0
}

///|
pub fn GraphAnalysis::component_count(self : GraphAnalysis) -> Int {
  self.components.length()
}

///|
pub fn GraphAnalysis::cycle_count(self : GraphAnalysis) -> Int {
  self.cycles.length()
}

///|
pub fn GraphAnalysis::orphan_count(self : GraphAnalysis) -> Int {
  self.orphan_ids.length()
}

///|
pub fn GraphAnalysis::largest_component(
  self : GraphAnalysis,
) -> GraphComponent? {
  let mut result : GraphComponent? = None
  for component in self.components {
    match result {
      Some(current) if current.entity_ids.length() >=
        component.entity_ids.length() => ()
      _ => result = Some(component)
    }
  }
  result
}

///|
pub fn GraphAnalysis::headline(self : GraphAnalysis) -> String {
  "nodes=" +
  self.nodes.to_string() +
  " edges=" +
  self.edges.to_string() +
  " roots=" +
  self.roots.length().to_string() +
  " leaves=" +
  self.leaves.length().to_string() +
  " components=" +
  self.components.length().to_string() +
  " cycles=" +
  self.cycles.length().to_string()
}

///|
pub fn GraphDegree::headline(self : GraphDegree) -> String {
  "#" +
  self.id.to_string() +
  " in=" +
  self.incoming.to_string() +
  " out=" +
  self.outgoing.to_string()
}

///|
pub fn GraphEdge::headline(self : GraphEdge) -> String {
  "#" +
  self.from.to_string() +
  " -> #" +
  self.to.to_string() +
  " " +
  self.relation +
  "[" +
  self.argument.to_string() +
  "]"
}

///|
pub fn GraphPath::headline(self : GraphPath) -> String {
  self.ids.map(id => "#" + id.to_string()).join(" -> ") +
  " cost=" +
  self.total_cost.to_string()
}

///|
pub fn GraphComponent::headline(self : GraphComponent) -> String {
  "root=#" +
  self.root.to_string() +
  " nodes=" +
  self.entity_ids.length().to_string() +
  " edges=" +
  self.edge_count.to_string() +
  " cyclic=" +
  self.cyclic.to_string()
}

///|
pub fn GraphAnalysis::to_json(self : GraphAnalysis) -> String {
  let roots = self.roots.map(id => id.to_string()).join(",")
  let leaves = self.leaves.map(id => id.to_string()).join(",")
  let orphans = self.orphan_ids.map(id => id.to_string()).join(",")
  let cycles = self.cycles
    .map(cycle => "[" + cycle.map(id => id.to_string()).join(",") + "]")
    .join(",")
  "{\"nodes\":" +
  self.nodes.to_string() +
  ",\"edges\":" +
  self.edges.to_string() +
  ",\"roots\":[" +
  roots +
  "],\"leaves\":[" +
  leaves +
  "],\"orphan_ids\":[" +
  orphans +
  "],\"max_depth\":" +
  self.max_depth.to_string() +
  ",\"cycles\":[" +
  cycles +
  "]}"
}

///|
pub fn GraphAnalysis::to_markdown(self : GraphAnalysis) -> String {
  let builder = StringBuilder()
  builder <+ "# Entity graph\n\n"
  builder <+ "- Nodes: \{self.nodes}\n"
  builder <+ "- Edges: \{self.edges}\n"
  builder <+ "- Components: \{self.components.length()}\n"
  builder <+ "- Cycles: \{self.cycles.length()}\n"
  builder <+ "- Maximum depth: \{self.max_depth}\n"
  if self.orphan_ids.length() > 0 {
    builder <+
      "\nOrphans: \{self.orphan_ids.map(id => id.to_string()).join(", ")}\n"
  }
  builder.to_string()
}

///|
pub fn graph_path(model : Model, start : Int, goal : Int) -> GraphPath? {
  entity_graph(model).shortest_path(start, goal)
}

///|
pub fn graph_reachable(model : Model, roots : Array[Int]) -> Array[Int] {
  entity_graph(model).reachable(roots)
}

///|
pub fn graph_dependents(model : Model, targets : Array[Int]) -> Array[Int] {
  entity_graph(model).dependents(targets)
}

///|
pub fn graph_degrees(model : Model) -> Array[GraphDegree] {
  entity_graph(model).degrees()
}

///|
pub fn graph_topological_order(model : Model) -> Array[Int] {
  entity_graph(model).topological_order()
}

///|
pub fn graph_cycles(model : Model) -> Array[Array[Int]] {
  entity_graph(model).cycles()
}

///|
pub fn graph_component_for(model : Model, id : Int) -> GraphComponent? {
  let graph = entity_graph(model)
  for component in graph.components() {
    if component.entity_ids.contains(id) {
      return Some(component)
    }
  }
  None
}