Skip to main content

ratatui_flow/
connection.rs

1use ratatui::{
2	buffer::Buffer,
3	layout::{Position, Rect},
4	style::{Color, Style},
5	symbols::line,
6	widgets::BorderType,
7};
8use std::collections::{BTreeMap as Map, BinaryHeap};
9
10use crate::id::{NodeId, PortId};
11
12const SEARCH_TIMEOUT: usize = 5000;
13
14#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, Hash)]
15pub enum LineType {
16	#[default]
17	Plain,
18	Rounded,
19	Double,
20	Thick,
21}
22
23impl LineType {
24	fn to_line_set(self) -> line::Set<'static> {
25		match self {
26			LineType::Plain => line::NORMAL,
27			LineType::Rounded => line::ROUNDED,
28			LineType::Double => line::DOUBLE,
29			LineType::Thick => line::THICK,
30		}
31	}
32}
33
34impl From<BorderType> for LineType {
35	fn from(value: BorderType) -> Self {
36		match value {
37			BorderType::Plain => LineType::Plain,
38			BorderType::Rounded => LineType::Rounded,
39			BorderType::Double => LineType::Double,
40			BorderType::Thick => LineType::Thick,
41			BorderType::LightDoubleDashed
42			| BorderType::LightTripleDashed
43			| BorderType::LightQuadrupleDashed => LineType::Plain,
44			BorderType::HeavyDoubleDashed
45			| BorderType::HeavyTripleDashed
46			| BorderType::HeavyQuadrupleDashed => LineType::Thick,
47			BorderType::QuadrantInside | BorderType::QuadrantOutside => LineType::Plain,
48		}
49	}
50}
51
52#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
53pub(crate) enum Direction {
54	North = 0,
55	South = 1,
56	East = 2,
57	West = 3,
58}
59
60impl Direction {
61	fn is_vertical(&self) -> bool {
62		(*self as usize) < 2
63	}
64	/*
65	fn invert(self) -> Self {
66		use Direction as D;
67		match self {
68			D::North => D::South,
69			D::South => D::North,
70			D::East => D::West,
71			D::West => D::East,
72		}
73	}
74	fn rotate(self) -> Self {
75		use Direction as D;
76		match self {
77			D::North => D::East,
78			D::East => D::South,
79			D::South => D::West,
80			D::West => D::North,
81		}
82	}
83	*/
84}
85
86impl std::fmt::Debug for Direction {
87	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
88		let print = match self {
89			Direction::North => '↑',
90			Direction::South => '↓',
91			Direction::East => '→',
92			Direction::West => '←',
93		};
94		write!(f, "{}", print)
95	}
96}
97
98#[derive(Debug, Clone, Copy)]
99pub struct Connection<'a> {
100	pub(crate) from_node: NodeId,
101	pub(crate) from_port: PortId,
102	pub(crate) to_node: NodeId,
103	pub(crate) to_port: PortId,
104	line_type: LineType,
105	line_style: Style,
106	label: Option<&'a str>,
107}
108
109impl<'a> Connection<'a> {
110	pub fn new(
111		from_node: NodeId,
112		from_port: PortId,
113		to_node: NodeId,
114		to_port: PortId,
115	) -> Self {
116		Self {
117			from_node,
118			from_port,
119			to_node,
120			to_port,
121			line_type: LineType::Rounded,
122			line_style: Style::default(),
123			label: None,
124		}
125	}
126
127	pub fn from_node(&self) -> NodeId {
128		self.from_node
129	}
130
131	pub fn from_port(&self) -> PortId {
132		self.from_port
133	}
134
135	pub fn to_node(&self) -> NodeId {
136		self.to_node
137	}
138
139	pub fn to_port(&self) -> PortId {
140		self.to_port
141	}
142
143	pub fn with_line_type(mut self, line_type: LineType) -> Self {
144		self.line_type = line_type;
145		self
146	}
147
148	pub fn line_type(&self) -> LineType {
149		self.line_type
150	}
151
152	pub fn with_line_style(mut self, line_style: Style) -> Self {
153		self.line_style = line_style;
154		self
155	}
156
157	pub fn line_style(&self) -> Style {
158		self.line_style
159	}
160
161	/// Attach a **label** to this connection, rendered horizontally at the
162	/// midpoint of the routed path on top of the line (with a solid background
163	/// so the line stays readable under the text).
164	///
165	/// Labels are purely opt-in: a connection built without `with_label` has
166	/// `label == None` and renders identically to a label-less graph.
167	///
168	/// The label is borrowed for the connection's lifetime `'a`, so `Connection`
169	/// stays `Copy` and can be used exactly as before (`add_connection`,
170	/// `.copied()`, etc.). Passing a `&'static str` is the common case.
171	///
172	/// The label text is truncated on screen to fit (see [`label`]); in
173	/// vertical layouts (`Ttb`/`Btt`) it is still written horizontally (the
174	/// terminal cannot rotate text), which may overlap neighbouring nodes —
175	/// this is an accepted visual compromise.
176	///
177	/// [`label`]: Self::label
178	#[must_use]
179	pub fn with_label(mut self, label: &'a str) -> Self {
180		self.label = Some(label);
181		self
182	}
183
184	/// The label attached via [`with_label`], or `None` (the default).
185	pub fn label(&self) -> Option<&str> {
186		self.label
187	}
188}
189
190/// Layout/routing problems detected during [`NodeGraph::calculate`][crate::NodeGraph::calculate] that would
191/// otherwise fail silently (a node not placed, a bad connection ignored, or a
192/// connection that couldn't be routed and fell back to an alias character).
193///
194/// Retrieve them via [`NodeGraph::diagnostics`][crate::NodeGraph::diagnostics].
195/// They are also emitted through `log::warn!`.
196#[derive(Debug, Clone, PartialEq, Eq)]
197pub enum Diagnostic {
198	/// A node is unreachable (not on any root node's upstream chain — e.g. a pure
199	/// cycle or an isolated node) and was therefore not placed.
200	UnplacedNode {
201		node: NodeId,
202	},
203	/// A connection referenced an out-of-bounds node index and was ignored.
204	InvalidConnectionRef {
205		from_node: NodeId,
206		to_node: NodeId,
207	},
208	/// A connection could not be routed (the search timed out or found no path)
209	/// and was downgraded to an alias character for display.
210	RoutingFailed {
211		from_node: NodeId,
212		from_port: PortId,
213		to_node: NodeId,
214		to_port: PortId,
215	},
216}
217
218/// Generate the correct connection symbol for this node.
219///
220/// `is_input` selects the in-port (┤) vs out-port (├) variant. `vertical`
221/// switches between horizontal-edge ports (drawn on the left/right border, the
222/// original `Ltr`/`Rtl` behavior) and vertical-edge ports (drawn on the
223/// top/bottom border for `Ttb`/`Btt`).
224pub(crate) fn conn_symbol(
225	is_input: bool,
226	block_style: BorderType,
227	conn_style: LineType,
228	vertical: bool,
229) -> &'static str {
230	// Each entry is (input_symbol, output_symbol). For horizontal ports the
231	// input is on the left edge (┤ family) and output on the right (├ family);
232	// for vertical ports input is on the top edge (┴ family) and output on the
233	// bottom (┬ family).
234	let out = if !vertical {
235		match (block_style, conn_style) {
236			(BorderType::Plain | BorderType::Rounded, LineType::Thick) => ("┥", "┝"),
237			(BorderType::Plain | BorderType::Rounded, LineType::Double) => ("╡", "╞"),
238			(
239				BorderType::Plain | BorderType::Rounded,
240				LineType::Plain | LineType::Rounded,
241			) => ("┤", "├"),
242
243			(BorderType::Thick, LineType::Thick) => ("┫", "┣"),
244			(BorderType::Thick, LineType::Double) => ("╡", "╞"), // fallback
245			(BorderType::Thick, LineType::Plain | LineType::Rounded) => ("┨", "┠"),
246
247			(BorderType::Double, LineType::Thick) => ("╢", "╟"), // fallback
248			(BorderType::Double, LineType::Double) => ("╣", "╠"),
249			(BorderType::Double, LineType::Plain | LineType::Rounded) => ("╢", "╟"),
250
251			(
252				BorderType::LightDoubleDashed
253				| BorderType::LightTripleDashed
254				| BorderType::LightQuadrupleDashed,
255				_,
256			) => ("┤", "├"),
257			(
258				BorderType::HeavyDoubleDashed
259				| BorderType::HeavyTripleDashed
260				| BorderType::HeavyQuadrupleDashed,
261				_,
262			) => ("┤", "├"),
263			(BorderType::QuadrantInside | BorderType::QuadrantOutside, _) => ("┤", "├"),
264		}
265	} else {
266		// vertical-edge ports: ┴ (input/top) and ┬ (output/bottom) families.
267		match (block_style, conn_style) {
268			(BorderType::Plain | BorderType::Rounded, LineType::Thick) => ("┻", "┳"),
269			(BorderType::Plain | BorderType::Rounded, LineType::Double) => ("╨", "╥"),
270			(
271				BorderType::Plain | BorderType::Rounded,
272				LineType::Plain | LineType::Rounded,
273			) => ("┴", "┬"),
274
275			(BorderType::Thick, LineType::Thick) => ("┻", "┳"),
276			(BorderType::Thick, LineType::Double) => ("╨", "╥"), // fallback
277			(BorderType::Thick, LineType::Plain | LineType::Rounded) => ("┴", "┬"),
278
279			(BorderType::Double, LineType::Thick) => ("╨", "╥"), // fallback
280			(BorderType::Double, LineType::Double) => ("╩", "╦"),
281			(BorderType::Double, LineType::Plain | LineType::Rounded) => ("╨", "╥"),
282
283			(
284				BorderType::LightDoubleDashed
285				| BorderType::LightTripleDashed
286				| BorderType::LightQuadrupleDashed,
287				_,
288			) => ("┴", "┬"),
289			(
290				BorderType::HeavyDoubleDashed
291				| BorderType::HeavyTripleDashed
292				| BorderType::HeavyQuadrupleDashed,
293				_,
294			) => ("┴", "┬"),
295			(BorderType::QuadrantInside | BorderType::QuadrantOutside, _) => ("┴", "┬"),
296		}
297	};
298	if is_input { out.0 } else { out.1 }
299}
300
301/// The direction-arrow symbol drawn on a connection's `to` port (the in port,
302/// where the line enters the node), pointing in the direction of flow — i.e.
303/// *into* the `to` node, the way the data/contribution flows. The variant
304/// scales with `line_type`: heavy line types (`Thick`/`Double`) use the solid
305/// heavy arrows (`◀▶▼▲`); light types (`Plain`/`Rounded`) use the thin arrows
306/// (`◄►▽△`).
307///
308/// This **replaces** the in-port connection glyph (`┤`/`┴` family) when
309/// [`NodeGraph::show_arrows`][crate::NodeGraph] is enabled (the default), so
310/// the flow direction is visible at a glance. The out port (`from_node` side)
311/// keeps its `├`/`┬` family glyph regardless.
312///
313/// Direction → pointing:
314/// - `Rtl` (flow right→left): points left `◄`/`◀`
315/// - `Ltr` (flow left→right): points right `►`/`▶`
316/// - `Ttb` (flow top→bottom): points down `▼`/`▽`
317/// - `Btt` (flow bottom→top): points up `▲`/`△`
318pub(crate) fn arrow_symbol(
319	direction: crate::FlowDirection,
320	line_type: LineType,
321) -> &'static str {
322	let heavy = matches!(line_type, LineType::Thick | LineType::Double);
323	match direction {
324		crate::FlowDirection::Rtl => {
325			if heavy {
326				"◀"
327			} else {
328				"◄"
329			}
330		}
331		crate::FlowDirection::Ltr => {
332			if heavy {
333				"▶"
334			} else {
335				"►"
336			}
337		}
338		crate::FlowDirection::Ttb => {
339			if heavy {
340				"▼"
341			} else {
342				"▽"
343			}
344		}
345		crate::FlowDirection::Btt => {
346			if heavy {
347				"▲"
348			} else {
349				"△"
350			}
351		}
352	}
353}
354
355pub(crate) const ALIAS_CHARS: [&str; 24] = [
356	"α", "β", "γ", "δ", "ε", "ζ", "η", "θ", "ι", "κ", "λ", "μ", "ν", "ξ", "ο", "π", "ρ",
357	"σ", "τ", "υ", "φ", "χ", "ψ", "ω",
358];
359
360#[derive(Default, Debug, Clone, Copy, PartialEq, Eq)]
361pub(crate) enum Edge {
362	#[default]
363	Empty,
364	Blocked,
365	Connection(usize),
366}
367const E: Edge = Edge::Empty;
368const B: Edge = Edge::Blocked;
369
370#[derive(Debug, Clone)]
371pub(crate) struct ConnectionsLayout<'a> {
372	ports: Map<(bool, NodeId, PortId), (usize, usize)>, // (x,y)
373	connections: Vec<(Connection<'a>, usize)>,          // ((from, to), class)
374	edge_field: Betweens<Edge>,
375	width: usize,
376	height: usize,
377	pub(crate) alias_connections: Map<(bool, NodeId, PortId), &'static str>,
378	line_types: Map<usize, LineType>,
379	line_styles: Map<usize, Style>,
380	/// Per-class label text (only connections that called `with_label`). Filled
381	/// during [`push_connection`][Self::push_connection]; read during
382	/// [`calculate`][Self::calculate] to decide which classes record a midpoint
383	/// and during [`render`][Self::render] to draw the text.
384	label_texts: Map<usize, &'a str>,
385	/// Per-class connection midpoint in canvas coordinates, captured during the
386	/// second-pass backtrace in [`calculate`][Self::calculate]. Only populated
387	/// for classes that appear in [`label_texts`][Self::label_texts] (i.e. have
388	/// a label). An absent entry means "no label → render nothing".
389	///
390	/// TODO: when two connections' midpoints coincide their labels overwrite
391	/// each other. Stacking/offsetting is out of scope for Step 8.
392	labels: Map<usize, (usize, usize)>,
393	/// Routing failures detected during [`calculate`][Self::calculate], drained
394	/// into `NodeGraph::diagnostics` by the caller.
395	pub(crate) diagnostics: Vec<Diagnostic>,
396}
397
398impl<'a> ConnectionsLayout<'a> {
399	pub(crate) fn new(width: usize, height: usize) -> Self {
400		Self {
401			ports: Map::new(),
402			connections: Vec::new(),
403			edge_field: Betweens::new(width, height),
404			width,
405			height,
406			alias_connections: Map::new(),
407			line_types: Map::new(),
408			line_styles: Map::new(),
409			label_texts: Map::new(),
410			labels: Map::new(),
411			diagnostics: Vec::new(),
412		}
413	}
414
415	pub(crate) fn push_connection(&mut self, connection: (Connection<'a>, usize)) {
416		// Record the label text (if any) for this class so that `calculate`
417		// knows to capture a midpoint and `render` knows to draw it. The label
418		// is borrowed for lifetime 'a (the NodeGraph's lifetime), which is
419		// independent of the `connection` tuple itself — so we can read it
420		// before moving the tuple.
421		let label: Option<&'a str> = connection.0.label;
422		let class = connection.1;
423		if let Some(label) = label {
424			self.label_texts.insert(class, label);
425		}
426		self.connections.push(connection)
427	}
428
429	pub(crate) fn insert_port(
430		&mut self,
431		is_input: bool,
432		node: NodeId,
433		port: PortId,
434		pos: (usize, usize),
435	) {
436		self.ports.insert((is_input, node, port), pos);
437	}
438
439	pub(crate) fn block_zone(&mut self, area: Rect) {
440		for x in 0..area.width {
441			for y in 0..area.height {
442				let cx = (x + area.x) as usize;
443				let cy = (y + area.y) as usize;
444				// Guard: skip cells that fall outside the canvas. East indexes
445				// horizontal[cy][cx+1] (needs cy<height && cx<width) and South
446				// indexes vertical[cy+1][cx] (needs cy<height && cx<width).
447				if cx >= self.width || cy >= self.height {
448					continue;
449				}
450				if x != area.width - 1 {
451					self.edge_field[((cx, cy), Direction::East).into()] = Edge::Blocked;
452				}
453				if y != area.height - 1 {
454					self.edge_field[((cx, cy), Direction::South).into()] = Edge::Blocked;
455				}
456			}
457		}
458	}
459
460	/// Block the edges that cross the port's flow axis so routed connections
461	/// don't zig-zag through a port. For **horizontal** ports (the connection
462	/// runs along x) we block the vertical (North/South) edges; for **vertical**
463	/// ports (connection runs along y) we block the horizontal (East/West) edges.
464	pub(crate) fn block_port(&mut self, coord: (usize, usize), vertical: bool) {
465		// Guard: edges index into grids sized width×(height+1) or
466		// (width+1)×height; both need coord.0<width && coord.1<height.
467		if coord.0 >= self.width || coord.1 >= self.height {
468			return;
469		}
470		if vertical {
471			self.edge_field[(coord, Direction::East).into()] = Edge::Blocked;
472			self.edge_field[(coord, Direction::West).into()] = Edge::Blocked;
473		} else {
474			self.edge_field[(coord, Direction::North).into()] = Edge::Blocked;
475			self.edge_field[(coord, Direction::South).into()] = Edge::Blocked;
476		}
477	}
478
479	pub(crate) fn calculate(&mut self, direction: crate::FlowDirection) {
480		let mut idx_next_alias = 0;
481		'outer: for ea_conn in &self.connections {
482			self.line_types.insert(ea_conn.1, ea_conn.0.line_type());
483			self.line_styles.insert(ea_conn.1, ea_conn.0.line_style());
484			let start = (
485				self.ports[&(false, ea_conn.0.from_node, ea_conn.0.from_port)],
486				direction.main_out_direction(),
487			);
488			let goal = (
489				self.ports[&(true, ea_conn.0.to_node, ea_conn.0.to_port)],
490				direction.main_in_direction(),
491			);
492			if start.0.0 > self.edge_field.width || start.0.1 > self.edge_field.height {
493				continue;
494			}
495			if goal.0.0 > self.edge_field.width || goal.0.1 > self.edge_field.height {
496				continue;
497			}
498			//println!("drawing connection {start:?} to {goal:?}");
499			let mut frontier = BinaryHeap::new();
500			let mut came_from = Betweens::<Option<_>>::new(self.width, self.height);
501			let mut cost = Betweens::<isize>::new(self.width, self.height);
502			frontier.push(((0, 0), start));
503			let mut count = 0;
504			while let Some((_, current)) = frontier.pop() {
505				count += 1;
506				if count > SEARCH_TIMEOUT {
507					break;
508				}
509				if current == goal {
510					break;
511				}
512				for ea_nei in neighbors(current.0, self.width, self.height) {
513					let ea_edge = ea_nei.into();
514					let current_cost = cost[current.into()];
515					//println!("{current_cost}");
516					let new_cost = current_cost.saturating_add(
517						self.calc_cost(current, ea_nei, start.0, goal.0, ea_conn.1),
518					);
519					if came_from[ea_edge].is_none() || new_cost < cost[ea_edge] {
520						let prio = (-new_cost, -Self::heuristic(ea_nei.0, goal.0));
521						if new_cost != isize::MAX {
522							frontier.push((prio, ea_nei));
523						}
524						came_from[ea_edge] = Some(current);
525						cost[ea_edge] = new_cost;
526					}
527				}
528				/*
529				print!("\x1b[2J\x1b[1;1H");
530				println!("{frontier:?}");
531				let mut prio = Betweens::new(self.width, self.height);
532				for ea_front in frontier.iter() {
533					prio[ea_front.1.into()] = ea_front.0;
534				}
535				println!("prio\n");
536				prio.print_with(4, |ea| print!("{:>4} ", ea.0));
537				prio.print_with(4, |ea| print!("{:>4} ", ea.1));
538				println!("cost\n");
539				cost.print_with(4, |ea| print!("{:>4} ", ea));
540				println!("from\n");
541				came_from.print_with(1, |ea| {
542					if let Some(inner) = ea {
543						print!("{:?} ", inner.1);
544					}
545					else {
546						print!("_ ");
547					}
548				});
549				std::io::stdin().read_line(&mut String::new()).unwrap();
550				*/
551			}
552			// first pass: mark connections that didnt reach the goal
553			let mut next = goal;
554			loop {
555				if next == start {
556					break;
557				}
558				if let Some(from) = came_from[next.into()] {
559					next = from;
560				} else {
561					// routing failed (search timed out or found no path):
562					// record a structured diagnostic, then fall back to an alias
563					// character so the connection still has *some* on-screen
564					// representation.
565					log::warn!(
566						"routing failed: no path found \
567						 (from_node={}, from_port={}, to_node={}, to_port={})",
568						ea_conn.0.from_node,
569						ea_conn.0.from_port,
570						ea_conn.0.to_node,
571						ea_conn.0.to_port,
572					);
573					self.diagnostics.push(Diagnostic::RoutingFailed {
574						from_node: ea_conn.0.from_node,
575						from_port: ea_conn.0.from_port,
576						to_node: ea_conn.0.to_node,
577						to_port: ea_conn.0.to_port,
578					});
579					// register alias character
580					let alias = *self
581						.alias_connections
582						.entry((false, ea_conn.0.from_node, ea_conn.0.from_port))
583						.or_insert_with(|| {
584							let a = ALIAS_CHARS[idx_next_alias % ALIAS_CHARS.len()];
585							idx_next_alias += 1;
586							a
587						});
588					self.alias_connections
589						.insert((true, ea_conn.0.to_node, ea_conn.0.to_port), alias);
590					continue 'outer;
591				}
592			}
593
594			// second pass: collect the path sequence (goal → start), then draw
595			// the edges along it. The sequence also yields the connection's
596			// midpoint (`seq[len/2]`) for label rendering.
597			let mut seq: Vec<(usize, usize)> = Vec::new();
598			let mut next = goal;
599			loop {
600				if next == start {
601					break;
602				}
603				seq.push(next.0);
604				self.edge_field[next.into()] = Edge::Connection(ea_conn.1);
605				next = came_from[next.into()].unwrap();
606			}
607			// Record the midpoint for label rendering, but ONLY when this
608			// connection actually has a label — otherwise the map stays empty
609			// and `render` does no label work (keeping label-less rendering
610			// byte-for-byte identical to pre-Step-8 behavior).
611			if !seq.is_empty() && self.label_texts.contains_key(&ea_conn.1) {
612				let mid = seq[seq.len() / 2];
613				self.labels.insert(ea_conn.1, mid);
614			}
615		}
616	}
617
618	pub(crate) fn render(&self, area: Rect, buf: &mut Buffer) {
619		let bor = |idx: Edge| -> line::Set {
620			if let Edge::Connection(idx) = idx {
621				self.line_types[&idx].to_line_set()
622			} else if idx == Edge::Blocked {
623				line::THICK
624			} else {
625				line::Set {
626					vertical: " ",
627					horizontal: " ",
628					top_right: " ",
629					top_left: " ",
630					bottom_right: " ",
631					bottom_left: " ",
632					vertical_left: " ",
633					vertical_right: " ",
634					horizontal_down: " ",
635					horizontal_up: " ",
636					cross: " ",
637				}
638			}
639		};
640
641		let get_line_style = |idx: Edge| -> Style {
642			if let Edge::Connection(idx) = idx {
643				self.line_styles[&idx]
644			} else {
645				Style::default()
646			}
647		};
648		for y in 0..self.height {
649			for x in 0..self.width {
650				let pos = (x, y);
651				let north = self.edge_field[(pos, Direction::North).into()];
652				let south = self.edge_field[(pos, Direction::South).into()];
653				let east = self.edge_field[(pos, Direction::East).into()];
654				let west = self.edge_field[(pos, Direction::West).into()];
655				#[rustfmt::skip]
656				let (symbol, line_style) = match (north, south, east, west) {
657					(B | E, B | E, B | E, B | E) => continue,
658					(n, s, e, w) if n == B || s == B || e == B || w == B => {
659						if n == B && s == B && e != E || w != E && e == w {
660							(bor(e).horizontal, get_line_style(e))
661						} else if e == B && w == B && n != E && s != E && n == s {
662							(bor(n).vertical, get_line_style(n))
663						} else {
664							("*", Style::default())
665						}
666					}
667					(n, E, E, E) => (bor(n).vertical, get_line_style(n)),
668					(E, s, E, E) => (bor(s).vertical, get_line_style(s)),
669					(E, E, e, E) => (bor(e).horizontal, get_line_style(e)),
670					(E, E, E, w) => (bor(w).horizontal, get_line_style(w)),
671
672					(n, s, E, w) if n == s && n == w => (bor(n).vertical_left, get_line_style(n)),
673					(n, E, e, w) if n == e && n == w => (bor(n).horizontal_up, get_line_style(n)),
674					(n, s, e, E) if n == s && n == e => (bor(n).vertical_right, get_line_style(n)),
675					(E, s, e, w) if s == e && s == w => (bor(s).horizontal_down, get_line_style(s)),
676					(E, s, E, w) if s == w => (bor(s).top_right, get_line_style(s)),
677					(n, E, E, w) if n == w => (bor(n).bottom_right, get_line_style(n)),
678					(n, E, e, E) if n == e => (bor(n).bottom_left, get_line_style(n)),
679					(E, s, e, E) if s == e => (bor(s).top_left, get_line_style(s)),
680
681					(n, s, E, E) if n == s => (bor(n).vertical, get_line_style(n)),
682					(E, E, e, w) if e == w => (bor(e).horizontal, get_line_style(e)),
683
684					(n, s, e, w) if n == s && n == e && n == w => (bor(n).cross, get_line_style(n)),
685					// intersections should just be verticals
686					(n, s, e, w) if n == s && e == w && n != E && e != E => (bor(n).vertical, get_line_style(n)),
687					(_, _, _, _) => ("?", Style::default()),
688				};
689
690				if let Some(cell) = buf.cell_mut(Position::new(
691					x as u16 + area.left(),
692					y as u16 + area.top(),
693				)) {
694					cell.set_symbol(symbol).set_style(line_style);
695				}
696			}
697		}
698
699		// Render labels on top of the lines. This is the ONLY opt-in new paint
700		// added by Step 8: `self.labels` is empty for a label-less graph, so
701		// this loop is a complete no-op and the output above is untouched.
702		for (class, (mx, my)) in &self.labels {
703			let Some(&text) = self.label_texts.get(class) else {
704				continue;
705			};
706			// The label's color: reuse the connection's own line style so the
707			// text inherits its fg. The bg is forced to the canvas default
708			// (Black) so the characters punch a readable hole through the line
709			// underneath instead of blending into it.
710			let base_style = self.line_styles.get(class).copied().unwrap_or_default();
711			let label_style = Style::default()
712				.fg(base_style.fg.unwrap_or(Color::Reset))
713				.bg(Color::Black);
714			// Write the label horizontally from the midpoint, truncating to the
715			// canvas' right edge so we never write out of bounds. Iterate by
716			// grapheme-ish char boundaries: ratatui's `set_symbol` takes a &str,
717			// and each ASCII char of the label maps to one cell.
718			let start_x = *mx as u16 + area.left();
719			let y = *my as u16 + area.top();
720			let max_x = area.left() as usize + self.width;
721			let mut x = start_x;
722			for ch in text.chars() {
723				let cx = x;
724				if (cx as usize) >= max_x {
725					break;
726				}
727				if let Some(cell) = buf.cell_mut(Position::new(cx, y)) {
728					let mut buf_str = [0u8; 4];
729					let s = ch.encode_utf8(&mut buf_str);
730					cell.set_symbol(s).set_style(label_style);
731				}
732				x = match cx.checked_add(1) {
733					Some(v) => v,
734					None => break,
735				};
736			}
737		}
738	}
739
740	fn heuristic(from: (usize, usize), to: (usize, usize)) -> isize {
741		(from.0 as isize - to.0 as isize).pow(2)
742			+ (from.1 as isize - to.1 as isize).pow(2)
743	}
744
745	fn calc_cost(
746		&self,
747		current: ((usize, usize), Direction),
748		neigh: ((usize, usize), Direction),
749		start: (usize, usize),
750		end: (usize, usize),
751		conn_t: usize,
752	) -> isize {
753		let conn_t = Edge::Connection(conn_t);
754		let north = self.edge_field[(current.0, Direction::North).into()];
755		let south = self.edge_field[(current.0, Direction::South).into()];
756		let east = self.edge_field[(current.0, Direction::East).into()];
757		let west = self.edge_field[(current.0, Direction::West).into()];
758
759		let in_dir = self.edge_field[current.into()];
760		// TODO: fix
761		if !(in_dir == Edge::Empty || in_dir == conn_t) {
762			return isize::MAX;
763		}
764		//	assert!(in_dir == 0 || in_dir == conn_t); // should only calculate cost if its possible
765		let out_dir = self.edge_field[neigh.into()];
766		if out_dir == conn_t {
767			// already exists
768			1
769		} else if out_dir == Edge::Empty {
770			if north == conn_t || south == conn_t || east == conn_t || west == conn_t {
771				// intersecting with an existing connection
772				2 // maybe multiply with distances?
773			} else {
774				let in_is_vert = current.1.is_vertical();
775				let out_is_vert = neigh.1.is_vertical();
776				let straight = in_is_vert == out_is_vert;
777				if straight {
778					if north == Edge::Empty
779						&& south == Edge::Empty
780						&& east == Edge::Empty
781						&& west == Edge::Empty
782					{
783						2
784					} else {
785						4
786					}
787				} else {
788					// curved
789					if north != Edge::Empty
790						|| south != Edge::Empty
791						|| east != Edge::Empty
792						|| west != Edge::Empty
793					{
794						isize::MAX
795					} else {
796						let ax = current.0.0 as isize;
797						let ay = current.0.1 as isize;
798						let sx = start.0 as isize;
799						let sy = start.1 as isize;
800						let ex = end.0 as isize;
801						let ey = end.1 as isize;
802						4 + ((ax - sx).pow(2)
803							+ (ay - sy).pow(2) + (ax - ex).pow(2)
804							+ (ay - ey).pow(2))
805					}
806				}
807			}
808		} else {
809			isize::MAX
810		}
811	}
812}
813
814fn neighbors(
815	pos: (usize, usize),
816	width: usize,
817	height: usize,
818) -> Vec<((usize, usize), Direction)> {
819	let mut out = Vec::new();
820	if pos.0 < width - 1 {
821		out.push(((pos.0 + 1, pos.1), Direction::West));
822	}
823	if pos.1 < height - 1 {
824		out.push(((pos.0, pos.1 + 1), Direction::North));
825	}
826	if pos.0 > 0 {
827		out.push(((pos.0 - 1, pos.1), Direction::East));
828	}
829	if pos.1 > 0 {
830		out.push(((pos.0, pos.1 - 1), Direction::South));
831	}
832	out
833}
834
835use core::ops::{Index, IndexMut};
836
837#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
838struct EdgeIdx {
839	x: usize,
840	y: usize,
841	is_vertical: bool,
842}
843/*
844impl EdgeIdx {
845	fn pos(self) -> (usize, usize) {
846		(self.0, self.1)
847	}
848}
849*/
850impl From<((usize, usize), Direction)> for EdgeIdx {
851	fn from(value: ((usize, usize), Direction)) -> Self {
852		match value.1 {
853			Direction::North => Self { x: value.0.0, y: value.0.1, is_vertical: true },
854			Direction::South => {
855				Self { x: value.0.0, y: value.0.1 + 1, is_vertical: true }
856			}
857			Direction::East => {
858				Self { x: value.0.0 + 1, y: value.0.1, is_vertical: false }
859			}
860			Direction::West => Self { x: value.0.0, y: value.0.1, is_vertical: false },
861		}
862	}
863}
864
865// the outermost values are unnecessary
866#[derive(Debug, Clone)]
867struct Betweens<T: Default> {
868	horizontal: Vec<Vec<T>>,
869	vertical: Vec<Vec<T>>,
870	width: usize,
871	height: usize,
872}
873impl<T: Default> Index<EdgeIdx> for Betweens<T> {
874	type Output = T;
875	fn index(&self, index: EdgeIdx) -> &Self::Output {
876		if index.is_vertical {
877			&self.vertical[index.y][index.x]
878		} else {
879			&self.horizontal[index.y][index.x]
880		}
881	}
882}
883impl<T: Default> IndexMut<EdgeIdx> for Betweens<T> {
884	fn index_mut(&mut self, index: EdgeIdx) -> &mut T {
885		if index.is_vertical {
886			&mut self.vertical[index.y][index.x]
887		} else {
888			&mut self.horizontal[index.y][index.x]
889		}
890	}
891}
892
893impl<T: Default> Betweens<T> {
894	fn new(x: usize, y: usize) -> Self {
895		let mut out = Self {
896			horizontal: Vec::new(),
897			vertical: Vec::new(),
898			width: 0,
899			height: 0,
900		};
901		out.set_size(x, y);
902		out
903	}
904
905	fn set_size(&mut self, x: usize, y: usize) {
906		self.horizontal.resize_with(y, || {
907			let mut inner = Vec::new();
908			inner.resize_with(x + 1, Default::default);
909			inner
910		});
911		self.vertical.resize_with(y + 1, || {
912			let mut inner = Vec::new();
913			inner.resize_with(x, Default::default);
914			inner
915		});
916		self.width = x;
917		self.height = y;
918	}
919
920	#[allow(unused)]
921	fn print_with(&self, width: usize, f: impl Fn(&T)) {
922		for y in 0..(self.height + 1) {
923			for x in 0..self.width {
924				print!("{} ", "-".repeat(width));
925				f(&self.vertical[y][x]);
926			}
927			println!("{}", "-".repeat(width));
928			if y < self.height {
929				for x in 0..(self.width + 1) {
930					f(&self.horizontal[y][x]);
931					if x < self.width {
932						print!("{} ", "-".repeat(width));
933					}
934				}
935			}
936			println!();
937		}
938	}
939}