///|
/// A read-only snapshot of a graph in compressed adjacency form: one flat array
/// of neighbours per direction, with an offset per node.
///
/// Building costs one pass and one sort; every later `neighbors` call is a slice
/// of the flat array, which is what makes this the type to hand to an algorithm
/// that walks the same graph a million times. An undirected edge sits in both
/// directions, and each node's slice is sorted by target and then by edge number,
/// so two walks over the same edges visit them in the same order.
///
/// Edge numbers are the snapshot's own, dense from 0 and in the order the source
/// graph reported them.
///
/// ```mbt check
/// test {
///   let g : @moongraph.Graph[Unit, Int32] = @moongraph.Graph::from_edges(
///     [(0, 1), (1, 2)],
///     node=(),
///     edge=0,
///     directed=false,
///   )
///   let csr = @moongraph.Csr::from(g)
///   assert_eq(csr.node_count(), 3)
///   assert_eq(csr.neighbors(1), [0, 2][:])
///   assert_eq(csr.in_neighbors(2), [1][:])
/// }
/// ```
pub struct Csr[N, E] {
  directed : Bool
  n : Int32
  node_payload : Array[N]
  edge_payload : Array[E]
  froms : Array[Int32]
  tos : Array[Int32]
  f_off : Array[Int32]
  f_nbr : Array[Int32]
  f_eid : Array[Int32]
  r_off : Array[Int32]
  r_nbr : Array[Int32]
  r_eid : Array[Int32]
  scratch : Array[Int32]
}

///|
/// Builds the snapshot from a `Graph`.
pub fn[N, E] Csr::from(graph : Graph[N, E]) -> Csr[N, E] {
  let n = graph.node_count()
  let payload : Array[E] = []
  let froms : Array[Int32] = []
  let tos : Array[Int32] = []
  for eid in graph.edges() {
    payload.push(graph.edge_data(eid))
    let (from, to) = graph.endpoints(eid)
    froms.push(from)
    tos.push(to)
  }
  let nodes : Array[N] = []
  for node in graph.nodes() {
    nodes.push(graph.node_data(node))
  }
  Csr::assemble(graph.directed(), nodes, n, payload, froms, tos)
}

///|
/// Builds the snapshot from a `StableGraph`. Vacant numbers stay vacant: the
/// snapshot keeps the same node numbering, which is the point of the stable form.
pub fn[N, E] Csr::from_stable(graph : StableGraph[N, E]) -> Csr[N, E] {
  let n = graph.slot_count()
  let payload : Array[E] = []
  let froms : Array[Int32] = []
  let tos : Array[Int32] = []
  for eid in graph.edges() {
    payload.push(graph.edge_data(eid))
    let (from, to) = graph.endpoints(eid)
    froms.push(from)
    tos.push(to)
  }
  let nodes : Array[N] = []
  for node in 0.. Csr[N, E] {
  let forward : Array[Array[(Int32, Int32)]] = Array::makei(n, fn(_) {
    ([] : Array[(Int32, Int32)])
  })
  let reverse : Array[Array[(Int32, Int32)]] = Array::makei(n, fn(_) {
    ([] : Array[(Int32, Int32)])
  })
  for eid in 0..= 0 && from < n && to >= 0 && to < n {
      forward[from].push((to, eid))
      reverse[to].push((from, eid))
      if !directed && from != to {
        forward[to].push((from, eid))
        reverse[from].push((to, eid))
      }
    }
  }
  let f_off : Array[Int32] = [0]
  let f_nbr : Array[Int32] = []
  let f_eid : Array[Int32] = []
  for node in 0.. N {
  self.node_payload[node]
}

///|
/// The payload of an edge.
pub fn[N, E] Csr::edge_data(self : Csr[N, E], edge : Int32) -> E {
  self.edge_payload[edge]
}

///|
/// A weight function over edge numbers, derived from one over payloads.
pub fn[N, E] Csr::weights(
  self : Csr[N, E],
  of : (E) -> Double,
) -> (Int32) -> Double {
  fn(edge) { of(self.edge_payload[edge]) }
}

///|
/// Back to a mutable graph carrying the same payloads and the same numbering.
pub fn[N, E] Csr::to_graph(self : Csr[N, E]) -> Graph[N, E] {
  let g : Graph[N, E] = Graph::new(directed=self.directed)
  for node in 0.. ignore
  }
  for eid in 0.. ignore
  }
  g
}

///|
pub impl[N, E] Topology for Csr[N, E] with fn node_count(self) {
  self.n
}

///|
pub impl[N, E] Topology for Csr[N, E] with fn edge_count(self) {
  self.froms.length()
}

///|
pub impl[N, E] Topology for Csr[N, E] with fn directed(self) {
  self.directed
}

///|
pub impl[N, E] Topology for Csr[N, E] with fn neighbors(self, node) {
  if node < 0 || node >= self.n {
    return self.scratch.exact_view(start=0, end=0)
  }
  let start = self.f_off[node]
  let stop = self.f_off[node + 1]
  self.f_nbr.exact_view(start~, end=stop)
}

///|
pub impl[N, E] Topology for Csr[N, E] with fn incident(self, node) {
  if node < 0 || node >= self.n {
    return self.scratch.exact_view(start=0, end=0)
  }
  let start = self.f_off[node]
  let stop = self.f_off[node + 1]
  self.f_eid.exact_view(start~, end=stop)
}

///|
pub impl[N, E] Topology for Csr[N, E] with fn endpoints(self, edge) {
  if edge < 0 || edge >= self.froms.length() {
    return (-1, -1)
  }
  (self.froms[edge], self.tos[edge])
}

///|
pub impl[N, E] Inbound for Csr[N, E] with fn in_neighbors(self, node) {
  if node < 0 || node >= self.n {
    return self.scratch.exact_view(start=0, end=0)
  }
  let start = self.r_off[node]
  let stop = self.r_off[node + 1]
  self.r_nbr.exact_view(start~, end=stop)
}

///|
pub impl[N, E] Inbound for Csr[N, E] with fn in_incident(self, node) {
  if node < 0 || node >= self.n {
    return self.scratch.exact_view(start=0, end=0)
  }
  let start = self.r_off[node]
  let stop = self.r_off[node + 1]
  self.r_eid.exact_view(start~, end=stop)
}

///|
pub extend Csr with Topology::{
  node_count,
  edge_count,
  directed,
  neighbors,
  incident,
  endpoints,
}

///|
pub extend Csr with Inbound::{in_neighbors, in_incident}