From 1bce88f12244564a45a3aefa3bf51974fda4b4f4 Mon Sep 17 00:00:00 2001
From: metamuffin <metamuffin@disroot.org>
Date: Sun, 12 Oct 2025 22:32:06 +0200
Subject: reimplement diagram layouting

---
 server/data/src/book/diagram_layout.rs | 107 ++++++++++++++++++---------------
 1 file changed, 57 insertions(+), 50 deletions(-)

(limited to 'server/data/src')

diff --git a/server/data/src/book/diagram_layout.rs b/server/data/src/book/diagram_layout.rs
index 29240b69..cd929f44 100644
--- a/server/data/src/book/diagram_layout.rs
+++ b/server/data/src/book/diagram_layout.rs
@@ -16,15 +16,12 @@
 
 */
 
-use anyhow::{Result, anyhow};
-use hurrycurry_protocol::{book::Diagram, glam::Vec2};
-use serde::Deserialize;
-use std::{
-    collections::BTreeMap,
-    fmt::Write as W2,
-    io::Write,
-    process::{Command, Stdio},
+use anyhow::Result;
+use hurrycurry_protocol::{
+    book::Diagram,
+    glam::{Vec2, vec2},
 };
+use std::collections::{BTreeMap, BTreeSet};
 
 pub struct Layout {
     pub nodes: BTreeMap<String, Vec2>,
@@ -32,52 +29,62 @@ pub struct Layout {
 }
 
 pub fn diagram_layout(diagram: &mut Diagram) -> Result<()> {
-    // seems to have problems with a single node
-    if diagram.nodes.len() < 2 {
-        return Ok(());
-    }
+    let mut graph = Graph {
+        vertices: (0..diagram.nodes.len())
+            .map(|i| vec2(i as f32, i as f32) * 30.)
+            .collect(),
+        edges: diagram.edges.iter().map(|e| (e.src, e.dst)).collect(),
+    };
 
-    let mut child = Command::new("dot")
-        .arg("-Tjson")
-        .arg("-Kdot")
-        .stdin(Stdio::piped())
-        .stdout(Stdio::piped())
-        .spawn()?;
+    graph.layout();
 
-    let mut out = String::new();
-    writeln!(out, "digraph {{")?;
-    for (i, _) in diagram.nodes.iter().enumerate() {
-        writeln!(out, "k{i} [width=1, height=1]")?;
-    }
-    for edge in &diagram.edges {
-        writeln!(out, "k{} -> k{}", edge.src, edge.dst)?;
-    }
-    writeln!(out, "}}")?;
+    diagram
+        .nodes
+        .iter_mut()
+        .zip(graph.vertices.iter())
+        .for_each(|(n, v)| n.position = *v);
 
-    child.stdin.as_mut().unwrap().write_all(out.as_bytes())?;
-    let output = child.wait_with_output()?;
+    Ok(())
+}
 
-    #[derive(Deserialize)]
-    struct Out {
-        objects: Vec<Object>,
-    }
-    #[derive(Deserialize)]
-    struct Object {
-        name: String,
-        pos: String,
-    }
-    let graph: Out = serde_json::from_slice(&output.stdout)?;
-    for o in graph.objects {
-        let pos = o.pos.split_once(",").ok_or(anyhow!("malformed position"))?;
-        let pos = Vec2::new(pos.0.parse()?, pos.1.parse()?);
+pub struct Graph {
+    pub vertices: Vec<Vec2>,
+    pub edges: Vec<(usize, usize)>,
+}
+impl Graph {
+    pub fn layout(&mut self) {
+        let mut layers = Vec::new();
+        let mut previous_layers = BTreeSet::new();
 
-        let index = o
-            .name
-            .strip_prefix("k")
-            .ok_or(anyhow!("invalid node name"))?
-            .parse::<usize>()?;
-        diagram.nodes[index].position = pos
-    }
+        let mut to_insert = Vec::new();
+        to_insert.extend(0..self.vertices.len());
 
-    Ok(())
+        while !to_insert.is_empty() {
+            let mut next_layer = Vec::new();
+            to_insert.retain(|&vi| {
+                for &(src, dst) in &self.edges {
+                    if src == vi && !previous_layers.contains(&dst) {
+                        return true;
+                    }
+                }
+                next_layer.push(vi);
+                false
+            });
+            previous_layers.extend(next_layer.iter().copied());
+            layers.push(next_layer);
+        }
+
+        for y in 0..layers.iter().len() {
+            let mut layer = layers[y].clone();
+            layer.sort_by_cached_key(|&vi| {
+                self.edges
+                    .iter()
+                    .find(|&&(src, _)| src == vi)
+                    .map_or(0, |&(_, dst)| (self.vertices[dst].x * 100.) as i64)
+            });
+            for (x, &vi) in layer.iter().enumerate() {
+                self.vertices[vi] = vec2(x as f32 - layer.len() as f32 / 2., y as f32) * 100.;
+            }
+        }
+    }
 }
-- 
cgit v1.3