Skip to main content

leptos_node_graph/
subway.rs

1//! Orthogonal "subway map" routing.
2//!
3//! Routes every connection as an axis-aligned polyline that goes AROUND node
4//! bounding boxes instead of through them. Paths are found with A* over a
5//! sparse routing grid built from the inflated node bounds (plus the anchor
6//! stub coordinates), with a bend penalty so runs stay long and straight.
7//! After routing, collinear segments that would sit exactly on top of each
8//! other are nudged apart into parallel lanes — so distinct connections only
9//! ever cross at 90° and never overlap along a shared corridor.
10//!
11//! Pure module: no reactive graph, no DOM, fully unit-testable. Rects and
12//! connections are addressed by INDEX (their position in the input slices),
13//! so the caller keeps its own id types.
14//!
15//! Ported from the Svelte client's `nodes/subwayRouter.ts`; the phase
16//! structure, cost model and default tuning are kept identical so both
17//! clients draw the same picture.
18
19use std::collections::{HashMap, HashSet};
20
21use crate::types::Position;
22
23/// Coordinate slop. Two coordinates within this are the same grid line.
24const EPS: f64 = 0.5;
25
26const DIR_NONE: usize = 0;
27const DIR_H: usize = 1;
28const DIR_V: usize = 2;
29
30/// Slightly inflate the heuristic — trades exact optimality for speed.
31/// Keep close to 1: a weight of w admits paths up to w× longer than optimal,
32/// and route inefficiency is far more visible than solve time.
33const HEURISTIC_WEIGHT: f64 = 1.1;
34
35/// Horizontal travel off the goal row costs slightly more than on it.
36/// L-shaped routes have two equal-cost corner orientations (turn at the source
37/// vs turn at the target); without a bias A* picks arbitrarily per wire and
38/// neighbouring wires swing opposite ways. The bias makes every wire do its
39/// vertical run early — at its source escape column — and approach along the
40/// input row, one consistent corner family.
41const OFF_GOAL_ROW_BIAS: f64 = 0.04;
42
43/// Furthest an escape fan may spread beyond a node's inflated boundary.
44const ESCAPE_SPREAD_BUDGET: f64 = 64.0;
45
46/// A node's bounding box in canvas space.
47#[derive(Clone, Copy, Debug, Default, PartialEq)]
48pub struct SubwayRect {
49    pub x: f64,
50    pub y: f64,
51    pub w: f64,
52    pub h: f64,
53}
54
55/// One wire to route, anchor to anchor.
56#[derive(Clone, Copy, Debug, PartialEq)]
57pub struct SubwayConnection {
58    /// Output-anchor position.
59    pub start: Position,
60    /// Input-anchor position.
61    pub end: Position,
62    /// Index into the rect slice, when the endpoint's node is known.
63    pub start_rect: Option<usize>,
64    pub end_rect: Option<usize>,
65}
66
67/// Tuning. [`Default`] matches the Svelte client.
68#[derive(Clone, Copy, Debug)]
69pub struct SubwayOptions {
70    /// Clearance kept around node bounds (and stub length off each anchor).
71    pub margin: f64,
72    /// Offset between parallel lanes sharing a corridor.
73    pub lane_gap: f64,
74    /// Extra cost per 90° turn — higher means straighter routes.
75    pub bend_penalty: f64,
76    /// Bail out to elbow fallback when the routing grid gets this big.
77    pub max_grid_cells: usize,
78    /// Per-connection A* expansion cap before falling back to an elbow.
79    pub max_expansions: usize,
80    /// Whole-batch A* expansion budget — keeps worst-case latency bounded.
81    pub max_total_expansions: usize,
82    /// Cost of crossing an already-routed line (0 disables crossing avoidance).
83    pub crossing_penalty: f64,
84    /// Length multiplier for riding a corridor an unrelated route occupies —
85    /// negative DISCOUNTS sharing, bundling routes into common trunks.
86    pub overlap_factor: f64,
87}
88
89impl Default for SubwayOptions {
90    fn default() -> Self {
91        Self {
92            margin: 16.0,
93            lane_gap: 8.0,
94            bend_penalty: 60.0,
95            max_grid_cells: 400_000,
96            max_expansions: 30_000,
97            max_total_expansions: 600_000,
98            // A clean 90° crossing is part of the subway look, so it's priced
99            // LOW — half a bend. High penalties (or corridor discounts) fund
100            // long hook detours around busy bundles, which read far worse than
101            // the crossings they avoid. Keep it below 2 × bend_penalty or A*
102            // buys S-jogs to relocate crossings onto quieter vertices.
103            crossing_penalty: 30.0,
104            overlap_factor: 0.0,
105        }
106    }
107}
108
109/// Rounded anchor position, used to tell "same pin" wires apart from foreign
110/// ones. Routes sharing a pin are one subway line, not competing lanes.
111type AnchorKey = (i64, i64);
112
113fn anchor_key(p: Position) -> AnchorKey {
114    (p.x.round() as i64, p.y.round() as i64)
115}
116
117/// True when any segment of an orthogonal route comes within `pad` of the
118/// rect. Segments are axis-aligned, so AABB overlap is exact.
119pub fn route_intersects_rect(pts: &[Position], rect: SubwayRect, pad: f64) -> bool {
120    let left = rect.x - pad;
121    let right = rect.x + rect.w + pad;
122    let top = rect.y - pad;
123    let bottom = rect.y + rect.h + pad;
124    pts.windows(2).any(|w| {
125        let (a, b) = (w[0], w[1]);
126        a.x.max(b.x) >= left
127            && a.x.min(b.x) <= right
128            && a.y.max(b.y) >= top
129            && a.y.min(b.y) <= bottom
130    })
131}
132
133/// Diagnostic summary for a Subway batch.
134#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
135pub struct SubwayRoutingStats {
136    pub grid_width: usize,
137    pub grid_height: usize,
138    pub grid_cells: usize,
139    pub expansions: usize,
140    pub routed: usize,
141    pub grid_fallbacks: usize,
142    pub budget_fallbacks: usize,
143    pub no_path_fallbacks: usize,
144}
145
146impl SubwayRoutingStats {
147    pub fn fallbacks(self) -> usize {
148        self.grid_fallbacks + self.budget_fallbacks + self.no_path_fallbacks
149    }
150}
151
152/// Compute orthogonal routes for all connections at once.
153///
154/// Returns one waypoint list per connection, in input order, anchor to anchor
155/// inclusive. Every connection always gets a route: those that can't be routed
156/// around obstacles (or when the scene exceeds the grid budget) fall back to a
157/// mid-point elbow, which the lane pass still keeps non-overlapping.
158pub fn compute_subway_routes(
159    rects: &[SubwayRect],
160    connections: &[SubwayConnection],
161    options: &SubwayOptions,
162) -> Vec<Vec<Position>> {
163    compute_subway_routes_with_stats(rects, connections, options).0
164}
165
166pub fn compute_subway_routes_with_stats(
167    rects: &[SubwayRect],
168    connections: &[SubwayConnection],
169    options: &SubwayOptions,
170) -> (Vec<Vec<Position>>, SubwayRoutingStats) {
171    let mut routes: Vec<Vec<Position>> = vec![Vec::new(); connections.len()];
172    let mut stats = SubwayRoutingStats::default();
173    if connections.is_empty() {
174        return (routes, stats);
175    }
176
177    // Unmeasured nodes (zero size) are not obstacles.
178    let valid: Vec<usize> = (0..rects.len())
179        .filter(|&i| rects[i].w > 0.0 && rects[i].h > 0.0)
180        .collect();
181    let valid_rects: Vec<SubwayRect> = valid.iter().map(|&i| rects[i]).collect();
182
183    // Per-side inflation, clamped to half the gap to the nearest neighbour on
184    // that side. With a fixed margin, tightly packed rows produce OVERLAPPING
185    // obstacles — no corridor exists, every route between them strands and
186    // falls back to a through-the-boxes elbow. Clamping guarantees a corridor
187    // between any two non-touching boxes.
188    let inflations = compute_inflations(&valid_rects, options.margin);
189    // rect index → index into `valid_rects` / `inflations`
190    let mut slot: HashMap<usize, usize> = HashMap::new();
191    for (slot_idx, &rect_idx) in valid.iter().enumerate() {
192        slot.insert(rect_idx, slot_idx);
193    }
194    let inflation_of = |rect_idx: Option<usize>| -> Option<&SideInflation> {
195        rect_idx.and_then(|i| slot.get(&i)).map(|&s| &inflations[s])
196    };
197    let rect_of = |rect_idx: Option<usize>| -> Option<SubwayRect> {
198        rect_idx.and_then(|i| slot.get(&i)).map(|&s| valid_rects[s])
199    };
200
201    // Anchor stubs: step out to the node's inflated boundary in the direction
202    // the anchor faces, so the path starts ON a routable corridor. Anchor
203    // centers sit slightly INSIDE the node bounds, so stepping from the anchor
204    // itself would land inside the node's own obstacle and strand the search.
205    let mut jobs: Vec<Job> = connections
206        .iter()
207        .enumerate()
208        .map(|(i, c)| Job {
209            index: i,
210            conn: *c,
211            stub_start: make_stub(
212                c.start,
213                rect_of(c.start_rect),
214                inflation_of(c.start_rect),
215                options.margin,
216            ),
217            stub_end: make_stub(
218                c.end,
219                rect_of(c.end_rect),
220                inflation_of(c.end_rect),
221                options.margin,
222            ),
223        })
224        .collect();
225
226    // Escape lanes: the FIRST bend out of a pin (and the last one into a pin)
227    // is a special case — all wires sharing a node side get their own
228    // staggered stub column, ranked so the corners nest: among down-turning
229    // wires the topmost pin turns furthest out, among up-turners the
230    // bottommost does. Same-pin wires share one column (they're a trunk).
231    apply_escape_lanes(
232        &mut jobs,
233        &slot,
234        &valid_rects,
235        &inflations,
236        options.lane_gap,
237    );
238
239    let inflated: Vec<InflatedRect> = valid_rects
240        .iter()
241        .zip(inflations.iter())
242        .map(|(r, s)| InflatedRect {
243            left: r.x - s.left,
244            right: r.x + r.w + s.right,
245            top: r.y - s.top,
246            bottom: r.y + r.h + s.bottom,
247        })
248        .collect();
249
250    // Routing grid: every inflated rect edge plus every stub coordinate is a
251    // candidate corridor. Paths travel along these lines only.
252    let mut xs_raw = Vec::with_capacity(inflated.len() * 2 + jobs.len() * 2);
253    let mut ys_raw = Vec::with_capacity(inflated.len() * 2 + jobs.len() * 2);
254    for r in &inflated {
255        xs_raw.push(r.left);
256        xs_raw.push(r.right);
257        ys_raw.push(r.top);
258        ys_raw.push(r.bottom);
259    }
260    for j in &jobs {
261        xs_raw.push(j.stub_start.x);
262        xs_raw.push(j.stub_end.x);
263        ys_raw.push(j.stub_start.y);
264        ys_raw.push(j.stub_end.y);
265    }
266    let xs = dedupe_sorted(xs_raw);
267    let ys = dedupe_sorted(ys_raw);
268    let (nx, ny) = (xs.len(), ys.len());
269    stats.grid_width = nx;
270    stats.grid_height = ny;
271    stats.grid_cells = nx.saturating_mul(ny);
272
273    if nx < 2 || ny < 2 || stats.grid_cells > options.max_grid_cells {
274        for j in &jobs {
275            routes[j.index] = elbow_route(&j.conn, j.stub_start, j.stub_end);
276        }
277        stats.grid_fallbacks = jobs.len();
278        nudge_overlaps(&mut routes, options.lane_gap, &valid_rects);
279        return (routes, stats);
280    }
281
282    // Edge blockers: h_blocked[yi * (nx-1) + xi] — the horizontal grid edge
283    // from xs[xi]→xs[xi+1] along ys[yi] passes through a node interior.
284    // Running exactly ON an inflated boundary is allowed (that IS the corridor).
285    let mut h_blocked = vec![false; ny * (nx - 1)];
286    let mut v_blocked = vec![false; nx * (ny - 1)];
287    for r in &inflated {
288        // Rows whose y is strictly inside the rect
289        let ry0 = upper_bound(&ys, r.top + EPS);
290        let ry1 = lower_bound(&ys, r.bottom - EPS) as isize - 1;
291        // Horizontal edges overlapping the rect's open x-interval
292        let hx0 = (upper_bound(&xs, r.left + EPS) as isize - 1).max(0);
293        let hx1 = (lower_bound(&xs, r.right - EPS) as isize - 1).min(nx as isize - 2);
294        for yi in ry0 as isize..=ry1 {
295            let base = yi as usize * (nx - 1);
296            for xi in hx0..=hx1 {
297                h_blocked[base + xi as usize] = true;
298            }
299        }
300        // Columns whose x is strictly inside the rect
301        let cx0 = upper_bound(&xs, r.left + EPS);
302        let cx1 = lower_bound(&xs, r.right - EPS) as isize - 1;
303        // Vertical edges overlapping the rect's open y-interval
304        let vy0 = (upper_bound(&ys, r.top + EPS) as isize - 1).max(0);
305        let vy1 = (lower_bound(&ys, r.bottom - EPS) as isize - 1).min(ny as isize - 2);
306        for xi in cx0 as isize..=cx1 {
307            let base = xi as usize * (ny - 1);
308            for yi in vy0..=vy1 {
309                v_blocked[base + yi as usize] = true;
310            }
311        }
312    }
313
314    // Scratch buffers shared across all A* runs (generation-stamped so they
315    // don't need clearing between connections).
316    let states = nx * ny * 3;
317    let mut scratch = AStarScratch {
318        g_score: vec![0.0; states],
319        came_from: vec![-1; states],
320        generation: vec![0; states],
321        current_gen: 0,
322        heap: MinHeap::default(),
323        expansions_used: 0,
324    };
325
326    // Crossing avoidance: routes are laid down shortest-first, each leaving an
327    // occupancy imprint; later routes pay to cross or ride a foreign line, so
328    // pairs cross only where their endpoints force it. Same-pin routes are
329    // exempt — they SHOULD share a trunk corridor.
330    let mut occ = Occupancy::default();
331    let mut order: Vec<usize> = (0..jobs.len()).collect();
332    order.sort_by(|&a, &b| {
333        let span =
334            |j: &Job| (j.stub_end.x - j.stub_start.x).abs() + (j.stub_end.y - j.stub_start.y).abs();
335        span(&jobs[a])
336            .partial_cmp(&span(&jobs[b]))
337            .unwrap_or(std::cmp::Ordering::Equal)
338            .then(a.cmp(&b))
339    });
340
341    for oi in order {
342        let j = &jobs[oi];
343        let sxi = index_of(&xs, j.stub_start.x);
344        let syi = index_of(&ys, j.stub_start.y);
345        let exi = index_of(&xs, j.stub_end.x);
346        let eyi = index_of(&ys, j.stub_end.y);
347
348        let budget = options.max_expansions.min(
349            options
350                .max_total_expansions
351                .saturating_sub(scratch.expansions_used),
352        );
353
354        let s_key = anchor_key(j.conn.start);
355        let e_key = anchor_key(j.conn.end);
356
357        let expansions_before = scratch.expansions_used;
358        let mut path = None;
359        if budget > 0
360            && let (Some(sxi), Some(syi), Some(exi), Some(eyi)) = (sxi, syi, exi, eyi)
361        {
362            path = astar(
363                &xs,
364                &ys,
365                &h_blocked,
366                &v_blocked,
367                (sxi, syi),
368                (exi, eyi),
369                options,
370                2.0 * options.margin + EPS,
371                budget,
372                &mut scratch,
373                if options.crossing_penalty > 0.0 || options.overlap_factor > 0.0 {
374                    Some(&occ)
375                } else {
376                    None
377                },
378                s_key,
379                e_key,
380            );
381        }
382
383        match path {
384            Some(path) => {
385                stats.routed += 1;
386                let mut full = Vec::with_capacity(path.len() + 2);
387                full.push(j.conn.start);
388                full.extend(path);
389                full.push(j.conn.end);
390                let full = simplify(&full);
391                mark_occupancy(&mut occ, &xs, &ys, &full, s_key, e_key);
392                routes[j.index] = full;
393            }
394            None => {
395                if budget == 0 || scratch.expansions_used - expansions_before >= budget {
396                    stats.budget_fallbacks += 1;
397                } else {
398                    stats.no_path_fallbacks += 1;
399                }
400                routes[j.index] = elbow_route(&j.conn, j.stub_start, j.stub_end);
401            }
402        }
403    }
404
405    stats.expansions = scratch.expansions_used;
406    nudge_overlaps(&mut routes, options.lane_gap, &valid_rects);
407    (routes, stats)
408}
409
410struct Job {
411    index: usize,
412    conn: SubwayConnection,
413    stub_start: Position,
414    stub_end: Position,
415}
416
417#[derive(Clone, Copy)]
418struct InflatedRect {
419    left: f64,
420    right: f64,
421    top: f64,
422    bottom: f64,
423}
424
425#[derive(Clone, Copy)]
426struct SideInflation {
427    left: f64,
428    right: f64,
429    top: f64,
430    bottom: f64,
431    /// Horizontal distance to the nearest vertically-overlapping neighbour —
432    /// bounds how far escape-lane stubs may extend (infinite when clear).
433    clear_left: f64,
434    clear_right: f64,
435}
436
437/// Per-rect, per-side obstacle inflation: starts at `margin` and shrinks to
438/// half the gap toward any neighbour closer than 2×margin on that side, so
439/// obstacle bounds never swallow the free space between two boxes.
440fn compute_inflations(rects: &[SubwayRect], margin: f64) -> Vec<SideInflation> {
441    let mut inf = vec![
442        SideInflation {
443            left: margin,
444            right: margin,
445            top: margin,
446            bottom: margin,
447            clear_left: f64::INFINITY,
448            clear_right: f64::INFINITY,
449        };
450        rects.len()
451    ];
452    for i in 0..rects.len() {
453        for j in (i + 1)..rects.len() {
454            let (a, b) = (rects[i], rects[j]);
455            // Horizontal gaps only constrain when the rects are vertically
456            // close enough for their inflated bands to interact, and vice versa.
457            let v_close = a.y - margin < b.y + b.h + margin && b.y - margin < a.y + a.h + margin;
458            if v_close {
459                if a.x + a.w <= b.x {
460                    let gap = b.x - (a.x + a.w);
461                    inf[i].clear_right = inf[i].clear_right.min(gap);
462                    inf[j].clear_left = inf[j].clear_left.min(gap);
463                    let half = (gap / 2.0).max(0.0);
464                    if half < margin {
465                        inf[i].right = inf[i].right.min(half);
466                        inf[j].left = inf[j].left.min(half);
467                    }
468                } else if b.x + b.w <= a.x {
469                    let gap = a.x - (b.x + b.w);
470                    inf[j].clear_right = inf[j].clear_right.min(gap);
471                    inf[i].clear_left = inf[i].clear_left.min(gap);
472                    let half = (gap / 2.0).max(0.0);
473                    if half < margin {
474                        inf[j].right = inf[j].right.min(half);
475                        inf[i].left = inf[i].left.min(half);
476                    }
477                }
478            }
479            let h_close = a.x - margin < b.x + b.w + margin && b.x - margin < a.x + a.w + margin;
480            if h_close {
481                if a.y + a.h <= b.y {
482                    let half = ((b.y - (a.y + a.h)) / 2.0).max(0.0);
483                    if half < margin {
484                        inf[i].bottom = inf[i].bottom.min(half);
485                        inf[j].top = inf[j].top.min(half);
486                    }
487                } else if b.y + b.h <= a.y {
488                    let half = ((a.y - (b.y + b.h)) / 2.0).max(0.0);
489                    if half < margin {
490                        inf[j].bottom = inf[j].bottom.min(half);
491                        inf[i].top = inf[i].top.min(half);
492                    }
493                }
494            }
495        }
496    }
497    inf
498}
499
500/// +1 when the anchor sits on the right half of its node (output side), -1 otherwise.
501fn stub_direction(anchor: Position, rect: Option<SubwayRect>) -> f64 {
502    match rect {
503        Some(r) if r.w > 0.0 => {
504            if anchor.x >= r.x + r.w / 2.0 {
505                1.0
506            } else {
507                -1.0
508            }
509        }
510        _ => 1.0,
511    }
512}
513
514/// Stub point on the node's inflated boundary, horizontal from the anchor.
515fn make_stub(
516    anchor: Position,
517    rect: Option<SubwayRect>,
518    inflation: Option<&SideInflation>,
519    margin: f64,
520) -> Position {
521    let dir = stub_direction(anchor, rect);
522    let Some(r) = rect.filter(|r| r.w > 0.0) else {
523        return Position::new(anchor.x + dir * margin, anchor.y);
524    };
525    let x = if dir > 0.0 {
526        (anchor.x + EPS).max(r.x + r.w + inflation.map_or(margin, |s| s.right))
527    } else {
528        (anchor.x - EPS).min(r.x - inflation.map_or(margin, |s| s.left))
529    };
530    Position::new(x, anchor.y)
531}
532
533/// Stagger stub columns per (node, side) so first/last bends nest. Mutates the
534/// jobs' stub points; runs before the routing grid is built so the staggered
535/// columns become grid corridors.
536fn apply_escape_lanes(
537    jobs: &mut [Job],
538    slot: &HashMap<usize, usize>,
539    valid_rects: &[SubwayRect],
540    inflations: &[SideInflation],
541    lane_gap: f64,
542) {
543    struct EscapeRef {
544        job: usize,
545        /// false = stub_start, true = stub_end
546        is_end: bool,
547        node_slot: usize,
548        pin_y: f64,
549        away_y: f64,
550        dir: f64,
551        anchor: AnchorKey,
552    }
553
554    let mut groups: HashMap<(usize, i8), Vec<EscapeRef>> = HashMap::new();
555    for (ji, j) in jobs.iter().enumerate() {
556        for is_end in [false, true] {
557            let (rect_idx, pin, away) = if is_end {
558                (j.conn.end_rect, j.conn.end, j.conn.start)
559            } else {
560                (j.conn.start_rect, j.conn.start, j.conn.end)
561            };
562            let Some(&s) = rect_idx.and_then(|i| slot.get(&i)) else {
563                continue;
564            };
565            let rect = valid_rects[s];
566            let dir = stub_direction(pin, Some(rect));
567            groups
568                .entry((s, if dir > 0.0 { 1 } else { -1 }))
569                .or_default()
570                .push(EscapeRef {
571                    job: ji,
572                    is_end,
573                    node_slot: s,
574                    pin_y: pin.y,
575                    away_y: away.y,
576                    dir,
577                    anchor: anchor_key(pin),
578                });
579        }
580    }
581
582    // Deterministic group order — HashMap iteration isn't stable and the
583    // ranking below feeds geometry.
584    let mut keys: Vec<(usize, i8)> = groups.keys().copied().collect();
585    keys.sort();
586
587    for key in keys {
588        let group = &groups[&key];
589        // Rank unique anchors — wires sharing a pin ride one trunk column.
590        let mut anchors: HashMap<AnchorKey, (f64, f64, usize)> = HashMap::new();
591        for m in group {
592            let e = anchors.entry(m.anchor).or_insert((m.pin_y, 0.0, 0));
593            e.1 += m.away_y;
594            e.2 += 1;
595        }
596        if anchors.len() < 2 {
597            continue;
598        }
599
600        let min_y = anchors.values().map(|a| a.0).fold(f64::INFINITY, f64::min);
601        let max_y = anchors
602            .values()
603            .map(|a| a.0)
604            .fold(f64::NEG_INFINITY, f64::max);
605
606        // Nesting depth: a wire turning down must clear every pin below it, so
607        // the topmost down-turner sits outermost; mirrored for up-turners.
608        let mut ranked: Vec<(AnchorKey, f64, f64)> = anchors
609            .iter()
610            .map(|(&k, &(pin_y, away_sum, n))| {
611                let away = away_sum / n as f64;
612                let depth = if away > pin_y {
613                    max_y - pin_y
614                } else {
615                    pin_y - min_y
616                };
617                (k, depth, pin_y)
618            })
619            .collect();
620        ranked.sort_by(|p, q| {
621            p.1.partial_cmp(&q.1)
622                .unwrap_or(std::cmp::Ordering::Equal)
623                .then(p.2.partial_cmp(&q.2).unwrap_or(std::cmp::Ordering::Equal))
624                .then(p.0.cmp(&q.0))
625        });
626        let rank_of: HashMap<AnchorKey, usize> =
627            ranked.iter().enumerate().map(|(i, r)| (r.0, i)).collect();
628
629        for m in group {
630            let rank = rank_of[&m.anchor];
631            if rank == 0 {
632                continue;
633            }
634            let s = inflations[m.node_slot];
635            let (inf, clear) = if m.dir > 0.0 {
636                (s.right, s.clear_right)
637            } else {
638                (s.left, s.clear_left)
639            };
640            let max_spread = ESCAPE_SPREAD_BUDGET.min(clear - inf - 4.0).max(0.0);
641            let ext = (rank as f64 * lane_gap).min(max_spread);
642            if ext > 0.0 {
643                let job = &mut jobs[m.job];
644                let stub = if m.is_end {
645                    &mut job.stub_end
646                } else {
647                    &mut job.stub_start
648                };
649                stub.x += m.dir * ext;
650            }
651        }
652    }
653}
654
655/// Mid-x elbow through the stub points — used when A* can't find a route.
656fn elbow_route(c: &SubwayConnection, stub_start: Position, stub_end: Position) -> Vec<Position> {
657    let mid_x = (stub_start.x + stub_end.x) / 2.0;
658    simplify(&[
659        c.start,
660        stub_start,
661        Position::new(mid_x, stub_start.y),
662        Position::new(mid_x, stub_end.y),
663        stub_end,
664        c.end,
665    ])
666}
667
668// =============================================================================
669// A* over the sparse grid (direction-aware so bend penalties are exact)
670// =============================================================================
671
672struct AStarScratch {
673    g_score: Vec<f64>,
674    came_from: Vec<i32>,
675    /// Generation stamp — an entry is only valid when generation[i] == current_gen.
676    generation: Vec<i32>,
677    current_gen: i32,
678    heap: MinHeap,
679    /// Running batch total, checked against `max_total_expansions`.
680    expansions_used: usize,
681}
682
683/// Occupancy imprint of already-routed connections, for crossing avoidance.
684#[derive(Default)]
685struct Occupancy {
686    /// Horizontal grid edges covered by horizontal runs (edge idx → anchors).
687    h_edge: HashMap<usize, HashSet<AnchorKey>>,
688    /// Vertical grid edges covered by vertical runs.
689    v_edge: HashMap<usize, HashSet<AnchorKey>>,
690    /// Vertices interior to horizontal runs (vertex idx → anchors).
691    h_vertex: HashMap<usize, HashSet<AnchorKey>>,
692    /// Vertices interior to vertical runs.
693    v_vertex: HashMap<usize, HashSet<AnchorKey>>,
694}
695
696/// True when the occupant set contains a route unrelated to both anchors.
697fn has_foreign(set: &HashSet<AnchorKey>, k1: AnchorKey, k2: AnchorKey) -> bool {
698    set.iter().any(|k| *k != k1 && *k != k2)
699}
700
701fn add_occ(map: &mut HashMap<usize, HashSet<AnchorKey>>, idx: usize, k1: AnchorKey, k2: AnchorKey) {
702    let set = map.entry(idx).or_default();
703    set.insert(k1);
704    set.insert(k2);
705}
706
707#[allow(clippy::too_many_arguments)]
708fn astar(
709    xs: &[f64],
710    ys: &[f64],
711    h_blocked: &[bool],
712    v_blocked: &[bool],
713    start: (usize, usize),
714    goal: (usize, usize),
715    options: &SubwayOptions,
716    escape_cap: f64,
717    max_expansions: usize,
718    scratch: &mut AStarScratch,
719    occ: Option<&Occupancy>,
720    s_key: AnchorKey,
721    e_key: AnchorKey,
722) -> Option<Vec<Position>> {
723    let (nx, ny) = (xs.len(), ys.len());
724    let (sxi, syi) = start;
725    let (exi, eyi) = goal;
726    let state_of = |xi: usize, yi: usize, dir: usize| (yi * nx + xi) * 3 + dir;
727
728    // Clamp the search to a window around the endpoints. Detours rarely need
729    // to wander further; if a route genuinely can't fit it falls back to an
730    // elbow, which the lane pass still keeps non-overlapping.
731    const WINDOW_PAD: f64 = 800.0;
732    let xi_min = lower_bound(xs, xs[sxi].min(xs[exi]) - WINDOW_PAD);
733    let xi_max = upper_bound(xs, xs[sxi].max(xs[exi]) + WINDOW_PAD) - 1;
734    let yi_min = lower_bound(ys, ys[syi].min(ys[eyi]) - WINDOW_PAD);
735    let yi_max = upper_bound(ys, ys[syi].max(ys[eyi]) + WINDOW_PAD) - 1;
736
737    scratch.current_gen += 1;
738    let generation = scratch.current_gen;
739    scratch.heap.clear();
740
741    let (ex, ey) = (xs[exi], ys[eyi]);
742
743    let start_state = state_of(sxi, syi, DIR_NONE);
744    scratch.g_score[start_state] = 0.0;
745    scratch.came_from[start_state] = -1;
746    scratch.generation[start_state] = generation;
747    scratch.heap.push(
748        start_state,
749        ((ex - xs[sxi]).abs() + (ey - ys[syi]).abs()) * HEURISTIC_WEIGHT,
750    );
751
752    let mut expansions = 0usize;
753    while let Some(current) = scratch.heap.pop() {
754        scratch.expansions_used += 1;
755        expansions += 1;
756        if expansions > max_expansions {
757            return None;
758        }
759
760        let dir = current % 3;
761        let cell = current / 3;
762        let xi = cell % nx;
763        let yi = cell / nx;
764
765        if xi == exi && yi == eyi {
766            return Some(reconstruct(xs, ys, nx, scratch, generation, current));
767        }
768
769        let g = scratch.g_score[current];
770        // The first hop out of the start (and the final hop into the goal) may
771        // cross a SHORT blocked edge — anchors of tightly packed nodes can sit
772        // inside a NEIGHBOUR's inflated bounds, and without an escape hatch the
773        // search would strand there and fall back to a through-everything
774        // elbow. The length cap stops the exception from tunnelling whole nodes.
775        let is_start = current == start_state;
776
777        // Horizontal neighbours
778        for step in [-1isize, 1] {
779            let nxi = xi as isize + step;
780            if nxi < xi_min as isize || nxi > xi_max as isize {
781                continue;
782            }
783            let nxi = nxi as usize;
784            let edge = yi * (nx - 1) + if step == 1 { xi } else { nxi };
785            let len = (xs[nxi] - xs[xi]).abs();
786            if h_blocked[edge] {
787                let may_escape = is_start || (nxi == exi && yi == eyi);
788                if !may_escape || len > escape_cap {
789                    continue;
790                }
791            }
792            let mut cost =
793                len * if yi == eyi {
794                    1.0
795                } else {
796                    1.0 + OFF_GOAL_ROW_BIAS
797                } + if dir == DIR_V {
798                    options.bend_penalty
799                } else {
800                    0.0
801                };
802            if let Some(occ) = occ {
803                if occ
804                    .h_edge
805                    .get(&edge)
806                    .is_some_and(|s| has_foreign(s, s_key, e_key))
807                {
808                    cost += len * options.overlap_factor;
809                }
810                if occ
811                    .v_vertex
812                    .get(&(yi * nx + nxi))
813                    .is_some_and(|s| has_foreign(s, s_key, e_key))
814                {
815                    cost += options.crossing_penalty;
816                }
817            }
818            let next = state_of(nxi, yi, DIR_H);
819            let ng = g + cost;
820            if scratch.generation[next] != generation || ng < scratch.g_score[next] {
821                scratch.g_score[next] = ng;
822                scratch.came_from[next] = current as i32;
823                scratch.generation[next] = generation;
824                let h = ((ex - xs[nxi]).abs() + (ey - ys[yi]).abs()) * HEURISTIC_WEIGHT;
825                scratch.heap.push(next, ng + h);
826            }
827        }
828
829        // Vertical neighbours
830        for step in [-1isize, 1] {
831            let nyi = yi as isize + step;
832            if nyi < yi_min as isize || nyi > yi_max as isize {
833                continue;
834            }
835            let nyi = nyi as usize;
836            let edge = xi * (ny - 1) + if step == 1 { yi } else { nyi };
837            let len = (ys[nyi] - ys[yi]).abs();
838            if v_blocked[edge] {
839                let may_escape = is_start || (xi == exi && nyi == eyi);
840                if !may_escape || len > escape_cap {
841                    continue;
842                }
843            }
844            let mut cost = len
845                + if dir == DIR_H {
846                    options.bend_penalty
847                } else {
848                    0.0
849                };
850            if let Some(occ) = occ {
851                if occ
852                    .v_edge
853                    .get(&edge)
854                    .is_some_and(|s| has_foreign(s, s_key, e_key))
855                {
856                    cost += len * options.overlap_factor;
857                }
858                if occ
859                    .h_vertex
860                    .get(&(nyi * nx + xi))
861                    .is_some_and(|s| has_foreign(s, s_key, e_key))
862                {
863                    cost += options.crossing_penalty;
864                }
865            }
866            let next = state_of(xi, nyi, DIR_V);
867            let ng = g + cost;
868            if scratch.generation[next] != generation || ng < scratch.g_score[next] {
869                scratch.g_score[next] = ng;
870                scratch.came_from[next] = current as i32;
871                scratch.generation[next] = generation;
872                let h = ((ex - xs[xi]).abs() + (ey - ys[nyi]).abs()) * HEURISTIC_WEIGHT;
873                scratch.heap.push(next, ng + h);
874            }
875        }
876    }
877
878    None
879}
880
881/// Record a routed path's grid edges and interior vertices so later routes can
882/// price crossings and corridor sharing. Segments whose endpoints are off-grid
883/// (the anchor→stub jogs) are skipped — they're a stub long.
884fn mark_occupancy(
885    occ: &mut Occupancy,
886    xs: &[f64],
887    ys: &[f64],
888    pts: &[Position],
889    s_key: AnchorKey,
890    e_key: AnchorKey,
891) {
892    let nx = xs.len();
893    let ny = ys.len();
894    for w in pts.windows(2) {
895        let (a, b) = (w[0], w[1]);
896        if (a.y - b.y).abs() < EPS && (a.x - b.x).abs() >= EPS {
897            let Some(yi) = index_of(ys, a.y) else {
898                continue;
899            };
900            let (Some(i1), Some(i2)) = (index_of(xs, a.x.min(b.x)), index_of(xs, a.x.max(b.x)))
901            else {
902                continue;
903            };
904            for e in i1..i2 {
905                add_occ(&mut occ.h_edge, yi * (nx - 1) + e, s_key, e_key);
906            }
907            for v in (i1 + 1)..i2 {
908                add_occ(&mut occ.h_vertex, yi * nx + v, s_key, e_key);
909            }
910        } else if (a.x - b.x).abs() < EPS && (a.y - b.y).abs() >= EPS {
911            let Some(xi) = index_of(xs, a.x) else {
912                continue;
913            };
914            let (Some(i1), Some(i2)) = (index_of(ys, a.y.min(b.y)), index_of(ys, a.y.max(b.y)))
915            else {
916                continue;
917            };
918            for e in i1..i2 {
919                add_occ(&mut occ.v_edge, xi * (ny - 1) + e, s_key, e_key);
920            }
921            for v in (i1 + 1)..i2 {
922                add_occ(&mut occ.v_vertex, v * nx + xi, s_key, e_key);
923            }
924        }
925    }
926}
927
928fn reconstruct(
929    xs: &[f64],
930    ys: &[f64],
931    nx: usize,
932    scratch: &AStarScratch,
933    generation: i32,
934    end: usize,
935) -> Vec<Position> {
936    let mut pts = Vec::new();
937    let mut cur = end as i32;
938    while cur >= 0 && scratch.generation[cur as usize] == generation {
939        let state = cur as usize;
940        let cell = state / 3;
941        let xi = cell % nx;
942        let yi = cell / nx;
943        pts.push(Position::new(xs[xi], ys[yi]));
944        cur = scratch.came_from[state];
945    }
946    pts.reverse();
947    simplify(&pts)
948}
949
950/// Drop duplicate and collinear interior points.
951fn simplify(pts: &[Position]) -> Vec<Position> {
952    let mut out: Vec<Position> = Vec::with_capacity(pts.len());
953    for &p in pts {
954        if let Some(prev) = out.last()
955            && (prev.x - p.x).abs() < EPS
956            && (prev.y - p.y).abs() < EPS
957        {
958            continue;
959        }
960        while out.len() >= 2 {
961            let a = out[out.len() - 2];
962            let b = out[out.len() - 1];
963            let collinear_x = (a.x - b.x).abs() < EPS && (b.x - p.x).abs() < EPS;
964            let collinear_y = (a.y - b.y).abs() < EPS && (b.y - p.y).abs() < EPS;
965            if collinear_x || collinear_y {
966                out.pop();
967            } else {
968                break;
969            }
970        }
971        out.push(p);
972    }
973    out
974}
975
976// =============================================================================
977// Lane nudging — separate collinear overlapping segments across paths
978// =============================================================================
979
980#[derive(Clone, Copy, PartialEq, Eq, Debug)]
981enum Axis {
982    X,
983    Y,
984}
985
986#[derive(Clone, Copy)]
987struct LaneSegment {
988    /// Which route, and which segment within it (pts[i] → pts[i+1]).
989    route: usize,
990    i: usize,
991    /// Corridor coordinate (x for verticals, y for horizontals).
992    coord: f64,
993    /// Range along the segment axis.
994    lo: f64,
995    hi: f64,
996    /// First/last segments are pinned to their anchor — never shifted.
997    pinned: bool,
998    /// Perpendicular position of the neighbours, used to order lanes.
999    sort_key: f64,
1000    /// Which side the route connects on at the lo end of the segment: sign of
1001    /// (neighbour waypoint − corridor) along the perpendicular axis, 0 when the
1002    /// segment ends at an anchor. Drives nesting order.
1003    lo_dir: f64,
1004    /// Same at the hi end.
1005    hi_dir: f64,
1006}
1007
1008/// Pairwise nesting preference used as a vote, not directly as a sort
1009/// comparator: three bracket-shaped runs can form a preference cycle.
1010fn lane_nesting_preference(a: &LaneSegment, b: &LaneSegment) -> f64 {
1011    let mut preference = 0.0;
1012    if a.hi < b.hi - EPS {
1013        preference += a.hi_dir;
1014    } else if b.hi < a.hi - EPS {
1015        preference -= b.hi_dir;
1016    }
1017    if a.lo > b.lo + EPS {
1018        preference += a.lo_dir;
1019    } else if b.lo > a.lo + EPS {
1020        preference -= b.lo_dir;
1021    }
1022    preference
1023}
1024
1025fn aggregate_nesting_scores(representatives: &[LaneSegment]) -> Vec<f64> {
1026    representatives
1027        .iter()
1028        .map(|a| {
1029            representatives
1030                .iter()
1031                .map(|b| lane_nesting_preference(a, b))
1032                .sum()
1033        })
1034        .collect()
1035}
1036
1037#[derive(Clone, Copy)]
1038struct LaneOrderKey {
1039    nesting_score: f64,
1040    sort_key: f64,
1041    coord: f64,
1042    stable_key: (usize, usize),
1043}
1044
1045fn compare_lane_order(a: LaneOrderKey, b: LaneOrderKey) -> std::cmp::Ordering {
1046    a.nesting_score
1047        .total_cmp(&b.nesting_score)
1048        .then(a.sort_key.total_cmp(&b.sort_key))
1049        .then(a.coord.total_cmp(&b.coord))
1050        .then(a.stable_key.cmp(&b.stable_key))
1051}
1052
1053struct Shift {
1054    seg: LaneSegment,
1055    axis: Axis,
1056    offset: f64,
1057}
1058
1059/// Find groups of segments that share a corridor (same or nearly-same x for
1060/// verticals / y for horizontals) AND overlap along it, then fan them out into
1061/// parallel lanes `lane_gap` apart. Proximity-based: segments within two lanes'
1062/// width of each other count as sharing the corridor, so near-misses (e.g.
1063/// elbow midlines a few px apart) separate too. Segments whose routes share a
1064/// start or end anchor merge onto ONE trunk line instead of fanning (a fan from
1065/// a single pin is one subway line, not parallel lanes). Shifts that would push
1066/// a segment into a node box are skipped. Runs to a fixpoint — a shifted
1067/// segment can land next to a segment from another corridor group, so detection
1068/// repeats until no segment moves.
1069fn nudge_overlaps(routes: &mut [Vec<Position>], lane_gap: f64, rects: &[SubwayRect]) {
1070    const MAX_PASSES: usize = 3;
1071    for _ in 0..MAX_PASSES {
1072        let mut v_segs: Vec<LaneSegment> = Vec::new();
1073        let mut h_segs: Vec<LaneSegment> = Vec::new();
1074
1075        for (ri, pts) in routes.iter().enumerate() {
1076            if pts.len() < 2 {
1077                continue;
1078            }
1079            for i in 0..pts.len() - 1 {
1080                let a = pts[i];
1081                let b = pts[i + 1];
1082                let pinned = i == 0 || i == pts.len() - 2;
1083                let prev_pt = if i >= 1 { Some(pts[i - 1]) } else { None };
1084                let next_pt = pts.get(i + 2).copied();
1085                if (a.x - b.x).abs() < EPS && (a.y - b.y).abs() >= EPS {
1086                    let prev = prev_pt.map_or(a.x, |p| p.x);
1087                    let next = next_pt.map_or(a.x, |p| p.x);
1088                    // lo end = smaller y; its connecting neighbour is prev when
1089                    // the segment travels downward (a above b), next otherwise
1090                    let travel_down = b.y > a.y;
1091                    let (lo_nbr, hi_nbr) = if travel_down {
1092                        (prev_pt, next_pt)
1093                    } else {
1094                        (next_pt, prev_pt)
1095                    };
1096                    v_segs.push(LaneSegment {
1097                        route: ri,
1098                        i,
1099                        coord: a.x,
1100                        lo: a.y.min(b.y),
1101                        hi: a.y.max(b.y),
1102                        pinned,
1103                        sort_key: (prev + next) / 2.0,
1104                        lo_dir: lo_nbr.map_or(0.0, |p| (p.x - a.x).signum_or_zero()),
1105                        hi_dir: hi_nbr.map_or(0.0, |p| (p.x - a.x).signum_or_zero()),
1106                    });
1107                } else if (a.y - b.y).abs() < EPS && (a.x - b.x).abs() >= EPS {
1108                    let prev = prev_pt.map_or(a.y, |p| p.y);
1109                    let next = next_pt.map_or(a.y, |p| p.y);
1110                    let travel_right = b.x > a.x;
1111                    let (lo_nbr, hi_nbr) = if travel_right {
1112                        (prev_pt, next_pt)
1113                    } else {
1114                        (next_pt, prev_pt)
1115                    };
1116                    h_segs.push(LaneSegment {
1117                        route: ri,
1118                        i,
1119                        coord: a.y,
1120                        lo: a.x.min(b.x),
1121                        hi: a.x.max(b.x),
1122                        pinned,
1123                        sort_key: (prev + next) / 2.0,
1124                        lo_dir: lo_nbr.map_or(0.0, |p| (p.y - a.y).signum_or_zero()),
1125                        hi_dir: hi_nbr.map_or(0.0, |p| (p.y - a.y).signum_or_zero()),
1126                    });
1127                }
1128            }
1129        }
1130
1131        let mut shifts: Vec<Shift> = Vec::new();
1132        collect_shifts(&mut v_segs, Axis::X, &mut shifts, lane_gap, rects, routes);
1133        collect_shifts(&mut h_segs, Axis::Y, &mut shifts, lane_gap, rects, routes);
1134
1135        if shifts.is_empty() {
1136            break;
1137        }
1138
1139        for Shift { seg, axis, offset } in shifts {
1140            for k in [seg.i, seg.i + 1] {
1141                let p = &mut routes[seg.route][k];
1142                match axis {
1143                    Axis::X => p.x += offset,
1144                    Axis::Y => p.y += offset,
1145                }
1146            }
1147        }
1148    }
1149}
1150
1151trait SignumOrZero {
1152    fn signum_or_zero(self) -> f64;
1153}
1154impl SignumOrZero for f64 {
1155    /// `f64::signum` returns ±1 for zero; lane nesting needs a true zero.
1156    fn signum_or_zero(self) -> f64 {
1157        if self == 0.0 { 0.0 } else { self.signum() }
1158    }
1159}
1160
1161/// Sweep-cluster segments of one orientation: first by corridor proximity
1162/// (coords within one lane_gap), then by overlap along the corridor; assign
1163/// lane offsets within each overlapping cluster.
1164fn collect_shifts(
1165    segs: &mut [LaneSegment],
1166    axis: Axis,
1167    out: &mut Vec<Shift>,
1168    lane_gap: f64,
1169    rects: &[SubwayRect],
1170    routes: &[Vec<Position>],
1171) {
1172    if segs.len() < 2 {
1173        return;
1174    }
1175    segs.sort_by(|a, b| {
1176        a.coord
1177            .partial_cmp(&b.coord)
1178            .unwrap_or(std::cmp::Ordering::Equal)
1179            .then((a.route, a.i).cmp(&(b.route, b.i)))
1180    });
1181
1182    let mut corridor: Vec<LaneSegment> = Vec::new();
1183    let mut corridor_max = f64::NEG_INFINITY;
1184    for seg in segs.iter() {
1185        if !corridor.is_empty() && seg.coord - corridor_max > lane_gap - EPS {
1186            if corridor.len() > 1 {
1187                cluster_by_overlap(&mut corridor, axis, out, lane_gap, rects, routes);
1188            }
1189            corridor.clear();
1190            corridor_max = f64::NEG_INFINITY;
1191        }
1192        corridor.push(*seg);
1193        corridor_max = corridor_max.max(seg.coord);
1194    }
1195    if corridor.len() > 1 {
1196        cluster_by_overlap(&mut corridor, axis, out, lane_gap, rects, routes);
1197    }
1198}
1199
1200/// Within one corridor, find clusters that overlap along the run axis.
1201fn cluster_by_overlap(
1202    corridor: &mut [LaneSegment],
1203    axis: Axis,
1204    out: &mut Vec<Shift>,
1205    lane_gap: f64,
1206    rects: &[SubwayRect],
1207    routes: &[Vec<Position>],
1208) {
1209    corridor.sort_by(|a, b| {
1210        a.lo.partial_cmp(&b.lo)
1211            .unwrap_or(std::cmp::Ordering::Equal)
1212            .then((a.route, a.i).cmp(&(b.route, b.i)))
1213    });
1214
1215    let mut cluster: Vec<LaneSegment> = Vec::new();
1216    let mut cluster_hi = f64::NEG_INFINITY;
1217    for seg in corridor.iter() {
1218        // Strict overlap only — touching at a shared endpoint is a junction,
1219        // not an overlapping run, and shouldn't fan out.
1220        if !cluster.is_empty() && seg.lo < cluster_hi - EPS {
1221            cluster.push(*seg);
1222            cluster_hi = cluster_hi.max(seg.hi);
1223        } else {
1224            if cluster.len() > 1 {
1225                assign_lanes(&cluster, axis, out, lane_gap, rects, routes);
1226            }
1227            cluster.clear();
1228            cluster.push(*seg);
1229            cluster_hi = seg.hi;
1230        }
1231    }
1232    if cluster.len() > 1 {
1233        assign_lanes(&cluster, axis, out, lane_gap, rects, routes);
1234    }
1235}
1236
1237/// True when placing this segment at `target` would cross a node box.
1238fn lane_blocked(seg: &LaneSegment, axis: Axis, target: f64, rects: &[SubwayRect]) -> bool {
1239    rects.iter().any(|r| match axis {
1240        Axis::X => {
1241            target > r.x + 1.0
1242                && target < r.x + r.w - 1.0
1243                && seg.hi > r.y + 1.0
1244                && seg.lo < r.y + r.h - 1.0
1245        }
1246        Axis::Y => {
1247            target > r.y + 1.0
1248                && target < r.y + r.h - 1.0
1249                && seg.hi > r.x + 1.0
1250                && seg.lo < r.x + r.w - 1.0
1251        }
1252    })
1253}
1254
1255fn assign_lanes(
1256    cluster: &[LaneSegment],
1257    axis: Axis,
1258    out: &mut Vec<Shift>,
1259    lane_gap: f64,
1260    rects: &[SubwayRect],
1261    routes: &[Vec<Position>],
1262) {
1263    // Routes sharing a start or end anchor are ONE subway line — union their
1264    // segments into trunk units that ride a single coordinate instead of
1265    // fanning into separate lanes.
1266    let n = cluster.len();
1267    let mut parent: Vec<usize> = (0..n).collect();
1268    fn find(parent: &mut [usize], mut i: usize) -> usize {
1269        while parent[i] != i {
1270            parent[i] = parent[parent[i]];
1271            i = parent[i];
1272        }
1273        i
1274    }
1275    let mut by_key: HashMap<(bool, AnchorKey), usize> = HashMap::new();
1276    for i in 0..n {
1277        let pts = &routes[cluster[i].route];
1278        let Some((&first, &last)) = pts.first().zip(pts.last()) else {
1279            continue;
1280        };
1281        for key in [(false, anchor_key(first)), (true, anchor_key(last))] {
1282            match by_key.get(&key) {
1283                None => {
1284                    by_key.insert(key, i);
1285                }
1286                Some(&seen) => {
1287                    let a = find(&mut parent, seen);
1288                    let b = find(&mut parent, i);
1289                    if a != b {
1290                        parent[b] = a;
1291                    }
1292                }
1293            }
1294        }
1295    }
1296    let mut unit_map: HashMap<usize, Vec<LaneSegment>> = HashMap::new();
1297    // Insertion order is kept separately: lane assignment below is
1298    // order-sensitive and `HashMap` iteration isn't stable.
1299    let mut unit_order: Vec<usize> = Vec::new();
1300    for (i, seg) in cluster.iter().enumerate() {
1301        let root = find(&mut parent, i);
1302        let unit = unit_map.entry(root).or_insert_with(|| {
1303            unit_order.push(root);
1304            Vec::new()
1305        });
1306        unit.push(*seg);
1307    }
1308
1309    struct LaneUnit {
1310        segs: Vec<LaneSegment>,
1311        pinned: bool,
1312        coord: f64,
1313        sort_key: f64,
1314        /// Longest member — its end-connections stand in for the unit when
1315        /// deciding nesting order.
1316        rep: LaneSegment,
1317    }
1318    let units: Vec<LaneUnit> = unit_order
1319        .iter()
1320        .map(|root| {
1321            let segs = unit_map[root].clone();
1322            let mut rep = segs[0];
1323            for s in &segs {
1324                if s.hi - s.lo > rep.hi - rep.lo {
1325                    rep = *s;
1326                }
1327            }
1328            LaneUnit {
1329                pinned: segs.iter().any(|s| s.pinned),
1330                coord: segs.iter().map(|s| s.coord).sum::<f64>() / segs.len() as f64,
1331                sort_key: segs.iter().map(|s| s.sort_key).sum::<f64>() / segs.len() as f64,
1332                rep,
1333                segs,
1334            }
1335        })
1336        .collect();
1337
1338    // When the full lane offset would push a segment into a node box (tight
1339    // corridors between packed nodes), back off progressively — partial
1340    // separation beats either tunnelling a box or staying coincident.
1341    let push_shift = |seg: &LaneSegment, target: f64, out: &mut Vec<Shift>| {
1342        let want = target - seg.coord;
1343        if want.abs() <= EPS / 2.0 {
1344            return;
1345        }
1346        for f in [1.0, 0.75, 0.5, 0.25] {
1347            let t = seg.coord + want * f;
1348            if !lane_blocked(seg, axis, t, rects) {
1349                out.push(Shift {
1350                    seg: *seg,
1351                    axis,
1352                    offset: want * f,
1353                });
1354                return;
1355            }
1356        }
1357    };
1358
1359    // Pinned units hold their anchor line; their movable members snap onto it
1360    // so a trunk shared with a stub reads as one continuous line.
1361    let pinned_units: Vec<&LaneUnit> = units.iter().filter(|u| u.pinned).collect();
1362    for u in &pinned_units {
1363        let anchored: Vec<&LaneSegment> = u.segs.iter().filter(|s| s.pinned).collect();
1364        let line = anchored.iter().map(|s| s.coord).sum::<f64>() / anchored.len() as f64;
1365        for seg in &u.segs {
1366            if !seg.pinned {
1367                push_shift(seg, line, out);
1368            }
1369        }
1370    }
1371
1372    // Lane targets are absolute positions centred on the cluster, so
1373    // near-coincident corridors collapse into an evenly spaced fan. Units are
1374    // ordered by where their segments come from / go to, so parallel runs peel
1375    // off in a stable order and avoid gratuitous criss-crossing.
1376    let movable_units: Vec<&LaneUnit> = units.iter().filter(|unit| !unit.pinned).collect();
1377    let representatives: Vec<_> = movable_units.iter().map(|unit| unit.rep).collect();
1378    let nesting_scores = aggregate_nesting_scores(&representatives);
1379    let mut movable: Vec<_> = movable_units.into_iter().zip(nesting_scores).collect();
1380    movable.sort_by(|(a, a_score), (b, b_score)| {
1381        compare_lane_order(
1382            LaneOrderKey {
1383                nesting_score: *a_score,
1384                sort_key: a.sort_key,
1385                coord: a.coord,
1386                stable_key: (a.rep.route, a.rep.i),
1387            },
1388            LaneOrderKey {
1389                nesting_score: *b_score,
1390                sort_key: b.sort_key,
1391                coord: b.coord,
1392                stable_key: (b.rep.route, b.rep.i),
1393            },
1394        )
1395    });
1396    let movable: Vec<_> = movable.into_iter().map(|(unit, _)| unit).collect();
1397    if movable.is_empty() {
1398        return;
1399    }
1400
1401    if !pinned_units.is_empty() {
1402        // Fan movable units around the pinned centre, alternating sides.
1403        let center = pinned_units.iter().map(|u| u.coord).sum::<f64>() / pinned_units.len() as f64;
1404        for (k, u) in movable.iter().enumerate() {
1405            let lane = (k / 2) as f64 + 1.0;
1406            let side = if k % 2 == 0 { 1.0 } else { -1.0 };
1407            let target = center + side * lane * lane_gap;
1408            for seg in &u.segs {
1409                push_shift(seg, target, out);
1410            }
1411        }
1412        return;
1413    }
1414
1415    let n = movable.len();
1416    let center = movable.iter().map(|u| u.coord).sum::<f64>() / n as f64;
1417
1418    // Free corridor band: the widest interval around the cluster centre —
1419    // across the cluster's combined run-range — that touches no node box. Lanes
1420    // are spread evenly inside it (graceful fan-out, in nesting order so no two
1421    // lanes swap), compressing spacing only when the corridor is genuinely
1422    // narrower than the full fan.
1423    let mut range_lo = f64::INFINITY;
1424    let mut range_hi = f64::NEG_INFINITY;
1425    for u in &movable {
1426        for s in &u.segs {
1427            range_lo = range_lo.min(s.lo);
1428            range_hi = range_hi.max(s.hi);
1429        }
1430    }
1431    const PAD: f64 = 2.0;
1432    let mut band_lo = f64::NEG_INFINITY;
1433    let mut band_hi = f64::INFINITY;
1434    for r in rects {
1435        let (r_lo, r_hi, s_lo, s_hi) = match axis {
1436            Axis::X => (r.x, r.x + r.w, r.y, r.y + r.h),
1437            Axis::Y => (r.y, r.y + r.h, r.x, r.x + r.w),
1438        };
1439        if s_hi <= range_lo + 1.0 || s_lo >= range_hi - 1.0 {
1440            continue;
1441        }
1442        if r_hi <= center {
1443            band_lo = band_lo.max(r_hi);
1444        } else if r_lo >= center {
1445            band_hi = band_hi.min(r_lo);
1446        }
1447        // A rect spanning the centre means the cluster already runs through it
1448        // (shouldn't happen) — ignore rather than produce an empty band.
1449    }
1450
1451    let span = (n as f64 - 1.0) * lane_gap;
1452    let mut spacing = lane_gap;
1453    let mut start = center - span / 2.0;
1454    let lo = band_lo + PAD;
1455    let hi = band_hi - PAD;
1456    if lo.is_finite() && hi.is_finite() {
1457        let width = hi - lo;
1458        if width <= 0.0 {
1459            spacing = 0.0;
1460            start = center;
1461        } else {
1462            spacing = if n > 1 {
1463                lane_gap.min(width / (n as f64 - 1.0))
1464            } else {
1465                0.0
1466            };
1467            start = center - (spacing * (n as f64 - 1.0)) / 2.0;
1468            start = start.max(lo).min(hi - spacing * (n as f64 - 1.0));
1469        }
1470    } else if lo.is_finite() {
1471        start = start.max(lo);
1472    } else if hi.is_finite() {
1473        start = start.min(hi - span);
1474    }
1475
1476    for (k, u) in movable.iter().enumerate() {
1477        let target = start + k as f64 * spacing;
1478        for seg in &u.segs {
1479            let offset = target - seg.coord;
1480            if offset.abs() <= EPS / 2.0 {
1481                continue;
1482            }
1483            if lane_blocked(seg, axis, target, rects) {
1484                continue;
1485            }
1486            out.push(Shift {
1487                seg: *seg,
1488                axis,
1489                offset,
1490            });
1491        }
1492    }
1493}
1494
1495// =============================================================================
1496// Small utilities
1497// =============================================================================
1498
1499fn dedupe_sorted(mut values: Vec<f64>) -> Vec<f64> {
1500    values.sort_by(|a, b| a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal));
1501    let mut out: Vec<f64> = Vec::with_capacity(values.len());
1502    for v in values {
1503        if out.last().is_none_or(|&last| v - last > EPS) {
1504            out.push(v);
1505        }
1506    }
1507    out
1508}
1509
1510/// First index with arr[i] >= v.
1511fn lower_bound(arr: &[f64], v: f64) -> usize {
1512    arr.partition_point(|&x| x < v)
1513}
1514
1515/// First index with arr[i] > v.
1516fn upper_bound(arr: &[f64], v: f64) -> usize {
1517    arr.partition_point(|&x| x <= v)
1518}
1519
1520/// Index of v in the deduped sorted array (within EPS).
1521fn index_of(arr: &[f64], v: f64) -> Option<usize> {
1522    let i = lower_bound(arr, v - EPS);
1523    if i < arr.len() && (arr[i] - v).abs() <= EPS {
1524        Some(i)
1525    } else {
1526        None
1527    }
1528}
1529
1530/// Binary min-heap keyed by f-score. Ties break on the state index so a solve
1531/// is reproducible run to run.
1532#[derive(Default)]
1533struct MinHeap {
1534    items: Vec<(f64, usize)>,
1535}
1536
1537impl MinHeap {
1538    fn clear(&mut self) {
1539        self.items.clear();
1540    }
1541
1542    fn less(a: (f64, usize), b: (f64, usize)) -> bool {
1543        match a.0.partial_cmp(&b.0) {
1544            Some(std::cmp::Ordering::Less) => true,
1545            Some(std::cmp::Ordering::Equal) => a.1 < b.1,
1546            _ => false,
1547        }
1548    }
1549
1550    fn push(&mut self, item: usize, score: f64) {
1551        self.items.push((score, item));
1552        let mut i = self.items.len() - 1;
1553        while i > 0 {
1554            let parent = (i - 1) / 2;
1555            if !Self::less(self.items[i], self.items[parent]) {
1556                break;
1557            }
1558            self.items.swap(i, parent);
1559            i = parent;
1560        }
1561    }
1562
1563    fn pop(&mut self) -> Option<usize> {
1564        if self.items.is_empty() {
1565            return None;
1566        }
1567        let top = self.items[0].1;
1568        let last = self.items.pop().unwrap();
1569        if !self.items.is_empty() {
1570            self.items[0] = last;
1571            let mut i = 0;
1572            loop {
1573                let (l, r) = (i * 2 + 1, i * 2 + 2);
1574                let mut smallest = i;
1575                if l < self.items.len() && Self::less(self.items[l], self.items[smallest]) {
1576                    smallest = l;
1577                }
1578                if r < self.items.len() && Self::less(self.items[r], self.items[smallest]) {
1579                    smallest = r;
1580                }
1581                if smallest == i {
1582                    break;
1583                }
1584                self.items.swap(i, smallest);
1585                i = smallest;
1586            }
1587        }
1588        Some(top)
1589    }
1590}
1591
1592#[cfg(test)]
1593mod tests {
1594    use super::*;
1595
1596    fn p(x: f64, y: f64) -> Position {
1597        Position::new(x, y)
1598    }
1599
1600    /// Every waypoint pair is axis-aligned (no diagonals ever leave the router).
1601    fn assert_orthogonal(route: &[Position]) {
1602        for w in route.windows(2) {
1603            let dx = (w[0].x - w[1].x).abs();
1604            let dy = (w[0].y - w[1].y).abs();
1605            assert!(
1606                dx < EPS || dy < EPS,
1607                "diagonal segment {:?} → {:?}",
1608                w[0],
1609                w[1]
1610            );
1611        }
1612    }
1613
1614    /// True when a segment passes through the rect's interior (not just its edge).
1615    fn crosses_interior(route: &[Position], r: SubwayRect) -> bool {
1616        let pad = 1.0;
1617        route.windows(2).any(|w| {
1618            let (a, b) = (w[0], w[1]);
1619            a.x.min(b.x) < r.x + r.w - pad
1620                && a.x.max(b.x) > r.x + pad
1621                && a.y.min(b.y) < r.y + r.h - pad
1622                && a.y.max(b.y) > r.y + pad
1623        })
1624    }
1625
1626    #[test]
1627    fn routes_are_orthogonal_and_touch_both_anchors() {
1628        let rects = [
1629            SubwayRect {
1630                x: 0.0,
1631                y: 0.0,
1632                w: 100.0,
1633                h: 60.0,
1634            },
1635            SubwayRect {
1636                x: 300.0,
1637                y: 200.0,
1638                w: 100.0,
1639                h: 60.0,
1640            },
1641        ];
1642        let conns = [SubwayConnection {
1643            start: p(100.0, 30.0),
1644            end: p(300.0, 230.0),
1645            start_rect: Some(0),
1646            end_rect: Some(1),
1647        }];
1648        let routes = compute_subway_routes(&rects, &conns, &SubwayOptions::default());
1649        assert_eq!(routes.len(), 1);
1650        let r = &routes[0];
1651        assert!(r.len() >= 2);
1652        assert_eq!(r[0], conns[0].start);
1653        assert_eq!(*r.last().unwrap(), conns[0].end);
1654        assert_orthogonal(r);
1655    }
1656
1657    #[test]
1658    fn route_goes_around_a_blocking_node() {
1659        // A wall sits directly between the two endpoints, on their shared row.
1660        let rects = [
1661            SubwayRect {
1662                x: 0.0,
1663                y: 0.0,
1664                w: 80.0,
1665                h: 40.0,
1666            },
1667            SubwayRect {
1668                x: 150.0,
1669                y: -60.0,
1670                w: 60.0,
1671                h: 160.0,
1672            },
1673            SubwayRect {
1674                x: 300.0,
1675                y: 0.0,
1676                w: 80.0,
1677                h: 40.0,
1678            },
1679        ];
1680        let conns = [SubwayConnection {
1681            start: p(80.0, 20.0),
1682            end: p(300.0, 20.0),
1683            start_rect: Some(0),
1684            end_rect: Some(2),
1685        }];
1686        let routes = compute_subway_routes(&rects, &conns, &SubwayOptions::default());
1687        let r = &routes[0];
1688        assert_orthogonal(r);
1689        assert!(
1690            !crosses_interior(r, rects[1]),
1691            "route tunnels the wall: {r:?}"
1692        );
1693        // Going around costs bends — a straight shot would be 2 points.
1694        assert!(r.len() > 2, "expected a detour, got {r:?}");
1695    }
1696
1697    #[test]
1698    fn parallel_wires_do_not_share_a_corridor() {
1699        // Two independent node pairs stacked so their natural mid-x elbows would
1700        // land on the same vertical corridor.
1701        let rects = [
1702            SubwayRect {
1703                x: 0.0,
1704                y: 0.0,
1705                w: 80.0,
1706                h: 40.0,
1707            },
1708            SubwayRect {
1709                x: 400.0,
1710                y: 300.0,
1711                w: 80.0,
1712                h: 40.0,
1713            },
1714            SubwayRect {
1715                x: 0.0,
1716                y: 100.0,
1717                w: 80.0,
1718                h: 40.0,
1719            },
1720            SubwayRect {
1721                x: 400.0,
1722                y: 400.0,
1723                w: 80.0,
1724                h: 40.0,
1725            },
1726        ];
1727        let conns = [
1728            SubwayConnection {
1729                start: p(80.0, 20.0),
1730                end: p(400.0, 320.0),
1731                start_rect: Some(0),
1732                end_rect: Some(1),
1733            },
1734            SubwayConnection {
1735                start: p(80.0, 120.0),
1736                end: p(400.0, 420.0),
1737                start_rect: Some(2),
1738                end_rect: Some(3),
1739            },
1740        ];
1741        let routes = compute_subway_routes(&rects, &conns, &SubwayOptions::default());
1742
1743        // Collect vertical runs of each route and check no pair is collinear
1744        // AND overlapping — that's the "never run on top of each other" rule.
1745        let verticals = |r: &Vec<Position>| -> Vec<(f64, f64, f64)> {
1746            r.windows(2)
1747                .filter(|w| (w[0].x - w[1].x).abs() < EPS && (w[0].y - w[1].y).abs() >= EPS)
1748                .map(|w| (w[0].x, w[0].y.min(w[1].y), w[0].y.max(w[1].y)))
1749                .collect()
1750        };
1751        for a in verticals(&routes[0]) {
1752            for b in verticals(&routes[1]) {
1753                let same_corridor = (a.0 - b.0).abs() < EPS;
1754                let overlaps = a.1 < b.2 - EPS && b.1 < a.2 - EPS;
1755                assert!(
1756                    !(same_corridor && overlaps),
1757                    "vertical runs overlap: {a:?} vs {b:?}"
1758                );
1759            }
1760        }
1761    }
1762
1763    #[test]
1764    fn wires_from_one_pin_share_their_trunk() {
1765        // A fan-out from a single output pin is ONE subway line: the segments
1766        // leaving the pin must stay on a common column, not fan into lanes.
1767        let rects = [
1768            SubwayRect {
1769                x: 0.0,
1770                y: 0.0,
1771                w: 80.0,
1772                h: 120.0,
1773            },
1774            SubwayRect {
1775                x: 300.0,
1776                y: 0.0,
1777                w: 80.0,
1778                h: 40.0,
1779            },
1780            SubwayRect {
1781                x: 300.0,
1782                y: 200.0,
1783                w: 80.0,
1784                h: 40.0,
1785            },
1786        ];
1787        let start = p(80.0, 60.0);
1788        let conns = [
1789            SubwayConnection {
1790                start,
1791                end: p(300.0, 20.0),
1792                start_rect: Some(0),
1793                end_rect: Some(1),
1794            },
1795            SubwayConnection {
1796                start,
1797                end: p(300.0, 220.0),
1798                start_rect: Some(0),
1799                end_rect: Some(2),
1800            },
1801        ];
1802        let routes = compute_subway_routes(&rects, &conns, &SubwayOptions::default());
1803        for r in &routes {
1804            assert_eq!(r[0], start, "route must start at the shared pin");
1805            assert_orthogonal(r);
1806        }
1807        // Both leave along the same escape column.
1808        assert!(
1809            (routes[0][1].x - routes[1][1].x).abs() < EPS,
1810            "trunk split: {:?} vs {:?}",
1811            routes[0][1],
1812            routes[1][1]
1813        );
1814    }
1815
1816    #[test]
1817    fn missing_rects_still_route() {
1818        // Endpoints with unknown/unmeasured nodes fall back to plain stubs.
1819        let conns = [SubwayConnection {
1820            start: p(0.0, 0.0),
1821            end: p(200.0, 100.0),
1822            start_rect: None,
1823            end_rect: None,
1824        }];
1825        let routes = compute_subway_routes(&[], &conns, &SubwayOptions::default());
1826        assert_eq!(routes.len(), 1);
1827        assert_orthogonal(&routes[0]);
1828        assert_eq!(routes[0][0], conns[0].start);
1829        assert_eq!(*routes[0].last().unwrap(), conns[0].end);
1830    }
1831
1832    #[test]
1833    fn solving_is_deterministic() {
1834        let rects = [
1835            SubwayRect {
1836                x: 0.0,
1837                y: 0.0,
1838                w: 80.0,
1839                h: 40.0,
1840            },
1841            SubwayRect {
1842                x: 200.0,
1843                y: 90.0,
1844                w: 80.0,
1845                h: 40.0,
1846            },
1847            SubwayRect {
1848                x: 120.0,
1849                y: -40.0,
1850                w: 40.0,
1851                h: 200.0,
1852            },
1853        ];
1854        let conns = [
1855            SubwayConnection {
1856                start: p(80.0, 20.0),
1857                end: p(200.0, 110.0),
1858                start_rect: Some(0),
1859                end_rect: Some(1),
1860            },
1861            SubwayConnection {
1862                start: p(80.0, 30.0),
1863                end: p(200.0, 100.0),
1864                start_rect: Some(0),
1865                end_rect: Some(1),
1866            },
1867        ];
1868        let a = compute_subway_routes(&rects, &conns, &SubwayOptions::default());
1869        let b = compute_subway_routes(&rects, &conns, &SubwayOptions::default());
1870        assert_eq!(a, b);
1871    }
1872
1873    #[test]
1874    fn simplify_drops_duplicates_and_collinear_points() {
1875        let pts = [
1876            p(0.0, 0.0),
1877            p(0.0, 0.0),
1878            p(10.0, 0.0),
1879            p(20.0, 0.0),
1880            p(20.0, 10.0),
1881        ];
1882        assert_eq!(
1883            simplify(&pts),
1884            vec![p(0.0, 0.0), p(20.0, 0.0), p(20.0, 10.0)]
1885        );
1886    }
1887
1888    #[test]
1889    fn route_intersects_rect_detects_near_misses() {
1890        let route = [p(0.0, 0.0), p(100.0, 0.0), p(100.0, 100.0)];
1891        let far = SubwayRect {
1892            x: 200.0,
1893            y: 200.0,
1894            w: 10.0,
1895            h: 10.0,
1896        };
1897        let near = SubwayRect {
1898            x: 50.0,
1899            y: 5.0,
1900            w: 10.0,
1901            h: 10.0,
1902        };
1903        assert!(!route_intersects_rect(&route, far, 4.0));
1904        assert!(route_intersects_rect(&route, near, 8.0));
1905    }
1906
1907    #[test]
1908    fn aggregate_nesting_order_resolves_pairwise_preference_cycle() {
1909        let segment = |route, lo, hi, lo_dir, hi_dir| LaneSegment {
1910            route,
1911            i: 0,
1912            coord: 10.0,
1913            lo,
1914            hi,
1915            pinned: false,
1916            sort_key: 0.0,
1917            lo_dir,
1918            hi_dir,
1919        };
1920        // These three brackets vote A < B, B < C, and C < A. Feeding those
1921        // votes directly to sort_by was the non-transitive live-WASM panic.
1922        let a = segment(0, 1.0, 3.0, -1.0, 1.0);
1923        let b = segment(1, 0.0, 3.0, -1.0, -1.0);
1924        let c = segment(2, 1.0, 4.0, 0.0, -1.0);
1925        assert!(lane_nesting_preference(&a, &b) < 0.0);
1926        assert!(lane_nesting_preference(&b, &c) < 0.0);
1927        assert!(lane_nesting_preference(&c, &a) < 0.0);
1928
1929        let permutations = [
1930            vec![a, b, c],
1931            vec![a, c, b],
1932            vec![b, a, c],
1933            vec![b, c, a],
1934            vec![c, a, b],
1935            vec![c, b, a],
1936        ];
1937        for representatives in permutations {
1938            let scores = aggregate_nesting_scores(&representatives);
1939            let mut ranked: Vec<_> = representatives.into_iter().zip(scores).collect();
1940            ranked.sort_by(|(a, a_score), (b, b_score)| {
1941                compare_lane_order(
1942                    LaneOrderKey {
1943                        nesting_score: *a_score,
1944                        sort_key: a.sort_key,
1945                        coord: a.coord,
1946                        stable_key: (a.route, a.i),
1947                    },
1948                    LaneOrderKey {
1949                        nesting_score: *b_score,
1950                        sort_key: b.sort_key,
1951                        coord: b.coord,
1952                        stable_key: (b.route, b.i),
1953                    },
1954                )
1955            });
1956            assert_eq!(
1957                ranked
1958                    .into_iter()
1959                    .map(|(segment, _)| segment.route)
1960                    .collect::<Vec<_>>(),
1961                vec![0, 1, 2]
1962            );
1963        }
1964    }
1965
1966    #[test]
1967    fn oversized_grid_falls_back_to_elbows() {
1968        let rects = [
1969            SubwayRect {
1970                x: 0.0,
1971                y: 0.0,
1972                w: 80.0,
1973                h: 40.0,
1974            },
1975            SubwayRect {
1976                x: 300.0,
1977                y: 0.0,
1978                w: 80.0,
1979                h: 40.0,
1980            },
1981        ];
1982        let conns = [SubwayConnection {
1983            start: p(80.0, 20.0),
1984            end: p(300.0, 20.0),
1985            start_rect: Some(0),
1986            end_rect: Some(1),
1987        }];
1988        let opts = SubwayOptions {
1989            max_grid_cells: 1,
1990            ..Default::default()
1991        };
1992        let routes = compute_subway_routes(&rects, &conns, &opts);
1993        assert_orthogonal(&routes[0]);
1994        assert_eq!(routes[0][0], conns[0].start);
1995        assert_eq!(*routes[0].last().unwrap(), conns[0].end);
1996    }
1997}