"""Generic checker for sequences of exchanges of root subgroups (Lemma 20.9).
A state is a set S of roots (vectors) and a set chi of roots on which the character is nontrivial.
exchange(x,y): replaces x by y after checking the hypotheses of the exchange lemma on the level of roots."""
def add(a,b): return tuple(p+q for p,q in zip(a,b))
class State:
    def __init__(self,S,chi,is_root,name=''):
        self.S=set(S); self.chi=set(chi); self.is_root=is_root; self.log=[]; self.name=name
        self.check_group(self.S,'initial')
    def check_group(self,S,what):
        for a in S:
            for b in S:
                if a<b:
                    c=add(a,b)
                    if self.is_root(c):
                        if c not in S: self.log.append(f'{what}: not closed: {a}+{b}')
                        if c in self.chi: self.log.append(f'{what}: character nontrivial on commutator {a}+{b}')
    def exchange(self,x,y,step=''):
        if x not in self.S: self.log.append(f'{step}: x absent'); return
        if y in self.S: self.log.append(f'{step}: y already present')
        if x in self.chi or y in self.chi: self.log.append(f'{step}: character nontrivial on X or Y')
        U=self.S-{x}
        self.check_group(U,f'{step} common subgroup')
        z=add(x,y)
        if not (self.is_root(z) and z in U and z in self.chi): self.log.append(f'{step}: pairing [X,Y] not a character root')
        for name,v in (('X',x),('Y',y)):
            for u in U:
                c=add(u,v)
                if self.is_root(c):
                    if c not in U: self.log.append(f'{step}: {name} does not normalize: {u}+{v}')
                    elif c in self.chi: self.log.append(f'{step}: {name} changes the character via {u}')
        self.S=U|{y}
    def remove(self,x,step=''):
        if x in self.chi: self.log.append(f'{step}: removing a character root')
        U=self.S-{x}
        self.check_group(U,f'{step} after removal')
        # x must normalize U and preserve the character
        for u in U:
            c=add(u,x)
            if self.is_root(c):
                if c not in U: self.log.append(f'{step}: removed root does not normalize: {u}')
                elif c in self.chi: self.log.append(f'{step}: removed root changes the character via {u}')
        self.S=U