###############################################################################
# Section 1
#
# Orientation-preserving symmetries of the universal regular tessellation
# of type {p,q,r} and cusp modulus z = a + b u

# As finitely presented group

SymmetriesUniversalRegularTessellation := function(p, q, r, a, b)
    local F, P, Q, R, rels;

    F := FreeGroup(3);;
    P := F.1;; Q := F.2;; R := F.3;;

    rels := [ P^p, Q^q, R^r, (P*Q)^2, (Q*R)^2, (P*Q*R)^2,
              (Q*R^(r/2+1))^a * (R*Q*R^(r/2))^b];;

    return F/rels;
end;;

# As permutation group, this is much faster for subsequent computations

SymmetriesUniversalRegularTessellationPermGroup := function(p, q, r, a, b)
    local G;
    G := SymmetriesUniversalRegularTessellation(p, q, r, a, b);
    return Image(IsomorphismPermGroup(G));
end;;

###############################################################################
# Section 2
#
# Functions to find all regular tessellation of given cusp modulus when the
# universal regular tessellation is finite.

# Finds all elements in the symmetry group G of a universal regular
# tessellation U that are fixing an edge or a cusp.
#
# A quotient U/H by a subgroup H of G is again a manifold tessellation of the
# same cusp modulus if H intersects TorsionAndCuspFixingElements(G) trivially.

TorsionAndCuspFixingElements := function(G)
    local gens, C1, C2, C3, B, all, g, h;

    gens := GeneratorsOfGroup(G);;

    C1 := Group(gens[1]);;
    C2 := Group(gens[1] * gens[2]);;
    C3 := Group(gens[1] * gens[2] * gens[3]);;
    B  := Group([gens[2], gens[3]]);;
    
    # Take union and all conjugates
    all := Set([]);
    for g in Union(C1, C2, C3, B) do
        for h in G do
            AddSet(all, h * g * h^-1);;
        od;
    od;
    
    return all;
end;;

# Predicate of two groups intersecting in the trivial group

HasTrivialIntersection := function(G, H)
    return Size(Intersection(G, H)) = 1;
end;;

# Given the symmetry group G of a universal regular tessellation U
# return all normal subgroups N of G such that the quotient U/N is a manifold
# regular tessellation.
# Note that G has to be finite. gap's algorithm to find normal subgroups
# does not return them in a particular order (even might change from run to
# run). We sort by size of the subgroup, but two subgroups of the same
# order might still be flipped.

AllRegularTessellationsFromUniversalRegularTessellation := function(G)
    local torsionAndCuspFixingElements, normalSubgroups;
    torsionAndCuspFixingElements := TorsionAndCuspFixingElements(G);

    normalSubgroups := Filtered(NormalSubgroups(G),
                 H -> HasTrivialIntersection(H, torsionAndCuspFixingElements));
    Sort(normalSubgroups, function (a,b) return Size(a) < Size(b); end);
    return normalSubgroups;
end;;

###############################################################################
# Section 3
#
# Method to detect chiral regular tessellations covered by amphicheiral
# universal regular tessellations

# If G is the symmetry group of a amphicheiral universal regular tessellation,
# this returns a group automorphism G->G corresponding to conjugating each
# element in G by a mirror symmetry.

MirrorIsomorphismUniversalRegularTessellation := function(G)
    local gens, P, Q, R, imgs;
    gens := GeneratorsOfGroup(G);;
    P := gens[1];;
    Q := gens[2];;
    R := gens[3];;
    imgs := [ Q^-1 * P^-1 * Q, Q^-1, R^-1 ];;
    return GroupHomomorphismByImages(G, G, gens, imgs);
end;;

# If G is as above and H is a normal subgroup of G, then this method returns
# true if the quotient U/H is an amphicheiral regular tessellation.

IsAmphicheiralRegularTessellation := function(H, G)
    local mu;
    mu := MirrorIsomorphismUniversalRegularTessellation(G);
    return Image(mu, H) = H; 
end;;

###############################################################################
# Section 4
#
# Methods to export subgroups to python

# Given an element g in a group G with three generators, give it as word in
# the generators when naming the generators P, Q, and R.
ElementAsWord := function(g, G)
    local epi;
    epi := EpimorphismFromFreeGroup(G:names:=["P","Q","R"]);

    return PreImagesRepresentative(epi, g);
end;;

# As above but encode the word as list, e.g., [1, -2, 3], where 1 stands for
# the first generator, -2 for the inverse of the second generator, etc.
ElementAsWordNumberList := function(g, G)
    return LetterRepAssocWord(
        ElementAsWord(g, G));
end;;

# Given a list of generators l for a subgroup of G, return each generator
# as list as described above.
ElementsAsWordNumberList := function(l, G)
    return List(l, g->ElementAsWordNumberList(g, G));
end;;