jellyflow_layout/
freeform.rs

1use std::cmp::Ordering;
2use std::collections::{BTreeMap, BTreeSet};
3
4use jellyflow_core::{CanvasPoint, CanvasRect, CanvasSize, Graph, GraphTransaction, NodeId};
5
6use crate::engine::{
7    LayoutContext, LayoutDirection, LayoutEngine, LayoutEngineId, LayoutError, LayoutNodePosition,
8    LayoutOptions, LayoutRequest, LayoutResult, MIND_MAP_FREEFORM_LAYOUT_ENGINE_ID,
9    node_rect_from_position, position_from_center, resolve_node_origin, resolve_node_size,
10    validate_request,
11};
12use crate::projection::{
13    VisibleLayoutEdge, build_visible_edge_list, center_from_position, result_from_placements,
14};
15
16/// Built-in freeform mind-map engine that only resolves overlaps.
17#[derive(Debug, Default, Clone, Copy)]
18pub struct MindMapFreeformLayoutEngine;
19
20impl LayoutEngine for MindMapFreeformLayoutEngine {
21    fn id(&self) -> LayoutEngineId {
22        LayoutEngineId::new(MIND_MAP_FREEFORM_LAYOUT_ENGINE_ID)
23    }
24
25    fn layout(
26        &self,
27        graph: &Graph,
28        request: &LayoutRequest,
29        context: &LayoutContext,
30    ) -> Result<LayoutResult, LayoutError> {
31        layout_graph_with_mind_map_freeform_context(graph, request, context)
32    }
33}
34
35/// Runs the native freeform mind-map engine.
36pub fn layout_graph_with_mind_map_freeform(
37    graph: &Graph,
38    request: &LayoutRequest,
39) -> Result<LayoutResult, LayoutError> {
40    layout_graph_with_mind_map_freeform_context(graph, request, &LayoutContext::default())
41}
42
43/// Runs the native freeform mind-map engine and converts the result into a transaction.
44pub fn layout_graph_to_transaction_with_mind_map_freeform(
45    graph: &Graph,
46    request: &LayoutRequest,
47) -> Result<GraphTransaction, LayoutError> {
48    layout_graph_with_mind_map_freeform(graph, request)?.to_transaction(graph)
49}
50
51fn layout_graph_with_mind_map_freeform_context(
52    graph: &Graph,
53    request: &LayoutRequest,
54    context: &LayoutContext,
55) -> Result<LayoutResult, LayoutError> {
56    validate_request(graph, request)?;
57
58    let mut projection = FreeformProjection::new(graph, request, context)?;
59    projection.layout(request.options);
60    projection.into_result()
61}
62
63struct FreeformProjection<'a> {
64    graph: &'a Graph,
65    request: &'a LayoutRequest,
66    node_infos: BTreeMap<NodeId, FreeformNodeInfo>,
67    visible_edges: Vec<VisibleLayoutEdge>,
68    placements: BTreeMap<NodeId, LayoutNodePosition>,
69}
70
71#[derive(Debug, Clone, Copy)]
72struct FreeformNodeInfo {
73    size: CanvasSize,
74    origin: (f32, f32),
75    current_center: CanvasPoint,
76    pinned: bool,
77}
78
79impl<'a> FreeformProjection<'a> {
80    fn new(
81        graph: &'a Graph,
82        request: &'a LayoutRequest,
83        context: &'a LayoutContext,
84    ) -> Result<Self, LayoutError> {
85        let mut node_infos = BTreeMap::new();
86        let mut visible_nodes = BTreeSet::new();
87
88        for (id, node) in &graph.nodes {
89            if node.hidden || !request.scope.contains(*id) {
90                continue;
91            }
92
93            let size = resolve_node_size(graph, request, context, *id)?;
94            let origin = resolve_node_origin(node.origin, request.options.node_origin, context);
95            let current_center = center_from_position(node.pos, size, origin);
96
97            node_infos.insert(
98                *id,
99                FreeformNodeInfo {
100                    size,
101                    origin,
102                    current_center,
103                    pinned: context.pinned_nodes.contains(id),
104                },
105            );
106            visible_nodes.insert(*id);
107        }
108
109        let visible_edges = build_visible_edge_list(graph, &visible_nodes)?;
110
111        Ok(Self {
112            graph,
113            request,
114            node_infos,
115            visible_edges,
116            placements: BTreeMap::new(),
117        })
118    }
119
120    fn layout(&mut self, options: LayoutOptions) {
121        if self.node_infos.is_empty() {
122            return;
123        }
124
125        let gap = freeform_gap(options);
126        let mut node_order = self.node_infos.keys().copied().collect::<Vec<_>>();
127        node_order.sort_by(|left, right| self.compare_nodes(*left, *right, options.direction));
128
129        for node in node_order {
130            let Some(info) = self.node_infos.get(&node).copied() else {
131                continue;
132            };
133
134            let center = if info.pinned {
135                info.current_center
136            } else {
137                self.resolve_node_center(info, gap, options.direction)
138            };
139            let pos = position_from_center(center, info.size, info.origin);
140
141            self.placements.insert(
142                node,
143                LayoutNodePosition {
144                    node,
145                    pos,
146                    center,
147                    size: info.size,
148                },
149            );
150        }
151    }
152
153    fn compare_nodes(&self, left: NodeId, right: NodeId, direction: LayoutDirection) -> Ordering {
154        let left_info = self.node_infos.get(&left).expect("left node info");
155        let right_info = self.node_infos.get(&right).expect("right node info");
156
157        right_info
158            .pinned
159            .cmp(&left_info.pinned)
160            .then_with(|| match direction {
161                LayoutDirection::TopToBottom | LayoutDirection::BottomToTop => left_info
162                    .current_center
163                    .y
164                    .total_cmp(&right_info.current_center.y)
165                    .then_with(|| {
166                        left_info
167                            .current_center
168                            .x
169                            .total_cmp(&right_info.current_center.x)
170                    }),
171                LayoutDirection::LeftToRight | LayoutDirection::RightToLeft => left_info
172                    .current_center
173                    .x
174                    .total_cmp(&right_info.current_center.x)
175                    .then_with(|| {
176                        left_info
177                            .current_center
178                            .y
179                            .total_cmp(&right_info.current_center.y)
180                    }),
181            })
182            .then_with(|| left.cmp(&right))
183    }
184
185    fn resolve_node_center(
186        &self,
187        info: FreeformNodeInfo,
188        gap: f32,
189        direction: LayoutDirection,
190    ) -> CanvasPoint {
191        let mut center = info.current_center;
192
193        for _ in 0..64 {
194            let rect = rect_from_center(center, info.size, info.origin);
195            let Some(other) = self
196                .placements
197                .values()
198                .map(node_rect_from_position)
199                .find(|other| rects_overlap_with_gap(rect, *other, gap))
200            else {
201                break;
202            };
203
204            center =
205                shift_center_out_of_rect(center, info.size, info.origin, other, direction, gap);
206        }
207
208        center
209    }
210
211    fn into_result(mut self) -> Result<LayoutResult, LayoutError> {
212        Ok(result_from_placements(
213            self.graph,
214            self.request.options,
215            &mut self.placements,
216            &self.visible_edges,
217        ))
218    }
219}
220
221fn freeform_gap(options: LayoutOptions) -> f32 {
222    options.spacing.nodesep.max(24.0)
223}
224
225fn rect_from_center(center: CanvasPoint, size: CanvasSize, origin: (f32, f32)) -> CanvasRect {
226    CanvasRect {
227        origin: position_from_center(center, size, origin),
228        size,
229    }
230}
231
232fn shift_center_out_of_rect(
233    center: CanvasPoint,
234    size: CanvasSize,
235    origin: (f32, f32),
236    other: CanvasRect,
237    direction: LayoutDirection,
238    gap: f32,
239) -> CanvasPoint {
240    let rect = rect_from_center(center, size, origin);
241    let expanded = expand_rect(other, gap);
242
243    match direction {
244        LayoutDirection::TopToBottom => CanvasPoint {
245            x: center.x,
246            y: center.y + (expanded.origin.y + expanded.size.height - rect.origin.y),
247        },
248        LayoutDirection::BottomToTop => CanvasPoint {
249            x: center.x,
250            y: center.y - (rect.origin.y + rect.size.height - expanded.origin.y),
251        },
252        LayoutDirection::LeftToRight => CanvasPoint {
253            x: center.x + (expanded.origin.x + expanded.size.width - rect.origin.x),
254            y: center.y,
255        },
256        LayoutDirection::RightToLeft => CanvasPoint {
257            x: center.x - (rect.origin.x + rect.size.width - expanded.origin.x),
258            y: center.y,
259        },
260    }
261}
262
263fn rects_overlap_with_gap(candidate: CanvasRect, other: CanvasRect, gap: f32) -> bool {
264    let other = expand_rect(other, gap);
265    let candidate_right = candidate.origin.x + candidate.size.width;
266    let candidate_bottom = candidate.origin.y + candidate.size.height;
267    let other_right = other.origin.x + other.size.width;
268    let other_bottom = other.origin.y + other.size.height;
269
270    candidate.origin.x < other_right
271        && candidate_right > other.origin.x
272        && candidate.origin.y < other_bottom
273        && candidate_bottom > other.origin.y
274}
275
276fn expand_rect(rect: CanvasRect, gap: f32) -> CanvasRect {
277    CanvasRect {
278        origin: CanvasPoint {
279            x: rect.origin.x - gap,
280            y: rect.origin.y - gap,
281        },
282        size: CanvasSize {
283            width: rect.size.width + gap * 2.0,
284            height: rect.size.height + gap * 2.0,
285        },
286    }
287}
jellyflow_layout/freeform.rs

jellyflow_layout/
freeform.rs
