#############################################################################
##
#W  scanmtx.gi     GAP 4 packages `atlasrep' and `meataxe'      Thomas Breuer
##
#H  @(#)$Id: scanmtx.gi,v 1.32 2004/03/23 09:34:37 gap Exp $
##
#Y  Copyright (C)  2001,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
##
##  Whenever this file is changed in one of the packages
##  `atlasrep' or `meataxe',
##  do not forget to update the corresponding file in the other package!
##
##  This file contains the implementation part of the interface routines for
##  reading and writing {\MeatAxe} text format and straight line programs
##  used in the {\ATLAS} of Group Representations.
##
if IsBound( Revision ) then
  Revision.( "atlasrep/gap/scanmtx_gi" ) :=
    "@(#)$Id: scanmtx.gi,v 1.32 2004/03/23 09:34:37 gap Exp $";
  Revision.( "cmeataxe/gap/scanmtx_gi" ) :=
    "@(#)$Id: scanmtx.gi,v 1.32 2004/03/23 09:34:37 gap Exp $";
fi;


############################################################################
##
#V  CMeatAxe
##
InstallValue( CMeatAxe,
    rec(
                gennames := [],
                alpha    := "abcdefghijklmnopqrstuvwxyz",
                maxnr    := 0
               ) );


#############################################################################
##
##  The C-{\MeatAxe} defines the bijection between the elements in the field
##  with $q = p^d$ elements and the set $\{ 0, 1, \ldots, q-1 \}$ of integers
##  by assigning the field element $\sum_{i=0}^{d-1} c_i z^i$ to the integer
##  $\sum_{i=0}^{d-1} c_i p^i$,
##  where the $c_i$ are in the set $\{ 0, 1, \ldots, p-1 \}$ and $z$ is the
##  primitive root of the field with $q$ elements that corresponds to the
##  residue class of the indeterminate, modulo the ideal spanned by the
##  Conway polynomial of degree $d$ over the field with $p$ elements.
##
##  The bijection is implemented via lookup tables `l1 = FFList( GF(<q>) )'
##  and `l2 = FFLogList( GF(<q>) )'.
##
##  If the field element <x> corresponds to the integer <i> then
##  the relations $<i> = `Position( FFList( GF(<q>) ), <x> )' - 1$ and
##  $<x> = `FFList( GF(<q>) )'[ <i>+1 ]$ hold.
##
##  If $q = p$ then $<i> = `IntFFE'( <x> )$ holds,
##  which is cheaper to compute than via `Position';
##  Also $<x> = <i> * `Z(p)^0'$ holds, so the lookup table need not be
##  created for large prime fields.
##
##  In order to avoid the calls to `Position' also in the case of non-prime
##  fields, the lookup list `FFLogList( GF(<q>) )' is used.
##  For $<x> = <z>^k$,
##  we have `String( <i> ) = FFLogList( GF(<q>) )[ LogFFE( <x>, <z> ) + 1 ]'.
##


#############################################################################
##
#V  FFLists
#V  FFLogLists
#V  NONNEG_INTEGERS_STRINGS
##
InstallFlushableValue( FFLists, [] );
InstallFlushableValue( FFLogLists, [] );
InstallFlushableValue( NONNEG_INTEGERS_STRINGS, [] );


#############################################################################
##
#F  FFList( <F> )
##
##  (This program was originally written by Meinolf Geck.)
##
InstallGlobalFunction( FFList, function( F )
    local sizeF,
          p,
          dim,
          elms,
          root,
          powers,
          i,
          pow;

    sizeF:= Size( F );

    if not IsBound( FFLists[ sizeF ] ) then

      p:= Characteristic( F );
      dim:= DegreeOverPrimeField( F );
      elms:= List( Cartesian( List( [ 1 .. dim ], i -> [ 0 .. p-1 ] ) ),
                   Reversed );
      root:= PrimitiveRoot( F );
      pow:= One( root );
      powers:= [ pow ];
      for i in [ 2 .. dim ] do
        pow:= pow * root;
        powers[i]:= pow;
      od;
      elms:= elms * powers;
      ConvertToVectorRep( elms, sizeF );
      FFLists[ sizeF ]:= elms;

    fi;

    return FFLists[ sizeF ];
end );


#############################################################################
##
#F  FFLogList( <F> )
##
InstallGlobalFunction( FFLogList, function( F )
    local sizeF, fflist, z, result, i;

    sizeF:= Size( F );

    if not IsBound( FFLogLists[ sizeF ] ) then
      fflist:= FFList( F );
      z:= Z( sizeF );
      result:= [ 0 ];
      result[ Length( fflist ) ]:= 0;
      for i in [ 2 .. Length( fflist ) ] do
        result[ LogFFE( fflist[i], z ) + 1 ]:= String( i-1 );
      od;
      FFLogLists[ sizeF ]:= result;
    fi;

    return FFLogLists[ sizeF ];
end );


#############################################################################
##
#F  IntegerStrings( <q> )
##
InstallGlobalFunction( IntegerStrings, function( q )
    local i;
    for i in [ Length( NONNEG_INTEGERS_STRINGS ) + 1 .. q ] do
      NONNEG_INTEGERS_STRINGS[i]:= String( i-1 );
    od;
    return NONNEG_INTEGERS_STRINGS;
end );


#############################################################################
##
#F  CMeatAxeFileHeaderInfo( <string> )
##
InstallGlobalFunction( "CMeatAxeFileHeaderInfo", function( string )
    local lline, header, pos, line, degree;

    # Remove a comment part if necessary.
    pos:= Position( string, '#' );
    if pos <> fail then
      string:= string{ [ 1 .. pos ] };
    fi;

    # Split the header string, and convert the entries to integers.
    lline:= List( SplitString( string, "", " \n" ), Int );
    if fail in lline then

      # If the header is valid then it is of new type;
      # remove everything before a leading `"'.
      header:= SplitString( string, "", " \n" );
      pos:= First( header, x -> not IsEmpty( x ) and x[1] = '\"' );
      if pos <> fail then
        header:= header{ [ pos .. Length( header ) ] };
      fi;

      if Length( header ) = 2 and header[1] = "permutation" then

        line:= [ 12, 1,, 1 ];
        if 7 < Length( header[2] ) and header[2]{ [ 1 .. 7 ] } = "degree=" then
          degree:= Int( header[2]{ [ 8 .. Length( header[2] ) ] } );
          line[3]:= degree;
        fi;

      elif Length( header ) = 4 and header[1] = "matrix" then

        line:= [ 6 ];
        if 6 < Length( header[2] ) and header[2]{ [ 1 .. 6 ] } = "field=" then
          line[2]:= Int( header[2]{ [ 7 .. Length( header[2] ) ] } );
          if IsInt( line[2] ) and line[2] < 10 then
            line[1]:= 1;
          fi;
        fi;
        if 5 < Length( header[3] ) and header[3]{ [ 1 .. 5 ] } = "rows=" then
          line[3]:= Int( header[3]{ [ 6 .. Length( header[3] ) ] } );
        fi;
        if 5 < Length( header[4] ) and header[4]{ [ 1 .. 5 ] } = "cols=" then
          line[4]:= Int( header[4]{ [ 6 .. Length( header[4] ) ] } );
        fi;

      fi;

      if fail in line or Number( line ) <> 4 then
        Info( InfoCMeatAxe, 1,
              "corrupted (new) MeatAxe file header" );
        return fail;
      fi;

    else

      # The header is of old type, consisting of four integers.
      if Length( lline ) = 3 and lline[1] = 12 then

        # We may be dealing with permutations of a degree requiring
        # (at least) six digits, for example the header for a permutation
        # on $100000$ points can be `12     1100000     1'.
        line:= String( lline[2] );
        if line[1] = '1' then
          lline[4]:= lline[3];
          lline[3]:= Int( line{ [ 2 .. Length( line ) ] } );
          lline[2]:= 1;
        fi;

      fi;

      if Length( lline ) <> 4 then
        Info( InfoCMeatAxe, 1,
              "corrupted (old) MeatAxe file header" );
        return fail;
      fi;
      line:= lline;

    fi;

    return line;
end );


#############################################################################
##
#F  ScanMeatAxeFile( <filename>[, <q>] )
#F  ScanMeatAxeFile( <string>[, <q>], "string" )
##
InstallGlobalFunction( ScanMeatAxeFile, function( arg )
    local PermListWithTest,
          filename,
          file,
          line,
          q,
          mode,
          degree,
          result,
          string,
          headlen,
          pos,
          pos2,
          offset,
          j,
          imgs,
          i,
          Fsize,
          F,
          nrows,
          fflist,
          newline,
          ncols,
          one,
          len;

    PermListWithTest:= function( list )
      local perm;

      perm:= PermList( list );
      if perm = fail then
        if ForAny( list, x -> not IsInt( x ) ) then
          Info( InfoCMeatAxe, 1,
                "non-permutation in file, contains ",
                Filtered( list, x -> not IsInt( x ) ) );
        fi;
        Info( InfoCMeatAxe, 1,
              "non-permutation in file,\n#I  ",
              Difference( [ 1 .. degree ], list ), " missing, ",
              List( Filtered( Collected( list ),
                    x -> x[2] <> 1 ), x -> x[1] ), " duplicate" );
      fi;
      return perm;
    end;

    if    Length( arg ) = 1
       or ( Length( arg ) = 2 and IsPosInt( arg[2] ) ) then

      filename:= arg[1];

      # Do we want to read the file *fast* (but using more space)?
      InfoRead1( "#I  reading `", filename, "' started\n" );
      if IsBound( CMeatAxe.FastRead ) and CMeatAxe.FastRead = true then
        string:= StringFile( filename );
        if Length( arg ) = 1 then
          return ScanMeatAxeFile( string, "string" );
        else
          return ScanMeatAxeFile( string, arg[2], "string" );
        fi;
      fi;

      file:= InputTextFile( filename );
      if file = fail then
        Error( "cannot create input stream for file <filename>" );
      fi;
      line:= ReadLine( file );
      if line = fail then
        Info( InfoCMeatAxe, 1, "no first line exists" );
        CloseStream( file );
        return fail;
      fi;
      if Length( arg ) = 2 then
        q:= arg[2];
      fi;

    elif    ( Length( arg ) = 2 and IsString( arg[1] ) and arg[2] = "string" )
         or ( Length( arg ) = 3 and IsString( arg[1] ) and IsPosInt( arg[2] )
                                and arg[3] = "string" ) then

      # Cut out the header line.
      string:= arg[1];
      headlen:= Position( string, '\n' );
      if headlen = fail then
        return fail;
      fi;
      line:= string{ [ 1 .. headlen-1 ] };
      string:= ShallowCopy( string );
      string{ [ 1 .. headlen ] }:= ListWithIdenticalEntries( headlen, ' ' );
      if Length( arg ) = 3 then
        q:= arg[2];
      fi;

    else
      Error( "usage: ScanMeatAxeFile( <filename>[, <q>] )" );
    fi;

    # Interpret the first line as file header.
    # From the first line, determine whether a matrix or a permutation
    # is to be read.
    line:= CMeatAxeFileHeaderInfo( line );
    if line = fail then
      Info( InfoCMeatAxe, 1, "corrupted file header" );
      if not IsBound( string ) then
        CloseStream( file );
      fi;
      return fail;
    fi;

    mode:= line[1];

    if mode in [ 2, 12 ] then

      # a permutation, to be converted to a matrix,
      # or a list of permutations
      if not IsBound( string ) then
        string:= StringFile( filename );

        # Omit the header line.
        headlen:= Position( string, '\n' );
        string{ [ 1 .. headlen ] }:= ListWithIdenticalEntries( headlen, ' ' );

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

      # Remove comment parts
      # (not really clever, but we actually do not expect comments).
      pos:= Position( string, '#' );
      while pos <> fail do
        pos2:= Position( string, '\n', pos );
        if pos2 = fail then
          pos2:= Length( string ) + 1;
        fi;
        string:= Concatenation( string{ [ 1 .. pos-1 ] },
                                string{ [ pos2 .. Length( string ) ] } );
        pos:= Position( string, '#' );
      od;

      # Split the line into substrings representing numbers.
      # (Admittedly, the code looks ugly, but simply calling `SplitString'
      # and `Int' is slower, and calling `SplitString' and `EvalString'
      # would be even slower than that.)
      if 12 < headlen then
        string{ [ 1 .. 13 ] }:= "SMFSTRING:=[ ";
      else
        string:= Concatenation( "SMFSTRING:=[ ", string );
      fi;
      NormalizeWhitespace( string );
      pos:= Position( string, ' ' );
      pos:= Position( string, ' ', pos );
      while pos <> fail do
        string[ pos ]:= ',';
        pos:= Position( string, ' ', pos );
      od;
      Append( string, "];" );
      file:= InputTextString( string );
      Read( file );
      string:= SMFSTRING;
      SMFSTRING:= "";

      if mode = 12 then

        # mode = 12:
        # a list of permutations (in free format)
        degree:= line[3];
        result:= [];
        if Length( string ) <> degree * line[4] then
          Info( InfoCMeatAxe, 1, "corrupted file, wrong number of entries" );
          return fail;
        fi;
        if line[4] = 1 then
          # This is the usual case (avoid duplicating the list).
          result[1]:= PermListWithTest( string );
        else
          offset:= 0;
          for j in [ 1 .. line[4] ] do
            result[j]:=
                PermListWithTest( string{ [ offset+1 .. offset+degree ] } );
            offset:= offset + degree;
          od;
        fi;
        if fail in result then
          return fail;
        fi;

      else

        # mode = 2:
        # a permutation, to be converted to a matrix
        # (Note that we cannot leave the task to `PermutationMat'
        # because we admit also non-square results.)
        nrows:= line[3];
        if Length( string ) <> nrows then
          Info( InfoCMeatAxe, 1, "corrupted file" );
          return fail;
        fi;
        F:= GF( line[2] );
        result:= NullMat( nrows, line[4], F );
        one:= One( F );
        for i in [ 1 .. nrows ] do
          result[i][ string[i] ]:= one;
        od;

        # Convert the matrix to the compressed representation.
        MakeImmutable( result );
        if not IsBound( q ) then
          q:= line[2];
        fi;
        ConvertToMatrixRep( result, q );

      fi;

    elif mode = 1 then

      # a matrix, in fixed format
      Fsize:= line[2];
      F:= GF( Fsize );
      fflist:= FFList( F );
      fflist:= fflist{ Concatenation( ListWithIdenticalEntries( 47, 1 ),
                                      [ 1 .. Length( fflist ) ] ) };
      nrows:= line[3];
      ncols:= line[4];
      result:= [];

      if IsBound( string ) then

        # Remove comment parts
        # (not really clever, but we actually do not expect comments).
        pos:= Position( string, '#' );
        while pos <> fail do
          pos2:= Position( string, '\n', pos );
          if pos2 = fail then
            pos2:= Length( string ) + 1;
          fi;
          string:= Concatenation( string{ [ 1 .. pos-1 ] },
                                  string{ [ pos2 .. Length( string ) ] } );
          pos:= Position( string, '#' );
        od;

        # The string is available in {\GAP}.
        RemoveCharacters( string, " \n" );
        if Length( string ) <> nrows * ncols then
          Info( InfoCMeatAxe, 1, "string length does not fit" );
          return fail;
        fi;
        pos:= 0;
        for i in [ 1 .. nrows ] do
          result[i]:= fflist{ SINTLIST_STRING(
                                  string{ [ pos+1 .. pos+ncols ] } ) };
          pos:= pos + ncols;
        od;

      else

        # The file is read line by line (for space reasons).
        line:= "";
        len:= 0;
        for i in [ 1 .. nrows ] do

          # Read enough lines from the file to fill the `i'-th row.
          while len < ncols do
            newline:= ReadLine( file );
            if newline = fail then
              Info( InfoCMeatAxe, 1, "corrupted file" );
              CloseStream( file );
              return fail;
            fi;

            # Remove comment parts.
            pos:= Position( newline, '#' );
            if pos <> fail then
              newline:= newline{ [ 1 .. pos-1 ] };
            fi;

            RemoveCharacters( newline, " \n" );
            Append( line, newline );
            len:= len + Length( newline );
          od;
          result[i] := fflist{ SINTLIST_STRING( line{ [ 1 .. ncols ] } ) };
          line:= line{ [ ncols + 1 .. len ] };
          len:= len - ncols;

        od;

        # Close the stream.
        CloseStream( file );
        InfoRead1( "#I  reading `", filename, "' done\n" );

      fi;

      # Convert further.
      MakeImmutable( result );
      if not IsBound( q ) then
        q:= Fsize;
      fi;
      ConvertToMatrixRep( result, q );

    elif mode in [ 3, 4, 5, 6 ] then

      # a matrix, in various free formats
      # (Prime fields could be treated in a special way,
      # without calling `FFList'; but this seems to yield no speedup,
      # except in exotic cases where `FFList' itself is the most expensive
      # part of the computation.)
      Fsize:= line[2];
      F:= GF( Fsize );
      nrows:= line[3];
      ncols:= line[4];
      result:= [];
      if not IsBound( q ) then
        q:= Fsize;
      fi;

      if mode = 5 then
        one:= One( F );
      else
        fflist:= FFList( F );
      fi;

      # The case of a string that is available in {\GAP} is dealt with
      # in parallel with the case of a file that is read line by line
      # (for space reasons).
      if IsBound( string ) then

        # Remove comment parts if applicable.
        # (not really clever, but we actually do not expect comments).
        while '#' in string do
          pos:= Position( string, '#' );
          pos2:= Position( string, '\n', pos );
          if pos2 = fail then
            pos2:= Length( string ) + 1;
          fi;
          string:= Concatenation( string{ [ 1 .. pos-1 ] },
                                  string{ [ pos2 .. Length( string ) ] } );
        od;

        # Split the string into substrings representing numbers.
        # (Admittedly, the code looks ugly, but simply calling `SplitString'
        # and `Int' is slower, and calling `SplitString' and `EvalString'
        # would be even slower than that.)
        if 12 < headlen then
          string{ [ 1 .. 13 ] }:= "SMFSTRING:=[ ";
        else
          string:= Concatenation( "SMFSTRING:=[ ", string );
        fi;
        NormalizeWhitespace( string );
        pos:= Position( string, ' ' );
        pos:= Position( string, ' ', pos );
        while pos <> fail do
          string[ pos ]:= ',';
          pos:= Position( string, ' ', pos );
        od;
        Append( string, "];" );
        file:= InputTextString( string );
        Read( file );
        string:= SMFSTRING;
        SMFSTRING:= "";
        line:= string;

        if Length( line ) <> nrows * ncols then
          Info( InfoCMeatAxe, 1, "corrupted file" );
          return fail;
        fi;

        pos:= 0;
        for i in [ 1 .. nrows ] do
          if mode = 5 then
            # an integer matrix (in free format), to be reduced mod a prime
            result[i]:= ( line{ [ pos+1 .. pos+ncols ] } + 1 ) * one;
          else
            result[i]:= fflist{ line{ [ pos+1 .. pos+ncols ] } + 1 };
          fi;
          pos:= pos + ncols;
        od;

      else

        # The file is read line by line (for space reasons).
        line:= "";
        len:= 0;

        for i in [ 1 .. nrows ] do

          # Read enough lines from the file to fill the `i'-th row.
          while len < ncols do
            newline:= ReadLine( file );
            if newline = fail then
              Info( InfoCMeatAxe, 1, "corrupted file" );
              CloseStream( file );
              return fail;
            fi;

            # Remove comment parts.
            pos:= Position( newline, '#' );
            if pos <> fail then
              newline:= newline{ [ 1 .. pos-1 ] };
            fi;

            newline:= List( SplitString( newline, "", " \n" ), Int );
            Append( line, newline );
            len:= len + Length( newline );
          od;

          if mode = 5 then
            # an integer matrix (in free format), to be reduced mod a prime
            result[i]:= ( line{ [ 1 .. ncols ] } + 1 ) * one;
          else
            result[i]:= fflist{ line{ [ 1 .. ncols ] } + 1 };
          fi;
          line:= line{ [ ncols + 1 .. len ] };
          len:= len - ncols;

        od;

        # Close the stream.
        CloseStream( file );
        InfoRead1( "#I  reading `", filename, "' done\n" );

      fi;

      # Convert further.
      MakeImmutable( result );
      ConvertToMatrixRep( result, q );

    else
      Info( InfoCMeatAxe, 1, "unknown mode" );
      return fail;
    fi;

    return result;
end );


#############################################################################
##
#M  MeatAxeString( <mat>, <q> )
##
InstallMethod( MeatAxeString,
    "for matrix over a finite field, and field order",
    [ IsTable and IsFFECollColl, IsPosInt ],
    function( mat, q )
    local nrows,     # number of rows of `mat'
          ncols,     # number of columns of `mat'
          one,       # identity element of the field of matrix entries
          zero,      # zero element of the field of matrix entries
          perm,      # list of perm. images if `mat' is a perm. matrix
          i,         # loop over the rows of `mat'
          noone,     # no `one' found yet in the current row
          row,       # one row of `mat'
          j,         # loop over the columns of `mat'
          mode,      # mode of the {\MeatAxe} string (first header entry)
          str,       # {\MeatAxe} string, result
          tail,      #
          fflist,    #
          ffloglist, #
          z,         #
          values,
          linelen,
          nol,
          k;

    # Check that `mat' is rectangular.
    if not IsMatrix( mat ) then
      Error( "<mat> must be a matrix" );
    fi;
    nrows:= Length( mat );
    ncols:= Length( mat[1] );

    # Check that `q' and `mat' are compatible.
    if not IsPrimePowerInt( q ) or ( q mod Characteristic( mat ) <> 0 ) then
      Error( "<q> and the characteristic of <mat> are incompatible" );
    fi;

    # If the matrix is a ``generalized permutation matrix''
    # then construct a string of {\MeatAxe} mode 2.
    one:= One( mat[1][1] );
    zero:= Zero( one );
    perm:= [];
    for i in [ 1 .. nrows ] do
      noone:= true;
      row:= mat[i];
      if IsZero( row ) then
        perm:= fail;
      else
        for j in [ 1 .. ncols ] do
          if row[j] = one then
            if noone and not j in perm then
              perm[i]:= j;
              noone:= false;
            else
              perm:= fail;
              break;
            fi;
          elif row[j] <> zero then
            perm:= fail;
            break;
          fi;
        od;
      fi;
      if perm = fail then
        break;
      fi;
    od;

    # Start with the header line.
    # We try to keep the files as small as possible by using the (old)
    # mode `1' whenever possible.
    if perm <> fail then
      mode:= "2";
    elif q < 10 then
      mode:= "1";
    else
      mode:= "6";
    fi;
    str:= ShallowCopy( mode );          # mode,
    Append( str, " " );
    Append( str, String( q ) );         # field size,
    Append( str, " " );
    Append( str, String( nrows ) );     # number of rows,
    Append( str, " " );
    Append( str, String( ncols ) );     # number of columns
    Append( str, "\n" );

    # Add the matrix entries.
    if mode = "1" then

      # Set the parameters for filling lines in the fixed format
      values:= "0123456789";
      linelen:= 80;
      nol:= Int( ncols / linelen );
      tail:= [ nol * linelen + 1 .. ncols ];
      fflist:= FFList( GF(q) );

      for row in mat do
        i:= 1;
        for j in [ 0 .. nol-1 ] do
          for k in [ 1 .. linelen ] do
            Add( str, values[ Position( fflist, row[i] ) ] );
            i:= i + 1;
          od;
          Add( str, '\n' );
        od;
        if not IsEmpty( tail ) then
          for i in tail do
            Add( str, values[ Position( fflist, row[i] ) ] );
          od;
          Add( str, '\n' );
        fi;
      od;

    elif mode = "2" then

      for i in perm do
        Append( str, String( i ) );
        Add( str, '\n' );
      od;

    else

      # free format
      if IsPrimeInt( q ) then
        # Avoid the call to `FFList', and expensive `Position' calls.
        # Also store the strings once;
        # this cache avoids garbage collections and thus saves time
        # if the matrix is not too small, compared to the field.
        values:= IntegerStrings( q );
        for row in mat do
          for i in row do
            Append( str, values[ IntFFE( i ) + 1 ] );
            Add( str, '\n' );
          od;
        od;
      else
        # Avoid expensive `Position' calls for the result of `FFList'.
        ffloglist:= FFLogList( GF(q) );
        z:= Z(q);
        for row in mat do
          for i in row do
            if i = zero then
              Append( str, "0\n" );
            else
              Append( str, ffloglist[ LogFFE( i, z ) + 1 ] );
              Add( str, '\n' );
            fi;
          od;
        od;
      fi;

    fi;

    # Return the result.
    return str;
    end );


#############################################################################
##
#M  MeatAxeString( <perms>, <degree> )
##
InstallMethod( MeatAxeString,
    "for list of permutations, and degree",
    [ IsPermCollection and IsList, IsPosInt ],
    function( perms, degree )
    local str, perm, i;

    # Start with the header line.
    str:= "12 1 ";
    Append( str, String( degree ) );
    Append( str, " " );
    Append( str, String( Length( perms ) ) );
    Append( str, "\n" );

    # Add the images.
    for perm in perms do
      for i in [ 1 .. degree ] do
        Append( str, String( i ^ perm ) );
        Add( str, '\n' );
      od;
    od;

    # Return the result.
    return str;
    end );


#############################################################################
##
#M  MeatAxeString( <perm>, <q>, <dims> )
##
InstallMethod( MeatAxeString,
    "for permutation, field order, and dimensions",
    [ IsPerm, IsPosInt, IsList ],
    function( perm, q, dims )
    local str, i;

    # Start with the header line.
    # (The mode is `2': a permutation, to be converted to a matrix.)
    str:= "2 ";                         # mode,
    Append( str, String( q ) );         # field size,
    Append( str, " " );
    Append( str, String( dims[1] ) );   # number of rows,
    Append( str, " " );
    Append( str, String( dims[2] ) );   # number of columns
    Append( str, "\n" );

    # Add the images.
    for i in [ 1 .. dims[1] ] do
      Append( str, String( i ^ perm ) );
      Add( str, '\n' );
    od;

    # Return the result.
    return str;
    end );


#############################################################################
##
#F  ScanStraightLineProgram( <filename> )
#F  ScanStraightLineProgram( <string>, "string" )
##
InstallGlobalFunction( ScanStraightLineProgram, function( arg )
    local filename,
          strdata,
          file,
          data,
          echo,
          line,
          labels,
          i,
          lines,
          output,
          a, b, c,
          outputs,
          result,
          search;

    # Get and check the input.
    if   Length( arg ) = 1 and IsString( arg[1] ) then
      # Read the data.
      filename:= arg[1];
      InfoRead1( "#I  reading `", filename, "' started\n" );
      strdata:= StringFile( filename );
      InfoRead1( "#I  reading `", filename, "' done\n" );
      if strdata = fail then
        Error( "cannot read file <filename>" );
      fi;
    elif Length( arg ) = 2 and IsString( arg[1] ) and arg[2] = "string" then
      strdata:= arg[1];
    else
      Error( "usage: ScanStraightLineProgram( <filename>[, \"string\"] )" );
    fi;

    data:= [];
    echo:= [];
    for line in SplitString( strdata, "", "\n" ) do

      # Omit empty lines and comment lines.
      if   4 < Length( line ) and line{ [ 1 .. 4 ] } = "echo" then
        Add( echo, line );
      elif not IsEmpty( line ) and line[1] <> '#' then
        line:= SplitString( line, "", " \n" );
        if not IsEmpty( line ) then
          Add( data, line );
        fi;
      fi;

    od;

    # Determine the labels that occur.
    labels:= [];
    if IsEmpty( data ) or data[1][1] <> "inp" then

      # There is no `inp' line.
      # The default input is given by the labels `1' and `2'.
      labels:=[ "1", "2" ];

    fi;
    for line in data do
      if line[1] = "inp" then
        if Length( line ) = 2 and Int( line[2] ) <> fail then
          Append( labels, List( [ 1 .. Int( line[2] ) ], String ) );
        elif Int( line[2] ) = Length( line ) - 2 then
          Append( labels, line{ [ 3 .. Length( line ) ] } );
        else
          Info( InfoCMeatAxe, 1, "corrupted line `", line, "'" );
          return fail;
        fi;
      elif line[1] <> "cjr" then
        i:= Length( line );
        if not line[i] in labels then
          Add( labels, line[i] );
        fi;
      fi;
    od;

    # Translate the lines.
    lines:= [];
    output:= [];
    c:= 0;
    for line in data do
      if line[1] = "oup" or line[1] = "op" then

        Add( output, line );

      elif line[1] <> "inp" then

        if   line[1] = "mu" and Length( line ) = 4 then
          a:= Position( labels, line[2] );
          b:= Position( labels, line[3] );
          c:= Position( labels, line[4] );
          Add( lines, [ [ a, 1, b, 1 ], c ] );
        elif line[1] = "iv" and Length( line ) = 3 then
          a:= Position( labels, line[2] );
          b:= Position( labels, line[3] );
          Add( lines, [ [ a, -1 ], b ] );
        elif line[1] = "pwr" and Length( line ) = 4 then
          a:= Int( line[2] );
          b:= Position( labels, line[3] );
          c:= Position( labels, line[4] );
          Add( lines, [ [ b, a ], c ] );
        elif line[1] = "cjr" and Length( line ) = 3 then
          a:= Position( labels, line[2] );
          b:= Position( labels, line[3] );
          Add( lines, [ [ b, -1, a, 1, b, 1 ], a ] );
        elif line[1] = "cp" and Length( line ) = 3 then
          a:= Position( labels, line[2] );
          b:= Position( labels, line[3] );
          Add( lines, [ [ a, 1 ], b ] );
        elif line[1] = "cj" and Length( line ) = 4 then
          a:= Position( labels, line[2] );
          b:= Position( labels, line[3] );
          c:= Position( labels, line[4] );
          Add( lines, [ [ b, -1, a, 1, b, 1 ], c ] );
        elif line[1] = "com" and Length( line ) = 4 then
          a:= Position( labels, line[2] );
          b:= Position( labels, line[3] );
          c:= Position( labels, line[4] );
          Add( lines, [ [ a, -1, b, -1, a, 1, b, 1 ], c ] );
        else
          Info( InfoCMeatAxe, 1, "strange line `", line, "'" );
          return fail;
        fi;
        if a = fail or b = fail or c = fail then
          Info( InfoCMeatAxe, 1, "line `", line, "' uses undefined label" );
          return fail;
        fi;

      fi;
    od;

    # Specify the output.
    result:= rec();
    if IsEmpty( output ) then

      # The default output is given by the labels `1' and `2'.
      # Note that this is allowed only if these labels really occur.
      if IsSubset( labels, [ "1", "2" ] ) then
        Add( lines, [ [ Position( labels, "1" ), 1 ],
                      [ Position( labels, "2" ), 1 ] ] );
      else
        Info( InfoCMeatAxe, 1, "missing `oup' statement" );
        return fail;
      fi;

    else

      # The `oup' lines list the output labels.
      outputs:= [];
      for line in output do
        if Length( line ) = 2 and Int( line[2] ) <> fail then
          Append( outputs, List( [ 1 .. Int( line[2] ) ],
                          x -> [ Position( labels, String( x ) ), 1 ] ) );
        elif Length( line ) = Int( line[2] ) + 2 then
          Append( outputs, List( line{ [ 3 .. Length( line ) ] },
                          x -> [ Position( labels, x ), 1 ] ) );
        else
          Info( InfoCMeatAxe, 1, "corrupted line `", line, "'" );
          return fail;
        fi;
      od;
      if ForAny( outputs, pair -> pair[1] = fail ) then
        Info( InfoCMeatAxe, 1, "undefined label used in output line(s)" );
        return fail;
      fi;
      Add( lines, outputs );

      # The straight line program is thought for computing
      # class representatives,
      # and the bijection between the output labels and the class names
      # is given by the `echo' lines.
      # For the line `oup <l> <b1> <b2> ... <bl>',
      # there must be the `echo' line `Classes <n1> <n2> ... <nl>'.
      echo:= List( echo, line -> SplitString( line, "", "\" \n" ) );
      while     not IsEmpty( echo )
            and LowercaseString( echo[1][2] ) <> "classes" do
        echo:= echo{ [ 2 .. Length( echo ) ] };
      od;

      if not IsEmpty( echo ) then

        # Check that the `echo' lines fit to the `oup' lines.
        echo:= List( echo, x -> Filtered( x,
                 y -> y <> "echo" and LowercaseString( y ) <> "classes" ) );
        outputs:= Concatenation( echo );
        output:= Sum( List( output, x -> Int( x[2] ) ), 0 );
        if Length( outputs ) < output then
          Info( InfoCMeatAxe, 1,
                "`oup' and `echo' lines not compatible" );
          return fail;
        fi;
        outputs:= outputs{ [ 1 .. output ] };
        result.outputs:= outputs;

      fi;

    fi;

    # Construct and return the result.
    result.program:= StraightLineProgramNC( lines );
    return result;
end );


#############################################################################
##
#F  AtlasStringOfStraightLineProgram( <prog>[, <outputnames>] )
##
InstallGlobalFunction( AtlasStringOfStraightLineProgram, function( arg )
    local prog,           # straight line program, first argument
          outputnames,    # list of strings, optional second argument
          str,            # string, result
          resused,        # maximal label currently used in the program
          i,
          translateword,  # local function
          line,
          lastresult,
          namline,
          resline,
          inline;

    # Get and check the arguments.
    if   Length( arg ) = 1 and IsStraightLineProgram( arg[1] ) then
      prog:= arg[1];
    elif Length( arg ) = 2 and IsStraightLineProgram( arg[1] )
                           and IsList( arg[2] ) then
      prog:= arg[1];
      outputnames:= arg[2];
    else
      Error( "usage: ",
             "AtlasStringOfStraightLineProgram( <prog>[, <outputnames>] )" );
    fi;

    # Write the line of inputs.
    str:= "inp ";
    resused:= NrInputsOfStraightLineProgram( prog );
    Append( str, String( resused ) );
    Add( str, '\n' );

    # function to translate a word into a series of simple operations
    translateword:= function( word, respos )

      local used,  # maximal label, including intermediate results
            new,
            i;

      if resused < respos then
        resused:= respos;
      fi;
      used:= resused;

      if Length( word ) = 2 then

        # The word describes a simple powering.
        if word[2] = -1 then
          Append( str,
                  Concatenation( "iv ", String( word[1] ),
                                 " ", String( respos ), "\n" ) );
        elif 0 <= word[2] then
          Append( str,
                  Concatenation( "pwr ", String( word[2] ),
                                 " ", String( word[1] ),
                                 " ", String( respos ), "\n" ) );
        else
          used:= used + 1;
          Append( str,
                  Concatenation( "iv ", String( word[1] ),
                                 " ", String( used ), "\n" ) );
          Append( str,
                  Concatenation( "pwr ", String( -word[i] ),
                                 " ", String( used ),
                                 " ", String( respos ), "\n" ) );
        fi;

      elif Length( word ) = 6 and word[2] = -1 and word[4] = 1
                              and word[6] =  1 and word[1] = word[5] then

        # The word describes a conjugation.
        Append( str,
                Concatenation( "cj ", String( word[3] ),
                                 " ", String( word[1] ),
                                 " ", String( respos ), "\n" ) );

      else

        # Get rid of the powerings.
        new:= [];
        for i in [ 2, 4 .. Length( word ) ] do
          if word[i] = 1 then
            Add( new, word[ i-1 ] );
          elif 0 < word[i] then
            used:= used + 1;
            Append( str,
                    Concatenation( "pwr ", String( word[i] ),
                                   " ", String( word[ i-1 ] ),
                                   " ", String( used ), "\n" ) );
            Add( new, used );
          else
            used:= used + 1;
            Append( str,
                    Concatenation( "iv ", String( word[ i-1 ] ),
                                   " ", String( used ), "\n" ) );
            if word[i] < -1 then
              used:= used + 1;
              Append( str,
                      Concatenation( "pwr ", String( -word[i] ),
                                     " ", String( used-1 ),
                                     " ", String( used ), "\n" ) );
            fi;
            Add( new, used );
          fi;
        od;

        # Now form the product of the elements in `new'.
        if Length( new ) = 1 then
          if new[1] <> respos then
            Append( str,
                    Concatenation( "pwr 1 ", String( new[1] ),
                                   " ", String( respos ), "\n" ) );
          fi;
        elif Length( new ) = 2 then
          Append( str,
                  Concatenation( "mu ", String( new[1] ),
                                 " ", String( new[2] ),
                                 " ", String( respos ), "\n" ) );
        else
          used:= used + 1;
          Append( str,
                  Concatenation( "mu ", String( new[1] ),
                                 " ", String( new[2] ),
                                 " ", String( used ), "\n" ) );
          for i in [ 3 .. Length( new )-1 ] do
            used:= used + 1;
            Append( str,
                    Concatenation( "mu ", String( used - 1 ),
                                   " ", String( new[i] ),
                                   " ", String( used ), "\n" ) );
          od;
          used:= used + 1;
          Append( str,
                  Concatenation( "mu ", String( used - 1 ),
                                 " ", String( new[ Length( new ) ] ),
                                 " ", String( respos ), "\n" ) );
        fi;

      fi;
    end;

    # Loop over the lines.
    for line in LinesOfStraightLineProgram( prog ) do

      if ForAll( line, IsList ) then

        # The list describes the return values.
        lastresult:= [];
        for i in [ 1 .. Length( line ) ] do
          if Length( line[i] ) = 2 and line[i][2] = 1 then
            Add( lastresult, String( line[i][1] ) );
          else
            resused:= resused + 1;
            translateword( line[i], resused );
            Add( lastresult, String( resused ) );
          fi;
        od;

        if IsBound( outputnames ) then

          if Length( line ) <> Length( outputnames ) then
            Error( "<outputnames> has the wrong length" );
          fi;

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

        elif ForAll( [ 1 .. Length( line ) ], i -> line[i] = [ i, 1 ] ) then

          # Write a short output statement.
          Append( str, "oup " );
          Append( str, String( Length( line ) ) );
          Add( str, '\n' );

        else

          # Write the full output statements.
          i:= 1;
          resline:= "";
          inline:= 0;
          while i <= Length( lastresult ) do
            if 60 < Length( resline ) + Length( lastresult[i] ) then
              Append( str,
                  Concatenation( "oup ", String( inline ), resline, "\n" ) );
              resline:= "";
              inline:= 0;
            fi;
            Add( resline, ' ' );
            Append( resline, lastresult[i] );
            inline:= inline + 1;
            i:= i + 1;
          od;
          if inline <> 0 then
            Append( str,
                Concatenation( "oup ", String( inline ), resline, "\n" ) );
          fi;

        fi;

        # Return the result.
        return str;

      else

        # Separate word and position where to put the result,
        # and translate the line into a sequence of simple steps.
        if ForAll( line, IsInt ) then
          resused:= resused + 1;
          lastresult:= resused;
          translateword( line, resused );
        else
          lastresult:= line[2];
          translateword( line[1], lastresult );
        fi;

      fi;
    od;

    # (If we arrive here then there is exactly one output value.)

    # Write the `echo' statements if applicable.
    # (This isn't really probable, is it?)
    if IsBound( outputnames ) then
      if Length( outputnames ) <> 1 then
        Error( "<outputnames> has the wrong length" );
      fi;
      Append( str,
          Concatenation( "echo \"Classes ", outputnames[1], "\"\n" ) );
    fi;

    # Write the output statement.
    Append( str, "oup 1 " );
    Append( str, String( lastresult ) );
    Add( str, '\n' );

    # Return the result;
    return str;
end );


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

