AM/FM Receiver Molecule

"""Grid A* router that completes connections the autorouter left open.

For every ratsnest edge still open after Freerouting (+ zone fill), route from the smaller
copper island to the other one on F.Cu/B.Cu (vias allowed), honouring netclass width and
clearance.  For plane nets (GND/+5VA/+3V3) a via dropped inside the net's plane zone counts
as reaching the target.
"""
import math, heapq, sys, os
import numpy as np
import pcbnew

RES = 0.05        # grid resolution (mm)
# Items removed from the board stay referenced here: letting SWIG garbage-collect a removed
# PCB_TRACK corrupts pcbnew's type table for the rest of the process.
GRAVEYARD = []
VIA_D, VIA_DRILL = 0.6, 0.3
PLANE_LAYER = {'GND': pcbnew.In1_Cu, '+5VA': pcbnew.In2_Cu, '+3V3': pcbnew.In2_Cu}


def tomm(v):
    return pcbnew.ToMM(v)


def mm(v):
    return pcbnew.FromMM(v)


class Router:
    def __init__(self, board, ox, oy, w, h):
        self.b = board
        self.ox, self.oy = ox, oy
        self.nx, self.ny = int(round(w / RES)) + 1, int(round(h / RES)) + 1
        xs = ox + np.arange(self.nx) * RES
        ys = oy + np.arange(self.ny) * RES
        self.X, self.Y = np.meshgrid(xs, ys, indexing='ij')
        self.w, self.h = w, h
        self.collect()

    # ------------------------------------------------------------------ copper inventory
    def collect(self):
        self.items = []   # dict(kind, net, layers, geometry)
        for fp in self.b.GetFootprints():
            for p in fp.Pads():
                bb = p.GetBoundingBox()
                lays = set()
                for L, key in ((pcbnew.F_Cu, 'F'), (pcbnew.B_Cu, 'B')):
                    if p.IsOnLayer(L):
                        lays.add(key)
                if p.GetAttribute() in (pcbnew.PAD_ATTRIB_PTH, pcbnew.PAD_ATTRIB_NPTH):
                    lays = {'F', 'B'}
                self.items.append(dict(kind='pad', net=p.GetNetCode(), layers=lays, obj=p,
                                       rect=(tomm(bb.GetLeft()), tomm(bb.GetTop()), tomm(bb.GetRight()),
                                             tomm(bb.GetBottom())), hole=p.GetAttribute() != pcbnew.PAD_ATTRIB_SMD))
        for t in self.b.GetTracks():
            if t.GetClass() == 'PCB_VIA':
                p = t.GetPosition()
                self.items.append(dict(kind='via', net=t.GetNetCode(), layers={'F', 'B'}, obj=t,
                                       c=(tomm(p.x), tomm(p.y)), r=tomm(t.GetWidth(pcbnew.F_Cu)) / 2))
            else:
                L = t.GetLayer()
                if L not in (pcbnew.F_Cu, pcbnew.B_Cu):
                    continue
                a, e = t.GetStart(), t.GetEnd()
                self.items.append(dict(kind='track', net=t.GetNetCode(), layers={'F' if L == pcbnew.F_Cu else 'B'},
                                       obj=t, a=(tomm(a.x), tomm(a.y)), e=(tomm(e.x), tomm(e.y)),
                                       r=tomm(t.GetWidth()) / 2))

    # ------------------------------------------------------------------ rasterisation
    def _window(self, x0, y0, x1, y1):
        i0 = max(0, int(math.floor((x0 - self.ox) / RES)))
        i1 = min(self.nx, int(math.ceil((x1 - self.ox) / RES)) + 1)
        j0 = max(0, int(math.floor((y0 - self.oy) / RES)))
        j1 = min(self.ny, int(math.ceil((y1 - self.oy) / RES)) + 1)
        return i0, i1, j0, j1

    def paint(self, grid, it, margin):
        if it['kind'] == 'pad':
            x0, y0, x1, y1 = it['rect']
            i0, i1, j0, j1 = self._window(x0 - margin, y0 - margin, x1 + margin, y1 + margin)
            if i0 >= i1 or j0 >= j1:
                return
            X, Y = self.X[i0:i1, j0:j1], self.Y[i0:i1, j0:j1]
            dx = np.maximum(np.maximum(x0 - X, 0), X - x1)
            dy = np.maximum(np.maximum(y0 - Y, 0), Y - y1)
            grid[i0:i1, j0:j1] |= (dx * dx + dy * dy) <= margin * margin
        elif it['kind'] == 'via':
            cx, cy = it['c']
            R = it['r'] + margin
            i0, i1, j0, j1 = self._window(cx - R, cy - R, cx + R, cy + R)
            X, Y = self.X[i0:i1, j0:j1], self.Y[i0:i1, j0:j1]
            grid[i0:i1, j0:j1] |= (X - cx) ** 2 + (Y - cy) ** 2 <= R * R
        else:
            (ax, ay), (ex, ey), r = it['a'], it['e'], it['r']
            R = r + margin
            i0, i1, j0, j1 = self._window(min(ax, ex) - R, min(ay, ey) - R, max(ax, ex) + R, max(ay, ey) + R)
            X, Y = self.X[i0:i1, j0:j1], self.Y[i0:i1, j0:j1]
            vx, vy = ex - ax, ey - ay
            L2 = vx * vx + vy * vy
            if L2 == 0:
                t = np.zeros_like(X)
            else:
                t = np.clip(((X - ax) * vx + (Y - ay) * vy) / L2, 0, 1)
            px, py = ax + t * vx, ay + t * vy
            grid[i0:i1, j0:j1] |= (X - px) ** 2 + (Y - py) ** 2 <= R * R

    def obstacle_maps(self, net, hw, clr):
        blk = {k: np.zeros((self.nx, self.ny), bool) for k in 'FB'}
        via_blk = np.zeros((self.nx, self.ny), bool)
        rv = VIA_D / 2
        for it in self.items:
            same = it['net'] == net and net != 0
            for L in it['layers']:
                if not same:
                    self.paint(blk[L], it, clr + hw + RES * 0.75)
            if not same:
                self.paint(via_blk, it, clr + rv + RES * 0.75)
            else:
                if it['kind'] == 'pad':
                    self.paint(via_blk, it, rv + 0.05)          # no via-in-pad
            if it['kind'] == 'via':
                self.paint(via_blk, it, VIA_DRILL / 2 + 0.25 + RES)   # hole-to-hole
            if it['kind'] == 'pad' and it.get('hole'):
                self.paint(via_blk, it, rv + 0.25)
        # board edge
        e = 0.3
        for g in (blk['F'], blk['B']):
            g[(self.X < self.ox + e + hw) | (self.X > self.ox + self.w - e - hw) |
              (self.Y < self.oy + e + hw) | (self.Y > self.oy + self.h - e - hw)] = True
        via_blk[(self.X < self.ox + e + rv) | (self.X > self.ox + self.w - e - rv) |
                (self.Y < self.oy + e + rv) | (self.Y > self.oy + self.h - e - rv)] = True
        return blk, via_blk

    def target_maps(self, items):
        tg = {k: np.zeros((self.nx, self.ny), bool) for k in 'FB'}
        for it in items:
            for L in it['layers']:
                self.paint(tg[L], it, 0.0)
        return tg

    def plane_mask(self, netname):
        """Cells where a via would land inside the net's plane zone (outline, 0.8 mm margin)."""
        L = PLANE_LAYER.get(netname)
        m = np.zeros((self.nx, self.ny), bool)
        if L is None:
            return m
        for z in self.b.Zones():
            if z.GetNetname() != netname or not z.IsOnLayer(L):
                continue
            bb = z.Outline().BBox()
            x0, y0, x1, y1 = tomm(bb.GetLeft()) + 0.8, tomm(bb.GetTop()) + 0.8, tomm(bb.GetRight()) - 0.8, tomm(bb.GetBottom()) - 0.8
            m |= (self.X >= x0) & (self.X <= x1) & (self.Y >= y0) & (self.Y <= y1)
        return m

    # ------------------------------------------------------------------ search
    def astar(self, starts, tg, blk, via_blk, plane_goal, via_cost=40, max_nodes=3000000):
        """starts: list of (i, j, layer). Returns list of (i, j, layer, 'via'|'') or None."""
        nx, ny = self.nx, self.ny
        LAY = {'F': 0, 'B': 1}
        goal_idx = [np.argwhere(tg['F']), np.argwhere(tg['B'])]
        pg = np.argwhere(plane_goal & ~via_blk) if plane_goal is not None else np.zeros((0, 2), int)
        allg = [g for g in (goal_idx[0], goal_idx[1], pg) if len(g)]
        if not allg:
            return None
        allg = np.vstack(allg)
        # coarse heuristic: distance to nearest goal among a subsample
        sub = allg[:: max(1, len(allg) // 400)]

        def h(i, j):
            d = np.min(np.abs(sub[:, 0] - i) + np.abs(sub[:, 1] - j))
            return 0.9 * d

        open_ = []
        g = {}
        parent = {}
        for (i, j, L) in starts:
            s = (i, j, LAY[L])
            g[s] = 0.0
            heapq.heappush(open_, (h(i, j), 0.0, s))
            parent[s] = None
        dirs = [(1, 0, 1.0), (-1, 0, 1.0), (0, 1, 1.0), (0, -1, 1.0),
                (1, 1, 1.414), (1, -1, 1.414), (-1, 1, 1.414), (-1, -1, 1.414)]
        blkL = [blk['F'], blk['B']]
        tgL = [tg['F'], tg['B']]
        hcache = {}
        n = 0
        while open_:
            f, gc, s = heapq.heappop(open_)
            if g.get(s, 1e18) < gc - 1e-9:
                continue
            i, j, L = s
            n += 1
            if n > max_nodes:
                return None
            if tgL[L][i, j] and parent[s] is not None:
                return self._path(parent, s)
            if plane_goal is not None and plane_goal[i, j] and not via_blk[i, j] and parent[s] is not None:
                return self._path(parent, s) + [(i, j, L, 'plane')]
            for di, dj, c in dirs:
                a, b_ = i + di, j + dj
                if a < 0 or b_ < 0 or a >= nx or b_ >= ny:
                    continue
                if blkL[L][a, b_] and not tgL[L][a, b_]:
                    continue
                # changing direction costs a little (keeps tracks straight)
                ns = (a, b_, L)
                ng = gc + c
                if ng < g.get(ns, 1e18):
                    g[ns] = ng
                    parent[ns] = (s, '')
                    key = (a // 8, b_ // 8)
                    if key not in hcache:
                        hcache[key] = h(a, b_)
                    heapq.heappush(open_, (ng + hcache[key], ng, ns))
            if not via_blk[i, j]:
                ns = (i, j, 1 - L)
                ng = gc + via_cost
                if not blkL[1 - L][i, j] and ng < g.get(ns, 1e18):
                    g[ns] = ng
                    parent[ns] = (s, 'via')
                    key = (i // 8, j // 8)
                    if key not in hcache:
                        hcache[key] = h(i, j)
                    heapq.heappush(open_, (ng + hcache[key], ng, ns))
        return None

    def _path(self, parent, s):
        out = []
        cur = s
        while cur is not None:
            p = parent[cur]
            out.append((cur[0], cur[1], cur[2], p[1] if p else ''))
            cur = p[0] if p else None
        out.reverse()
        return out

    def commit(self, path, net, width, locked=False, start_anchor=None, end_anchor=None):
        """Turn a cell path into straight track runs and vias on the board.  Anchors (x, y) pull the
        ends onto the centre of the pad/via/track they touch so KiCad sees a solid connection."""
        pts = [(self.ox + i * RES, self.oy + j * RES, L, flag) for i, j, L, flag in path]
        if start_anchor is not None:
            pts.insert(0, (start_anchor[0], start_anchor[1], pts[0][2], ''))
        if end_anchor is not None and pts[-1][3] != 'plane':
            pts.append((end_anchor[0], end_anchor[1], pts[-1][2], ''))
        layer_id = [pcbnew.F_Cu, pcbnew.B_Cu]
        segs, vias = [], []
        run = [pts[0]]
        for k in range(1, len(pts)):
            x, y, L, flag = pts[k]
            if flag == 'via':
                segs.append(run)
                vias.append((x, y))
                run = [pts[k]]
                continue
            run.append(pts[k])
        segs.append(run)
        if pts[-1][3] == 'plane':
            vias.append((pts[-1][0], pts[-1][1]))
        added = []
        for run in segs:
            if len(run) < 2:
                continue
            # compress collinear points
            simp = [run[0]]
            for k in range(1, len(run) - 1):
                x0, y0 = simp[-1][0], simp[-1][1]
                x1, y1 = run[k][0], run[k][1]
                x2, y2 = run[k + 1][0], run[k + 1][1]
                if abs((x1 - x0) * (y2 - y1) - (y1 - y0) * (x2 - x1)) > 1e-9:
                    simp.append(run[k])
            simp.append(run[-1])
            for a, b in zip(simp, simp[1:]):
                t = pcbnew.PCB_TRACK(self.b)
                t.SetStart(pcbnew.VECTOR2I(mm(a[0]), mm(a[1])))
                t.SetEnd(pcbnew.VECTOR2I(mm(b[0]), mm(b[1])))
                t.SetWidth(mm(width))
                t.SetLayer(layer_id[a[2]])
                t.SetNetCode(net)
                self.b.Add(t)
                added.append(t)
                self.items.append(dict(kind='track', net=net, layers={'FB'[a[2]]}, obj=t, a=(a[0], a[1]),
                                       e=(b[0], b[1]), r=width / 2))
        for x, y in vias:
            v = pcbnew.PCB_VIA(self.b)
            v.SetPosition(pcbnew.VECTOR2I(mm(x), mm(y)))
            v.SetWidth(mm(VIA_D))
            v.SetDrill(mm(VIA_DRILL))
            v.SetViaType(pcbnew.VIATYPE_THROUGH)
            v.SetLayerPair(pcbnew.F_Cu, pcbnew.B_Cu)
            v.SetNetCode(net)
            self.b.Add(v)
            added.append(v)
            self.items.append(dict(kind='via', net=net, layers={'F', 'B'}, obj=v, c=(x, y), r=VIA_D / 2))
        return added


def item_dicts(router, objs):
    ids = {id(o) for o in objs}
    out = []
    keyset = set()
    for o in objs:
        keyset.add(o.m_Uuid.AsString())
    for it in router.items:
        if it['obj'].m_Uuid.AsString() in keyset:
            out.append(it)
    return out


def anchor_for(r, items, x, y, layer):
    """Centre of the copper item (pad/via) or nearest centre-line point (track) under (x, y)."""
    best, bd = None, 1e9
    for it in items:
        if layer not in it['layers']:
            continue
        if it['kind'] == 'pad':
            x0, y0, x1, y1 = it['rect']
            d = math.hypot(max(x0 - x, 0, x - x1), max(y0 - y, 0, y - y1))
            c = ((x0 + x1) / 2, (y0 + y1) / 2)
            pos = it['obj'].GetPosition()
            c = (tomm(pos.x), tomm(pos.y))
        elif it['kind'] == 'via':
            d = max(0.0, math.hypot(x - it['c'][0], y - it['c'][1]) - it['r'])
            c = it['c']
        else:
            (ax, ay), (ex, ey) = it['a'], it['e']
            vx, vy = ex - ax, ey - ay
            L2 = vx * vx + vy * vy
            t = 0.0 if L2 == 0 else max(0.0, min(1.0, ((x - ax) * vx + (y - ay) * vy) / L2))
            c = (ax + t * vx, ay + t * vy)
            d = max(0.0, math.hypot(x - c[0], y - c[1]) - it['r'])
        if d < bd:
            best, bd = c, d
    return best if bd <= RES * 2 else None


TYPES = [pcbnew.PCB_TRACE_T, pcbnew.PCB_PAD_T, pcbnew.PCB_VIA_T, pcbnew.PCB_ARC_T]


def net_islands(board):
    """{netcode: (netname, [island, ...])} for nets whose pads sit on more than one copper island.
    An island is a list of board items (pads, tracks, vias) that connect, zones included."""
    board.BuildConnectivity()
    conn = board.GetConnectivity()
    pads_by_net = {}
    for fp in board.GetFootprints():
        for p in fp.Pads():
            if p.GetNetCode() > 0:
                pads_by_net.setdefault(p.GetNetCode(), []).append(p)
    out = {}
    for code, pads in pads_by_net.items():
        if len(pads) < 2:
            continue
        seen = {}
        islands = []
        for p in pads:
            u = p.m_Uuid.AsString()
            if u in seen:
                continue
            items = list(conn.GetConnectedItems(p)) + [p]
            idx = len(islands)
            islands.append(items)
            for it in items:
                seen[it.m_Uuid.AsString()] = idx
        if len(islands) > 1:
            out[code] = (pads[0].GetNetname(), islands)
    return out


def fix(board, ox, oy, w, h, width_of, clearance_of, log=print, max_rounds=3, first=()):
    r = Router(board, ox, oy, w, h)
    routed = failed = 0
    for rnd in range(max_rounds):
        todo = net_islands(board)
        log('  round %d: %d nets with open connections %s' % (rnd, len(todo),
                                                            [v[0] for v in todo.values()]))
        if not todo:
            break
        progress = False
        order = sorted(todo.items(), key=lambda kv: (kv[0] not in first, kv[0]))
        for code, (netname, islands) in order:
            islands.sort(key=len)
            src_items = item_dicts(r, islands[0])
            tgt_items = item_dicts(r, [it for isl in islands[1:] for it in isl])
            tg = r.target_maps(tgt_items)
            src = r.target_maps(src_items)
            plane_goal = r.plane_mask(netname) if netname in PLANE_LAYER else None
            path = None
            # full netclass width first; neck down (board minimum 0.15 mm) only to escape fine-pitch pins
            for w in sorted({width_of(netname), 0.2, 0.15}, reverse=True):
                if w > width_of(netname):
                    continue
                hw = w / 2
                blk, via_blk = r.obstacle_maps(code, hw, clearance_of(netname))
                starts = []
                for L in 'FB':
                    cells = np.argwhere(src[L] & ~blk[L])
                    if len(cells) == 0:
                        cells = np.argwhere(src[L])
                    for c in cells[:: max(1, len(cells) // 80)]:
                        starts.append((int(c[0]), int(c[1]), L))
                path = r.astar(starts, tg, blk, via_blk, plane_goal)
                if path is not None:
                    break
            if path is None:
                log('   FAILED %s' % netname)
                failed += 1
                continue
            i0, j0, L0, _ = path[0]
            i1, j1, L1, f1 = path[-1]
            sa = anchor_for(r, src_items, ox + i0 * RES, oy + j0 * RES, 'FB'[L0])
            ea = None if f1 == 'plane' else anchor_for(r, tgt_items, ox + i1 * RES, oy + j1 * RES, 'FB'[L1])
            r.commit(path, code, 2 * hw, start_anchor=sa, end_anchor=ea)
            board.BuildConnectivity()
            routed += 1
            progress = True
            log('   routed %s (%d cells)' % (netname, len(path)))
        if not progress:
            break
    return routed, failed


def remove_item(board, r, obj):
    u = obj.m_Uuid.AsString()
    r.items = [it for it in r.items if it['obj'].m_Uuid.AsString() != u]
    board.Remove(obj)
    GRAVEYARD.append(obj)


def cleanup_orphans(board, r, log=print):
    """Delete track/via clusters that touch no pad (dangling leftovers of a rip-up)."""
    board.BuildConnectivity()
    conn = board.GetConnectivity()
    removed = 0
    for t in list(board.GetTracks()):
        if t.IsLocked():
            continue
        items = list(conn.GetConnectedItems(t))
        if not any(i.GetClass() == 'PAD' or i.GetClass() == 'ZONE' for i in items):
            remove_item(board, r, t)
            removed += 1
    if removed:
        log('   removed %d orphan track/via pieces' % removed)


def rip_near(board, r, code, radius=1.6, log=print):
    """Remove other-net unlocked track segments passing within `radius` of `code`'s pads that
    are stranded (the failed island).  Returns the set of affected net codes."""
    board.BuildConnectivity()
    todo = net_islands(board)
    if code not in todo:
        return set()
    netname, islands = todo[code]
    islands.sort(key=len)
    pads = [it for it in islands[0] if it.GetClass() == 'PAD']
    hit = set()
    for p in pads:
        pos = p.GetPosition()
        px, py = tomm(pos.x), tomm(pos.y)
        for t in list(board.GetTracks()):
            if t.GetNetCode() == code or t.IsLocked():
                continue
            if t.GetClass() == 'PCB_VIA':
                q = t.GetPosition()
                d = math.hypot(tomm(q.x) - px, tomm(q.y) - py)
            else:
                a, e = t.GetStart(), t.GetEnd()
                from pcbgeom import seg_point_dist
                d = seg_point_dist(tomm(a.x), tomm(a.y), tomm(e.x), tomm(e.y), px, py)
            if d < radius:
                hit.add(t.GetNetCode())
                remove_item(board, r, t)
    log('   ripped up segments of %d nets around %s' % (len(hit), netname))
    return hit


def rip_corridor(board, r, code, width_of, clearance_of, log=print):
    """For a net blocked somewhere along a long route: find its path with only pads as obstacles,
    then remove the other nets' tracks and vias that sit on that corridor.  Returns their net codes."""
    board.BuildConnectivity()
    todo = net_islands(board)
    if code not in todo:
        return set()
    netname, islands = todo[code]
    islands.sort(key=len)
    src_items = item_dicts(r, islands[0])
    tgt_items = item_dicts(r, [it for isl in islands[1:] for it in isl])
    hw, clr = min(width_of(netname), 0.2) / 2, clearance_of(netname)
    saved = r.items
    r.items = [it for it in saved if it['kind'] == 'pad' or it['net'] == code]
    blk, via_blk = r.obstacle_maps(code, hw, clr)
    r.items = saved
    tg, src = r.target_maps(tgt_items), r.target_maps(src_items)
    starts = []
    for L in 'FB':
        cells = np.argwhere(src[L] & ~blk[L])
        for c in cells[:: max(1, len(cells) // 80)]:
            starts.append((int(c[0]), int(c[1]), L))
    path = r.astar(starts, tg, blk, via_blk, None, via_cost=60)
    if path is None:
        log('   corridor: no pad-only path for %s' % netname)
        return set()
    pts = {0: [], 1: []}
    for i, j, L, flag in path:
        x, y = r.ox + i * RES, r.oy + j * RES
        pts[L].append((x, y))
        if flag == 'via':
            pts[1 - L].append((x, y))
    P = {L: np.array(v) if v else np.zeros((0, 2)) for L, v in pts.items()}
    hit = set()
    for t in list(board.GetTracks()):
        if t.GetNetCode() == code or t.IsLocked():
            continue
        if t.GetClass() == 'PCB_VIA':
            q = t.GetPosition()
            qx, qy = tomm(q.x), tomm(q.y)
            reach = tomm(t.GetWidth(pcbnew.F_Cu)) / 2 + hw + clr
            d = min((np.min(np.hypot(P[L][:, 0] - qx, P[L][:, 1] - qy)) for L in (0, 1) if len(P[L])), default=1e9)
        else:
            L = 0 if t.GetLayer() == pcbnew.F_Cu else 1 if t.GetLayer() == pcbnew.B_Cu else None
            if L is None or not len(P[L]):
                continue
            a, e = t.GetStart(), t.GetEnd()
            ax, ay, ex, ey = tomm(a.x), tomm(a.y), tomm(e.x), tomm(e.y)
            vx, vy = ex - ax, ey - ay
            L2 = vx * vx + vy * vy or 1e-12
            tt = np.clip(((P[L][:, 0] - ax) * vx + (P[L][:, 1] - ay) * vy) / L2, 0, 1)
            d = np.min(np.hypot(P[L][:, 0] - (ax + tt * vx), P[L][:, 1] - (ay + tt * vy)))
            reach = tomm(t.GetWidth()) / 2 + hw + clr
        if d < reach:
            hit.add(t.GetNetCode())
            remove_item(board, r, t)
    log('   corridor: ripped up segments of %d nets along the path of %s' % (len(hit), netname))
    return hit


def fix_with_ripup(board, ox, oy, w, h, width_of, clearance_of, log=print, attempts=4):
    routed, failed = fix(board, ox, oy, w, h, width_of, clearance_of, log=log)
    for k in range(attempts):
        todo = net_islands(board)
        if not todo:
            break
        r = Router(board, ox, oy, w, h)
        for code in list(todo):
            if k == 2:          # third try: clear the whole blocked corridor instead of just around the pads
                rip_corridor(board, r, code, width_of, clearance_of, log=log)
            else:
                rip_near(board, r, code, radius=1.2 + 0.6 * k, log=log)
        cleanup_orphans(board, r, log=log)
        # route the originally failed nets first, then everything that got cut
        routed2, failed = fix(board, ox, oy, w, h, width_of, clearance_of, log=log, max_rounds=4,
                              first=set(todo))
        routed += routed2
    return routed, failed


def remove_dangling(board, log=print):
    """Iteratively delete unlocked track segments with an unconnected end."""
    total = 0
    for _ in range(20):
        board.BuildConnectivity()
        conn = board.GetConnectivity()
        dead = [t for t in board.GetTracks()
                if t.GetClass() != 'PCB_VIA' and not t.IsLocked() and conn.TestTrackEndpointDangling(t, False)]
        if not dead:
            break
        for t in dead:
            board.Remove(t)
            GRAVEYARD.append(t)
        total += len(dead)
    if total:
        log('  removed %d dangling track stubs' % total)
    return total