"""Planar maps with boundary for diagrams built from a rotation invariant
trivalent vertex 'T' and a rotation invariant 4-valent vertex 'X' (the crossing).

A map has
  nodes : {vid: (type, [darts in counterclockwise order])}
  bdry  : [darts], boundary positions 0..k-1 in counterclockwise order around
          the disk (for Hom(m,n): b0..b_{m-1}, t_{n-1}..t_0)
  alpha : involution on darts (edges)
  loops : number of vertex-free closed loops
"""
import itertools


class ClosedComponent(Exception):
    pass


class PMap:
    __slots__ = ("nodes", "bdry", "alpha", "loops", "_vof")

    def __init__(self, nodes, bdry, alpha, loops=0):
        self.nodes, self.bdry, self.alpha, self.loops = nodes, bdry, alpha, loops
        self._vof = None

    @property
    def k(self):
        return len(self.bdry)

    def vof(self):
        if self._vof is None:
            v = {}
            for vid, (_, ds) in self.nodes.items():
                for i, d in enumerate(ds):
                    v[d] = (vid, i)
            for j, d in enumerate(self.bdry):
                v[d] = ("B", j)
            self._vof = v
        return self._vof

    def sigma(self, d):
        vid, i = self.vof()[d]
        if vid == "B":
            return self.bdry[(i - 1) % len(self.bdry)]
        ds = self.nodes[vid][1]
        return ds[(i + 1) % len(ds)]

    def sigma_inv(self, d):
        vid, i = self.vof()[d]
        if vid == "B":
            return self.bdry[(i + 1) % len(self.bdry)]
        ds = self.nodes[vid][1]
        return ds[(i - 1) % len(ds)]

    def vtype(self, d):
        vid, _ = self.vof()[d]
        return "B" if vid == "B" else self.nodes[vid][0]

    def nverts(self):
        return len(self.nodes)

    # ------------------------------------------------------------------
    def rotated(self, r):
        """boundary position j of the new map = position j - r of the old,
        i.e. old position i becomes new position i + r."""
        k = self.k
        nb = [self.bdry[(j - r) % k] for j in range(k)]
        return PMap(self.nodes, nb, self.alpha, self.loops)

    def code(self):
        """canonical code rooted at boundary position 0 (k>=1)."""
        assert self.k >= 1
        root = self.bdry[0]
        lab = {root: 0}
        order = [root]
        i = 0
        while i < len(order):
            d = order[i]
            i += 1
            for e in (self.sigma(d), self.alpha[d]):
                if e not in lab:
                    lab[e] = len(order)
                    order.append(e)
        if len(order) != len(self.alpha):
            raise ClosedComponent()
        return (self.k, self.loops, tuple((self.vtype(d), lab[self.sigma(d)], lab[self.alpha[d]]) for d in order))

    def canon(self):
        """return (rcode, r) with rcode = code(self.rotated(r)) minimal; also the
        stabiliser list."""
        k = self.k
        best, br, stab = None, None, []
        for r in range(k):
            c = self.rotated(r).code()
            if best is None or c < best:
                best, br, stab = c, r, [r]
            elif c == best:
                stab.append(r)
        return best, br, stab

    def renumbered(self, off):
        """copy with all darts shifted by off"""
        nodes = {("%d" % off, vid) if not isinstance(vid, tuple) else (str(off),) + vid: (tp, [d + off for d in ds])
                 for vid, (tp, ds) in self.nodes.items()}
        return PMap(nodes, [d + off for d in self.bdry], {d + off: e + off for d, e in self.alpha.items()}, self.loops)

    def maxdart(self):
        return max(self.alpha) if self.alpha else -1


# ----------------------------------------------------------------------
# building maps from words
GEN = {  # name: (n_in, n_out, vertex type or None, ccw order as list of ('in',i)/('out',j))
    "T": (2, 1, "T", [("in", 0), ("in", 1), ("out", 0)]),
    "Ts": (1, 2, "T", [("in", 0), ("out", 1), ("out", 0)]),
    "X": (2, 2, "X", [("in", 0), ("in", 1), ("out", 1), ("out", 0)]),
    "cup": (0, 2, None, None),
    "cap": (2, 0, None, None),
}


def from_word(m, layers):
    """layers: list of (gen, pos) applied bottom to top.  Returns (PMap, n)."""
    cnt = itertools.count()
    alpha = {}
    nodes = {}
    wire = {}  # 2-valent smoothing nodes: dart -> other dart
    bottom = [next(cnt) for _ in range(m)]
    cur = list(bottom)  # darts waiting for a partner (pointing up)
    vidc = itertools.count()
    for gen, pos in layers:
        nin, nout, tp, order = GEN[gen]
        ins = cur[pos:pos + nin]
        assert len(ins) == nin, (gen, pos, len(cur))
        if tp is None:
            if gen == "cup":
                a, b = next(cnt), next(cnt)
                wire[a] = b
                wire[b] = a
                outs_wait = [a, b]
                cur = cur[:pos] + outs_wait + cur[pos:]
            else:  # cap
                a, b = next(cnt), next(cnt)
                wire[a] = b
                wire[b] = a
                alpha[ins[0]] = a
                alpha[a] = ins[0]
                alpha[ins[1]] = b
                alpha[b] = ins[1]
                cur = cur[:pos] + cur[pos + 2:]
            continue
        indarts = [next(cnt) for _ in range(nin)]
        outdarts = [next(cnt) for _ in range(nout)]
        for x, y in zip(ins, indarts):
            alpha[x] = y
            alpha[y] = x
        ds = [indarts[i] if s == "in" else outdarts[i] for s, i in order]
        nodes[next(vidc)] = (tp, ds)
        cur = cur[:pos] + outdarts + cur[pos + nin:]
    n = len(cur)
    top = [next(cnt) for _ in range(n)]
    for x, y in zip(cur, top):
        alpha[x] = y
        alpha[y] = x
    bdry = bottom + list(reversed(top))
    return smooth(nodes, bdry, alpha, wire), n


def smooth(nodes, bdry, alpha, wire):
    """remove 2-valent wire nodes; count free loops"""
    real = [d for d in alpha if d not in wire] + [d for d in bdry if d not in alpha]
    na = {}
    used = set()
    for d in alpha:
        if d in wire or d in na:
            continue
        x = alpha[d]
        while x in wire:
            used.add(x)
            y = wire[x]
            used.add(y)
            x = alpha[y]
        na[d] = x
        na[x] = d
    loops = 0
    for w in wire:
        if w in used:
            continue
        loops += 1
        x = w
        while True:
            used.add(x)
            y = wire[x]
            used.add(y)
            x = alpha[y]
            if x == w:
                break
    return PMap(nodes, bdry, na, loops)


# ----------------------------------------------------------------------
def faces(M):
    """list of faces, each a list of darts d (face traversal d -> sigma_inv(alpha(d)))"""
    seen = set()
    out = []
    for d in M.alpha:
        if d in seen:
            continue
        f = []
        x = d
        while x not in seen:
            seen.add(x)
            f.append(x)
            x = M.sigma_inv(M.alpha[x])
        out.append(f)
    return out


def euler_check(M):
    V = len(M.nodes) + (1 if M.k else 0)
    E = len(M.alpha) // 2
    F = len(faces(M))
    return V - E + F