#############################################################################
##
#A  twogp.grp                   GAP group library              Alice Niemeyer
#A                                                           & Eamonn O'Brien
##
#A  @(#)$Id: twogp.grp,v 3.4 1994/01/21 16:23:09 sam Rel $
##
#Y  Copyright 1991-1992,  M.F. Newman and E.A. O'Brien
#Y  Mathematics Research Section, School of Mathematical Sciences 
#Y  Australian National University, Canberra, Australia
##
##  This   file contains the   extraction,  selection  and  example functions
##  for the library of 2-groups of size  dividing 256.  The  descriptions  of
##  those groups themselves are stored on the secondary  files  "twogp*.grp".
##
#H  $Log: twogp.grp,v $
#H  Revision 3.4  1994/01/21  16:23:09  sam
#H  removed dummy function 'Rank' (now dispatcher exists)
#H
#H  Revision 3.3  1993/02/10  15:18:47  martin
#H  changed call of 'READ' to 'ReadPath'
#H
#H  Revision 3.2  1992/08/03  09:05:45  fceller
#H  new version by Eamonn O'Brien and Alice Niemeyer
#H
#H  Revision 3.1  1992/04/02  18:25:31  martin
#H  initial revision under RCS
#H
##


#############################################################################
##
#F  InfoTwoGroup1( <arg> )  . . . . . . . . . . . . . . . package information
#F  InfoTwoGroup2( <arg> )  . . . . . . . . . . . . package debug information
##
if not IsBound( InfoTwoGroup1 )  then InfoTwoGroup1 := Print;   fi;
if not IsBound( InfoTwoGroup2 )  then InfoTwoGroup2 := Ignore;  fi;


#############################################################################
##
#V  TGParts . . . . . . . . . . . . . . . . . . . . . list of secondary files
##
##  The 2-groups  are stored  in several  parts,  each   part residing   on a
##  secondary file. 
##
##  'TGParts'  is   a list  that  specifies those  parts.  For  each  part it
##  contains a record with the following components:
##
##  'sizes'     the sizes of the groups in this part;
##
##  'ranks'     the ranks of the groups in this part; 
##
##  'pclasses'  the exponent-p classes of groups in this part;
##
##  'number'    the number of groups in this part (needed if not  all  groups
##              of one size are in one part);
##
##  'name'      the filename  of the  secondary  file  containing  this  part
##              (if <size> is at most 128 this is "twogp<size>", if <size> is
##              256 and the group is generated by <d> generators with <d>  in
##              [1,2,6,7,8]  this  is  "twogpd<d>",  and  otherwise  this  is
##              "twogpd<d><a>" where <a> is a  letter  between  'a'  and  'e'
##              corresponding to nondecreasing exponent 2-class);
##
##  'status'    a string describing the status of this file:
##              "unknown"       means that no attempt was made load the file;
##              "loaded"        means  that  this  part  is currently loaded;
##              "unloaded"      means that the part  was  unloaded  again  to
##                              make room for other parts;
##              "userloaded"    means that this part was loaded by  the  user
##                              and must not be unloaded;
##              "unloadable"    means that the file could not be read.
##
##  <grps>      a list containing the descriptions  of groups  in  this  part
##              (is unbounded  unless <status> is  "loaded" or "userloaded");
##
TGParts := rec(
 2   := rec( sizes := [ 2 ],    ranks := [1],       pclasses := [1],
             number := 1,       name := "twogp2",   status := "unknown" ),
 4   := rec( sizes := [ 4 ],    ranks := [1..2],    pclasses := [1..2],
             number := 2,       name := "twogp4",   status := "unknown" ),
 8   := rec( sizes := [ 8 ],    ranks := [1..3],    pclasses := [1..3],
             number := 5,       name := "twogp8",   status := "unknown" ),
 16  := rec( sizes := [ 16 ],   ranks := [1..4],    pclasses := [1..4],
             number := 14,      name := "twogp16",  status := "unknown" ),
 32  := rec( sizes := [ 32 ],   ranks := [1..5],    pclasses := [1..5],
             number := 51,      name := "twogp32",  status := "unknown" ),
 64  := rec( sizes := [ 64 ],   ranks := [1..6],    pclasses := [1..6],
             number := 267,     name := "twogp64",  status := "unknown" ),
 128 := rec( sizes := [ 128 ],  ranks := [1..7],    pclasses := [1..7],
             number := 2328,    name := "twogp128", status := "unknown" ),
 d1  := rec( sizes := [ 256 ],  ranks := [1],       pclasses := [8],
             number := 1,       name := "twogpd1",  status := "unknown" ),
 d2  := rec( sizes := [ 256 ],  ranks := [2],       pclasses := [3..7],
             number := 540,     name := "twogpd2",  status := "unknown" ),
 d3a := rec( sizes := [ 256 ],  ranks := [3],       pclasses := [2],
             number := 4,       name := "twogpd3a", status := "unknown" ),
 d3b := rec( sizes := [ 256 ],  ranks := [3],       pclasses := [3],
             number := 3838,    name := "twogpd3b", status := "unknown" ),
 d3c := rec( sizes := [ 256 ],  ranks := [3],       pclasses := [4],
             number := 2150,    name := "twogpd3c", status := "unknown" ),
 d3d := rec( sizes := [ 256 ],  ranks := [3],       pclasses := [5],
             number := 189,     name := "twogpd3d", status := "unknown" ),
 d3e := rec( sizes := [ 256 ],  ranks := [3],       pclasses := [6],
             number := 9,       name := "twogpd3e", status := "unknown" ),
 d4a := rec( sizes := [ 256 ],  ranks := [4],       pclasses := [2],
             number := 3566,    name := "twogpd4a", status := "unknown" ),
 d4b := rec( sizes := [ 256 ],  ranks := [4],       pclasses := [3],
             number := 8004,    name := "twogpd4b", status := "unknown" ),
 d4c := rec( sizes := [ 256 ],  ranks := [4],       pclasses := [3],
             number := 8006,    name := "twogpd4c", status := "unknown" ),
 d4d := rec( sizes := [ 256 ],  ranks := [4],       pclasses := [4],
             number := 651,     name := "twogpd4d", status := "unknown" ),
 d4e := rec( sizes := [ 256 ],  ranks := [4],       pclasses := [5],
             number := 14,      name := "twogpd4e", status := "unknown" ),
 d5a := rec( sizes := [ 256 ],  ranks := [5],       pclasses := [2],
             number := 8688,    name := "twogpd5a", status := "unknown" ),
 d5b := rec( sizes := [ 256 ],  ranks := [5],       pclasses := [2],
             number := 8688,    name := "twogpd5b", status := "unknown" ),
 d5c := rec( sizes := [ 256 ],  ranks := [5],       pclasses := [2],
             number := 8689,    name := "twogpd5c", status := "unknown" ),
 d5d := rec( sizes := [ 256 ],  ranks := [5],       pclasses := [3],
             number := 2570,    name := "twogpd5d", status := "unknown" ),
 d5e := rec( sizes := [ 256 ],  ranks := [5],       pclasses := [4],
             number := 18,      name := "twogpd5e", status := "unknown" ),
 d6  := rec( sizes := [ 256 ],  ranks := [6],       pclasses := [2..3],
             number := 456,     name := "twogpd6",  status := "unknown" ),
 d7  := rec( sizes := [ 256 ],  ranks := [7],       pclasses := [2],
             number := 10,      name := "twogpd7",  status := "unknown" ),
 d8  := rec( sizes := [ 256 ],  ranks := [8],       pclasses := [1],
             number := 1,       name := "twogpd8",  status := "unknown" )
);


#############################################################################
##
#F  TGLoad(<part>)  . . . . . . load a secondary file of the 2-groups library
##
##  'TGLoad' loads a part <part>, which  must be a record as described above,
##  and returns  the list of group  descriptions of that  part.  If a part is
##  already loaded, only the list is returned.
##
##  Before loading a part all other parts are unloaded, i.e.,  their 'groups'
##  component is  unbound and their status is set to  "unloaded".  Note  that
##  user loaded parts (those with status "userloaded") are not unloaded.
##
##  If a file can not be loaded the empty list is returned and a  warning  is
##  printed (but only once).
##
##  'TGLoad' uses finds the files in the directory  specified  by  'TWONAME',
##  this variable is set in the init file 'LIBNAME/\"init.g\"'.
##
TGLoad := function ( part )
    local   name;

    # test whether we actually need to load this file
    if part.status = "loaded"  or part.status = "userloaded"  then
        return part.groups;
    fi;

    # test whether the file can be loaded
    if part.status = "unloadable"  then
        return [];
    fi;

    # unload the other files
    for name  in RecFields( TGParts )  do
        if TGParts.(name) <> part  and TGParts.(name).status = "loaded"  then
            Unbind( TGParts.(name).groups );
            TGParts.(name).status := "unloaded";
        fi;
    od;

    # try to load the file
    InfoTwoGroup2( "#I  loading secondary two groups file ",part.name,"\n");
    if ReadPath( TWONAME, part.name, ".grp", "ReadTwo" )  then
        part.status := "loaded";
        return part.groups;
    else
        InfoTwoGroup1("#W  cannot load secondary 2-groups file ",name,"\n");
        part.status := "unloadable";
        return [];
    fi;

end;



#############################################################################
##
#F  TGGroup(<desc>) . . . . . . . . . . . . . . . . . . .  create a two group
##
##  'TGGroup' creates a 2-group from the description <desc>.
##
##  Each 2-group is compactly described by a list of 4 integers.  The 
##  integers have the following meaning:
##       1st integer: The rank of the Frattini quotient of group
##       2nd integer: The number of pcp generators of the group 
##       3rd integer: The exponent-p class of the group
##       4th integer: A long integer encoding the pc-presentation
##
##  The pc-presentation is encoded in the following way. 
##  Let $G$ be a 2-group described by a pc-presentation on 
##  $n$ generators,  $g_1, \ldots, g_n$, and with relations
##  $g_i^2 = g_{i+1}^{e^{i,i}_{i+1}} \cdots g_n^{e^{i,i}_n}$ for 
##  $1 \le i \le n$ and the relations 
##  $[g_i, g_j]  = g_{i+1}^{e^{i,j}_{i+1}} \cdots g_n^{e^{i,j}_n}$ for 
##  $1 \le j < i \le n$. 
##  Since the group is a 2-group, all exponents, $e^{i,j}_k$, are either
##  $0$ or $1$.  We order the exponents occuring on the right hand sides
##  of the relations and in this way obtain a binary word.
##  This binary word is converted to an integer, which is used
##  to encode the presentation. 
##
TGGroup := function ( desc )
    local   grp,        # group described by 'desc', result
            gens,       # generators of the group
            rels,       # relators of the group
            exps,       # exponent bit string
            rhs,        # right hand sides of the relators
            i, k, l;    # loop variables

    # make the generators
    gens := [];
    for i  in [1..desc[2]]  do
        gens[i] := AbstractGenerator(ConcatenationString("a",StringInt(i)));
    od;

    # make the right hand sides of the relations
    exps := desc[4];
    rhs := [];
    for i  in [1..desc[2]]  do
        rhs[i] := [];
        for k  in [1..i-1]  do
            rhs[i][k] := gens[1]^0;
            for l  in [k..i-1]  do
                rhs[l][k] := rhs[l][k] * gens[i]^(exps mod 2);
                exps := QuoInt( exps, 2 );
            od;
        od;
        rhs[i][i] := gens[1]^0;
    od;

    # make the relators
    rels := [];
    for i  in [1..desc[2]]  do
        Add( rels, gens[i]^2/rhs[i][i] );
        for k  in [1..i-1]  do
            Add( rels, Comm(gens[i],gens[k])/rhs[i][k] );
        od;
    od;

    # make the finitely presented group
    grp := Group( gens, gens[1]^0 );
    grp.relators := rels;

    # make the finite polycyclic group and enter rank and pclass
    grp := AgGroupFpGroup( grp );
    grp.rank               := desc[1];
    grp.pclass             := desc[3];
    grp.abstractGenerators := gens;
    grp.abstractRelators   := rels;

    # return the finite polycyclic group
    return grp;
end;


#############################################################################
##
#F  TwoGroup(<size>,<number>) . . . . .  extract one 2-group from the library
##
##  'TwoGroup' returns the <number>-th group of size <size> from the library.
##
TwoGroup := function ( size, number )
    local   name,       # name of a part of the two groups library
            total;      # total number of groups of size 'size'

    # check the size and the size
    if not size in [2,4,8,16,32,64,128,256]  then
        Error("<size> must be a power of 2 at most 256");
    fi;
    if not IsInt( number )  or number <= 0  then
        Error("<number> must be a positive integer");
    fi;

    # find the file
    total := 0;
    for name  in RecFields( TGParts )  do
        if size in TGParts.(name).sizes  then
            if number <= total + TGParts.(name).number then
                TGLoad( TGParts.(name) );
                return TGGroup( TGParts.(name).groups[number-total] );
            else
                total := total + TGParts.(name).number;
            fi;
        fi;
    od;

    # if we end here <number> was too large
    Error("<number> must be at most ",total);
end;


#############################################################################
##
#F  pClass(<grp>) . . . . . . . . . . .  p class of a p group, dummy function
##
pClass := function ( grp )
    if IsGroup( grp )  and IsBound( grp.pclass )  then
        return grp.pclass;
    else
        Error("pClass: function is not implemented,\n",
              "it is just a dummy to be used in the call of\n",
              "'AllTwoGroups' and 'OneTwoGroup'" );
    fi;
end;


#############################################################################
##
#F  AllTwoGroups(<fun1>,<val1>,...) . select groups from the 2-groups library
##
##  'AllTwoGroups' returns a list of all  2-groups that  have the  properties
##  given as arguments.  Each <funi> is a function that can be applied to the
##  groups; the corresponding <vali> is  either a  single value or a  list of
##  values that <funi> must return in order to select that group.
##
AllTwoGroups := function ( arg )
    local   result,     # list of selected groups, result
            sizes,      # list of sizes of the wanted groups
            ranks,      # list of the ranks of the wanted groups
            max,        # maximal rank in 'ranks'
            pclasses,   # list of the pclasses of the wanted groups
            name,       # name of a part of the library
            part,       # that part of the library
            grps,       # list of surviving groups in this part
            grps2,      # temporary list of groups
            grp,        # one group
            funs,       # properties other than 'Size', 'Rank', 'pClass'
            vals,       # corresponding value arguments
            i;          # loop variable

    # loop over the arguments
    sizes    := [2,4,8,16,32,64,128,256];
    ranks    := [1..8];
    pclasses := [1..8];
    funs     := [];
    vals     := [];
    for i  in [ 1 .. Length(arg)/2 ]  do

        # special case for 'Size'
        if arg[2*i-1] = Size  then
            if IsInt( arg[2*i] )  then
                sizes := Intersection( sizes, [ arg[2*i] ] );
                if sizes = []  then
                    InfoTwoGroup1("#I  no group has this size\n");
                    return [];
                fi;
            else
                sizes := Intersection( sizes, arg[2*i] );
                if sizes = []  then
                    InfoTwoGroup1("#I  no group has one of those sizes\n");
                    return [];
                elif sizes <> Set( arg[2*i] )  then
                    InfoTwoGroup1("#I  size restricted to ",sizes,"\n");
                fi;
            fi;

        # special case for 'Rank'
        elif arg[2*i-1] = Rank  then
            if IsInt( arg[2*i] )  then
                ranks := Intersection( ranks, [ arg[2*i] ] );
                if ranks = []  then
                    InfoTwoGroup1("#I  no group has this rank\n");
                    return [];
                fi;
            else
                ranks := Intersection( ranks, arg[2*i] );
                if ranks = []  then
                    InfoTwoGroup1("#I  no group has one of those ranks\n");
                    return [];
                elif ranks <> Set( arg[2*i] )  then
                    InfoTwoGroup1("#I  rank restricted to ",ranks,"\n");
                fi;
            fi;

        # special case for 'pClass'
        elif arg[2*i-1] = pClass  then
            if IsInt( arg[2*i] )  then
                pclasses := Intersection( pclasses, [ arg[2*i] ] );
                if pclasses = []  then
                    InfoTwoGroup1("#I  no group has this p class\n");
                    return [];
                fi;
            else
                pclasses := Intersection( pclasses, arg[2*i] );
                if pclasses = []  then
                  InfoTwoGroup1("#I  no group has one of those p classes\n");
                  return [];
                elif pclasses <> Set( arg[2*i] )  then
                  InfoTwoGroup1("#I  p class restricted to ",pclasses,"\n");
                fi;
            fi;

        # general case
        elif IsFunc( arg[2*i-1] )  then
            Add( funs, arg[2*i-1] );
            Add( vals, arg[2*i]   );

        # error message
        else
            Error("<fun",i,"> must be a function");
        fi;

    od;

    # we have not yet selected a group
    result := [];

    # loop over all parts of the library
    for name  in RecFields( TGParts )  do
        part := TGParts.(name);

        # sieve the groups through the 'Size' filter
        if IsSubset( sizes, part.sizes )  then
            grps := "all";
        else
            grps := [];
        fi;

        # sieve the groups through the 'Rank' filter
        grps2 := [];
        if IsSubset( ranks, part.ranks )  then
            grps2 := grps;
        elif Intersection( ranks, part.ranks ) <> []  then
            if grps = "all"  then  grps := TGLoad( part );  fi;
            max := Maximum( Intersection( ranks, part.ranks ) );
            i := 1;
            while i <= Length(grps)  and grps[i][1] <= max  do
                if grps[i][1]  in ranks  then
                    Add( grps2, grps[i] );
                fi;
                i := i + 1;
            od;
        else
            grps2 := [];
        fi;
        grps := grps2;

        # sieve the groups through the 'pClass' filter
        grps2 := [];
        if IsSubset( pclasses, part.pclasses )  then
            grps2 := grps;
        elif Intersection( pclasses, part.pclasses ) <> []  then
            if grps = "all"  then  grps := TGLoad( part );  fi;
            for grp  in grps  do
                if grp[3] in pclasses  then
                    Add( grps2, grp );
                fi;
            od;
        else
            grps2 := [];
        fi;
        grps := grps2;

        # sieve the groups through the other properties
        if grps = "all"  then grps := TGLoad( part );  fi;
        for grp  in grps  do
            grp := TGGroup( grp );
            i := 1;
            while     i <= Length(funs)
                  and (funs[i]( grp ) = vals[i]
                       or IsList( vals[i] )  and funs[i]( grp ) in vals[i])
            do
                i := i + 1;
            od;
            if i = Length(funs)+1  then
                Add( result, grp );
            fi;
        od;

    od;

    # return the result
    return result;
end;


#############################################################################
##
#F  OneTwoGroup(<fun1>,<val1>,...) select one group from the 2-groups library
##
##  'OneTwoGroups'  returns one  2-group that  has  the  properties  given as
##  arguments.  Each <funi> is a function that can be  applied to the groups;
##  the corresponding <vali> is  either a  single value or a  list of  values
##  that <funi> must return in order to select that group.
##
OneTwoGroup := function ( arg )
    local   sizes,      # list of sizes of the wanted groups
            ranks,      # list of the ranks of the wanted groups
            max,        # maximal rank in 'ranks'
            pclasses,   # list of the pclasses of the wanted groups
            name,       # name of a part of the library
            part,       # that part of the library
            grps,       # list of surviving groups in this part
            grps2,      # temporary list of groups
            grp,        # one group
            funs,       # properties other than 'Size', 'Rank', 'pClass'
            vals,       # corresponding value arguments
            i;          # loop variable

    # loop over the arguments
    sizes    := [2,4,8,16,32,64,128,256];
    ranks    := [1..8];
    pclasses := [1..8];
    funs     := [];
    vals     := [];
    for i  in [ 1 .. Length(arg)/2 ]  do

        # special case for 'Size'
        if arg[2*i-1] = Size  then
            if IsInt( arg[2*i] )  then
                sizes := Intersection( sizes, [ arg[2*i] ] );
                if sizes = []  then
                    InfoTwoGroup1("#I  no group has this size\n");
                    return [];
                fi;
            else
                sizes := Intersection( sizes, arg[2*i] );
                if sizes = []  then
                    InfoTwoGroup1("#I  no group has one of those sizes\n");
                    return [];
                elif sizes <> Set( arg[2*i] )  then
                    InfoTwoGroup1("#I  size restricted to ",sizes,"\n");
                fi;
            fi;

        # special case for 'Rank'
        elif arg[2*i-1] = Rank  then
            if IsInt( arg[2*i] )  then
                ranks := Intersection( ranks, [ arg[2*i] ] );
                if ranks = []  then
                    InfoTwoGroup1("#I  no group has this rank\n");
                    return [];
                fi;
            else
                ranks := Intersection( ranks, arg[2*i] );
                if ranks = []  then
                    InfoTwoGroup1("#I  no group has one of those ranks\n");
                    return [];
                elif ranks <> Set( arg[2*i] )  then
                    InfoTwoGroup1("#I  rank restricted to ",ranks,"\n");
                fi;
            fi;

        # special case for 'pClass'
        elif arg[2*i-1] = pClass  then
            if IsInt( arg[2*i] )  then
                pclasses := Intersection( pclasses, [ arg[2*i] ] );
                if pclasses = []  then
                    InfoTwoGroup1("#I  no group has this p class\n");
                    return [];
                fi;
            else
                pclasses := Intersection( pclasses, arg[2*i] );
                if pclasses = []  then
                  InfoTwoGroup1("#I  no group has one of those p classes\n");
                  return [];
                elif pclasses <> Set( arg[2*i] )  then
                  InfoTwoGroup1("#I  p class restricted to ",pclasses,"\n");
                fi;
            fi;

        # general case
        elif IsFunc( arg[2*i-1] )  then
            Add( funs, arg[2*i-1] );
            Add( vals, arg[2*i]   );

        # error message
        else
            Error("<fun",i,"> must be a function");
        fi;

    od;

    # loop over all parts of the library
    for name  in RecFields( TGParts )  do
        part := TGParts.(name);

        # sieve the groups through the 'Size' filter
        if IsSubset( sizes, part.sizes )  then
            grps := "all";
        else
            grps := [];
        fi;

        # sieve the groups through the 'Rank' filter
        grps2 := [];
        if IsSubset( ranks, part.ranks )  then
            grps2 := grps;
        elif Intersection( ranks, part.ranks ) <> []  then
            if grps = "all"  then  grps := TGLoad( part );  fi;
            max := Maximum( Intersection( ranks, part.ranks ) );
            i := 1;
            while i <= Length(grps)  and grps[i][1] <= max  do
                if grps[i][1]  in ranks  then
                    Add( grps2, grps[i] );
                fi;
                i := i + 1;
            od;
        else
            grps2 := [];
        fi;
        grps := grps2;

        # sieve the groups through the 'pClass' filter
        grps2 := [];
        if IsSubset( pclasses, part.pclasses )  then
            grps2 := grps;
        elif Intersection( pclasses, part.pclasses ) <> []  then
            if grps = "all"  then  grps := TGLoad( part );  fi;
            for grp  in grps  do
                if grp[3] in pclasses  then
                    Add( grps2, grp );
                fi;
            od;
        else
            grps2 := [];
        fi;
        grps := grps2;

        # sieve the groups through the other properties
        if grps = "all"  then grps := TGLoad( part );  fi;
        for grp  in grps  do
            grp := TGGroup( grp );
            i := 1;
            while     i <= Length(funs)
                  and (funs[i]( grp ) = vals[i]
                       or IsList( vals[i] )  and funs[i]( grp ) in vals[i])
            do
                i := i + 1;
            od;
            if i = Length(funs)+1  then
                return grp;
            fi;
        od;

    od;

    # return the result
    return false;
end;


#############################################################################
##
#E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables
##
##  Local Variables:
##  mode:               outline
##  outline-regexp:     "#F\\|#V\\|#E"
##  fill-column:        73
##  fill-prefix:        "##  "
##  eval:               (hide-body)
##  End:
##