The AbstractPermutation
interface
The AbstractPermutation
interface consists of just three mandatory functions. Note that none of them is exported, hence it is safe to import
/using
the package without introducing any naming conflicts with other packages.
Mandatory methods
The three mandatory methods are:
- a constructor,
AbstractPermutations.degree
andBase.^
.
The meaning of degree
doesn't have a well established tradition in mathematics. This is still ok, as long as we define its meaning with care for precision and use it in a consistent and predictable way.
AbstractPermutations.AbstractPermutation
— TypeAbstractPermutation
Abstract type representing bijections of positive integers ℕ = {1,2,…}
finitely supported. That is, we treat permutations as functions ℕ → ℕ
such that for every permutation σ
there are only finitely many k
different from their image under σ
.
Mandatory interface
Subtypes APerm <: AbstractPermutation
must implement the following functions:
APerm(images::AbstractVector{<:Integer}[; check::Bool=true])
- a constructor of aAPerm
from a vector of images. Optionally the keyword argumentcheck
may be set tofalse
when the caller knows thatimages
constitute a honest permutation.Base.:^(i::Integer, σ::APerm)
the customary notation for the image ofi
underσ
.degree(σ::APerm)
the minimald ≥ 0
such thatσ
fixes allk ≥ d
.
There is no formal requirement that the APerm(images)
constructor actually returns a APerm
. Any AbstractPermutation
object would do. This may be useful if constructing permutation from images is not technically feasible.
Even though AbstractPermutation <: GroupsCore.GroupElement
they don't necessarily implement the whole of GroupElement
interface, e.g. it is possible to implement parent
-less permutations.
Optional interface
perm(σ::APerm)
by default returnsσ
- the "simplest" (implementation-wise) permutation underlyingσ
.inttype(::Type{<:APerm})
by default returnsUInt32
.__unsafe_image(i::Integer, σ::APerm)
defaults toi^σ
.
AbstractPermutations.degree
— Functiondegree(σ::AbstractPermutation)
Return a minimal number n ≥ 0
such that k^σ == k
for all k > n
.
Such number n
can be understood as a degree of a permutation, since we can regard σ
as an element of Sym(n)
(and not of Sym(n-1)
).
Base.:^
— Method^(i::Integer, σ::AbstractPermutation)
Return the image of i
under σ
preserving the type of i
.
We consider σ
as a permutation of ℕ
(the positive integers), with finite support, so k^σ = k
for all k > degree(σ)
.
Suplementary methods
Moreover there are three internal, suplementary functions that may be overloaded by the implementer, if needed (mostly for performance reasons).
AbstractPermutations.inttype
— Functioninttype(σ::Type{<:AbstractPermutation})
Return the underlying "storage" integer.
The intention is to provide optimal storage type when the images
vector constructor is used (to save allocations and memory copy). For example a hypothetic permutation Perm8
of elements up to length 255
may alter the default to UInt8
.
The default is UInt32
.
AbstractPermutations.perm
— Functionperm(p::AbstractPermutation)
Return the "bare-metal" permutation (unwrap). Return σ
by default.
Provide access to wrapped permutation object. For "bare-metal" permutations this method needs to return the identical (i.e. `===
) object.
The intention of this method is to provide an un-wrapped permutations to computationally intensive algorithms, so that the external wrappers (if present) do not hinder the performance.
AbstractPermutations.__unsafe_image
— Function__unsafe_image(i::Integer, σ::AbstractPermutation)
The same as i^σ
, but assuming that i ∈ Base.OneTo(degree(σ))
.
Example implementation
For an example, very simple implementation of the AbstractPermutation
interface you may find in ExamplePerms
module defined in perms_by_images.jl
.
Here we provide an alternative implementation which keeps the internal storage at fixed length.
Implementing mandatory methods
import AbstractPermutations
struct APerm{T} <: AbstractPermutations.AbstractPermutation
images::Vector{T}
degree::Int
function APerm{T}(images::AbstractVector{<:Integer}; check::Bool=true) where T
if check
isperm(images) || throw(ArgumentError("`images` vector is not a permutation"))
end
deg = something(findlast(i->images[i] ≠ i, eachindex(images)), 0)
return new{T}(images, deg)
end
end
Above we defined permutations by storing the vector of their images together with the computed degree deg
.
Now we need to implement the remaining two functions which will be simple enough:
AbstractPermutations.degree(p::APerm) = p.degree
function Base.:^(i::Integer, p::APerm)
deg = AbstractPermutations.degree(p)
# make sure that we return something of the same type as `i`
return 1 ≤ i ≤ deg ? oftype(i, p.images[i]) : i
end
With this the interface is implementation is complete. To test whether the implementation follows the specification a test suite is provided:
include(joinpath(pkgdir(AbstractPermutations), "test", "abstract_perm_API.jl"))
abstract_perm_interface_test(APerm{UInt16})
Test Summary: | Pass Total Time
AbstractPermutation API test: Main.APerm{UInt16} | 127 127 0.5s
Suplementary Methods
Since in APerm{T}
we store images as a Vector{T}
, to avoid spurious allocations we may define
AbstractPermutations.inttype(::Type{APerm{T}}) where T = T
There is no need to define AbstractPermutations.perm
as APerm
is already very low level and suitable for high performance code-paths.
Finally to squeeze even more performance one could define __unsafe_image
with the same semantics as n^σ
under the assumption that n
belongs to Base.OneTo(degree(σ))
:
@inline function AbstractPermutations.__unsafe_image(n::Integer, σ::APerm)
return oftype(n, @inbounds σ.images[n])
end