def test_subgroup_presentations():
    F, x, y = free_group("x, y")
    f = FpGroup(F, [x**3, y**5, (x*y)**2])
    H = [x*y, x**-1*y**-1*x*y*x]
    p1 = reidemeister_presentation(f, H)
    assert str(p1) == "((y_1, y_2), (y_1**2, y_2**3, y_2*y_1*y_2*y_1*y_2*y_1))"

    H = f.subgroup(H)
    assert (H.generators, H.relators) == p1

    f = FpGroup(F, [x**3, y**3, (x*y)**3])
    H = [x*y, x*y**-1]
    p2 = reidemeister_presentation(f, H)
    assert str(p2) == "((x_0, y_0), (x_0**3, y_0**3, x_0*y_0*x_0*y_0*x_0*y_0))"

    f = FpGroup(F, [x**2*y**2, y**-1*x*y*x**-3])
    H = [x]
    p3 = reidemeister_presentation(f, H)
    assert str(p3) == "((x_0,), (x_0**4,))"

    f = FpGroup(F, [x**3*y**-3, (x*y)**3, (x*y**-1)**2])
    H = [x]
    p4 = reidemeister_presentation(f, H)
    assert str(p4) == "((x_0,), (x_0**6,))"

    # this presentation can be improved, the most simplified form
    # of presentation is <a, b | a^11, b^2, (a*b)^3, (a^4*b*a^-5*b)^2>
    # See [2] Pg 474 group PSL_2(11)
    # This is the group PSL_2(11)
    F, a, b, c = free_group("a, b, c")
    f = FpGroup(F, [a**11, b**5, c**4, (b*c**2)**2, (a*b*c)**3, (a**4*c**2)**3, b**2*c**-1*b**-1*c, a**4*b**-1*a**-1*b])
    H = [a, b, c**2]
    gens, rels = reidemeister_presentation(f, H)
    assert str(gens) == "(b_1, c_3)"
    assert len(rels) == 18

def test_order():
    from sympy import S
    F, x, y = free_group("x, y")
    f = FpGroup(F, [x**4, y**2, x*y*x**-1*y])
    assert f.order() == 8

    f = FpGroup(F, [x*y*x**-1*y**-1, y**2])
    assert f.order() == S.Infinity

    F, a, b, c = free_group("a, b, c")
    f = FpGroup(F, [a**250, b**2, c*b*c**-1*b, c**4, c**-1*a**-1*c*a, a**-1*b**-1*a*b])
    assert f.order() == 2000

def test_homomorphism():
    # FpGroup -> PermutationGroup
    F, a, b = free_group("a, b")
    G = FpGroup(F, [a**3, b**3, (a*b)**2])

    c = Permutation(3)(0, 1, 2)
    d = Permutation(3)(1, 2, 3)
    A = AlternatingGroup(4)
    T = homomorphism(G, A, [a, b], [c, d])
    assert T(a*b**2*a**-1) == c*d**2*c**-1
    assert T.is_isomorphism()
    assert T(T.invert(Permutation(3)(0, 2, 3))) == Permutation(3)(0, 2, 3)

    T = homomorphism(G, AlternatingGroup(4), G.generators)
    assert T.is_trivial()
    assert T.kernel().order() == G.order()

    E, e = free_group("e")
    G = FpGroup(E, [e**8])
    P = PermutationGroup([Permutation(0, 1, 2, 3), Permutation(0, 2)])
    T = homomorphism(G, P, [e], [Permutation(0, 1, 2, 3)])
    assert T.image().order() == 4
    assert T(T.invert(Permutation(0, 2)(1, 3))) == Permutation(0, 2)(1, 3)

    T = homomorphism(E, AlternatingGroup(4), E.generators, [c])
    assert T.invert(c**2) == e**-1 #order(c) == 3 so c**2 == c**-1

    # FreeGroup -> FreeGroup
    T = homomorphism(F, E, [a], [e])
    assert T(a**-2*b**4*a**2).is_identity

    # FreeGroup -> FpGroup
    G = FpGroup(F, [a*b*a**-1*b**-1])
    T = homomorphism(F, G, F.generators, G.generators)
    assert T.invert(a**-1*b**-1*a**2) == a*b**-1

    # PermutationGroup -> PermutationGroup
    D = DihedralGroup(8)
    p = Permutation(0, 1, 2, 3, 4, 5, 6, 7)
    P = PermutationGroup(p)
    T = homomorphism(P, D, [p], [p])
    assert T.is_injective()
    assert not T.is_isomorphism()
    assert T.invert(p**3) == p**3

    T2 = homomorphism(F, P, [F.generators[0]], P.generators)
    T = T.compose(T2)
    assert T.domain == F
    assert T.codomain == D
    assert T(a*b) == p

def test_permutation_methods():
    from sympy.combinatorics.fp_groups import FpSubgroup
    F, x, y = free_group("x, y")
    # DihedralGroup(8)
    G = FpGroup(F, [x**2, y**8, x*y*x**-1*y])
    T = G._to_perm_group()[1]
    assert T.is_isomorphism()
    assert G.center() == [y**4]

    # DiheadralGroup(4)
    G = FpGroup(F, [x**2, y**4, x*y*x**-1*y])
    S = FpSubgroup(G, G.normal_closure([x]))
    assert x in S
    assert y**-1*x*y in S

    # Z_5xZ_4
    G = FpGroup(F, [x*y*x**-1*y**-1, y**5, x**4])
    assert G.is_abelian
    assert G.is_solvable

    # AlternatingGroup(5)
    G = FpGroup(F, [x**3, y**2, (x*y)**5])
    assert not G.is_solvable

    # AlternatingGroup(4)
    G = FpGroup(F, [x**3, y**2, (x*y)**3])
    assert len(G.derived_series()) == 3
    S = FpSubgroup(G, G.derived_subgroup())
    assert S.order() == 4

 def __init__(self, fp_grp, subgroup, max_cosets=None):
     if not max_cosets:
         max_cosets = CosetTable.coset_table_max_limit
     self.fp_group = fp_grp
     self.subgroup = subgroup
     self.coset_table_max_limit = max_cosets
     # "p" is setup independent of Ω and n
     self.p = [0]
     # a list of the form `[gen_1, gen_1^{-1}, ... , gen_k, gen_k^{-1}]`
     self.A = list(chain.from_iterable((gen, gen**-1) \
             for gen in self.fp_group.generators))
     #P[alpha, x] Only defined when alpha^x is defined.
     self.P = [[None]*len(self.A)]
     # the mathematical coset table which is a list of lists
     self.table = [[None]*len(self.A)]
     self.A_dict = {x: self.A.index(x) for x in self.A}
     self.A_dict_inv = {}
     for x, index in self.A_dict.items():
         if index % 2 == 0:
             self.A_dict_inv[x] = self.A_dict[x] + 1
         else:
             self.A_dict_inv[x] = self.A_dict[x] - 1
     # used in the coset-table based method of coset enumeration. Each of
     # the element is called a "deduction" which is the form (α, x) whenever
     # a value is assigned to α^x during a definition or "deduction process"
     self.deduction_stack = []
     # Attributes for modified methods.
     H = self.subgroup
     self._grp = free_group(', ' .join(["a_%d" % i for i in range(len(H))]))[0]
     self.P = [[None]*len(self.A)]
     self.p_p = {}

def test_fp_subgroup():
    def _test_subgroup(K, T, S):
        _gens = T(K.generators)
        assert all(elem in S for elem in _gens)
        assert T.is_injective()
        assert T.image().order() == S.order()
    F, x, y = free_group("x, y")
    f = FpGroup(F, [x**4, y**2, x*y*x**-1*y])
    S = FpSubgroup(f, [x*y])
    assert (x*y)**-3 in S
    K, T = f.subgroup([x*y], homomorphism=True)
    assert T(K.generators) == [y*x**-1]
    _test_subgroup(K, T, S)

    S = FpSubgroup(f, [x**-1*y*x])
    assert x**-1*y**4*x in S
    assert x**-1*y**4*x**2 not in S
    K, T = f.subgroup([x**-1*y*x], homomorphism=True)
    assert T(K.generators[0]**3) == y**3
    _test_subgroup(K, T, S)

    f = FpGroup(F, [x**3, y**5, (x*y)**2])
    H = [x*y, x**-1*y**-1*x*y*x]
    K, T = f.subgroup(H, homomorphism=True)
    S = FpSubgroup(f, H)
    _test_subgroup(K, T, S)

def define_schreier_generators(C):
    y = []
    gamma = 1
    f = C.fp_group
    X = f.generators
    C.P = [[None]*len(C.A) for i in range(C.n)]
    for alpha, x in product(C.omega, C.A):
        beta = C.table[alpha][C.A_dict[x]]
        if beta == gamma:
            C.P[alpha][C.A_dict[x]] = "<identity>"
            C.P[beta][C.A_dict_inv[x]] = "<identity>"
            gamma += 1
        elif x in X and C.P[alpha][C.A_dict[x]] is None:
            y_alpha_x = '%s_%s' % (x, alpha)
            y.append(y_alpha_x)
            C.P[alpha][C.A_dict[x]] = y_alpha_x
    grp_gens = list(free_group(', '.join(y)))
    C._schreier_free_group = grp_gens.pop(0)
    C._schreier_generators = grp_gens
    # replace all elements of P by, free group elements
    for i, j in product(range(len(C.P)), range(len(C.A))):
        # if equals "<identity>", replace by identity element
        if C.P[i][j] == "<identity>":
            C.P[i][j] = C._schreier_free_group.identity
        elif isinstance(C.P[i][j], str):
            r = C._schreier_generators[y.index(C.P[i][j])]
            C.P[i][j] = r
            beta = C.table[i][j]
            C.P[beta][j + 1] = r**-1

def test_subgroup_presentations():
    F, x, y = free_group("x, y")
    f = FpGroup(F, [x**3, y**5, (x*y)**2])
    H = [x*y, x**-1*y**-1*x*y*x]
    p1 = reidemeister_presentation(f, H)
    assert str(p1) == "((y_1, y_2), (y_1**2, y_2**3, y_2*y_1*y_2*y_1*y_2*y_1))"

    f = FpGroup(F, [x**3, y**3, (x*y)**3])
    H = [x*y, x*y**-1]
    p2 = reidemeister_presentation(f, H)
    assert str(p2) == "((x_0, y_0), (x_0**3, y_0**3, x_0*y_0*x_0*y_0*x_0*y_0))"

    f = FpGroup(F, [x**2*y**2, y**-1*x*y*x**-3])
    H = [x]
    p3 = reidemeister_presentation(f, H)
    assert str(p3) == "((x_0,), (x_0**4,))"

    f = FpGroup(F, [x**3*y**-3, (x*y)**3, (x*y**-1)**2])
    H = [x]
    p4 = reidemeister_presentation(f, H)
    assert str(p4) == "((x_0,), (x_0**6,))"

    # this presentation can be improved, the most simplified form
    # of presentation is <a, b | a^11, b^2, (a*b)^3, (a^4*b*a^-5*b)^2>
    # See [2] Pg 474 group PSL_2(11)
    # This is the group PSL_2(11)
    F, a, b, c = free_group("a, b, c")
    f = FpGroup(F, [a**11, b**5, c**4, (b*c**2)**2, (a*b*c)**3, (a**4*c**2)**3, b**2*c**-1*b**-1*c, a**4*b**-1*a**-1*b])
    H = [a, b, c**2]
    k = ("((a_0, b_1, c_3), "
        "(c_3**3, b_1**5, a_0**4*b_1**-2*a_0**-1*b_1**2, "
        "c_3*b_1**-2*c_3*b_1**-2*c_3*b_1**-2, b_1**-1*a_0*b_1**2*c_3**-1*b_1**-1*a_0*b_1**2*c_3**-1, "
        "a_0**11, a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1*b_1**2*a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1*b_1**2*c_3, "
        "a_0*b_1**-2*a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1*a_0*b_1**-2*a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1, "
        "a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1*a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1*a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1, "
        "a_0*b_1**-2*a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1*b_1*a_0*b_1**-2*a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1*b_1, "
        "b_1**-2*c_3*b_1*a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1*a_0*b_1**2*c_3**-1*b_1**-2*a_0*b_1**2*c_3**-1*b_1**-2, "
        "b_1*a_0*b_1**-2*a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1*b_1**2*a_0*b_1**-2*a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1*b_1, "
        "b_1**2*c_3*b_1**-2*c_3**-1*b_1*a_0*b_1**-2*a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1*b_1*a_0*b_1**2*c_3**-1*b_1*c_3, "
        "b_1**2*a_0*b_1**-2*a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1*b_1**-2*a_0*b_1**-2*a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1*b_1, "
        "c_3*b_1*a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1*b_1*c_3*b_1*a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1*b_1*c_3*b_1*a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1*b_1, "
        "c_3**-1*b_1*a_0*b_1**-2*a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1*b_1*a_0*b_1**2*c_3**-1*b_1*a_0*b_1**-2*a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1*b_1*a_0*b_1**2, "
        "b_1**2*a_0*b_1**2*c_3**-1*b_1**-1*a_0*b_1**-2*a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1*b_1*a_0*b_1**2*c_3**-1*b_1**2*c_3*b_1*a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1, "
        "c_3**-1*b_1*a_0*b_1**-2*a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1*b_1*a_0*c_3**-1*b_1*a_0*b_1**-2*a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1*b_1*a_0*c_3**-1*b_1*a_0*b_1**-2*a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1*b_1*a_0, "
        "a_0**5*b_1**-2*a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1*b_1*a_0**5*b_1**-2*a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1*b_1*a_0**5*b_1**-2*a_0*b_1**2*c_3**-1*b_1**-2*c_3**-1*b_1))"
        )
    assert str(reidemeister_presentation(f, H)) == k

def test_cyclic():
    F, x, y = free_group("x, y")
    f = FpGroup(F, [x*y, x**-1*y**-1*x*y*x])
    assert f.is_cyclic
    f = FpGroup(F, [x*y, x*y**-1])
    assert f.is_cyclic
    f = FpGroup(F, [x**4, y**2, x*y*x**-1*y])
    assert not f.is_cyclic

def test_order():
    F, x, y = free_group("x, y")
    f = FpGroup(F, [x**4, y**2, x*y*x**-1*y])
    assert f.order() == 8

    f = FpGroup(F, [x*y*x**-1*y**-1, y**2])
    assert f.order() == S.Infinity

    F, a, b, c = free_group("a, b, c")
    f = FpGroup(F, [a**250, b**2, c*b*c**-1*b, c**4, c**-1*a**-1*c*a, a**-1*b**-1*a*b])
    assert f.order() == 2000

    F, x = free_group("x")
    f = FpGroup(F, [])
    assert f.order() == S.Infinity

    f = FpGroup(free_group('')[0], [])
    assert f.order() == 1

def simplify_presentation(*args, **kwargs):
    '''
    For an instance of `FpGroup`, return a simplified isomorphic copy of
    the group (e.g. remove redundant generators or relators). Alternatively,
    a list of generators and relators can be passed in which case the
    simplified lists will be returned.

    By default, the generators of the group are unchanged. If you would
    like to remove redundant generators, set the keyword argument
    `change_gens = True`.

    '''
    change_gens = kwargs.get("change_gens", False)

    if len(args) == 1:
        if not isinstance(args[0], FpGroup):
            raise TypeError("The argument must be an instance of FpGroup")
        G = args[0]
        gens, rels = simplify_presentation(G.generators, G.relators,
                                              change_gens=change_gens)
        if gens:
            return FpGroup(gens[0].group, rels)
        return FpGroup(FreeGroup([]), [])
    elif len(args) == 2:
        gens, rels = args[0][:], args[1][:]
        if not gens:
            return gens, rels
        identity = gens[0].group.identity
    else:
        if len(args) == 0:
            m = "Not enough arguments"
        else:
            m = "Too many arguments"
        raise RuntimeError(m)

    prev_gens = []
    prev_rels = []
    while not set(prev_rels) == set(rels):
        prev_rels = rels
        while change_gens and not set(prev_gens) == set(gens):
            prev_gens = gens
            gens, rels = elimination_technique_1(gens, rels, identity)
        rels = _simplify_relators(rels, identity)

    if change_gens:
        syms = [g.array_form[0][0] for g in gens]
        F = free_group(syms)[0]
        identity = F.identity
        gens = F.generators
        subs = dict(zip(syms, gens))
        for j, r in enumerate(rels):
            a = r.array_form
            rel = identity
            for sym, p in a:
                rel = rel*subs[sym]**p
            rels[j] = rel
    return gens, rels

def test_fp_subgroup():
    F, x, y = free_group("x, y")
    f = FpGroup(F, [x**4, y**2, x*y*x**-1*y])
    S = FpSubgroup(f, [x*y])
    assert (x*y)**-3 in S

    S = FpSubgroup(F, [x**-1*y*x])
    assert x**-1*y**4*x in S
    assert x**-1*y**4*x**2 not in S

def test_isomorphisms():

    F, a, b = free_group("a, b")
    E, c, d = free_group("c, d")
    # Infinite groups with differently ordered relators.
    G = FpGroup(F, [a**2, b**3])
    H = FpGroup(F, [b**3, a**2])
    assert is_isomorphic(G, H)

    # Trivial Case
    # FpGroup -> FpGroup
    H = FpGroup(F, [a**3, b**3, (a*b)**2])
    F, c, d = free_group("c, d")
    G = FpGroup(F, [c**3, d**3, (c*d)**2])
    check, T =  group_isomorphism(G, H)
    assert check
    T(c**3*d**2) == a**3*b**2

    # FpGroup -> PermutationGroup
    # FpGroup is converted to the equivalent isomorphic group.
    F, a, b = free_group("a, b")
    G = FpGroup(F, [a**3, b**3, (a*b)**2])
    H = AlternatingGroup(4)
    check, T = group_isomorphism(G, H)
    assert check
    assert T(b*a*b**-1*a**-1*b**-1) == Permutation(0, 2, 3)
    assert T(b*a*b*a**-1*b**-1) == Permutation(0, 3, 2)

    # PermutationGroup -> PermutationGroup
    D = DihedralGroup(8)
    p = Permutation(0, 1, 2, 3, 4, 5, 6, 7)
    P = PermutationGroup(p)
    assert not is_isomorphic(D, P)

    A = CyclicGroup(5)
    B = CyclicGroup(7)
    assert not is_isomorphic(A, B)

    # Two groups of the same prime order are isomorphic to each other.
    G = FpGroup(F, [a, b**5])
    H = CyclicGroup(5)
    assert G.order() == H.order()
    assert is_isomorphic(G, H)

def test_free_group():
    G, a, b, c = free_group("a, b, c")
    assert F.generators == (x, y, z)
    assert x*z**2 in F
    assert x in F
    assert y*z**-1 in F
    assert (y*z)**0 in F
    assert a not in F
    assert a**0 not in F
    assert len(F) == 3
    assert str(F) == '<free group on the generators (x, y, z)>'
    assert not F == G
    assert F.order() == oo
    assert F.is_abelian == False
    assert F.center() == set([F.identity])

    (e,) = free_group("")
    assert e.order() == 1
    assert e.generators == ()
    assert e.elements == set([e.identity])
    assert e.is_abelian == True

def define_schreier_generators(C, homomorphism=False):
    '''
    Parameters
    ==========

    C -- Coset table.
    homomorphism -- When set to True, return a dictionary containing the images
                     of the presentation generators in the original group.
    '''
    y = []
    gamma = 1
    f = C.fp_group
    X = f.generators
    if homomorphism:
        # `_gens` stores the elements of the parent group to
        # to which the schreier generators correspond to.
        _gens = {}
        # compute the schreier Traversal
        tau = {}
        tau[0] = f.identity
    C.P = [[None]*len(C.A) for i in range(C.n)]
    for alpha, x in product(C.omega, C.A):
        beta = C.table[alpha][C.A_dict[x]]
        if beta == gamma:
            C.P[alpha][C.A_dict[x]] = "<identity>"
            C.P[beta][C.A_dict_inv[x]] = "<identity>"
            gamma += 1
            if homomorphism:
                tau[beta] = tau[alpha]*x
        elif x in X and C.P[alpha][C.A_dict[x]] is None:
            y_alpha_x = '%s_%s' % (x, alpha)
            y.append(y_alpha_x)
            C.P[alpha][C.A_dict[x]] = y_alpha_x
            if homomorphism:
                _gens[y_alpha_x] = tau[alpha]*x*tau[beta]**-1
    grp_gens = list(free_group(', '.join(y)))
    C._schreier_free_group = grp_gens.pop(0)
    C._schreier_generators = grp_gens
    if homomorphism:
        C._schreier_gen_elem = _gens
    # replace all elements of P by, free group elements
    for i, j in product(range(len(C.P)), range(len(C.A))):
        # if equals "<identity>", replace by identity element
        if C.P[i][j] == "<identity>":
            C.P[i][j] = C._schreier_free_group.identity
        elif isinstance(C.P[i][j], string_types):
            r = C._schreier_generators[y.index(C.P[i][j])]
            C.P[i][j] = r
            beta = C.table[i][j]
            C.P[beta][j + 1] = r**-1

    def subgroup(self, gens, C=None):
        '''
        Return the subgroup generated by `gens` using the
        Reidemeister-Schreier algorithm

        '''
        if not all([isinstance(g, FreeGroupElement) for g in gens]):
            raise ValueError("Generators must be `FreeGroupElement`s")
        if not all([g.group == self.free_group for g in gens]):
                raise ValueError("Given generators are not members of the group")
        g, rels = reidemeister_presentation(self, gens, C=C)
        if g:
            g = FpGroup(g[0].group, rels)
        else:
            g = FpGroup(free_group('')[0], [])
        return g

def test_rewriting():
    F, a, b = free_group("a, b")
    G = FpGroup(F, [a*b*a**-1*b**-1])
    a, b = G.generators
    R = G._rewriting_system
    assert R.is_confluent == False
    R.make_confluent()
    assert R.is_confluent == True

    assert G.reduce(b**3*a**4*b**-2*a) == a**5*b
    assert G.equals(b**2*a**-1*b, b**4*a**-1*b**-1)

    G = FpGroup(F, [a**3, b**3, (a*b)**2])
    R = G._rewriting_system
    R.make_confluent()
    assert R.is_confluent
    assert G.reduce(b*a**-1*b**-1*a**3*b**4*a**-1*b**-15) == a**-1*b**-1

def test_look_ahead():
    # Section 3.2 [Test Example] Example (d) from [2]
    F, a, b, c = free_group("a, b, c")
    f = FpGroup(F, [a**11, b**5, c**4, (a*c)**3, b**2*c**-1*b**-1*c, a**4*b**-1*a**-1*b])
    H = [c, b, c**2]
    table0 = [[1, 2, 0, 0, 0, 0],
              [3, 0, 4, 5, 6, 7],
              [0, 8, 9, 10, 11, 12],
              [5, 1, 10, 13, 14, 15],
              [16, 5, 16, 1, 17, 18],
              [4, 3, 1, 8, 19, 20],
              [12, 21, 22, 23, 24, 1],
              [25, 26, 27, 28, 1, 24],
              [2, 10, 5, 16, 22, 28],
              [10, 13, 13, 2, 29, 30]]
    CosetTable.max_stack_size = 10
    C_c = coset_enumeration_c(f, H)
    C_c.compress(); C_c.standardize()
    assert C_c.table[: 10] == table0

def test_rewriting():
    F, a, b = free_group("a, b")
    G = FpGroup(F, [a*b*a**-1*b**-1])
    a, b = G.generators
    R = G._rewriting_system
    assert R.is_confluent

    assert G.reduce(b**-1*a) == a*b**-1
    assert G.reduce(b**3*a**4*b**-2*a) == a**5*b
    assert G.equals(b**2*a**-1*b, b**4*a**-1*b**-1)

    G = FpGroup(F, [a**3, b**3, (a*b)**2])
    R = G._rewriting_system
    R.make_confluent()
    # R._is_confluent should be set to True after
    # a successful run of make_confluent
    assert R.is_confluent
    # but also the system should actually be confluent
    assert R._check_confluence()
    assert G.reduce(b*a**-1*b**-1*a**3*b**4*a**-1*b**-15) == a**-1*b**-1

def test_rewriting():
    F, a, b = free_group("a, b")
    G = FpGroup(F, [a*b*a**-1*b**-1])
    a, b = G.generators
    R = G._rewriting_system
    assert R.is_confluent

    assert G.reduce(b**-1*a) == a*b**-1
    assert G.reduce(b**3*a**4*b**-2*a) == a**5*b
    assert G.equals(b**2*a**-1*b, b**4*a**-1*b**-1)

    assert R.reduce_using_automaton(b*a*a**2*b**-1) == a**3
    assert R.reduce_using_automaton(b**3*a**4*b**-2*a) == a**5*b
    assert R.reduce_using_automaton(b**-1*a) == a*b**-1

    G = FpGroup(F, [a**3, b**3, (a*b)**2])
    R = G._rewriting_system
    R.make_confluent()
    # R._is_confluent should be set to True after
    # a successful run of make_confluent
    assert R.is_confluent
    # but also the system should actually be confluent
    assert R._check_confluence()
    assert G.reduce(b*a**-1*b**-1*a**3*b**4*a**-1*b**-15) == a**-1*b**-1
    # check for automaton reduction
    assert R.reduce_using_automaton(b*a**-1*b**-1*a**3*b**4*a**-1*b**-15) == a**-1*b**-1

    G = FpGroup(F, [a**2, b**3, (a*b)**4])
    R = G._rewriting_system
    assert G.reduce(a**2*b**-2*a**2*b) == b**-1
    assert R.reduce_using_automaton(a**2*b**-2*a**2*b) == b**-1
    assert G.reduce(a**3*b**-2*a**2*b) == a**-1*b**-1
    assert R.reduce_using_automaton(a**3*b**-2*a**2*b) == a**-1*b**-1
    # Check after adding a rule
    R.add_rule(a**2, b)
    assert R.reduce_using_automaton(a**2*b**-2*a**2*b) == b**-1
    assert R.reduce_using_automaton(a**4*b**-2*a**2*b**3) == b