AAGroups.jl

module Groups

using AbstractAlgebra
const Group = AbstractAlgebra.Group
const GroupElement = AbstractAlgebra.GroupElem

export hasgens, hasorder, rand_pseudo,
    direct_product, semidirect_product,
    one!, conj, conj!, comm, comm!, div_left!, div_right!

############### Parent calls and methods ###############
# the actual constructors of groups should be provided by specific implementations
# Group(gens::Vararg{T}; kwargs) where T<:GroupElement = ...
# Group(gens::AbstractVector{T}; kwargs) where T<:GroupElement = G(gens...; kwargs...)


# The methods each Group has to define:

(G::Group)() = ... # _uninitialized_ element
(G::Group)(g::GroupElement) = (parent(g) === G ? g : ... ) # coercion; no-copy if already in the group

AbstractAlgebra.elem_type(::Type{<:Group}) = ...
Base.hash(g::Group, h::UInt) = h # but its best to be defined

Base.one(G::Group) = ... # the identity element

hasorder(G::Group) = ... # Bool true when the order is known? is known to be finite?
AbstractAlgebra.order(::Type{T}, G::Group) where T <: Integer = ... # order of group G as computed using T (only gmp ints are guaranteed to produce the correct answer)

hasgens(G::Group) = ... # Bool?
AbstractAlgebra.gens(G::Group) = ... # the **tuple ? vector** of generators of G (as G was created)

Base.rand(G::Group) = ... # non-parametric rand
rand_pseudo(G::Group) = rand(G) # quick

function direct_product end # stub to be extended
function semidirect_product end # stub to be extended

# these methods we provide automatically:

AbstractAlgebra.order(G::Group) = order(BigInt, G)
AbstractAlgebra.gens(G::Group, i::Integer) = gens(G)[i]
AbstractAlgebra.ngens(G::Group) = hasgens(G) ? length(gens(G)) : -1 # ??

# iteration protocol (unfinished):
Base.iterate(G::Group) = one(G), state
Base.iterate(G::Group, state) = ...

Base.IteratorSize(::Type{<:Group}) = Base.SizeUnknown() # ??
Base.eltype(::Type{G}) where G<:Group = elem_type(G)

############### GroupElement methods ###############

AbstractAlgebra.parent(g::GroupElement) = ...
AbstractAlgebra.parent_type(::Type{<:GroupElement}) = ...

Base.hash(g::GroupElement, h::UInt) = h
Base.deepcopy_internal(g::GroupElement, stackdict::IdDict) = ...
# parent shall not be copied:
#
#   parent(g) === parent(deepcopy(g))
#
# however we require
#
#   hash(g) == hash(deepcopy(g))
#

# the cheap ? best effort equality, e.g. equality of words in FPGroup:
Base.:(==)(g::GroupElement, h::GroupElement) = ... # Base defaults to g === h

# the mathematical equality
Base.isequal(g::GroupElement, h::GroupElement) = ... # Base defaults to g == h

hasorder(g::GroupElement) = ... # see hasorder(G::Group) above
AbstractAlgebra.order(::Type{T}, g::GroupElement) = ... # see order(::Group) above

Base.:*(g::GroupElement, h::GroupElement) = (parent(g) === parent(h) ? .... : throw(DomainError((g,h), "Can not multiply elements from different groups")))
Base.inv(g::GroupElement) = ... # inversion




#### These methods we define automatically, but COULD be extended for specific types

Base.similar(g::GroupElement) = parent(g)() # this is the more idiomatic function in julia for the _uninitialized_ element;

Base.one(g::GroupElement) = one(parent(G))

Base.isone(g::GroupElement) = g == one(g) # note the cheap equality

AbstractAlgebra.order(g::GroupElement) = order(BigInt, g)

conj(g::GroupElement, h::GroupElement) = conj!(similar(g), g, h)
comm(g::GroupElement, h::GroupElement) = comm!(similar(g), g, h, similar(g))

# TODO: this could be probably more idiomatic
function Base.:^(g::GroupElement, n::Integer)
    n == 0 && return one(g)
    n < 0 && return inv(g)^-n
    return Base.power_by_squaring(g, n)
end

Base.literal_pow(typeof(^), g::GroupElem, ::Val{-1}) = inv(g)

# in-place operations:
one!(g::GroupElem) = one(parent(g)) # extension to user types RECOMMENDED

# aliasing of g with out is allowed
AbstractAlgebra.inv!(out::GroupElem, g::GroupElem) = inv(g) # extension to user types RECOMMENDED

# aliasing of g and h with out is allowed
AbstractAlgebra.mul!(out::GroupElem, g::GroupElem, h::GroupElem) = g*h  # extension to user types RECOMMENDED

# aliasing of g and h with out is allowed
function conj!(out::GroupElem, g::GroupElem, h::GroupElem) =
    out = (out === g || out === h ? inv(h), inv!(out, h))
    out = mul!(out, out, g)
    return mul!(out, out, h)
    # this seems to be optimal? extension to user types NOT RECOMMENDED
end

# aliasing of g and h with out is allowed;
# aliasing with tmp is NOT allowed → there is a 3 argument version (allocates 1 element)
# TODO: can we make comm! with 3 arguments without allocation??
function comm!(out::GroupElem, g::GroupElem, h::GroupElem, tmp::GroupElem=similar(out))
    tmp = conj!(tmp, g, h)
    out = inv!(out, g)
    return mul!(out, out, tmp)
    # this seems to be optimal? extension to user types NOT RECOMMENDED
end

# aliasing of g and h with out is allowed;
div_right!(out::GroupElem, g::GroupElem, h::GroupElem) = mul!(out, g, inv(h))
# extension to user types NOT RECOMMENDED

# aliasing of g and h with out is allowed;
function div_left!(out::GroupElem, g::GroupElem, h::GroupElem)
    out = (out === g || out === h ? inv(h), inv!(out, h))
    return mul!(out, out, g)
    # extension to user types NOT RECOMMENDED
end

using Test
function test_group_interface_conformance(g::GroupElement, h::GroupElement)
    @test parent(g) isa Group
    @test parent(h) isa Group
    G, H = parent(G), parent(H)
    G === H || throw("We need two elements of the same group to test conformance.")

    @testset "Parent methods" begin
        @test elem_type(G) == typeof(g)
        @test parent_type(typeof(g)) == typeof(G)
        @test G() isa GroupElement
        @test G() isa typeof(g)
        @test one(G) isa typeof(g)
        @test G(g) === g && G(h) === h
        @test one(G) == one(g) == one(h)

        @test hasorder(G) isa Bool
        @test hasgens(G) isa Bool
        @test ngens(G) isa Integer
        @test gens(G) isa Vector{typeof(g)}
        if hasorder(G)
            @test order(G) isa BigInt
            @test order(G) > 0
            @test order(Int, G) isa Int
        end
    end

    @testset "Equality, deepcopy && hash" begin
        @test (g == h) isa Bool
        @test isequal(g, h) isa Bool
        @test g == g
        @test isequal(h, h)
        @test deepcopy(g) isa GroupElement
        @test deepcopy(g) == g
        @test !(deepcopy(g) === g)
        k = deepcopy(g)
        @test parent(k) === parent(g)
        @test hash(g) isa UInt
        @test hash(g) == hash(k)
        @test similar(g) isa typeof(g)
    end

    @testset "Misc GroupElement methods" begin
        @test one(g) isa typeof(g)
        @test isone(g) isa Bool
        @test isone(one(g))

        @test hasorder(g) isa Bool

        if hasorder(g)
            @test order(g) isa BigInt
            @test order(Int, g) isa Int
        end

        @test similar(g) isa typeof(g)
    end

    @testset "Group operations" begin
        old_g, old_h = deepcopy(g), deepcopy(h)

        # check that the default operations don't mutate their arguments
        @test inv(g) isa typeof(g)
        @test g,h == old_g, old_h
        @test g*h isa typeof(g)
        @test g,h == old_g, old_h
        @test g^2 == g*g
        @test g,h == old_g, old_h
        @test g^-3 == inv(g)*inv(g)*inv(g)
        @test g,h == old_g, old_h
        @test (g*h)^-1 == inv(h)*inv(g)
        @test g,h == old_g, old_h
        @test conj(g, h) == inv(h)* g * h
        @test g,h == old_g, old_h
        @test comm(g, h) == g^-1*h^-1*g*h
        @test g,h == old_g, old_h
        @test isone(g*inv(g)) && isone(inv(g)*g)
    end

    @testset "In-place operations" begin
        old_g, old_h = deepcopy(g), deepcopy(h)
        out = similar(g)

        @test isone(one!(g))
        g = deepcopy(old_g)

        @test inv!(out, g) == inv(old_g)
        @test g == old_g
        @test inv!(g) == inv(old_g)
        g = deepcopy(old_g)

        @testset "mul!" begin
            @test mul!(out, g, h) == old_g * old_h
            @test g,h == old_g, old_h

            @test mul!(out, g, h) == old_g * old_h
            @test g,h == old_g, old_h

            @test mul!(g, g, h) == old_g * old_h
            @test h == old_h
            g = deepcopy(old_g)

            @test mul!(h, g, h) == old_g * old_h
            @test g == old_g
            h = deepcopy(old_h)

            @test mul!(g, g, g) == old_g * old_g
            g = deepcopy(old_g)
        end

        @testset "conj!" begin
            res = old_h^-1*old_g*old_h
            @test conj!(out, g, h) == res
            @test g,h == old_g, old_h

            @test conj!(g, g, h) == res
            @test h == old_h
            g = deepcopy(old_g)

            @test conj!(h, g, h) == res
            @test g == old_g
            h = deepcopy(old_h)

            @test conj!(g, g, g) == old_g
            g = deepcopy(old_g)
        end

        @testset "comm!" begin
            res = old_g^-1 * old_h^-1 * old_g * old_h

            @test comm!(out, g, h, similar(g)) == res
            @test g,h == old_g, old_h

            @test comm!(out, g, h) == res
            @test g,h == old_g, old_h

            @test comm!(g, g, h) == res
            @test h == old_h
            g = deepcopy(old_g)

            @test comm!(h, g, h) == res
            @test g == old_g
            h = deepcopy(old_h)
        end

        @testset "div_[left|right]!" begin
            res = g*h^-1
            @test div_right!(out, g, h) == res
            @test g,h == old_g, old_h

            @test div_right!(g, g, h) == res
            @test h == old_h
            g = deepcopy(old_g)

            @test div_right!(h, g, h) == res
            @test g == old_g
            h = deepcopy(old_h)

            @test div_right!(g, g, g) == one(g)
            g = deepcopy(old_g)


            res = h^-1*g
            @test div_left!(out, g, h) == res
            @test g,h == old_g, old_h

            @test div_left!(g, g, h) == res
            @test h == old_h
            g = deepcopy(old_g)

            @test div_left!(h, g, h) == res
            @test g == old_g
            h = deepcopy(old_h)

            @test div_left!(g, g, g) == one(g)
            g = deepcopy(old_g)
        end
    end
end

end #of module groups