///|
/// A dependency graph for arranging independent motion lanes in a
/// composition. Nodes carry timing only; payloads can remain in application
/// code and be sampled through the returned schedule.
pub struct TimelineGraphNode {
  id : Int
  name : String
  start : Double
  duration : Double
  enabled : Bool
} derive(Debug)

///|
pub fn timeline_graph_node(
  id : Int,
  name : String,
  start : Double,
  duration : Double,
) -> TimelineGraphNode {
  { id, name, start, duration: duration.max(0.0), enabled: true }
}

///|
pub fn TimelineGraphNode::id(self : TimelineGraphNode) -> Int {
  self.id
}

///|
pub fn TimelineGraphNode::name(self : TimelineGraphNode) -> String {
  self.name
}

///|
pub fn TimelineGraphNode::start(self : TimelineGraphNode) -> Double {
  self.start
}

///|
pub fn TimelineGraphNode::duration(self : TimelineGraphNode) -> Double {
  self.duration
}

///|
pub fn TimelineGraphNode::end(self : TimelineGraphNode) -> Double {
  self.start + self.duration
}

///|
pub fn TimelineGraphNode::enabled(self : TimelineGraphNode) -> Bool {
  self.enabled
}

///|
pub fn TimelineGraphNode::with_enabled(
  self : TimelineGraphNode,
  enabled : Bool,
) -> TimelineGraphNode {
  {
    id: self.id,
    name: self.name,
    start: self.start,
    duration: self.duration,
    enabled,
  }
}

///|
pub enum TimelineEdgeKind {
  StartAfterEnd
  StartAfterStart
  EndWithEnd
  OffsetLink(Double)
} derive(Debug)

///|
pub fn timeline_edge_kinds() -> Array[TimelineEdgeKind] {
  [StartAfterEnd, StartAfterStart, EndWithEnd, OffsetLink(0.0)]
}

///|
pub struct TimelineGraphEdge {
  from : Int
  to : Int
  kind : TimelineEdgeKind
} derive(Debug)

///|
pub fn timeline_graph_edge(
  from : Int,
  to : Int,
  kind : TimelineEdgeKind,
) -> TimelineGraphEdge {
  { from, to, kind }
}

///|
pub fn TimelineGraphEdge::from(self : TimelineGraphEdge) -> Int {
  self.from
}

///|
pub fn TimelineGraphEdge::to(self : TimelineGraphEdge) -> Int {
  self.to
}

///|
pub fn TimelineGraphEdge::kind(self : TimelineGraphEdge) -> TimelineEdgeKind {
  self.kind
}

///|
pub enum GraphBuildStatus {
  GraphReady
  GraphCycle
  GraphMissingNode
} derive(Debug)

///|
pub fn graph_build_statuses() -> Array[GraphBuildStatus] {
  [GraphReady, GraphCycle, GraphMissingNode]
}

///|
pub struct TimelineGraph {
  nodes : Array[TimelineGraphNode]
  edges : Array[TimelineGraphEdge]
} derive(Debug)

///|
pub fn timeline_graph() -> TimelineGraph {
  { nodes: [], edges: [] }
}

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

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

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

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

///|
fn TimelineGraph::find_index(self : TimelineGraph, id : Int) -> Int? {
  for index in 0.. Bool {
  if self.find_index(node.id) is Some(_) {
    return false
  }
  self.nodes.push(node)
  true
}

///|
pub fn TimelineGraph::add_edge(
  self : TimelineGraph,
  edge : TimelineGraphEdge,
) -> GraphBuildStatus {
  if self.find_index(edge.from) is None || self.find_index(edge.to) is None {
    return GraphMissingNode
  }
  self.edges.push(edge)
  if self.has_cycle() {
    ignore(self.edges.remove(self.edges.length() - 1))
    GraphCycle
  } else {
    GraphReady
  }
}

///|
fn TimelineGraph::outgoing(self : TimelineGraph, id : Int) -> Array[Int] {
  let result : Array[Int] = []
  for edge in self.edges {
    if edge.from == id {
      result.push(edge.to)
    }
  }
  result
}

///|
pub fn TimelineGraph::has_cycle(self : TimelineGraph) -> Bool {
  let visiting : Array[Int] = []
  let visited : Array[Int] = []
  fn visit(
    graph : TimelineGraph,
    id : Int,
    visiting : Array[Int],
    visited : Array[Int],
  ) -> Bool {
    if visiting.contains(id) {
      return true
    }
    if visited.contains(id) {
      return false
    }
    visiting.push(id)
    for next in graph.outgoing(id) {
      if visit(graph, next, visiting, visited) {
        return true
      }
    }
    ignore(visiting.remove(visiting.length() - 1))
    visited.push(id)
    false
  }
  for node in self.nodes {
    if visit(self, node.id, visiting, visited) {
      return true
    }
  }
  false
}

///|
pub fn TimelineGraph::topological_order(self : TimelineGraph) -> Array[Int] {
  let result : Array[Int] = []
  let indegree : Array[Int] = []
  for _ in self.nodes {
    indegree.push(0)
  }
  for edge in self.edges {
    if self.find_index(edge.to) is Some(index) {
      indegree[index] = indegree[index] + 1
    }
  }
  let queue : Array[Int] = []
  for index in 0.. Double {
  match kind {
    StartAfterEnd => source.end()
    StartAfterStart => source.start
    EndWithEnd => source.end() - target.duration
    OffsetLink(offset) => source.start + offset
  }
}

///|
pub fn TimelineGraph::resolve(self : TimelineGraph) -> GraphBuildStatus {
  if self.has_cycle() {
    return GraphCycle
  }
  for id in self.topological_order() {
    if self.find_index(id) is Some(target_index) {
      let target = self.nodes[target_index]
      for edge in self.edges {
        if edge.to == id && self.find_index(edge.from) is Some(source_index) {
          let source = self.nodes[source_index]
          let requested = apply_edge(target.start, source, target, edge.kind)
          self.nodes[target_index] = target.with_start(
            requested.max(target.start),
          )
        }
      }
    }
  }
  GraphReady
}

///|
pub fn TimelineGraphNode::with_start(
  self : TimelineGraphNode,
  start : Double,
) -> TimelineGraphNode {
  {
    id: self.id,
    name: self.name,
    start,
    duration: self.duration,
    enabled: self.enabled,
  }
}

///|
pub fn TimelineGraph::time_range(self : TimelineGraph) -> (Double, Double) {
  if self.nodes.length() == 0 {
    return (0.0, 0.0)
  }
  let mut first = self.nodes[0].start
  let mut last = self.nodes[0].end()
  for node in self.nodes {
    first = first.min(node.start)
    last = last.max(node.end())
  }
  (first, last)
}

///|
pub fn TimelineGraph::active_at(
  self : TimelineGraph,
  time : Double,
) -> Array[TimelineGraphNode] {
  let result : Array[TimelineGraphNode] = []
  for node in self.nodes {
    if node.enabled && time >= node.start && time <= node.end() {
      result.push(node)
    }
  }
  result
}

///|
pub fn TimelineGraph::shift(
  self : TimelineGraph,
  delta : Double,
) -> TimelineGraph {
  let nodes : Array[TimelineGraphNode] = []
  for node in self.nodes {
    nodes.push(node.with_start(node.start + delta))
  }
  { nodes, edges: self.edges.copy() }
}

///|
pub struct TimelineGraphSample {
  time : Double
  active_ids : Array[Int]
  progress : Array[Double]
} derive(Debug)

///|
pub fn TimelineGraphSample::time(self : TimelineGraphSample) -> Double {
  self.time
}

///|
pub fn TimelineGraphSample::active_ids(
  self : TimelineGraphSample,
) -> Array[Int] {
  self.active_ids.copy()
}

///|
pub fn TimelineGraphSample::progress(
  self : TimelineGraphSample,
) -> Array[Double] {
  self.progress.copy()
}

///|
pub fn TimelineGraph::sample(
  self : TimelineGraph,
  time : Double,
) -> TimelineGraphSample {
  let active_ids : Array[Int] = []
  let progress : Array[Double] = []
  for node in self.active_at(time) {
    active_ids.push(node.id)
    progress.push(
      if node.duration == 0.0 {
        1.0
      } else {
        clamp01((time - node.start) / node.duration)
      },
    )
  }
  { time, active_ids, progress }
}