(* Gap/Mathematica (gap.m)
   =======================

   Sebastian Egner (egner@zkm.de), 26. April 1994
   in Mathematica v2.0 on 386SX, running MSDOS v3.3

   This is a collection of some minimal support functions
   to read/write GAP-structures in Mathematica-syntax 
   generated by the "math.g" library extension.
   The Mathematica-file of the interface (this file) does
   not contain a Package[], it is just a collection of
   miscellaneous functions to do fundamental structure
   conversion. A Mathematica-package to understand most
   datatypes of GAP would be a major enterprise.
*)

(* Reading from GAP
   ================

   The "math.g" library extension writes GAP-structures in a
   way that is syntactically sound for Mathematica without
   any modification. However there is no Mathematica-interpretation
   of special structures like cyc[<Polynomial in E(n)>].
   This section provides a few fundamental conversions to
   map GAPish structures to their Mathematica-counterpart if
   it exists.
*)

RecFields::usage = "RecFields[GAPrec] gives the list of tags
 used in the GAP record"

Dot::usage = StringJoin[(Dot::usage), "; GAPrec . tag gives
 the value bound to tag in a GAP record (a tag is a String)"]

fromCycles::usage = "fromCycles[n][GAPperm] converts the GAP
permutation into a representation acting on the n point Range[n]"

largestMovedPoint::usage = "largestMovedPoint[GAPperm] computes
the largest moved point of the GAP permutation"

(* rec() <--> RuleTable[]
   ----------------------

   A GAP-record in Mathematica is represented as
   rec[Fs_List] where Fs is a List of Rule[] of
   the form (tag_String -> value_). This corresponds
   to rec(tag1 := value1, .., tagN := valueN) in GAP.
*)

(* fundamental selectors *)
RecFields[rec[Fs_]]            := #[[1]]& /@ Fs
rec /: rec[Fs_] . (tag_String) := tag /. Fs 

(* perm() <--> List of points
   --------------------------

   A permutations p in Mathematica is represented as
   a list of Integer such that i[[p]] is the image of i
   under p. This corresponds to i^p in GAP. Thus the
   permutation group multiplication in Mathematica h[[g]] 
   corresponds to g*h in GAP.
*)

(* type decision about list of point permutations *)
permutationQ[p_List] := TrueQ[Sort[p] == Range[Length[p]]]
permutationQ[_]      := False


(* group multiplication with list of points *)
times[g_]           := g
times[gs__, g_List] := g[[times[gs]]] /; permutationQ[g]


(* how many points to take *)
largestMovedPoint[perm[Cs_]] :=
  If[Length[Cs] == 0, 1, Max[Flatten[Cs]]]


(* perm --> List of points *)
fromCycles[nPoints_Integer][perm[{}]]  := Range[nPoints]
fromCycles[nPoints_Integer][perm[Cs_]] :=
  times @@ (fromCyclesOne[nPoints] /@ Cs) /;
    nPoints >= largestMovedPoint[perm[Cs]]

fromCyclesOne[nPoints_][C_] :=
  #[[2]]& /@ 
    Union[
      Transpose[{C, RotateLeft[C]}],         (* the moved {i, p[i]} *)
      {#, #}& /@ Complement[Range[nPoints], C] (* the others {j, j} *)
    ]

(* List of points --> perm *)
toCycles[p_List] :=
  Module[{Cs, C, Ps, i, j},
    Cs = {};                       (* resulting list of cycles *)
    Ps = Select[Union[p], (p[[#]] != #)&]; (* remaining points *)
    While[Length[Ps] > 0,
 
      (* one cycle *)
      i = Ps[[1]];             (* first point of current cycle *)
      C = {i};                                (* current cycle *)
      j = p[[i]];                             (* current point *)
      While[j != i,
        AppendTo[C, j];
        j = p[[j]]
      ];

      (* next *)
      AppendTo[Cs, C]; 
      Ps = Complement[Ps, Flatten[C]];
    ];
    perm[Cs]
  ] /;
    permutationQ[p]

(* Writing to GAP
   ==============
*)

(* Writing to GAP means ... *)

toCycles::usage = "toCycles[p] converts a permutation of
 the n points Range[n] into a cycle representation for use in GAP"

GAPForm::usage = "GAPForm[X] formats a structure X in a 
 form suitable for be read by GAP"

(* GAP v3.1 contains the following specialized fundamental datatypes:
     boolean, integer, rational, string of character, permutation,
     a cyclotomic field extension of the rationals, finite fields, 
     ag-word of symbols, list, record of (tag:value)-associations

   For output of Mathematica-expressions in native GAP-syntax
   a function FormatGAP is defined below. It converts an
   Mathematica-structure into a form which will print as a
   valid GAP-expression when printed in OutputForm[].
   Remember to open files in OutputForm[] with changing options,
   the default is InputForm[].

   GAP supports operators with precedence in the following
   precedence levels:
     80  ^                     (non-associative)
     70  (unary)+ (unary)-                       
     60  * / mod               (left associative)
     50  + -                   (left associative: 1-2-3 = (1-2)-3)
     40  = <> < <= > >= in     (non-associative)
     30  not                   
     20  and                   (left associative)
     10  or                    (left associative)
*)

GAPForm[X_] := 
  OutputForm[formatGAP[X]]

(* > boolean *)

formatGAP[False] := "false"
formatGAP[True]  := "true"

(* > Integer, Rational, String *)

formatGAP[z_Integer]  := z
formatGAP[s_String]   := CForm[s]
formatGAP[q_Rational] := 
  Infix[formatGAP /@ {Numerator[q], Denominator[q]}, "/", 60, Left]

(* > permutations *)

formatGAP[perm[{}]]  := "()"
formatGAP[perm[Cs_]] :=
  SequenceForm @@ (
    SequenceForm["(", infix[formatGAP /@ #, ","], ")"]& /@ 
      Cs
  )

(* > cyclotomic field *)
  
formatGAP[cyc[c_]] :=
  formatGAP[c /. e[n_Integer] :> E[n]]

(* > finite field extension *)

formatGAP[ffe[p_, n_][0, 1]] := (* forget the degree for 0 *)
  SequenceForm["0*Z(", formatGAP[p], ")"]    

formatGAP[ffe[p_, 1][e, 1]] :=            (* short forms.. *)
  SequenceForm["Z(", formatGAP[p], ")"]                

formatGAP[ffe[p_, 1][e, k_]] := 
  SequenceForm["Z(", formatGAP[p], ")^", formatGAP[k]]

formatGAP[ffe[p_, n_][e, 1]] :=           (* ..short forms *)
  SequenceForm["Z(", formatGAP[p], "^", formatGAP[n], ")"]

formatGAP[ffe[p_, n_][e, k_]] :=       (* general non-zero *)
  SequenceForm["Z(", formatGAP[p], "^", formatGAP[n], ")^", formatGAP[k]]

(* > agword *)

formatGAP[agword[]]    := "IdAgWord"
formatGAP[agword[w__]] :=
  infix[formatGAPAgWord /@ {w}, "*"]

formatGAPAgWord[Power[x_, n_]] :=
  SequenceForm[formatGAP[x], "^", n]

formatGAPAgWord[x_] :=
  formatGAP[x]

(* > list *)

formatGAP[x_List] :=
  SequenceForm["[\n", infix[formatGAP /@ x, ",\n"], "]\n"]

(* > record *)

formatGAP[rec[Fs_]] :=
  SequenceForm[
    "rec(\n", 
    infix[formatGAPRecField /@ Fs, ",\n"], 
    ")\n"
  ]

formatGAPRecField[tag_String -> value_] :=
  SequenceForm[formatGAPRecTag[tag], " := ", formatGAP[value]]

formatGAPRecTag[s_String] := 
  StringJoin["'", s, "'"]

(* > operators *)

formatGAP[X_Power] := formatGAPInfix[List @@ X, "^", 80, NonAssociative]

formatGAP[-(x_)] := formatGAPPrefix[x, "-", 70, Left]

formatGAP[(x_) / (y_)] := formatGAPInfix[{x, y}, "/", 60, Left]
formatGAP[(x_) * (y_)] := formatGAPInfix[{x, y}, "*", 60, Left]
formatGAP[mod[x_, y_]] := formatGAPInfix[{x, y}, "mod", 60, Left]

formatGAP[(x_) - (y_)] := formatGAPInfix[{x, y}, "-", 50, Left] 
formatGAP[X_Plus]      := formatGAPInfix[List @@ X, "+", 50, Left]

formatGAP[(x_) == (y_)] := formatGAPInfix[{x, y}, "=",  40, NonAssociative]
formatGAP[(x_) != (y_)] := formatGAPInfix[{x, y}, "<>", 40, NonAssociative]
formatGAP[(x_) < (y_)]  := formatGAPInfix[{x, y}, "<",  40, NonAssociative]
formatGAP[(x_) <= (y_)] := formatGAPInfix[{x, y}, "<=", 40, NonAssociative]
formatGAP[(x_) > (y_)]  := formatGAPInfix[{x, y}, ">",  40, NonAssociative]
formatGAP[(x_) >= (y_)] := formatGAPInfix[{x, y}, ">=", 40, NonAssociative]
formatGAP[in[x_, y_]]   := formatGAPInfix[{x, y}, "in", 40, NonAssociative]

formatGAP[!(x_)] := formatGAPPrefix[x, "not", 30, Left]

formatGAP[(x_) && (y_)] := formatGAPInfix[{x, y}, "and", 20, Right]

formatGAP[(x_) || (y_)] := formatGAPInfix[{x, y}, "or", 10, Right]

(* > symbols *)

formatGAP[s_Symbol] :=
  s

(* > catch-all *)

formatGAP[(f_)[xs___]] := 
  SequenceForm[
    formatGAP[f],
    "(",
    infix[formatGAP /@ {xs}, ", "],
    ")"
  ]


(* >> supporting functions *)

(* special precedence forms *)

formatGAPInfix[xs_, op_, p_, ass_] :=
  Infix[formatGAP /@ xs, StringJoin[" ", op, " "], p, ass]

formatGAPPrefix[x_, op_, p_, ass_] :=
  Prefix[{formatGAP[x]}, StringJoin[op, " "], p, ass]

(* splice a seperator into a list *)

infix[{}, _]           := SequenceForm[]
infix[{x_}, _]         := x
infix[xs_, seperator_] := Infix[xs, seperator]

