#############################################################################
##
#W  utils.gi             GAP 4 package `atlasrep'               Thomas Breuer
##
#H  @(#)$Id: utils.gi,v 1.22 2004/03/23 09:29:23 gap Exp $
##
#Y  Copyright (C)  2001,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
##
##  This file contains the implementations of utility functions for the
##  {\ATLAS} of Group Representations.
##
Revision.( "atlasrep/gap/utils_gi" ) :=
    "@(#)$Id: utils.gi,v 1.22 2004/03/23 09:29:23 gap Exp $";


#############################################################################
##
#V  AtlasClassNamesOffsetInfo
##
##  The component `ordinary' is used for cases where the outer automorphism
##  group is not of prime order, and so the ordering of cosets is important
##  for constructing the names.
##
##  The component `special' is used for cases where one table of a subgroup
##  is used more than once.
##  Each entry is a list of length three, with first entry the `Identifier'
##  of the table in question, second entry the list of `Identifier' values of
##  the tables that cover the classes of the table in question, and third
##  entry the list of corresponding class fusions (those stored on the tables
##  can be omitted here).
##
InstallValue( AtlasClassNamesOffsetInfo, rec(
    ordinary:= [
    [ "A6", "A6.2_1", "A6.2_2", "A6.2_3" ],
    [ "L2(16)", "L2(16).2", "L2(16).4" ],
    [ "L2(25)", "L2(25).2_1", "L2(25).2_2", "L2(25).2_3" ],
    [ "L2(27)", "L2(27).2", "L2(27).3", "L2(27).6" ],
    [ "L2(49)", "L2(49).2_1", "L2(49).2_2", "L2(49).2_3" ],
    [ "L2(81)", "L2(81).2_1", "L2(81).4_1", "L2(81).4_2", "L2(81).2_2",
      "L2(81).2_3" ],
    [ "L3(4)", "L3(4).2_1", "L3(4).3", "L3(4).6", "L3(4).2_2", "L3(4).2_3" ],
    [ "L3(7)", "L3(7).3", "L3(7).2" ],
    [ "L3(8)", "L3(8).2", "L3(8).3", "L3(8).6" ],
    [ "L3(9)", "L3(9).2_1", "L3(9).2_2", "L3(9).2_3" ],
    [ "L4(3)", "L4(3).2_1", "L4(3).2_2", "L4(3).2_3" ],
    [ "O8-(3)", "O8-(3).2_1", "O8-(3).2_2", "O8-(3).2_3" ],
    [ "O8+(2)", "O8+(2).3", "O8+(2).2" ],
    [ "O8+(3)", "O8+(3).2_1", "O8+(3).3", "O8+(3).2_2", "O8+(3).4" ],
    [ "S4(4)", "S4(4).2", "S4(4).4" ],
    [ "2E6(2)", "2E6(2).2", "2E6(2).3" ],
    [ "U3(4)", "U3(4).2", "U3(4).4" ],
    [ "U3(5)", "U3(5).3", "U3(5).2" ],
    [ "U3(8)", "U3(8).3_1", "U3(8).3_2", "U3(8).3_3", "U3(8).2", "U3(8).6" ],
    [ "U3(9)", "U3(9).2", "U3(9).4" ],
    [ "U3(11)", "U3(11).3", "U3(11).2" ],
    [ "U4(3)", "U4(3).2_1", "U4(3).4", "U4(3).2_2", "U4(3).2_3" ],
    [ "U6(2)", "U6(2).3", "U6(2).2" ],
    ],
    special:= [
    [ "O8+(3).(2^2)_{111}",
      [ "O8+(3)", "O8+(3).2_1", "O8+(3).2_1", "O8+(3).2_1" ],
      [,,[1,3,4,2,5,6,8,9,7,8,10,10,11,12,13,15,16,14,17,19,20,18,22,23,21,
      24,26,27,25,26,29,30,28,29,32,33,31,34,34,35,35,36,37,38,39,41,42,40,
      41,43,43,44,44,46,47,45,49,50,48,52,53,51,52,54,55,55,57,58,56,57,59,
      60,62,63,61,65,66,64,65,68,69,67,68,71,72,70,122,123,124,125,126,127,
      128,129,129,130,130,131,131,132,133,134,136,135,137,139,138,140,142,
      141,143,144,145,145,146,147,148,149,149,150,151,152,152,153,155,154,
      157,156,158,158,159,160,161,162,164,163,165,165,166,166,169,170,167,
      168],[1,4,2,3,5,6,9,7,8,9,10,10,11,12,13,16,14,15,17,20,18,19,23,21,22,
      24,27,25,26,27,30,28,29,30,33,31,32,34,34,35,35,36,37,38,39,42,40,41,
      42,43,43,44,44,47,45,46,50,48,49,53,51,52,53,54,55,55,58,56,57,58,59,
      60,63,61,62,66,64,65,66,69,67,68,69,72,70,71,171,172,173,174,175,176,
      177,178,178,179,179,180,180,181,182,183,184,185,186,187,188,189,190,
      191,192,193,194,194,195,196,197,198,198,199,200,201,201,202,203,204,
      205,206,207,207,208,209,210,211,212,213,214,214,215,215,216,217,218,
      219]] ],
    [ "O8+(3).D8",
      [ "O8+(3)", "O8+(3).2_1", "O8+(3).2_1", "O8+(3).2_2", "O8+(3).4" ],
      [,,[1,3,2,3,4,5,7,6,7,7,8,8,9,10,11,13,12,13,14,16,15,16,18,17,18,19,
      21,20,21,21,23,22,23,23,25,24,25,26,26,27,27,28,29,30,31,33,32,33,33,
      34,34,35,35,37,36,37,39,38,39,41,40,41,41,42,43,43,45,44,45,45,46,47,
      49,48,49,51,50,51,51,53,52,53,53,55,54,55,97,98,99,100,101,102,103,104,
      104,105,105,106,106,107,108,109,110,111,112,113,114,115,116,117,118,
      119,120,120,121,122,123,124,124,125,126,127,127,128,129,130,131,132,
      133,133,134,135,136,137,138,139,140,140,141,141,142,143,144,145]] ],
    [ "U4(3).(2^2)_{122}",
      [ "U4(3)", "U4(3).2_1", "U4(3).2_2", "U4(3).2_2" ],
      [,,,[1,2,3,5,4,6,7,8,9,10,12,11,13,14,16,16,15,17,46,47,48,49,50,50,51,
      52,53,54,55,56,57,58,59,59]] ],
    [ "U4(3).(2^2)_{133}",
      [ "U4(3)", "U4(3).2_1", "U4(3).2_3", "U4(3).2_3" ],
      [,,,[1,2,3,4,5,6,7,8,9,10,11,12,13,13,14,36,37,38,39,40,41,42,43,44,44]
      ] ],
    ] ) );


#############################################################################
##
#F  AtlasClassNames( <tbl> )
##
InstallGlobalFunction( AtlasClassNames, function( tbl )
    local centre,
          simple,
          factnames,
          map,
          names,    # list of classnames, result
          i,        # loop variable
          name,     # identifier of ...
          nameparts,
          pos,
          solvres,  # table of the perfect normal subgroup
          simplename,
          F,
          Finv,
          info,
          tbls,
          classes,
          tblname,
          subtbl,
          derclasses,
          subF,
          size,
          gens,
          fus,
          filt,
          special,
          subtblfustbl,
          Fproxies,
          j,        # loop variable
          inv,
          proxies,
          orb,
          imgs,
          img,
          count,
          k,
          alpha,    # alphabet
          lalpha,   # length of the alphabet
          orders,   # list of representative orders
          innernames,
          number,   # at position <i> the current number of
                    # classes of order <i>
          suborders,
          depname,
          dashes,
          subnames,
          relevant,
          intermed,       # loop over intermediate tables
          tblfusF;

    if not IsCharacterTable( tbl ) then

      Error( "<tbl> must be a character table" );

    elif IsSimpleCharacterTable( tbl ) then

      # For tables of simple groups, `ClassNames' is good enough.
      return ClassNames( tbl, "Atlas" );

    elif IsPerfectCharacterTable( tbl ) then

      # Derive the names for central extensions of simple groups
      # from the names for the simple factor.
      centre:= ClassPositionsOfCentre( tbl );
      if Length( centre ) = 1 then
        Error( "<tbl> is not the table of an almost simple group" );
      fi;
      simple:= tbl / centre;
      if not IsSimpleCharacterTable( simple ) then
        Error( "<tbl> is not a central extension of a simple group" );
      fi;

      factnames:= ClassNames( simple, "Atlas" );
      map:= InverseMap( GetFusionMap( tbl, simple ) );
      names:= [];
      for i in [ 1 .. Length( map ) ] do
        if IsInt( map[i] ) then
          Add( names, Concatenation( factnames[i], "_0" ) );
        else
          Append( names, List( [ 0 .. Length( map[i] )-1 ],
              j -> Concatenation( factnames[i], "_", String( j ) ) ) );
        fi;
      od;
      return names;

    fi;

    # `tbl' has nontrivial commutator factor group.
    # Find out which nonabelian simple group is involved,
    # and which upward extension of which central extension is given.
    # (We use the `Identifier' value of `tbl';
    # note that this function makes sense only for library tables.)
    name:= Identifier( tbl );
    nameparts:= SplitString( name, "." );
    if Length( nameparts ) = 1 then
      Error( "the identifier `", name,
             "' does not fit to an almost simple group" );
    fi;
    pos:= PositionProperty( nameparts, x -> ForAny( x, IsAlphaChar ) );
    if pos = fail then
      Error( "strange name `", name, "'" );
    fi;

    # Get the table of the solvable residuum.
    solvres:= CharacterTable( JoinStringsWithSeparator(
                                  nameparts{ [ 1 .. pos ] } ) );
    if solvres = fail then
      Error( "the identifier `", name,
             "' does not fit to an almost simple group" );
    fi;

    centre:= ClassPositionsOfCentre( solvres );
    if 1 < Length( centre ) then
      Error( "class names of downward extensions of nonsimple groups ",
             "are not yet implemented, sorry." );
#T missing code!
    fi;

    # Now we know that `solvres' has trivial centre.
    # So it must be simple.
    if not IsSimpleCharacterTable( solvres ) then
      Error( "<tbl> is not the table of a nearly simple group" );
    fi;

    simplename:= Identifier( solvres );
    F:= tbl / ClassPositionsOfSolvableResiduum( tbl );
    Finv:= InverseMap( GetFusionMap( tbl, F ) );

    # We use the global variable `AtlasClassNamesOffsetInfo'.
    info:= First( AtlasClassNamesOffsetInfo.ordinary,
                  x -> x[1] = simplename );

    # Compute the tables of all cyclic upward extensions of `solvres'
    # that are contained in `tbl',
    # and store the positions of the corresponding relevant classes in `tbl'.
    # Tables that are *not* involved in `tbl' but whose class names force
    # offsets for the class names of `tbl' are also stored,
    tbls:= [ solvres ];
    classes:= [ [ Finv[1], true ] ];

    if IsPrimeInt( Size( tbl ) / Size( solvres ) ) then

      # Here `AtlasClassNamesOffsetInfo' may be missing.
      if info = fail then
        Info( InfoCharacterTable, 2,
              "AtlasClassNames: ",
              "no info by `AtlasClassNamesOffsetInfo' available\n" );
      else

        tblname:= ShallowCopy( Identifier( tbl ) );
        while tblname[ Length( tblname ) ] = '\'' do
          Unbind( tblname[ Length( tblname ) ] );
        od;
        pos:= Position( info, tblname );
        for i in [ 2 .. pos-1 ] do

          subtbl:= CharacterTable( info[i] );
          derclasses:= ClassPositionsOfDerivedSubgroup( subtbl );
          subF:= subtbl / derclasses;

          # The classes are *not* involved in `tbl',
          # store the positions of the classes in generator cosets!
          size:= Size( subF );
          gens:= Filtered( [ 1 .. size ],
                     i -> OrdersClassRepresentatives( subF )[i] = size );
          fus:= GetFusionMap( subtbl, subF );
          filt:= Filtered( [ 1 .. NrConjugacyClasses( subtbl ) ],
                           i -> fus[i] in gens );

          Add( tbls, subtbl );
          Add( classes, [ filt, false ] );

        od;

      fi;
      special:= fail;

      # Add `tbl' itself.
      Add( tbls, tbl );
      Add( classes,
           [ Difference( [ 1 .. NrConjugacyClasses( tbl ) ], Finv[1] ),
             true ] );

    elif Size( solvres ) <> Size( tbl ) then

      # Here we definitely need `AtlasClassNamesOffsetInfo'.
      if info = fail then
        Error( "not enough information about <tbl>" );
      fi;

      # More information is needed if a table occurs more than once.
      special:= First( AtlasClassNamesOffsetInfo.special,
                       list -> list[1] = Identifier( tbl ) );
      if special <> fail then
        special:= ShallowCopy( special );
        special[4]:= [];
        info:= special[2];
      fi;

      # Test which intermediate tables are needed.
      # These are exactly the ones having a fusion into `tbl'.
      # The others are taken with `false' in `classes'.
      for i in [ 2 .. Length( info ) ] do

        subtbl:= CharacterTable( info[i] );
        derclasses:= ClassPositionsOfDerivedSubgroup( subtbl );
        subF:= subtbl / derclasses;

        if special = fail or not IsBound( special[3][i] ) then
          subtblfustbl:= GetFusionMap( subtbl, tbl );
        else
          subtblfustbl:= special[3][i];
        fi;

        if subtblfustbl = fail then

          # The classes are *not* involved in `tbl',
          # or `subtbl' is equal to `tbl'.
          # Store the positions of the classes in generator cosets!
          size:= Size( subF );
          gens:= Filtered( [ 1 .. size ],
                     i -> OrdersClassRepresentatives( subF )[i] = size );
          fus:= GetFusionMap( subtbl, subF );
          filt:= Filtered( [ 1 .. NrConjugacyClasses( subtbl ) ],
                           i -> fus[i] in gens );

          if Identifier( tbl ) = info[i] then
            Add( tbls, tbl );
            Add( classes, [ filt, true ] );
          else
            Add( tbls, subtbl );
            Add( classes, [ filt, false ] );
          fi;

        elif Set( subtblfustbl{ derclasses } ) <> Finv[1] then
          Error( "strange fusion ", Identifier( subtbl ),
                 " -> ", Identifier( tbl ) );
        else

          # The table is needed.
          # Store the positions in `tbl' of the classes in generator cosets!
          size:= Size( subF );
          gens:= Filtered( [ 1 .. size ],
                     i -> OrdersClassRepresentatives( subF )[i] = size );
          fus:= GetFusionMap( subtbl, subF );
          filt:= Filtered( [ 1 .. NrConjugacyClasses( subtbl ) ],
                           i -> fus[i] in gens );

          Add( tbls, subtbl );
          Add( classes, [ Set( subtblfustbl{ filt } ), true ] );

        fi;

      od;

      # Check whether all necessary tables are available.
      if Union( List( Filtered( classes, x -> x[2] = true ), y -> y[1] ) )
             <> [ 1 .. NrConjugacyClasses( tbl ) ] then
        Error( "not all necessary tables are available" );
      fi;

    fi;

    # Define a function that creates class names in {\ATLAS} style.
    alpha:= List( "ABCDEFGHIJKLMNOPQRSTUVWXYZ", x -> [ x ] );
    lalpha:= Length( alpha );
    name:= function( n )
      local m;
      if n <= lalpha then
        return alpha[n];
      else
        m:= (n-1) mod lalpha + 1;
        n:= ( n - m ) / lalpha;
        return Concatenation( alpha[m], String( n ) );
      fi;
    end;

    # Initialize the list of class names
    # and the counter for the names already constructed.
    names:= [];
    number:= [];

    # Loop over the tables.
    for pos in [ 1 .. Length( tbls ) ] do

      subtbl:= tbls[ pos ];
      relevant:= classes[ pos ][1];

      if special <> fail and IsBound( special[3][ pos ] ) then
        fus:= special[3][ pos ];
        subnames:= special[4][ Position( special[2], special[2][ pos ] ) ];
        for i in [ 1 .. Length( subnames ) ] do
          if not IsBound( subnames[i] ) then
            subnames[i]:= "?";
          fi;
        od;
        subnames:= Concatenation( [ 1 .. Maximum( Filtered(
            [ 1 .. Length( fus ) ], x -> fus[x] in relevant ) )
            - Length( subnames ) ], subnames );
        dashes:= Number( [ 1 .. pos-1 ],
                         x -> special[2][x] = special[2][ pos ] );
        dashes:= ListWithIdenticalEntries( dashes, '\'' );
        subnames:= List( subnames, ShallowCopy );
        for i in [ 1 .. Length( subnames ) ] do
          Append( subnames[i], dashes );
        od;

      else

        if classes[ pos ][2] then
          if Size( subtbl ) = Size( tbl ) then
            fus:= [ 1 .. NrConjugacyClasses( tbl ) ];
          elif special <> fail and IsBound( special[3][ pos ] ) then
            fus:= special[3][ pos ];
          else
            fus:= GetFusionMap( subtbl, tbl );
            if fus = fail then
              for intermed in tbls do
                if     GetFusionMap( subtbl, intermed ) <> fail
                   and GetFusionMap( intermed, tbl ) <> fail then
                  fus:= CompositionMaps( GetFusionMap( intermed, tbl ),
                                         GetFusionMap( subtbl, intermed ) );
                  break;
                fi;
              od;
            fi;
          fi;
        else
          fus:= fail;
        fi;

        # Choose proxy classes in the factor group,
        # that is, one generator class for each cyclic subgroup.
        F:= subtbl / ClassPositionsOfDerivedSubgroup( subtbl );
        Fproxies:= [];
        for i in [ 1 .. NrConjugacyClasses( F ) ] do
          if not IsBound( Fproxies[i] ) then
            for j in ClassOrbit( F, i ) do
              Fproxies[j]:= i;
            od;
          fi;
        od;

        # Transfer the proxy classes to `subtbl'.
        tblfusF:= GetFusionMap( subtbl, F );
        proxies:= [];
        for i in [ 1 .. Length( tblfusF ) ] do
          if not IsBound( proxies[i] ) then
            orb:= ClassOrbit( subtbl, i );
            imgs:= tblfusF{ orb };
            for j in [ 1 .. Length( orb ) ] do

              # Classes mapping to a proxy class in `F' are proxies also
              # in `subtbl'.
              # For the other classes,
              # we make use of the convention that in {\GAP} tables
              # (of upward extensions of simple groups),
              # the follower classes come immediately after their proxies.
              k:= j;
              while Fproxies[ imgs[k] ] <> imgs[k] do
                k:= k-1;
              od;
              proxies[ orb[j] ]:= orb[k];

            od;
          fi;
        od;

        # Compute the non-order parts of the names w.r.t. the subgroup.
        subnames:= [];
        suborders:= OrdersClassRepresentatives( subtbl );
        for i in [ 1 .. NrConjugacyClasses( subtbl ) ] do
          if ( fus <> fail and fus[i] in relevant ) then
            if proxies[i] = i then
              if not IsBound( number[ suborders[i] ] ) then
                number[ suborders[i] ]:= 1;
              fi;
              subnames[i]:= name( number[ suborders[i] ] );
              number[ suborders[i] ]:= number[ suborders[i] ] + 1;
            else
              depname:= ShallowCopy( subnames[ proxies[i] ] );
              while ForAny( [ 1 .. i-1 ], x -> IsBound( subnames[x] )
                         and subnames[x] = depname
                         and suborders[x] = suborders[i] ) do
                Add( depname, '\'' );
              od;
              subnames[i]:= depname;
            fi;
          fi;
        od;

        if special <> fail then
          special[4][ pos ]:= subnames;
        fi;

      fi;

      # For tables that are not needed,
      # just compute the class names for all outer generator classes
      if fus = fail then
        for i in classes[ pos ][1] do
          if Fproxies[ tblfusF[i] ] = tblfusF[i] then
            if not IsBound( number[ suborders[i] ] ) then
              number[ suborders[i] ]:= 1;
            fi;
            name( number[ suborders[i] ] );
            number[ suborders[i] ]:= number[ suborders[i] ] + 1;
          fi;
        od;
      fi;

      # Compute the dashes that are forced by the table name.
      dashes:= "";
      if pos <> 1 then
        i:= Length( Identifier( subtbl ) );
        while Identifier( subtbl )[i] = '\'' do
          Add( dashes, '\'' );
          i:= i-1;
        od;
      fi;

      # If the table is needed then form orbit concatenations of these names.
      if fus <> fail then
        orders:= OrdersClassRepresentatives( tbl );
        inv:= InverseMap( fus );
        for i in relevant do
          if IsInt( inv[i] ) then
            orb:= [ subnames[ inv[i] ] ];
          else
            orb:= List( inv[i], x -> subnames[x] );
            if     ForAny( orb, x -> '\'' in x )
               and not ForAll( orb, x -> '\'' in x ) then
              orb:= Filtered( orb, x -> not '\'' in x );
            fi;
          fi;
          orb:= List( orb, x -> Concatenation( x, dashes ) );
          names[i]:= Concatenation( String( orders[i] ),
                         Concatenation( orb ) );
        od;
      fi;

    od;

    # Return the list of classnames.
    return names;
end );


#############################################################################
##
#F  StringOfAtlasProgramCycToCcls( <filename>, <tbl>, <mode> )
##
InstallGlobalFunction( StringOfAtlasProgramCycToCcls,
    function( filename, tbl, mode )
    local file,
          classnames,
          labels,
          numbers,
          line,
          string,
          pos,
          nrlabels,
          inputline,
          inline,
          nccl,
          result,
          i,
          dashedclassnames,
          orders,
          primes,
          known,
          unchanged,
          p,
          map,
          img,
          pp,
          orb,
          k,
          j,
          e,
          namline,
          resline;

    # Check the input.
    if not ( IsString( filename ) and IsOrdinaryTable( tbl ) ) then
      Error("usage: StringOfAtlasProgramCycToCcls(<filename>,<tbl>,<mode>)");
    fi;

    # Read the data, and fetch the `echo' lines starting with `Classes';
    # they serve as inputs for the result program.
    file:= InputTextFile( filename );
    if file = fail then
      Error( "cannot create input stream for file <filename>" );
    fi;

    # Compute the classnames.
    classnames:= AtlasClassNames( tbl );

    # Determine the labels that occur.
    # `labels' is a list of labels that occur in `echo' lines of the
    # given script (class names, without dashes).
    # `numbers' is a list of labels that occur in `oup' lines of the
    # given script (numbers or classnames, with dashes).
    labels:= [];
    numbers:= [];
    InfoRead1( "#I  reading `", filename, "' started\n" );
    line:= ReadLine( file );
    while line <> fail do

      # Ignore lines that are neither `echo' nor `oup' statements.
      if   5 < Length( line ) and line{ [ 1 .. 4 ] } = "echo" then
        line:= SplitString( line, "", "\" \n" );
        if   "classes" in line then
          Append( labels,
              line{ [ Position( line, "classes" )+1 .. Length( line ) ] } );
        elif "Classes" in line then
          Append( labels,
              line{ [ Position( line, "Classes" )+1 .. Length( line ) ] } );
        elif not "Here" in line then
          Append( labels,
              line{ [ Position( line, "echo" )+1 .. Length( line ) ] } );
        fi;
      elif  4 < Length( line ) and line{ [ 1 .. 3 ] } = "oup" then
        line:= SplitString( line, "", "\" \n" );
        Append( numbers, line{ [ 3 .. Length( line ) ] } );
      fi;
      line:= ReadLine( file );

    od;
    CloseStream( file );
    InfoRead1( "#I  reading `", filename, "' done\n" );

    # Construct the list of class representatives from the labels.
    if   IsEmpty( labels ) then
      Info( InfoCMeatAxe, 1,
            "no class names specified as outputs" );
      return fail;
    elif not ForAll( labels, str -> str in classnames ) then
      Info( InfoCMeatAxe, 1,
            "labels `",
            Filtered( labels, str -> not str in classnames ),
            "' aren't class names" );
      return fail;
    fi;
    string:= "";

    # Write down the line(s) specifying the input list.
    pos:= 1;
    nrlabels:= Length( labels );
    while pos <= nrlabels do
      inputline:= "";
      inline:= 0;
      while pos <= nrlabels and
            Length( inputline ) + Length( numbers[ pos ] ) <= 71 do
        Add( inputline, ' ' );
        Append( inputline, numbers[ pos ] );
        pos:= pos + 1;
        inline:= inline + 1;
      od;
      Append( string, "inp " );
      Append( string, String( inline ) );
      Append( string, inputline );
      Add( string, '\n' );
    od;

    # The program shall return conjugacy class representatives.
    nccl:= Length( classnames );
    result:= [];
    for i in [ 1 .. nccl ] do
      if classnames[i] in labels then
        result[i]:= true;
      fi;
    od;

    # The inputs are numbers or class names,
    # and depending on `mode', the outputs are numbers or class names.
    if   mode = "names" then
      # Dashes in the labels must be escaped with backslashes.
      # (Note that names in `echo' lines must *not* be escaped.)
      numbers:= Concatenation( numbers,
                    List( Filtered( classnames, x -> not x in labels ),
                          str -> ReplacedString( str, "'", "\\'" ) ) );
    elif ForAll( numbers, x -> Int( x ) <> fail ) then
      # The inputs are numbers, and the outputs shall be numbers.
      numbers:= Concatenation( numbers,
                    Difference( List( [ 1 .. nccl ], String ), numbers ) );
    elif IsSubset( classnames, numbers ) and numbers = labels then
      # The inputs are class names (with dashes escaped),
      # and the outputs shall be numbers,
      dashedclassnames:= List( classnames, 
                               str -> ReplacedString( str, "'", "\\'" ) );
      numbers:= Concatenation( numbers,
                    List( Difference( [ 1 .. nccl ],
                              List( numbers,
                                    x -> Position( dashedclassnames, x ) ) ),
                          String ) );
    else
      Error( "all in <numbers> must be numbers or in <classnames>" );
    fi;
    labels:= Concatenation( labels,
                 Filtered( classnames, x -> not x in labels ) );

    # Use power maps to fill missing entries.
    orders:= OrdersClassRepresentatives( tbl );
    primes:= Set( Factors( Size( tbl ) ) );
    known:= Filtered( [ 1 .. nccl ], x -> IsBound( result[x] ) );
    SortParallel( - orders{ known }, known );
    repeat
      unchanged:= true;
      for p in primes do
        map:= PowerMap( tbl, p );
        for i in known do
          img:= map[i];
          pp:= p mod orders[i];
          if pp = 0 then
            pp:= p;
          fi;
          if not img in known then
            Append( string, "pwr " );
            Append( string, String( pp ) );
            Append( string, " " );
            Append( string, numbers[ Position( labels, classnames[i] ) ] );
            Append( string, " " );
            Append( string, numbers[ Position( labels,
                                               classnames[ img ] ) ] );
            Append( string, "\n" );
            result[ img ]:= true;
            Add( known, img );
            unchanged:= false;
          fi;
        od;
      od;
    until unchanged;

    # Use Galois conjugacy to fill missing entries.
    for i in Difference( [ 1 .. nccl ], known ) do
      if not IsBound( result[i] ) then
        orb:= ClassOrbit( tbl, i );
        k:= First( orb, x -> x in known );
        if k = fail then
          Info( InfoCMeatAxe, 1,
                "at least Galois orbit representatives of classes in\n",
                "#I  `", classnames{ orb }, "' are missing" );
          return fail;
        fi;
        for j in orb do

          e:= 1;
          while not IsBound( result[j] ) do

            # Find a *small* power that maps k to j.
            e:= e+1;
            if orders[k] mod e <> 0 then
              if PowerMap( tbl, e, k ) = j then
                Append( string, "pwr " );
                Append( string, String( e ) );
                Append( string, " " );
                Append( string, numbers[ Position( labels,
                                         classnames[k] ) ] );
                Append( string, " " );
                Append( string, numbers[ Position( labels,
                                                   classnames[j] ) ] );
                Append( string, "\n" );
                result[j]:= true;
              fi;
            fi;

          od;

        od;
      fi;
    od;

    # Write the `echo' and `oup' statements.
    # (Split the output specifications into lines if necessary.)
    i:= 1;
    namline:= "";
    resline:= "";
    inline:= 0;
    while i <= nccl do
      if    60 < Length( namline ) + Length( classnames[i] )
         or 60 < Length( resline ) + Length( numbers[ Position( labels,
                                         classnames[i] ) ] ) then
        Append( string,
            Concatenation( "echo \"Classes", namline, "\"\n" ) );
        Append( string,
            Concatenation( "oup ", String( inline ), resline, "\n" ) );
        namline:= "";
        resline:= "";
        inline:= 0;
      fi;
      Add( namline, ' ' );
      Append( namline, classnames[i] );
      Add( resline, ' ' );
      Append( resline, numbers[ Position( labels, classnames[i] ) ] );
      inline:= inline + 1;
      i:= i + 1;
    od;
    if inline <> 0 then
      Append( string,
          Concatenation( "echo \"Classes", namline, "\"\n" ) );
      Append( string,
          Concatenation( "oup ", String( inline ), resline, "\n" ) );
    fi;

    # Return the string.
    return string;
end );


#############################################################################
##
#F  CurrentDateTimeString( )
#F  CurrentDateTimeString( <options> )
##
InstallGlobalFunction( CurrentDateTimeString, function( arg )
    local options, name, str, out;

    if Length( arg ) = 0 then
      options:= [ "+%s", "-u" ];
    elif Length( arg ) = 1 then
      options:= arg[1];
    fi;

    name:= Filename( DirectoriesSystemPrograms(), "date" );
    if name = fail then
      return "unknown";
    fi;

    str:= "";
    out:= OutputTextString( str, true );
    Process( DirectoryCurrent(), name, InputTextNone(), out, options );
    CloseStream( out );

    # Strip the trailing newline character.
    Unbind( str[ Length( str ) ] );

    # In the default case, transform to a format that is compatible with
    # `StringDate' and `StringTime'.
    if Length( arg ) = 0 then
      str:= Int( str );
      str:= Concatenation( StringDate( Int( str / 86400 ) ),
                           ", ",
                           StringTime( 1000 * ( str mod 86400 ) ),
                           " UTC" );
    fi;

    return str;
end );


#############################################################################
##
#F  SendMail( <sendto>, <copyto>, <subject>, <text> )
##
InstallGlobalFunction( SendMail, function( sendto, copyto, subject, text )
    local sendmail, inp;

    sendto:= JoinStringsWithSeparator( sendto, "," );
    copyto:= JoinStringsWithSeparator( copyto, "," );
    sendmail:= Filename( DirectoriesSystemPrograms(), "mail" );
    inp:= InputTextString( text );

    return Process( DirectoryCurrent(), sendmail, inp, OutputTextNone(),
                    [ "-s", subject, "-c", copyto, sendto ] );
end  );


#############################################################################
##
#F  ParseBackwards( <string>, <format> )
##
InstallGlobalFunction( "ParseBackwards", function( string, format )
    local result, pos, j, pos2;

    # Scan the string backwards.
    result:= [];
    pos:= Length( string );
    for j in Reversed( format ) do
      if IsString( j ) then
        pos2:= pos - Length( j );
        if pos2 < 0 or string{ [ pos2+1 .. pos ] } <> j then
          return fail;
        fi;
      else
        pos2:= pos;
        while 0 < pos2 and j( string[ pos2 ] ) do
          pos2:= pos2-1;
        od;
      fi;
      if j = IsDigitChar then
        Add( result, Int( string{ [ pos2+1 .. pos ] } ) );
      else
        Add( result, string{ [ pos2+1 .. pos ] } );
      fi;
      pos:= pos2;
    od;
    if 0 < pos then
      return fail;
    fi;

    return Reversed( result );
    end );


#############################################################################
##
#F  ParseBackwardsWithPrefix( <string>, <format> )
##
InstallGlobalFunction( "ParseBackwardsWithPrefix", function( string, format )
    local prefixes, len, flen, fstr, fstrlen, result;

    # Remove string prefixes.
    prefixes:= [];
    len:= Length( string );
    flen:= Length( format );
    while 0 < flen and IsString( format[1] ) do
      fstr:= format[1];
      fstrlen:= Length( fstr );
      if len < fstrlen or string{ [ 1 .. fstrlen ] } <> fstr then
        return fail;
      fi;
      Add( prefixes, fstr );
      string:= string{ [ fstrlen + 1 .. len ] };
      format:= format{ [ 2 .. flen ] };
      len:= len - fstrlen;
      flen:= flen-1;
    od;

    # Parse the remaining string backwards.
    result:= ParseBackwards( string, format );
    if result = fail then
      return fail;
    fi;

    Append( prefixes, result );
    return prefixes;
end );


#############################################################################
##
#F  ParseForwards( <string>, <format> )
##
InstallGlobalFunction( "ParseForwards", function( string, format )
    local result, pos, j, pos2, len;

    result:= [];
    pos:= 0;
    for j in format do
      len:= Length( string );
      if IsString( j ) then
        pos2:= pos + Length( j );
        if len < pos2 or string{ [ pos+1 .. pos2 ] } <> j then
          return fail;
        fi;
      else
        pos2:= pos + 1;
        while pos2 <= len and j( string[ pos2 ] ) do
          pos2:= pos2 + 1;
        od;
        pos2:= pos2 - 1;
      fi;
      if j = IsDigitChar then
        Add( result, Int( string{ [ pos+1 .. pos2 ] } ) );
      else
        Add( result, string{ [ pos+1 .. pos2 ] } );
      fi;
      pos:= pos2;
    od;
    if pos <> len then
      return fail;
    fi;

    return result;
end );


#############################################################################
##
#F  ParseForwardsWithSuffix( <string>, <format> )
##
InstallGlobalFunction( "ParseForwardsWithSuffix", function( string, format )
    local suffixes, len, flen, fstr, fstrlen, result;

    # Remove string suffixes.
    suffixes:= [];
    len:= Length( string );
    flen:= Length( format );
    while 0 < flen and IsString( format[ flen ] ) do
      fstr:= format[ flen ];
      fstrlen:= Length( fstr );
      if len < fstrlen or string{ [ len-fstrlen+1 .. len ] } <> fstr then
        return fail;
      fi;
      suffixes:= Concatenation( [ fstr ], suffixes );
      len:= len - fstrlen;
      flen:= flen-1;
      string:= string{ [ 1 .. len ] };
      format:= format{ [ 1 .. flen ] };
    od;

    # Parse the remaining string forwards.
    result:= ParseForwards( string, format );
    if result = fail then
      return fail;
    fi;

    Append( result, suffixes );
    return result;
end );


#############################################################################
##
#F  IsLowerAlphaOrDigitChar( <char> )
##
BindGlobal( "IsLowerAlphaOrDigitChar",
    char -> IsLowerAlphaChar( char ) or IsDigitChar( char ) );


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

