AI Flow: Routing

//! Connectivity from copper alone: which pads of a net are joined by tracks, vias and zones.
//! Used by the checker and to find what still has to be routed on a partly routed board.

use crate::board::*;
use crate::geom::*;
use std::collections::HashMap;

#[derive(Clone)]
pub struct Uf(Vec<u32>);
impl Uf {
    pub fn new(n: usize) -> Uf {
        Uf((0..n as u32).collect())
    }
    pub fn find(&mut self, a: u32) -> u32 {
        let mut r = a;
        while self.0[r as usize] != r {
            r = self.0[r as usize];
        }
        let mut c = a;
        while self.0[c as usize] != r {
            let n = self.0[c as usize];
            self.0[c as usize] = r;
            c = n;
        }
        r
    }
    pub fn union(&mut self, a: u32, b: u32) {
        let (x, y) = (self.find(a), self.find(b));
        if x != y {
            self.0[x as usize] = y;
        }
    }
}

/// One piece of copper on one or more layers, for connectivity.
pub enum Piece {
    Pad(usize),
    Seg { layer: usize, a: V, b: V, r: f64 },
    Via { at: V, r: f64 },
    Fill { layer: usize, pts: Vec<V> },
}

pub fn touches(p: &Piece, q: &Piece, board: &Board) -> bool {
    use Piece::*;
    match (p, q) {
        (Pad(i), Pad(j)) => {
            let (a, b) = (&board.pads[*i], &board.pads[*j]);
            a.layers.iter().any(|l| b.layers.contains(l)) && a.shape.dist_shape(&b.shape) <= 1.0
        }
        (Pad(i), Seg { layer, a, b, r }) | (Seg { layer, a, b, r }, Pad(i)) => {
            let pad = &board.pads[*i];
            pad.layers.contains(layer) && pad.shape.dist_seg(*a, *b) <= r + 1.0
        }
        (Pad(i), Via { at, r }) | (Via { at, r }, Pad(i)) => board.pads[*i].shape.dist_pt(*at) <= r + 1.0 && !board.pads[*i].layers.is_empty(),
        (Pad(i), Fill { layer, pts }) | (Fill { layer, pts }, Pad(i)) => {
            let pad = &board.pads[*i];
            pad.layers.contains(layer) && shape_meets_poly(&pad.shape, pts)
        }
        (Seg { layer: l1, a, b, r }, Seg { layer: l2, a: c, b: d, r: s }) => l1 == l2 && seg_seg(*a, *b, *c, *d) <= r + s + 1.0,
        (Seg { a, b, r, .. }, Via { at, r: s }) | (Via { at, r: s }, Seg { a, b, r, .. }) => pt_seg(*at, *a, *b) <= r + s + 1.0,
        (Seg { layer: l1, a, b, r }, Fill { layer: l2, pts }) | (Fill { layer: l2, pts }, Seg { layer: l1, a, b, r }) => {
            l1 == l2 && (in_poly(*a, pts) || in_poly(*b, pts) || poly_seg_dist(pts, *a, *b) <= *r + 1.0)
        }
        (Via { at: a, r }, Via { at: b, r: s }) => hypot(sub(*a, *b)) <= r + s + 1.0,
        (Via { at, r }, Fill { pts, .. }) | (Fill { pts, .. }, Via { at, r }) => in_poly(*at, pts) || poly_seg_dist(pts, *at, *at) <= *r,
        (Fill { layer: l1, pts: a }, Fill { layer: l2, pts: b }) => l1 == l2 && polys_meet(a, b),
    }
}

/// Two fills are one piece of copper as soon as they overlap anywhere. Testing a single vertex
/// missed overlapping zones whose first vertices lie outside each other, which split nets KiCad
/// sees as joined (benchmark B's GND, +PS1_SENS, -PS1 and +PS2_RLY fills).
fn polys_meet(a: &[V], b: &[V]) -> bool {
    let bb = |p: &[V]| p.iter().fold((f64::MAX, f64::MAX, f64::MIN, f64::MIN), |m, v| (m.0.min(v.0), m.1.min(v.1), m.2.max(v.0), m.3.max(v.1)));
    let (ba, bc) = (bb(a), bb(b));
    if ba.0 > bc.2 + 1.0 || bc.0 > ba.2 + 1.0 || ba.1 > bc.3 + 1.0 || bc.1 > ba.3 + 1.0 {
        return false;
    }
    if a.iter().any(|p| in_poly(*p, b)) || b.iter().any(|p| in_poly(*p, a)) {
        return true;
    }
    let (n, m) = (a.len(), b.len());
    for i in 0..n {
        let (p, q) = (a[i], a[(i + 1) % n]);
        if p.0.max(q.0) < bc.0 || p.0.min(q.0) > bc.2 || p.1.max(q.1) < bc.1 || p.1.min(q.1) > bc.3 {
            continue;
        }
        for j in 0..m {
            if seg_seg(p, q, b[j], b[(j + 1) % m]) <= 1.0 {
                return true;
            }
        }
    }
    false
}

fn poly_seg_dist(pts: &[V], a: V, b: V) -> f64 {
    let n = pts.len();
    let mut d = f64::INFINITY;
    for i in 0..n {
        d = d.min(seg_seg(a, b, pts[i], pts[(i + 1) % n]));
    }
    d
}

pub(crate) fn shape_meets_poly(s: &Shape, pts: &[V]) -> bool {
    let c = s.center();
    if in_poly(c, pts) {
        return true;
    }
    let n = pts.len();
    for i in 0..n {
        if s.dist_seg(pts[i], pts[(i + 1) % n]) <= 1.0 {
            return true;
        }
    }
    false
}

/// Groups of pad indices per net that the copper on `board` already joins. `extra` adds copper
/// from a route in progress, as (net, piece).
/// One connected piece of a net's copper.
pub struct Island {
    pub net: NetId,
    pub has_pad: bool,
    pub fill_pieces: usize,
    pub tracks: usize,
    pub vias: usize,
    pub layer: usize,
    pub at: V,
    pub area: f64,
}

/// Every connected piece of copper on the board, net by net, pads or none. `pad_groups` keeps only
/// what touches a pad, so a fill nothing feeds is invisible to it.
pub fn islands(board: &Board) -> Vec<Island> {
    let mut by_net: HashMap<NetId, Vec<Piece>> = HashMap::new();
    for (i, p) in board.pads.iter().enumerate() {
        if p.net != NO_NET && !p.layers.is_empty() {
            by_net.entry(p.net).or_default().push(Piece::Pad(i));
        }
    }
    for t in &board.tracks {
        if t.net != NO_NET {
            by_net.entry(t.net).or_default().push(Piece::Seg { layer: t.layer, a: t.a.into(), b: t.b.into(), r: t.width as f64 / 2.0 });
        }
    }
    for v in &board.vias {
        if v.net != NO_NET {
            by_net.entry(v.net).or_default().push(Piece::Via { at: v.at.into(), r: v.size as f64 / 2.0 });
        }
    }
    for z in &board.zones {
        if z.net == NO_NET || z.keepout_tracks {
            continue;
        }
        if z.fills.is_empty() {
            for &l in &z.layers {
                by_net.entry(z.net).or_default().push(Piece::Fill { layer: l, pts: z.outline.clone() });
            }
        } else {
            for (l, pts) in &z.fills {
                by_net.entry(z.net).or_default().push(Piece::Fill { layer: *l, pts: pts.clone() });
            }
        }
    }
    let mut out = Vec::new();
    for (net, pieces) in by_net {
        let mut uf = Uf::new(pieces.len());
        for i in 0..pieces.len() {
            for j in i + 1..pieces.len() {
                if uf.find(i as u32) != uf.find(j as u32) && touches(&pieces[i], &pieces[j], board) {
                    uf.union(i as u32, j as u32);
                }
            }
        }
        let mut groups: HashMap<u32, Island> = HashMap::new();
        for (i, p) in pieces.iter().enumerate() {
            let isl = groups.entry(uf.find(i as u32)).or_insert(Island { net, has_pad: false, fill_pieces: 0, tracks: 0, vias: 0, layer: 0, at: V(0.0, 0.0), area: 0.0 });
            match p {
                Piece::Pad(_) => isl.has_pad = true,
                Piece::Seg { layer, a, .. } => {
                    isl.tracks += 1;
                    if isl.fill_pieces == 0 {
                        isl.layer = *layer;
                        isl.at = *a;
                    }
                }
                Piece::Via { at, .. } => {
                    isl.vias += 1;
                    if isl.fill_pieces == 0 && isl.tracks == 0 {
                        isl.at = *at;
                    }
                }
                Piece::Fill { layer, pts } => {
                    isl.fill_pieces += 1;
                    isl.layer = *layer;
                    isl.at = pts.first().copied().unwrap_or(V(0.0, 0.0));
                    let n = pts.len();
                    let a: f64 = (0..n).map(|k| pts[k].0 * pts[(k + 1) % n].1 - pts[(k + 1) % n].0 * pts[k].1).sum();
                    isl.area += (a / 2.0).abs();
                }
            }
        }
        out.extend(groups.into_values());
    }
    out.sort_by(|a, b| (a.net, a.at.0.to_bits()).cmp(&(b.net, b.at.0.to_bits())));
    out
}

pub fn pad_groups(board: &Board, extra: &[(NetId, Piece)]) -> HashMap<NetId, Vec<Vec<usize>>> {
    let mut by_net: HashMap<NetId, Vec<Piece>> = HashMap::new();
    for (i, p) in board.pads.iter().enumerate() {
        if p.net != NO_NET && !p.layers.is_empty() {
            by_net.entry(p.net).or_default().push(Piece::Pad(i));
        }
    }
    for t in &board.tracks {
        by_net.entry(t.net).or_default().push(Piece::Seg { layer: t.layer, a: t.a.into(), b: t.b.into(), r: t.width as f64 / 2.0 });
    }
    for v in &board.vias {
        by_net.entry(v.net).or_default().push(Piece::Via { at: v.at.into(), r: v.size as f64 / 2.0 });
    }
    for z in &board.zones {
        if z.net == NO_NET || z.keepout_tracks {
            continue;
        }
        if z.fills.is_empty() {
            for &l in &z.layers {
                by_net.entry(z.net).or_default().push(Piece::Fill { layer: l, pts: z.outline.clone() });
            }
        } else {
            for (l, pts) in &z.fills {
                by_net.entry(z.net).or_default().push(Piece::Fill { layer: *l, pts: pts.clone() });
            }
        }
    }
    for (n, p) in extra {
        let q = match p {
            Piece::Pad(i) => Piece::Pad(*i),
            Piece::Seg { layer, a, b, r } => Piece::Seg { layer: *layer, a: *a, b: *b, r: *r },
            Piece::Via { at, r } => Piece::Via { at: *at, r: *r },
            Piece::Fill { layer, pts } => Piece::Fill { layer: *layer, pts: pts.clone() },
        };
        by_net.entry(*n).or_default().push(q);
    }
    let mut out = HashMap::new();
    for (net, pieces) in by_net {
        let mut uf = Uf::new(pieces.len());
        for i in 0..pieces.len() {
            for j in i + 1..pieces.len() {
                if uf.find(i as u32) != uf.find(j as u32) && touches(&pieces[i], &pieces[j], board) {
                    uf.union(i as u32, j as u32);
                }
            }
        }
        let mut groups: HashMap<u32, Vec<usize>> = HashMap::new();
        for (i, p) in pieces.iter().enumerate() {
            if let Piece::Pad(k) = p {
                groups.entry(uf.find(i as u32)).or_default().push(*k);
            }
        }
        let mut v: Vec<Vec<usize>> = groups.into_values().collect();
        v.sort();
        out.insert(net, v);
    }
    out
}

/// `pad_groups` for one net, with routed copper in progress: cheap enough to ask during routing.
pub fn net_groups(board: &Board, net: NetId, extra: &[(NetId, Piece)]) -> Vec<Vec<usize>> {
    let mut pieces: Vec<&Piece> = Vec::new();
    let mut own: Vec<Piece> = Vec::new();
    for (i, p) in board.pads.iter().enumerate() {
        if p.net == net && !p.layers.is_empty() {
            own.push(Piece::Pad(i));
        }
    }
    for t in board.tracks.iter().filter(|t| t.net == net) {
        own.push(Piece::Seg { layer: t.layer, a: t.a.into(), b: t.b.into(), r: t.width as f64 / 2.0 });
    }
    for v in board.vias.iter().filter(|v| v.net == net) {
        own.push(Piece::Via { at: v.at.into(), r: v.size as f64 / 2.0 });
    }
    for z in board.zones.iter().filter(|z| z.net == net && !z.keepout_tracks) {
        if z.fills.is_empty() {
            for &l in &z.layers {
                own.push(Piece::Fill { layer: l, pts: z.outline.clone() });
            }
        } else {
            for (l, pts) in &z.fills {
                own.push(Piece::Fill { layer: *l, pts: pts.clone() });
            }
        }
    }
    pieces.extend(own.iter());
    pieces.extend(extra.iter().filter(|(n, _)| *n == net).map(|(_, p)| p));
    let mut uf = Uf::new(pieces.len());
    for i in 0..pieces.len() {
        for j in i + 1..pieces.len() {
            if uf.find(i as u32) != uf.find(j as u32) && touches(pieces[i], pieces[j], board) {
                uf.union(i as u32, j as u32);
            }
        }
    }
    let mut groups: HashMap<u32, Vec<usize>> = HashMap::new();
    for (i, p) in pieces.iter().enumerate() {
        if let Piece::Pad(k) = p {
            groups.entry(uf.find(i as u32)).or_default().push(*k);
        }
    }
    let mut v: Vec<Vec<usize>> = groups.into_values().collect();
    v.sort();
    v
}