############################################################################
##
##  util.gi                       IRREDSOL                  Burkhard Höfling
##
##  Copyright © 2003–2016 Burkhard Höfling
##


############################################################################
##
#I  TestFlag(<n>, <i>)
##
##  tests if the i-th bit is set in binary representation the nonnegative 
##  integer n
##  
InstallGlobalFunction(TestFlag,
    function(n, i)
        return QuoInt(n, 2^i) mod 2 = 1;
    end);
    

############################################################################
##
#F  CodeCharacteristicPolynomial(<mat>, <q>)
##
##  given a matrix mat over GF(q), this computes a number which uniquely
##  identifies the characteristic polynomial of mat.
##  
InstallGlobalFunction(CodeCharacteristicPolynomial,
    function(mat, q)

        local cf, z, sum, c;

        z := Z(q);
        if Length(mat) = 2 then
            cf := [ mat[1][1]*mat[2][2] - mat[1][2]*mat[2][1],
                    - mat[1][1] - mat[2][2],
                    z^0];
        elif Length(mat) = 3 then
            cf := [ - mat[1][1]*mat[2][2]*mat[3][3] - mat[1][2]*mat[2][3]*mat[3][1] - mat[1][3]*mat[2][1]*mat[3][2]
                    + mat[1][1]*mat[2][3]*mat[3][2] + mat[2][2]*mat[1][3]*mat[3][1] + mat[3][3]*mat[2][1]*mat[1][2],
                    mat[1][1]*mat[2][2] + mat[2][2]*mat[3][3] + mat[1][1]*mat[3][3]
                        - mat[1][2]*mat[2][1] - mat[2][3]*mat[3][2] - mat[1][3]*mat[3][1],
                    - mat[1][1] - mat[2][2] - mat[3][3],
                    z^0];
        else
            cf := CoefficientsOfUnivariatePolynomial(CharacteristicPolynomial(mat, 1));
        fi;

        sum := 0;
        for c in cf do
            if c = 0*z then
                sum := sum * q;
            else 
                sum := sum * q + LogFFE(c, z) + 1;
            fi;
        od;

        return sum;
    end);


############################################################################
##
#F  FFMatrixByNumber(n, d, q)
##
##  computes a d x d matrix over GF(q) represented by the integer n
##  
InstallGlobalFunction(FFMatrixByNumber,
    function(n, d, q)
    
        local z, m, i, j, k;
        
        z := Z(q);
        m := NullMat(d,d, GF(q));
    
        for i in [d, d-1..1] do
            for j in [d, d-1..1] do
                k := RemInt(n, q);
                n := QuoInt(n, q);
                if k > 0 then
                    m[i][j] := z^(k-1);
                fi;
            od;
        od;
        ConvertToMatrixRep(m, q);
        return m;
    end);
    
    
############################################################################
##
#F  CanonicalPcgsByNumber(<pcgs>, <n>)
##
##  computes the canonical pcgs wrt. pcgs represented by the integer n
##  
InstallGlobalFunction(CanonicalPcgsByNumber,
    function(pcgs, n)
    
        local gens, cpcgs;
        
        gens := List(ExponentsCanonicalPcgsByNumber(RelativeOrders(pcgs), n), 
            exp -> PcElementByExponents(pcgs, exp));
        cpcgs := InducedPcgsByPcSequenceNC(pcgs, gens);
        SetIsCanonicalPcgs(cpcgs, true);
        return cpcgs;
    end);


############################################################################
##
#F  OrderGroupByCanonicalPcgsByNumber(<pcgs>, <n>)
##
##  computes Order(Group(CanonicalPcgsByNumber(<pcgs>, <n>))) without 
##  actually constructing the canonical pcgs or the group
##  
InstallGlobalFunction(OrderGroupByCanonicalPcgsByNumber,
    function(pcgs, n)
    
        local ros, order, j;
        
        order := 1;
        ros := RelativeOrders(pcgs);
        n := RemInt(n, 2^Length(ros));
        for j in [1..Length(ros)] do
            if RemInt(n, 2) > 0 then
                order := order * ros[j];
            fi;
            n := QuoInt(n, 2);
        od;
        return order;
    end);


############################################################################
##
#F  ExponentsCanonicalPcgsByNumber(<ros>, <n>)
##
##  computes the list of exponent vectors of the 
##  elements of CanonicalPcgsByNumber(<pcgs>, <n>)) without actually
##  constructing the canonical pcgs itself - it is enough to know the 
##  relative orders of the pc elements
##  
InstallGlobalFunction(ExponentsCanonicalPcgsByNumber,
    function(ros, n)
    
        local depths, len, d, exps, exp, j, cpcgs;
        depths := [];
        len := Length(ros);
        for j in [1..len] do
            d := RemInt(n, 2);
            n := QuoInt(n, 2);
            if d > 0 then
                Add(depths, j);
            fi;
        od;
    
        exps := [];
        for d in depths do
            exp := ListWithIdenticalEntries(len, 0);
            exp[d] := 1;
            for j in [d+1..len] do
                if not j in depths then
                    exp[j] := RemInt(n, ros[j]);
                    n := QuoInt(n, ros[j]);
                fi;
            od;
            Add(exps, exp);
        od;
        
        return exps;
    end);


############################################################################
##
#F  IsMatGroupOverFieldFam(famG, famF)
##
##  tests whether famG is the collections family of matrices over the field
##  whose family is famF
##  
InstallGlobalFunction(IsMatGroupOverFieldFam, function(famG, famF)
    return CollectionsFamily(CollectionsFamily(famF)) = famG;
end);


############################################################################
##
#V  IRREDSOL_DATA.PRIME_POWERS
##
##  cache of proper prime powers, preset to all prime powers <= 65535
##  
IRREDSOL_DATA.PRIME_POWERS := 
[ 4, 8, 9, 16, 25, 27, 32, 49, 64, 81, 121, 125, 128, 169, 243, 256, 289, 
  343, 361, 512, 529, 625, 729, 841, 961, 1024, 1331, 1369, 1681, 1849, 2048, 
  2187, 2197, 2209, 2401, 2809, 3125, 3481, 3721, 4096, 4489, 4913, 5041, 
  5329, 6241, 6561, 6859, 6889, 7921, 8192, 9409, 10201, 10609, 11449, 11881, 
  12167, 12769, 14641, 15625, 16129, 16384, 16807, 17161, 18769, 19321, 
  19683, 22201, 22801, 24389, 24649, 26569, 27889, 28561, 29791, 29929, 
  32041, 32761, 32768, 36481, 37249, 38809, 39601, 44521, 49729, 50653, 
  51529, 52441, 54289, 57121, 58081, 59049, 63001 ];


############################################################################
##
#F  IsPPowerInt(q)
##
##  tests whether q is a positive prime power, caching new prime powers
##  
InstallGlobalFunction(IsPPowerInt, 
    function(q)
        if not IsPosInt(q) then
            return false;
        elif IsPrimeInt(q) then
            return true;
        elif q in IRREDSOL_DATA.PRIME_POWERS then
            return true;
        elif IsPrimePowerInt(q) then
            AddSet(IRREDSOL_DATA.PRIME_POWERS, q);
            return true;
        else
            return false;
        fi;
    end);


############################################################################
##
#E
##