text:
#############################################################################
##
#A  toric.gi                  toric library                      David Joyner
##
##  this file contains implementations for toric
##
## 3-6-2006, changed Star to ToricStar, as a method instead of a
##           global function
##

#############################################################################
##
#F  InDualCone(<v>,<L>)
##
##  returns true if v belongs to the dual of the code generated by
##  the vectors in L
##
InstallGlobalFunction(InDualCone,function(v,L)
 local numgens,dim,i,V;
  TORIC.consistent_vectors(L);
  dim:=Size(v);
  numgens:=Size(L);
# V := Rationals^dim;
  for i in [1..numgens] do
   if TORIC.inner_product(v,L[i],IdentityMat(dim)) < 0 then return false; fi;
  od;
 return true;
end);

#############################################################################
##
#F  DualSemigroupGenerators(<L>)
##
##  Input: L is a list of integral n-vectors
##          generating a cone sigma
##  Output: the generators of S_sigma,
##
##  Idea:  let M be the max of the abs values of the
##  coords of the L[i]'s, for each vector v in
##  [1..M]^n, test if v in sigma^*. If so,
##  add to list of possible generators.
##  Once this for loop is finished, one can check
##  this list for redundant generators. The
##  trick below is to simply omit those elements
##  which are of the form d1+d2, where d1 and d2
##  are "small" elements in the integral dual cone.
##
InstallGlobalFunction(DualSemigroupGenerators,
function(L)
local d,i,dim,V,D,max,v,I,b,DpD,d1,d2,Dgens;
 TORIC.consistent_vectors(L);
 dim:=Size(L[1]);
 V := Rationals^dim;
 max:=TORIC.max_vectors(L);
 D:=[];
 I:= Cartesian(List([1..dim],i->[-max..max]));
 for v in I do
  if InDualCone(v,L) then
   Append(D,[v]);
  fi;
 od;
 DpD:=[];
 for d1 in D do
  if TORIC.inner_product(d1,d1,IdentityMat(dim)) <> 0 then
  for d2 in D do
   if TORIC.inner_product(d2,d2,IdentityMat(dim)) <> 0 then
      Append(DpD,[d1+d2]);
   fi;
  od;
  fi;
 od;
 Dgens:=[];
 for d in D do
  if not(d in DpD) then
     Append(Dgens,[d]);
  fi;
 od;
 return Dgens;
end);

#############################################################################
##
#F  EmbeddingAffineToricVariety(<L>)
##
##  Input: L is a list generating a cone
##        (as in dual_semigp_gens),
##  Output: the toroidal embedding of X=affine_toric_variety(L)
##       (given as a list of multinomials)
##
InstallGlobalFunction(EmbeddingAffineToricVariety,
function(L)
local map0,u,O,i,P1,P2,e,dim,V,R1,R2,hom;
 TORIC.consistent_vectors(L);
 u:=DualSemigroupGenerators(L);
 dim:=Size(u[1]);
 V:=Rationals^dim;
 O:=Zero(V);
 u:=Difference(u,[O]);
 map0:=[];
 for e in u do
  P1:=Filtered([1..dim],i->e[i] < 0);
  P2:=Filtered([1..dim],i->e[i] >= 0);
  if Size(P1) > 0 then
    Add(map0, Product(P2,i->X(Rationals,i)^(e[i]))/Product(P1,i->X(Rationals,i+dim)^(-e[i])));
  fi;
  if Size(P1) = 0 then
    Add(map0, Product(P2,i->X(Rationals,i)^(e[i])));
  fi;
 od;
 return map0;
end);

#############################################################################
##
#F  DivisorPolytope(<D>, <Rays>)
##
##  Input: D is the list of coeffs for the Weil divisor D
##  Rays is the list of vectors in the rays for the fan Delta
##   (Delta is determined by a list of generators L
##    but these are not explicitly needed here)
##  Output: the linear expressions in the affine coordinates of the
##   space of the cone which must be >0 for a point to be in the
##   desired polytope
##
InstallGlobalFunction(DivisorPolytope,
function(D,Rays)
local n,Inequalities,R,i,j;
 TORIC.consistent_vectors(Rays);
 n:=Size(Rays[1]);
 Inequalities:=[];
 R:=PolynomialRing(Rationals,n);
 for i in [1..Size(Rays)] do
  Add(Inequalities,D[i]+Sum([1..n],j->X(Rationals,j)*Rays[i][j]));
 od;
 return Inequalities;
end);

#############################################################################
##
#F  PolytopeLatticePoints(<A>, <Perps>)
##
##  Input: Perps=[v1,...,vk] is the list of "inward normal"
##            vectors perpendicular to the walls of the polytope P,
##         A=[a1,...,ak] is the amount wall is shifted from the
##            origin (ai>=0)
##       Eg, x=0, x=a, y=0, y=b has Perps=[[1,0],[-1,0],[0,1],[0,-1]]
##           and A=[0,a,0,b]
##  Output: the list of points in P \cap L^\perp
##
InstallGlobalFunction(PolytopeLatticePoints,
function(A,Perps)
local R,n,M,Pts,i,j,Inequalities,L0,L1,L2,v,ineq;
 TORIC.consistent_vectors(Perps);
 R:=ShallowCopy(Perps);
 n:=Size(R[1]);
 M:=Maximum(List([1..Size(A)],i->AbsoluteValue(A[i])));
 L0:=List([1..n],i->[-M..M]);
 Pts:=Cartesian(L0);
 L2:=[];
 for v in Pts do
  Inequalities:=[];
  for i in [1..Size(R)] do
   ineq:=A[i]+Sum([1..n],j->v[j]*R[i][j]);
   Add(Inequalities,ineq);
  od;
  if Minimum(Inequalities) >= 0 then Add(L2,v); fi;
 od;
 return L2;
end);

#############################################################################
##
#F  DivisorPolytopeLatticePoints(<D>, <Cones>, <Rays_ordered> )
##
##  Input: Cones is the fan
##         Rays_ordered is the *ordered* list of rays for Cones
##         D is the list of coeffs for the Weil divisor D
##  Output: the list of points in P_D \cap L^\perp
##            which paramterize the elements in L(D)
##
##  Caution: The set of rays do not determine the cones in a fan.
##
InstallGlobalFunction(DivisorPolytopeLatticePoints,
function(D,Cones,Rays_ordered)
local R,n,M,Pts,i,j,Inequalities,L0,L1,L2,v,ineq,Rays;
 TORIC.consistent_vectors(Rays_ordered);
 Rays:=Rays_ordered;
 R:=ShallowCopy(Rays);
 n:=Size(R[1]);
 M:=Maximum(List([1..Size(D)],i->AbsoluteValue(D[i])));
 L0:=List([1..n],i->[-M..M]);
 Pts:=Cartesian(L0);
 L2:=[];
 for v in Pts do
  Inequalities:=List([1..Size(R)],i->D[i]+Sum([1..n],j->v[j]*R[i][j]));
  if Minimum(Inequalities) >= 0 then Add(L2,v); fi;
 od;
 return L2;
end);

#############################################################################
##
#F  RiemannRochBasis(<D>, <Cones>, <Rays> )
##
##  Input: Cones is the fan
##         Rays_ordered is the *ordered* list of rays for Cones
##         D is the list of coeffs for the Weil divisor D
##
##  Output: computes a basis (a list of monomials)
##           for the RR space of the divisor represented by D
##
##
InstallGlobalFunction(RiemannRochBasis,
function(D,Cones,Rays)
local P,map0,d,R,e,i,P1,P2;
 TORIC.consistent_vectors(Rays);
 P:=DivisorPolytopeLatticePoints(D,Cones,Rays);
 map0:=[];
 d:=Size(Rays[1]);
 R:=PolynomialRing(Rationals,d);
 for e in P do
  P1:=Filtered([1..d],i->e[i] < 0);
  P2:=Filtered([1..d],i->e[i] >= 0);
  if Size(P1) > 0 and Size(P2) > 0 then
    Add(map0, Product(P2,i->X(Rationals,i)^(e[i]))/Product(P1,i->X(Rationals,i)^(-e[i])));
  fi;
  if Size(P1)= 0 then
    Add(map0, Product(P2,i->X(Rationals,i)^(e[i])));
  fi;
  if Size(P2) = 0 then
    Add(map0, 1/Product(P1,i->X(Rationals,i)^(-e[i])));
  fi;
 od;
 return map0;
end);

#############################################################################
##
#F  Faces( <Rays> )
##
##  Input: Rays is a list of rays for the fan Delta
##
##  Output: all the normals to the faces (hyperplanes of the cone)
##
##
InstallGlobalFunction(Faces,function(Rays)
local i,normals,n0,N,m,R,dim_sets,dim,v,pos,neg,n1,v0,N0;
 TORIC.consistent_vectors(Rays);
 normals:=[];
 R:=ShallowCopy(Rays);
 dim:=Size(R[1]);
 if dim<=1 then return
   Error("\n Dimension of ambient space for the rays must be >1.\n");
 fi;
 v:=Sum(R);
 dim_sets:=Combinations(R,dim-1); ##### must have dim>1 here!
 for m in dim_sets do
  n0:=TORIC.normal_to_hyperplane(m);
  if TORIC.inner_product(v,n0,IdentityMat(dim))>0 then Add(normals,n0);
    else
    Add(normals,-n0);
  fi;
 od;
 Sort(normals);
 N0:=ShallowCopy(normals);
 N:=ShallowCopy(normals);
 for n1 in N do
    if Minimum(List(Rays,v0->TORIC.inner_product(v0,n1,IdentityMat(dim))))<0 then
        N0:=Difference(N0,[n1]);
    fi;
 od;
 return Set(N0);
end);

#############################################################################
##
#F  InsideCone(<v>, <Rays> )
##
##  Input: Rays is a list of rays for the fan Delta
##
##  Output: true if v is in the cone represented by Rays
##          (a cone is a list of vectors generating it),
##          false otherwise
##
##  Idea: look at all dim-subsets of Rays and test if
##        there is a positive solns vector all the normals
##        to the faces (hyperplanes of the cone)
##
##
InstallGlobalFunction(InsideCone,function(v,Rays)
local w,F,dim,R;
 TORIC.consistent_vectors(Rays);
 R:=ShallowCopy(Rays);
 dim:=Size(R[1]);
 if Length(v)<>dim then
   Error("\n The vector ",v," must have the same dimension as the fan.\n");
 fi;
 if dim<=1 then return false; fi;
 F:=Faces(R);
 if Minimum(List(F,w->TORIC.inner_product(v,w,IdentityMat(dim))))<=0 then
  return false;
 fi;
 return true;
end);

#############################################################################
##
#F  NumberOfConesOfFan( <Delta>, <k> )
##
##  Input: Delta is the fan of cones
##         k is the dimension of the cones counted
##  Output: number of k-diml cones in the fan
##          (each hyperplane of one cone should not form the face
##           of any other cone in the fan)
##
##  Idea:   the fan Delta is represented as a set of max cones.
##          for each max cone, look at the k-diml faces
##          obtained by taking n choose k subsets of the
##          rays describing the cone.
##          **Certain** of these k-subsets yield the
##          desired cones
##
InstallGlobalFunction(NumberOfConesOfFan,
function(Cones,k)
local sigma,R,Rays,n,i,j,C,C0,dim,ell,k_cones,sigma0,N,v0,v;
 if k=0 then return 1; fi;
 C0:=ShallowCopy(Cones);
 Rays:=TORIC.flatten(C0);
 R:=ShallowCopy(Rays);
 if k=1 then return Size(R); fi;
 k_cones:=[];
 dim:=Size(R[1]);
 if k>dim then Print("dimension error\n"); return 0; fi;
 N:=Size(C0);
 if k=dim then return N; fi;
 for i in [1..N] do
  C:=ShallowCopy(Cones[i]);
  sigma:= Combinations(C,k);
  for ell in [1..Size(sigma)] do
     v0:=Sum(sigma[ell]);
     if not(InsideCone(v0,C)) then  Add(k_cones,sigma[ell]); fi;
  od;
 od;
 return Size(Set(k_cones));
end);

#############################################################################
##
#F  ConesOfFan( <Delta>, <k> )
##
##  Input: Delta is the fan of cones
##         k is the dimension of the cones taken
##  Output: the set of k-diml cones in the fan
##          (each hyperplane of one cone should not form the face
##           of any other cone in the fan, ie,
##           only takes those subcones which are *not* interior)
##
##
InstallGlobalFunction(ConesOfFan,
function(Cones,k)
local sigma,R,Rays,n,x,i,j,C,C0,dim,ell,k_cones,sigma0,N,v0,v;
 C0:=ShallowCopy(Cones);
 if k=0 then return 0*C0[1][1]; fi;
 Rays:=TORIC.flatten(C0);
 R:=ShallowCopy(Rays);
 if k=1 then return List(R,x->[x]); fi;
 k_cones:=[];
 dim:=Size(R[1]);
 if k>dim then Print("dimension error\n"); return 0; fi;
 N:=Size(C0);
 if k=dim then return C0; fi;
 for i in [1..N] do
  C:=ShallowCopy(Cones[i]);
  sigma:= Combinations(C,k);
  for ell in [1..Size(sigma)] do
      v0:=Sum(sigma[ell]);
   if not(InsideCone(v0,C)) then  Add(k_cones,sigma[ell]); fi;
  od; ##excludes the "interior" cones
 od;
 return Set(k_cones);
end);

#############################################################################
##
#F  ToricStar( <cone>, <Cones> )
##
##  Input: Cones is the fan of cones
##         <cone> is a cone of <Cones>
##  Output: the star of the cone in a fan
##          ie, the cones tau which have <cone> as a face
##
##
InstallGlobalFunction(ToricStar,
function(cone,Cones)
local T,tau,Taus,i,j,sigma,C0,R,Rays,dim;
 sigma:=ShallowCopy(cone);
 C0:=ShallowCopy(Cones);
 Rays:=TORIC.flatten(C0);
 R:=ShallowCopy(Rays);
 dim:=Size(R[1]);
 Taus:=[];
 for j in [1..dim] do
    tau:=ConesOfFan(C0,j);
    Append(Taus,tau);
 od;
 T:=[];
 for tau in Taus do
    if TORIC.is_sublist(sigma,tau) then Append(T,[tau]); fi;
 od;
 return T;
end);

#############################################################################
##
#F  BettiNumberToric( <Cones>, <k> )
##
##  Input: Cones is the fan of cones
##         k is an integer
##  Output: the k-th betti number of the toric variety
##          X(Delta), where Delta is a fan defined by its maximal
##          cones, Cones
##
##
InstallGlobalFunction(BettiNumberToric,
function(Cones,k0)
local i,j,n,a,C,k;
 if IsOddInt(k0) then return 0; fi;
 k:=Int(k0/2);
 C:=ShallowCopy(Cones)[1][1];
 n:=Size(C);
 a:=Sum( [k..n],i->(-1)^(i-k)*Binomial(i,k)*NumberOfConesOfFan(Cones,n-i));
 return a;
end);

#############################################################################
##
#F  EulerCharacteristic( <Cones> )
##
##  Input: Cones is the fan of cones
##  Output: Euler char of X(Delta), where
##          Delta is a fan defined by its maximal cones, Cones
##
##  Note: X(Delta) **must be non-singular***
##
## was InstallGlobalFunction(EulerCharacteristic,[IsList],
InstallMethod(EulerCharacteristic,[IsList],
function(Cones)
local sigma,R,Rays,C0,dim;
 C0:=ShallowCopy(Cones);
 Rays:=TORIC.flatten(C0);
 R:=ShallowCopy(Rays);
 dim:=Size(R[1]);
 return NumberOfConesOfFan(Cones,dim);
end);

#############################################################################
##
#F  CardinalityOfToricVariety( <Cones>, <q> )
##
##  Input: Cones is the fan of cones
##  Output: the number of elements of X(Delta) over GF(q), where
##          Delta is a fan defined by its maximal cones, Cones,
##          and where q is a prime power
##
##  Note: X(Delta) **must be non-singular***
##
InstallGlobalFunction(CardinalityOfToricVariety,
function(Cones,q)
local i,j,n,a;
 n:=Size(Cones[1][1]);
 a:=Sum([0..n],i->(q-1)^(i)*NumberOfConesOfFan(Cones,n-i));
 return a;
end);


text:
# Concatenate arrays
Concatenation([1, 2, 3], [4, 5, 6], [7, 8, 9]);
# [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

# Append to a variable
a := [1, 2, 3];
Append(a, [4, 5, 6);
Append(a, [7, 8, 9]);
a;
# [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

ext: gap

max_issues_repo_name: seanwallawalla-forks/RosettaCodeData

max_forks_repo_name: seanwallawalla-forks/RosettaCodeData


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

# NOTE: the code below checks if BF_NO_COPY flag is set. This is a bad way to check
#        whether something is a class, also hardcoding 128 will break sooner or later
_isclass := x->BinAnd(BagFlags(x),32768)=32768 or not IsRec(x);

_oid := x -> Cond(_isclass(x), x, ObjId(x));

Class(RewritableObjectOps, PrintOps, rec(
    \= := (s1,s2) -> Cond(
        _isclass(s1) and _isclass(s2), BagAddr(s1)=BagAddr(s2),
	_oid(s1) = _oid(s2) and s1.rChildren() = s2.rChildren()),

    \< := (s1,s2) -> Cond(
	_isclass(s1) and _isclass(s2), BagAddr(s1) < BagAddr(s2),
        _oid(s1) <> _oid(s2),        _oid(s1) < _oid(s2),
        s1.rChildren() < s2.rChildren())
));

#F RewritableObject - convenient base class for objects to be used
#F                    with rewriting.
#F
#F It provides
#F      __call__
#F      print
#F      rSetChild
#F      rChildren
#F      lessThan
#F      equal
#F
#F Constructor __call__ takes variable number of arguments and saves all
#F of them into .params field of the constructed instance.
#F
#F To do error checking and validation on .params, redefine .updateParams
#F in subclasses. It is also called after updates in .rSetChild
#F

Class(RewritableObject, rec(
    __call__ := meth(arg)
        local self, params, res;
        self := arg[1];
        params := Drop(arg, 1);
        res := WithBases(self,
            rec(params := params, operations := RewritableObjectOps));
        res.updateParams();
        return res;
    end,

    updateParams := self >> self,

    equals := (self, o) >>
        ObjId(self) = ObjId(o) and self.rChildren() = o.rChildren(),

    lessThan := (self, o) >> Cond(
        ObjId(self) <> ObjId(o), ObjId(self) < ObjId(o),
        [ ObjId(self), self.rChildren() ] < [ ObjId(o), o.rChildren() ]
    ),

    from_rChildren := (self, rch) >> ApplyFunc(ObjId(self), rch),
    rChildren := self >> self.params,
    rSetChild := meth(self, n, newC)
        self.params[n] := newC;
        self.updateParams();
    end,

    # Compatibility interface for Print, supports standard print() and
    # print(s, i, is).
    # NOTE: doesn't propagate it to children
    print := meth(arg)
        local self;
        self := arg[1];
        Print(self.__name__, "(", PrintCS(self.rChildren()), ")");
    end,
));

#F ConstClass - base class for constants.
#F

Class(ConstClass);

ext: gi


text:
##  Copyright (c) 2018-2021, Carnegie Mellon University
##  See LICENSE for details

RewriteRules(RulesStrengthReduce, rec(
    mul_rv_cxpack:= Rule([@(2, mul), @(1, Value, e->(e.t = TComplex and let(vv:= im(e.v).eval(), IsValue(vv) and vv.v = 0.0)) or e.t in [TReal, TInt] ), @(3, cxpack)],
        e->let(vv := Value(TReal, re(@(1).val).eval()), cxpack(vv * @(3).val.args[1], vv * @(3).val.args[2]))),
));

RewriteRules(RulesFuncSimp, rec(
    distribure_diagDirsum_fTensor_fId := Rule([@(1, fCompose), @(2, diagDirsum, e->ForAll(e.children(), c->c.domain() = e.children()[1].domain())), [@(3, fTensor), @(4, fId, e->e.range() = Length(@(2).val.children())),...]],
        e->diagDirsum(List([0..@(4).val.range()-1], j->fCompose(@(2).val.children()[j+1], fTensor(Drop(@(3).val.children(), 1)))))),

    distribure_diagDirsum_fTensor_fBase := Rule([@(1, fCompose), @(2, diagDirsum, e->ForAll(e.children(), c->c.domain() = e.children()[1].domain())), [@(3, fTensor), @(4, fBase, e->e.range() = Length(@(2).val.children())),...]],
        e->fCompose(@(2).val.child(@(4).val.params[2]+1), fTensor(Drop(@(3).val.children(), 1)))),

    flip_L_fbase_fId := ARule(fCompose, [ @(1,L), @(3, fTensor, e->let(ch := e.children(), ObjId(Last(ch)) = fId
            and ForAll(DropLast(ch, 1), j->ObjId(j) = fBase) and @(1).val.params[1] / @(1).val.params[2] = Last(ch).size))],
        e-> [ fTensor([Last(@(3).val.children())]::DropLast(@(3).val.children(), 1))]),

    push_RCData :=ARule(fCompose, [@(1,RCData), @(3, fTensor, e->ObjId(Last(e.children())) = fId and Last(e.children()).size = 2)],
        e->[RCData(fCompose(@(1).val.func, fTensor(DropLast(@(3).val.children(), 1))))]),

    diagMul_fConst_RCData := Rule([@(1, diagMul), @(2, fConst), @(3, RCData)],
        e->RCData(diagMul(fConst(@(2).val.params[1], @(2).val.params[2]/2, @(2).val.params[3]), @(3).val.func))),

    diagMul_diagTensor := Rule([@(1, diagMul), @(2, fConst), @(3, diagTensor)],
        e->let(ch := @(3).val.children(),
               loc := PositionProperty(ch, c->ObjId(c) = Lambda and ObjId(c.expr) = cxpack),
               chn := ch[loc],
               pre := [1..loc-1],
               post := [loc+1..Length(ch)],
               ldc := Filtered(ch, c->ObjId(c) = Lambda and IsValue(c.expr)),
               fct := Product(List(ldc), c->_unwrap(c.expr)),
               chl := List(ch{pre}, c->When(IsValue(c.expr), Lambda(c.vars, V(1)), c)),
               chr := List(ch{post}, c->When(IsValue(c.expr), Lambda(c.vars, V(1)), c)),
               diagTensor(chl::[Lambda(chn.vars, mul(V(fct * @(2).val.params[3]), chn.expr))]::chr))),

    fCompose_Lambda_fBase := Rule([@(1,fCompose), @(3,Lambda), @(2, fBase)], e->let(ii := Ind(1), Lambda(ii, @(3).val.at(@(2).val.params[2]))))

));

max_stars_repo_name: franzfranchetti/spiral-package-fftx

max_issues_repo_name: franzfranchetti/spiral-package-fftx

max_forks_repo_name: franzfranchetti/spiral-package-fftx


text:
#
# Read("~/Workspace/Chevalley.gap/init.gi"); Read(Filename(home_dir,"load.gi")); Read(Filename(test_dir,"psys.test.gi"));
#
# Read("~/Workspace/Chevalley.gap/init.gi"); Read(Filename(test_dir,"psys.test.init.gi")); Read(Filename(test_dir,"psys.test.gi"));
#
# Read(Filename(test_dir,"psys.test.gi"));
#

rsys:=RootSystem("F",4);
psys:=ParabolicSystem(rsys,[1,3]);

Print("Created ParabolicSystem ",psys,"\n");
Print("\t[",IsParabolicSystem(psys)=true,"] IsParabolicSystem(sys,[1,3])=true\n");

Print("\t[TODO] SupportRoots\n");
Print("\t[TODO] UnderlyingRootSystem\n");

radicalRootTest:=[ [ 0, 1, 0, 0 ], [ 0, 0, 0, 1 ], [ 0, 1, 0, 1 ], [ 0, 0, 1, 1 ], [ 1, 0, 1, 1 ], [ 0, 1, 1, 1 ],
  [ 0, 0, 2, 1 ], [ 1, 1, 1, 1 ], [ 1, 0, 2, 1 ], [ 0, 1, 2, 1 ], [ 1, 1, 2, 1 ], [ 2, 0, 2, 1 ],
  [ 0, 1, 2, 2 ], [ 1, 1, 2, 2 ], [ 2, 1, 2, 1 ], [ 1, 1, 3, 2 ], [ 2, 1, 2, 2 ], [ 2, 1, 3, 2 ],
  [ 2, 1, 4, 2 ], [ 2, 1, 4, 3 ], [ 2, 2, 4, 3 ] ]=RadicalRoots(psys);
Print("\t[",radicalRootTest,"] testing RadicalRoots(sys)\n");

Print("\t[TODO] iRadicalRoots\n");
Print("\t[TODO] Height\n");
Print("\t[TODO] Levels\n");
Print("\t[TODO] iLevels\n");
Print("\t[TODO] 0Level\n");
Print("\t[TODO] Shapes\n");
Print("\t[TODO] LeviModules\n");
Print("\t[TODO] iLeviModules\n");
Print("\t[TODO] Ordering\n");

Print("\t[TODO] Shape\n");
Print("\t[TODO] Shape\n");
Print("\t[TODO] LeviModule\n");
Print("\t[TODO] LeviModule\n");
Print("\t[TODO] iLeviModule\n");
Print("\t[TODO] iLeviModule\n");

Print("\t[TODO] LeviModules\n");
Print("\t[TODO] iLeviModules\n");
Print("\t[TODO] RootHeight\n");
Print("\t[TODO] RootHeight\n");
Print("\t[TODO] Level\n");
Print("\t[TODO] InRadical\n");


text:
# Copyright (c) 2018-2020, Carnegie Mellon University
# See LICENSE for details

# Radix N kernel for FFTE

buildScalarKernel_c := function(n, kk, conf, opts)
    local name, suffix, filesuffix, j, k, l, l1, m, tmp1, tmp3, i1, i2, gf, sf, gath, scat, gc, sc,
        dft, rts, opcnts, rt, dfts, dftc, cl, cc, c, clp, lp, mp;

    name := DFTnameStr(n, kk);
    suffix := "c";
    filesuffix := "c_";
#    suffix := "_k";
    Print("\n\n// == Generating \"", name, "\" ==================================================\n\n");

    # variables
    j := V(0);
    k := var.fresh_t("k", TInt);
    l := V(1);
    l1 := var.fresh_t("l", TInt);
    m := var.fresh_t("m", TInt);
    lp := var.fresh_t("lp", TPtr(TInt));
    mp := var.fresh_t("mp", TPtr(TInt));

    # temp arrays
    tmp1 := var.fresh_t("R", TArray(TReal, 2*n));
    tmp3 := var.fresh_t("T", TArray(TReal, 2*n));

    # gather and scatter
    i1 := var.fresh_t("i", n);
    i2 := var.fresh_t("i", n);
    gf := fTensor(Lambda(i1, k + j*m + i1*l1*m), fId(2));
    sf := fTensor(Lambda(i2, k+n*j*m + i2*m), fId(2));
    gath := Gath(gf);
    scat := Scat(sf);

    # generate gather and scatter code
    gc := BlockUnroll(unroll_cmd(opts.codegen(gath, tmp1, X, opts)), opts);
    sc := BlockUnroll(unroll_cmd(opts.codegen(scat, Y, tmp3, opts)), opts);

    # generate DFT kernel
    dft := RC(DFT(n, kk));
    rts := AllRuleTrees(dft, opts);
    opcnts := List(rts, r -> [ Length(Collect(CodeRuleTree(r, opts), @(1, [add, sub, mul], e->e.t=TReal))), r]);
    rt := Minimum(opcnts)[2];
    dfts := SumsRuleTree(rt, opts);
    dftc := BlockUnroll(opts.codegen(dfts, tmp3, tmp1, opts), opts);

    # stitch code fragments together
    cl := func(TVoid, "transform", [Y, X, j, k, l1, m],
            decl([tmp1, tmp3], chain(gc, dftc, sc)));
    cc := Compile(cl, opts);

    # fixup to push decls inside (?)
    c := func(TVoid, "transform", [Y, X, j, k, l1, m],
            decl(cc.vars, cc.cmd.cmds[1].cmd));

    # print Radix N FFTE kernel as function

    # function with j and k loop in the function call
    clp := func(TVoid, "transform", [Y, X, lp, mp],
        decl(c.cmd.vars::c.free()::[l1,m],
            chain(
                assign(l1, deref(lp)),
                assign(m, deref(mp)),
                loopn(k, m, c.cmd.cmd)
            )
        )
    );

    # print Radix N FFTE kernel as function
    PrintCode(opts.FortranIze(name::suffix), clp, opts);
    PrintTo(name::filesuffix::suffix::".c", PrintCode(opts.FortranIze(name::suffix), clp, opts));
end;

max_stars_repo_name: spiral-software/spiral-package-ffte

max_issues_repo_name: spiral-software/spiral-package-ffte

max_forks_repo_name: spiral-software/spiral-package-ffte


text:
# Copyright (c) 2018-2020, Carnegie Mellon University
# See LICENSE for details
#
# qEmbed Object, qJunc Object
# All objects and helpers needed to embed a logical transform onto a physical mesh
#

##
#F qJunc( <qubit_order>, <n>, <dir>) Object
##
#F Given architecture ordering qubit_order and number of qubits n
#F reorder logical qubit vector to achieve the relative ordering
#F dir = 1 is a forward reordering, dir = -1 is a backward reordering
Class(qJunc, TaggedNonTerminal, rec(
  abbrevs   := [ (l, n, dir) -> Checked(IsPosInt(n) , [l, n, dir])],
  dims      := self >> let(size := 2^self.params[2], [size, size]),
  terminate := self >> (JuncTerm(self.params[1], self.params[2], self.params[3])),
  isReal    := self >> false,
  rChildren := self >> self.params,
  from_rChildren := (self, rch) >> self.__bases__[1](rch[1], rch[2], rch[3]),
  SmallRandom := () -> Random([2..5]),
  LargeRandom := () -> Random([6..15]),
  normalizedArithCost := self >> Error("ArithCost not implemented"),
  TType := T_Complex(64)
));

##
#F GrowGroup( <arch>, <groups>, <bad> )
##
#F given an architecture and a list of qubit groupings, grow each grouping by 1,
#F not using any qubits in the bad set. Used as a helper function to grab
#F all sections of n connected qubits
##
GrowGroup := function(arch, groups, bad)
    local newgroups, g, q, es, newqs, newlocalgroups, n, group;
    newgroups := [];
    for g in groups do
        # for each group
        for q in g do
            #for each qubit in each group
            #get a list of edges
            es := GetEdges(arch, q);
            newqs := ListDifference(es, g);
            #newqs is the list of new qubits we can add to this group
            newqs := ListDifference(newqs, bad);
            # dont use any bad qubits
            newlocalgroups := Map(newqs, i -> Concatenation(g, [i]));
            Append(newgroups, newlocalgroups);
        od;
    od;
    return newgroups;
end;

##
#F FindAllSectionsOfn( <arch>, <n>, <bad> )
##
#F given an architecture and a set of off-limits qubits,
#F finds all possible size-n connected components in the architecture
#F using none of the bad qubits
FindAllSectionsOfn := function(arch, n, bad)
    local l, qub, groups, count, g;
    l := [];
    qub := 0;
    groups := [0..(Length(arch)-1)];
    groups := ListDifference(groups, bad);
    groups := Map(groups, i -> [i]);
    count := 1;
    while count < n do
        groups := GrowGroup(arch, groups, bad);
        count := count + 1;
    od;
    return groups;
end;

##
#F GenAllPartitions(<arch>, <S>)
##
#F given a list of different partitions sizes, for example S = [[3,3], [3,2]]
#F returns a list of all possible partitionings
#F for example S = [[3,3], [3,2]] will yield a list of 2 sublists,
#F the first sublist contains all possible ways of getting two connected components of 3
#F the second sublist contains all possible ways of getting a connected component of size 3 and size 2
GenAllPartitions := function (arch, S)
    local parts, groupings, s, sects, r, fact, groups, ss, result, g, idx, newgroups, bad, k;
    parts := S.groups();
    groupings := [];
    for s in parts do
        # now s is a list that contains all the needed connected subsets for the transform
        # a.k.a [3, 3]
        sects := FindAllSectionsOfn(arch, s[1], []);
        idx := 2;
        result := Map(sects, i ->[i]);
        while idx <= Length(s) do
            newgroups := [];
            # need to add a group of size g to every list in list groups
            for r in result do
                # add a size g grouping to this list
                # r is [ [1,2,3], ... ]
                bad := Flat(r);
                # don't use anything already used
                sects := FindAllSectionsOfn(arch, s[idx], bad);
                for k in sects do
                    Add(newgroups, Concatenation(r, [k]));
                od;
            od;
            result := newgroups;
            idx := idx + 1;
        od;
        #finished preparing all possible groups to satisfy the current partition
        Append(groupings, result);
    od;
    return groupings;
end;

##
#F PruneArch(<arch>, <in_use>)
##
#F take all rows and columns out of the arch adjmatrix that are not in in_use
#F and reorder rows and columns so that in_use[1] is qubit 0, in_use[2] is qubit 1, etc...
#F to achieve our recursive reordering
PruneArch := function(arch, in_use)
    local idcs, idx, j, row, newarch, u, r, newrow;
    idcs := [0..(Length(in_use)-1)];
    idx := 1;
    newarch := [];
    for u in in_use do
        row := arch[u+1]; # keep only the rows we need
        newrow := [];
        j := [1..Length(in_use)];
        j := Map(j, i -> in_use[i]);
        for r in j do
            # need to add columns back in order of in_use, and only those columns
            Add(newrow, row[r+1]);
        od;
        Add(newarch, newrow); # add rows back in the order listed
    od;
    return newarch;
end;

##
#F ReordIdx(<t>, <o>, <n>)
##
#F Helper to create all possible reorderings of the qubits, where o is the original ordering, and where
#F the qubits in list t are positioned at the upper indices of the new orderings
ReordIdx := function (t, o, n)
    local idcs, orderings, children, idx, e, diff, r, avail_idcs, reorderings, temp_orderings, tmp, child, a;
    idcs := [0..n-1];
    orderings := [];
    children := [];
    for i in idcs do # initialize
        idcs[i+1] := -1;
    od;
    idx := 1;
    for e in o do
        idcs[t[idx]+1] := o[idx];
        idx := idx + 1;
    od;
    # now need to generate all possible orderings of the rest of the qubits
    diff := ListDifference([0..n-1], o);
    avail_idcs := ListDifference([0..n-1], t);
    temp_orderings := Arrangements(diff, Length(diff));
    for tmp in temp_orderings do
        # fill in the remaining slots
        idx := 1;
        child := [];
        for e  in idcs do
            Add(child, e);
        od;
        for a in avail_idcs do
            child[a+1] := tmp[idx];
            idx := idx + 1;
        od;
        Add(orderings, child);
    od;
    return orderings;
end;

##
#F GenChild(<l>, <n>, <arch>, <S>)
##
#F Given a list of of affected qubits (l), the number of qubits in the system (n)
#F the architecture (arch) and the non-terminal to apply (S)
#F generate all possible embeddings
GenChild := function (l, n, arch, S)
    local children, possible_qubits, r, reorderings, possible, newarch, factor, mats, basequbit, forswapmat, backswapmat, subset, original_qubits, target_qubits, forjunction, backjunction, child, children;
    children := [];
    possible_qubits := GenAllPartitions(arch, S);
    # possible qubits is a list of all possible ways we can factor S into arch
    # so possible qubits, if need groups of 3 and 2 = [  [[0,1], [2,3,4]] , [[2,3], [7,8,9]], ... ]
    # for each of these factorizations, need to generate appropriate child
    # a proper child will be:
    # * SWAP proper qubits to get into the right position (canonical order)
    # * generate the proper Junction
    # * apply the transform
    # * reapply the proper Junction
    # * unSWAP the proper qubits to preserve ordering
    for factor in possible_qubits do
        # example factor = [[0, 1], [2,3,4]]
        original_qubits := [0..(Length(Flat(factor)) - 1)];
        original_qubits := Map(original_qubits, i -> l[i+1]);
        target_qubits := Flat(factor);
        reorderings := ReordIdx(target_qubits, original_qubits, n);
        # have swap matrices
        forjunction := qJunc(Flat(factor), n, 1);
        backjunction := qJunc(Flat(factor), n, -1);
        # have junctions
        # To prune arch, need to 1) eliminate all rows an columns of qubits not being used, i.e. in Flat(factor)
        # then need to rename the qubits to be 0,1,2,3,4, etc... canonical ordering with Flat(factor)
        newarch := PruneArch(arch, Flat(factor));
        for r in reorderings do
            child := (Reord(r, arch, 1) * forjunction * Tensor(S.recursive_def(newarch), I(2^(n-Length(l)))) * backjunction * Reord(r, arch, -1));
            if( VerifyPath(r, [0..n-1], arch) = true) then
                Add(children, [child]);
            fi;
        od;
    od;
    return children;
end;

##
#F ExpandTens( <l>, <n>, <S> )
##
## qEmbed terminate function. Generates a 2^n by 2^n matrix
## representing the application of Non-terminal S on the qubits in
## list l. We use canonical ordering
ExpandTens := function (l, n, S)
    local  size, swap1, swap2, trans;
    size := Length(l);
    # Generate swap matrix
    swap1 := PerfSwap([0..size-1], l, n);
    # Generate the reverse swap matrix
    swap2 := PerfSwap(Reversed([0..size-1]), Reversed(l), n);
    trans := Tensor(S(size), I(2^(n-size)));
    return swap1 * trans * swap2;
end;

##
#F qEmbed( <l>, <n>, <arch>, <Obj> ) Object
##
#F Embed the Obj Non-Terminal into the system of n qubits with given architecture arch
#F applied to the qubits in l
#F Represents a (2^n x 2^n)-matrix
Class(qEmbed, TaggedNonTerminal, rec(
  abbrevs   := [ (l, n, arch, nt) -> Checked(IsPosInt(n) , [l, n, arch, nt])],
  dims      := self >> let(size := 2^self.params[2], [size, size]),
  terminate := self >> (ExpandTens(self.params[1], self.params[2], self.params[4])),
  isReal    := self >> false,
  rChildren := self >> self.params,
  from_rChildren := (self, rch) >> self.__bases__[1](rch[1], rch[2], rch[3], rch[4]),
  recursive_def := (self, arch) >> self.__bases__[1](self.params[1], arch, self.params[2], arch, self.params[3]),
  SmallRandom := () -> Random([2..5]),
  LargeRandom := () -> Random([6..15]),
  normalizedArithCost := self >> Error("ArithCost not implemented"),
  TType := T_Complex(64)
));

##
#F PermIdx( <l>, <n> )
##
#F return an ordering of qubits indexed 0 through n-1
#F where the top |l| indices match l
PermIdx := function (l, n)
    local idcs, idx, e, tmp, diff, perms;
    idcs := [0..n-1];
    diff := ListDifference(idcs, l);
    perms := Arrangements(diff, Length(diff));
    idcs := Concatenation(l, perms[1]);
    return idcs;
end;

##
#F IsPerm( <l> )
##
#F verifies if the given ordering is a non-trivial permutation
IsPerm := function (l)
    local idcs;
    idcs := [0..(Length(l)-1)];
    if(l = idcs) then
        return 0;
    fi;
    return 1;
end;

##
#F qJunc Breakdown Rules
##
NewRulesFor(qJunc, rec(

    # Junc_Base rule
    # reduces a qJunc nonterminal to a Junc SPL object
    Junc_Base := rec (
        forTransposition := false,
        minSize          := 2,
        applicable       := (self, nt) >> (IsPerm(nt.params[1]) = 1),
        apply            := (nt, c, cnt) -> Junc( PermIdx(nt.params[1], nt.params[2]) , nt.params[3]),
    ),

    # Junc_ID rule
    # reduces a trivial qJunc nonterminal to an Identity SPL object
    Junc_Id := rec (
        forTransposition := false,
        minSize          := 2,
        applicable       := (self, nt) >> (IsPerm(nt.params[1]) = 0),
        apply            := (nt, c, cnt) -> I(2^(nt.params[2])),
    )

));

##
#F qEmbed Breakdown Rules
##
NewRulesFor(qEmbed, rec(

    # Embed_TryAll rule
    # Try every grouping possible placement on the given qubit architecture layout
    Embed_TryAll := rec (
        forTransposition := false,
        minSize          := 1,
        applicable       := (self, nt) >> (nt.params[3] <> [] and nt.params[1] <> [] and nt.params[2] >= 1),
        children         := nt -> List( GenChild(nt.params[1], nt.params[2], nt.params[3], nt.params[4]) ),
        apply            := (nt, c, cnt) -> c[1],
    )

));

max_stars_repo_name: spiral-software/spiral-package-quantum

max_issues_repo_name: spiral-software/spiral-package-quantum

max_forks_repo_name: spiral-software/spiral-package-quantum


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

# ==========================================================================
# Mat
# ==========================================================================
Class(Mat, BaseMat, rec(
    new := (self, M) >> Checked(IsMat(M),
	SPL(WithBases(self,
		rec( element    := M,
		     dimensions := DimensionsMat(M) )))),
    #-----------------------------------------------------------------------
    dims := self >> DimensionsMat(self.element),
    #-----------------------------------------------------------------------
    isPermutation := False,
    #-----------------------------------------------------------------------
    isReal := self >> ForAll(self.element, r -> ForAll(r, x -> IsRealNumber(x))),
    #-----------------------------------------------------------------------
    toAMat := self >> AMatMat(List(self.element, r -> List(r, EvalScalar))),
    #-----------------------------------------------------------------------
    transpose := self >>  # we use CopyFields to copy all fields of self
        CopyFields(self, rec(element := TransposedMat(self.element),
		          dimensions := Reversed(self.dimensions))),
    transpose := self >>  # we use CopyFields to copy all fields of self
        CopyFields(self, rec(element := self.element ^ -1,
		          dimensions := Reversed(self.dimensions))),
    conjTranspose := self >>  # we use CopyFields to copy all fields of self
        CopyFields(self, rec(element := MapMat(TransposedMat(self.element), conj),
		          dimensions := Reversed(self.dimensions))),

    #-----------------------------------------------------------------------
    arithmeticCost := meth(self, costMul, costAddMul)
        local cost, row, nz;
	cost := costMul(0) - costMul(0); # will work even when costMul(0) <> 0
	for row in self.element do
	    nz := Filtered(row, x -> x<>0);
	    if Length(nz) > 0 then
		cost := cost + costMul(nz[1])
		             + Sum(nz{[2..Length(nz)]}, x -> costAddMul(x));
	    fi;
	od;
	return cost;
    end,
));


text:
#############################################################################
##
#W  listops.gi             automgrp package                    Yevgen Muntyan
#W                                                             Dmytro Savchuk
##
#Y  Copyright (C) 2003 - 2018 Yevgen Muntyan, Dmytro Savchuk
##

###############################################################################
##
##  AG_IsCorrectAutomatonList( <list>, <invertible> )
##
InstallGlobalFunction(AG_IsCorrectAutomatonList,
function(list, invertible)
  local len, deg, i, j, sym, semi;

  if not IsDenseList(list) then
    return false;
  fi;

  len := Length(list);
  if len = 0 then
    return false;
  fi;

  for i in [1..len] do
    if not IsDenseList(list[i]) then
      return false;
    fi;
    if Length(list[i]) <> Length(list[1]) then
      return false;
    fi;
  od;

  deg := Length(list[1]) - 1;
  if deg < 1 then
    return false;
  fi;

  sym := SymmetricGroup(deg);
  semi := FullTransformationSemigroup(deg);

  for i in [1..len] do
    for j in [1..deg] do
      if not IsInt(list[i][j]) then
        return false;
      fi;
      if list[i][j] > len or list[i][j] < 1 then
        return false;
      fi;
    od;

    if not list[i][deg + 1] in sym then
      if not list[i][deg + 1] in semi then
        return false;
      fi;
      if invertible and list[i][deg + 1]^-1=fail then
        return false;
      fi;
    fi;
  od;

  return true;
end);

###############################################################################
##
##  AG_IsCorrectRecurList( <list>, <invertible> )
##
InstallGlobalFunction(AG_IsCorrectRecurList,
function(list, invertible)
  local len, deg, i, j, k, sym, semi, inv_states;

  if not IsDenseList(list) then
    return false;
  fi;

  len := Length(list);
  if len = 0 then
    return false;
  fi;

  for i in [1..len] do
    if not IsDenseList(list[i]) then
      return false;
    fi;
    if Length(list[i]) <> Length(list[1]) then
      return false;
    fi;
  od;

  deg := Length(list[1]) - 1;
  if deg < 2 then
    return false;
  fi;

  sym := SymmetricGroup(deg);
  semi := FullTransformationSemigroup(deg);

  for i in [1..len] do
    for j in [1..deg] do
      if IsInt(list[i][j]) then
        if list[i][j] > len or list[i][j] < -len or list[i][j] = 0 then
          return false;
        fi;
      elif IsList(list[i][j]) then
        if not IsDenseList(list[i][j]) then
          return false;
        fi;
        for k in list[i][j] do
          if (not IsInt(k)) or k > len or k < -len or k = 0 then
            return false;
          fi;
        od;
      else
        return false;
      fi;
    od;

    # Check that everything is correct here
    if (not IsPerm(list[i][deg + 1])) and (not IsTransformation(list[i][deg + 1])) then
      return false;
    elif LargestMovedPoint(list[i][deg + 1]) > deg then
      return false;
    elif IsTransformation(list[i][deg + 1]) and invertible and list[i][deg + 1]^-1=fail then
      return false;
    fi;
  od;

#  check if there is x^-1 in the list, while x is not invertible
  inv_states:=[];
  for i in [1..len] do
    if AG_IsInvertibleStateInList(i,list) then Add(inv_states,i); fi;
  od;

  for i in [1..len] do
    for j in [1..deg] do
      if IsInt(list[i][j]) then
        if list[i][j]<0 and not -list[i][j] in inv_states then
          return false;
        fi;
      else
        for k in list[i][j] do
          if k<0 and not -k in inv_states then
            return false;
          fi;
        od;
      fi;
    od;
  od;

  return true;
end);

###############################################################################
##
##  AG_ConnectedStatesInList(state, list)
##
##  Returns list of states which are reachable from given state,
##  it does not check correctness of arguments
##
InstallGlobalFunction(AG_ConnectedStatesInList,
function(state, list)
  local i, j, s, d, to_check, checked;

  d := Length(list[1]) - 1;

  to_check := [state];
  checked := [];

  while Length(to_check) <> 0 do
    for s in to_check do
      for i in [1..d] do
        if IsList(list[s][i]) then
          for j in AsSet(List(list[s][i],AbsInt)) do
            if (not j in checked) and (not j in to_check) then
              to_check := Union(to_check, [j]);
            fi;
          od;
        else
          if (not AbsInt(list[s][i]) in checked) and (not AbsInt(list[s][i]) in to_check) then
            to_check := Union(to_check, [AbsInt(list[s][i])]);
          fi;
        fi;
      od;
      checked := Union(checked, [s]);
      to_check := Difference(to_check, [s]);
    od;
  od;

  return checked;
end);

###############################################################################
##
##  AG_IsTrivialStateInList( <state>, <list>)
##
##  Checks whether given state is trivial.
##  Does not check correctness of arguments.
##
InstallGlobalFunction(AG_IsTrivialStateInList,
function(state, list)
  local deg;
  deg := Length(list[1]) - 1;
  # IsOne works for Transformation's
  return ForAll(AG_ConnectedStatesInList(state, list),
                s -> IsOne(list[s][deg+1]));
end);

###############################################################################
##
##  AG_IsObviouslyTrivialStateInList( <state>, <list>)
##
##  Checks whether given state is obviously trivial.
##  Works for lists generating self-similar groups.
##  Returns `true' if <state>=(*,...,*)(), where
##  * could be either +-<state> or [+-<state>], or [].
##
InstallGlobalFunction(AG_IsObviouslyTrivialStateInList,
function(state, list)
  local deg, check;

  check := function(s)
    if IsInt(s) then return state=AbsInt(s);
                else return s=[] or (Length(s)=1 and state=AbsInt(s[1]));
    fi;
  end;

  deg := Length(list[1]) - 1;
  if not IsOne(list[state][deg+1]) then return false; fi;
  # IsOne works for Transformation's
  return ForAll(list[state]{[1..deg]}, check);
end);

###############################################################################
##
##  AG_IsInvertibleStateInList( <state>, <list> )
##
##  Checks whether given state is invertible.
##  Does not check correctness of arguments.
##
InstallGlobalFunction(AG_IsInvertibleStateInList,
function(state, list)
  local deg;
  deg := Length(list[1]) - 1;
  return ForAll(AG_ConnectedStatesInList(state, list),
                s -> (list[s][deg+1]^-1<>fail));
end);

###############################################################################
##
##  AG_AreEquivalentStatesInList( <state1>, <state2>, <list> )
##
##  Checks whether two given states are equivalent.
##  Does not check correctness of arguments.
##
InstallGlobalFunction(AG_AreEquivalentStatesInList,
function(state1, state2, list)
  local d, checked_pairs, pos, s1, s2, np, i;

  d := Length(list[1]) - 1;
  checked_pairs := [[state1, state2]];
  pos := 0;

  while Length(checked_pairs) <> pos do
    pos := pos + 1;
    s1 := checked_pairs[pos][1];
    s2 := checked_pairs[pos][2];

    if list[s1][d+1] <> list[s2][d+1] then
      return false;
    fi;

    for i in [1..d] do
      np := [list[s1][i], list[s2][i]];
      if not np in checked_pairs then
        checked_pairs := Concatenation(checked_pairs, [np]);
      fi;
    od;
  od;

  return true;
end);

###############################################################################
##
##  AG_AreEquivalentStatesInLists( <state1>, <state2>, <list1>, <list2>)
##
##  Checks whether two given states in different lists are equivalent.
##  Does not check correctness of arguments.
##
InstallGlobalFunction(AG_AreEquivalentStatesInLists,
function(state1, state2, list1, list2)
  local d, checked_pairs, pos, s1, s2, np, i;

  d := Length(list1[1]) - 1;
  checked_pairs := [[state1, state2]];
  pos := 0;

  while Length(checked_pairs) <> pos do
    pos := pos + 1;
    s1 := checked_pairs[pos][1];
    s2 := checked_pairs[pos][2];

    if list1[s1][d+1] <> list2[s2][d+1] then
      return false;
    fi;

    for i in [1..d] do
      np := [list1[s1][i], list2[s2][i]];
      if not np in checked_pairs then
        checked_pairs := Concatenation(checked_pairs, [np]);
      fi;
    od;
  od;

  return true;
end);

###############################################################################
##
##  AG_ReducedAutomatonInList( <list> )
##
##  Returns [new_list, list_of_states, old_states] where new_list is a new list
##  which represents reduced form of given automaton, i-th elmt of list_of_states
##  is the number of i-th state of new automaton in the old one.
##  old_states[i] is the number of state which corresponds to the i-th state
##  of the original automaton.
##
##  First state of returned list is always first state of given one.
##  It does not remove trivial state, so it's not really "reduced automaton",
##  it just removes equivalent states.
##  TODO: write such function which removes trivial state
##
##  Does not check correctness of list.
##
##  WARNING: do *NOT* change it.
##
InstallGlobalFunction(AG_ReducedAutomatonInList,
function(list)
  local   i, n, triv_states, equiv_classes, checked_states, s, s1, s2,
          eq_cl, eq_cl_1, eq_cl_2, are_equiv, eq_cl_reprs,
          new_states, new_list, deg,
          reduced_automaton, state, states_reprs;

  n := Length(list);
  triv_states := [];
  equiv_classes := [];
  checked_states := [];
  deg := Length(list[1]) - 1;

  for s in [1..n] do
      if AG_IsTrivialStateInList(s, list) then
          triv_states := Union(triv_states, [s]);
      fi;
  od;

  equiv_classes:=[triv_states];
  for s1 in Difference([1..n], triv_states) do
  for s2 in Difference([s1+1..n], triv_states) do
    are_equiv := AG_AreEquivalentStatesInList(s1, s2, list);

    if s1 in checked_states then
      for eq_cl in equiv_classes do
        if s1 in eq_cl then
          eq_cl_1 := StructuralCopy(eq_cl);
          break; fi; od;
    else
      equiv_classes := Union(equiv_classes, [[s1]]);
      eq_cl_1 := [s1];
      checked_states := Union(checked_states, [s1]);
    fi;
    if s2 in checked_states then
      for eq_cl in equiv_classes do
        if s2 in eq_cl then
          eq_cl_2 := StructuralCopy(eq_cl);
          break; fi; od;
    else
      equiv_classes := Union(equiv_classes, [[s2]]);
      eq_cl_2 := [s2];
      checked_states := Union(checked_states, [s2]);
    fi;

    if are_equiv then
      equiv_classes := Difference(equiv_classes, [eq_cl_1, eq_cl_2]);
      equiv_classes := Union(equiv_classes, [Union(eq_cl_1, eq_cl_2)]);
    fi;
  od;
  od;
  states_reprs := [1..n];
  for eq_cl in equiv_classes do
    for s in eq_cl do
      states_reprs[s] := Minimum(eq_cl);
    od;
  od;

  new_states := Set(states_reprs);
  new_list := [];

  for s in new_states do
    state := [];
    state[deg+1] := list[s][deg+1];
    for i in [1..deg] do
      state[i] := Position(new_states, states_reprs[list[s][i]]);
    od;
    new_list := Concatenation(new_list, [state]);
  od;

  return [new_list, new_states, List([1..n], i -> Position(new_states, states_reprs[i]))];
end);

###############################################################################
##
##  AG_MinimalSubAutomatonInlist(<states>, <list>)
##
##  Returns list representation of automaton given by <list> which is minimal
##  subatomaton of automaton containing states <states>.
##
##  Does not check correctness of list.
##
InstallGlobalFunction(AG_MinimalSubAutomatonInlist,
function(states, list)
  local s, new_states, state, new_list, i, deg;

  new_states := [];
  for s in states do
    new_states := Union(new_states, AG_ConnectedStatesInList(s, list));
  od;

  new_list := [];
  deg := Length(list[1]) - 1;

  for s in new_states do
    state := [];
    for i in [1..deg] do
      state[i] := Position(new_states, list[s][i]);
    od;
    state[deg+1] := list[s][deg+1];
    new_list := Concatenation(new_list, [state]);
  od;

  return [new_list, new_states];
end);

###############################################################################
##
##  AG_PermuteStatesInList(<list>, <perm>)
##
##  Does not check correctness of arguments.
##
InstallGlobalFunction(AG_PermuteStatesInList,
function(list, perm)
  local new_list, i, j, deg;

  deg := Length(list[1]) - 1;
  new_list := [];
  for i in [1..Length(list)] do
    new_list[i^perm] := [];
    for j in [1..deg] do
      new_list[i^perm][j] := list[i][j]^perm;
    od;
    new_list[i^perm][deg+1] := list[i][deg+1];
  od;

  return new_list;
end);

###############################################################################
##
##  AG_WordStateInList(<w>, <s>, <list>, <reduce>, <trivstate>)
##
##  It's ProjectWord from selfs.g
##  Does not check correctness of arguments.
##
InstallGlobalFunction(AG_WordStateInList,
function(w, s, list, reduce, trivstate)
  local i, perm, d, proj, red, reduce_word;

  reduce_word := function(v)
    local len, red, x;
    len := 0;
    red := [];
    for x in v do
      if x <> trivstate then
        if len <> 0 and x = -red[len] then
          Remove(red, len);
          len := len - 1;
        else
          Add(red, x);
          len := len + 1;
        fi;
      fi;
    od;
    return red;
  end;

  d := Length(list[1])-1;
  proj := [];
  perm := ();
  for i in [1..Length(w)] do
    Add(proj, list[w[i]][s^perm]);
    perm := perm * list[w[i]][d+1];
  od;
  if reduce then
    return reduce_word(proj);
  else
    return proj;
  fi;
end);

###############################################################################
##
##  AG_WordStateAndPermInList(<w>, <s>, <list>)
##
##  Does not check correctness of arguments.
##
InstallGlobalFunction(AG_WordStateAndPermInList,
function(w, s, list)
  local i, perm, perm_res, new_state, d, proj;
  d := Length(list[1])-1;
  proj := [];
  perm := ();
  perm_res := ();
  for i in [1..Length(w)] do
    new_state := list[w[i]][s^perm];
    Add(proj, new_state);
    perm := perm * list[w[i]][d+1];
    perm_res := perm_res * list[new_state][d+1];
  od;
  return [proj, perm_res];
end);

###############################################################################
##
##  AG_ImageOfVertexInList(<list>, <init>, <vertex>)
##
##  Does not check correctness of arguments.
##
InstallGlobalFunction(AG_ImageOfVertexInList,
function(list, s, seq)
  local deg, img, x;

  deg := Length(list[1]) - 1;
  img := [];
  for x in seq do
      Add(img, x^list[s][deg+1]);
      s := list[s][x];
  od;

  return img;
end);

###############################################################################
##
##  AG_DiagonalPowerInList(<list>, <n>)
##
InstallGlobalFunction(AG_DiagonalPowerInList,
function(list, n, names)
  local d, nlist, nd, nalph, nstates, nperm,
        i, j, k, letter, n_letter, n_state, state,
        nnames;

  d := Length(list[1]) - 1;
  nd := d ^ n;
  nalph := Tuples([1..d], n);
  nstates := Tuples([1..Length(list)], n);
  nlist := List([1..Length(nstates)], i -> []);
  nnames := List(nstates, s->List(s, i->names[i]));

  for i in [1..Length(nlist)] do
    nperm := [];
    state := nstates[i];
    for j in [1..nd] do
      letter := nalph[j];
      n_letter := [];
      n_state := [];
      for k in [1..n] do
        n_letter[k] := letter[k]^list[state[k]][d+1];
        n_state[k] := list[state[k]][letter[k]];
      od;
      nperm[j] := n_letter;
      nlist[i][j] := Position(nstates, n_state);
    od;
    nlist[i][nd+1] := PermListList(nalph, nperm);
  od;

  nnames := List(nnames, l->Concatenation(l));
  return [nlist, nnames];
end);

###############################################################################
##
##  AG_MultAlphabetInList(<list>, <n>)
##
InstallGlobalFunction(AG_MultAlphabetInList,
function(list, n)
  local d, nlist, nd, nalph, nperm,
        i, j, k, letter, n_letter, st;

  d := Length(list[1]) - 1;
  nd := d ^ n;
  nalph := Tuples([1..d], n);
  nlist := List(list, i -> []);

  for i in [1..Length(nlist)] do
    nperm := [];
    for j in [1..Length(nalph)] do
      letter := nalph[j];
      n_letter := [];
      st := i;
      for k in [1..n] do
        Add(n_letter, letter[k]^list[st][d+1]);
        st := list[st][letter[k]];
      od;
      nlist[i][j] := st;
      nperm[j] := n_letter;
    od;
    nlist[i][nd+1] := PermListList(nalph, nperm);
  od;

  return nlist;
end);

###############################################################################
##
##  AG_HasDualInList(<list>)
##
InstallGlobalFunction(AG_HasDualInList,
function(list)
  local i, j, p, d, n;
  d := Length(list[1]) - 1;
  n := Length(list);
  for i in [1..d] do
    p := [];
    for j in [1..n] do
      p[j] := list[j][i];
    od;
    if PermListList([1..n], p) = fail then
      return false;
    fi;
  od;
  return true;
end);

###############################################################################
##
##  AG_DualAutomatonList(<list>)
##
InstallGlobalFunction(AG_DualAutomatonList,
function(list)
  local dual, d, n;
  d := Length(list[1]) - 1;
  n := Length(list);
  return List([1..d], i -> Concatenation(List([1..n], j -> i^list[j][d+1]),
    [PermList(List([1..n], j -> list[j][i]))]));
end);

###############################################################################
##
##  AG_HasDualOfInverseInList(<list>)
##
InstallGlobalFunction(AG_HasDualOfInverseInList,
function(list)
  return AG_HasDualInList(AG_InverseAutomatonList(list));
end);

###############################################################################
##
##  AG_InverseAutomatonList(<list>)
##
InstallGlobalFunction(AG_InverseAutomatonList,
function(list)
  local inv, d, i;
  d := Length(list[1]) - 1;
  inv := List(list, l -> Permuted(l, l[d+1]));
  for i in [1..Length(list)] do inv[i][d+1] := inv[i][d+1]^-1; od;
  return inv;
end);

#E

max_stars_repo_name: gap-packages/automgrp

max_issues_repo_name: gap-packages/automgrp

max_forks_repo_name: gap-packages/automgrp


text:
gap>List(SymmetricGroup(4), p -> Permuted([1 .. 4], p));
perms(4);
[ [ 1, 2, 3, 4 ], [ 4, 2, 3, 1 ], [ 2, 4, 3, 1 ], [ 3, 2, 4, 1 ], [ 1, 4, 3, 2 ], [ 4, 1, 3, 2 ], [ 2, 1, 3, 4 ],
  [ 3, 1, 4, 2 ], [ 1, 3, 4, 2 ], [ 4, 3, 1, 2 ], [ 2, 3, 1, 4 ], [ 3, 4, 1, 2 ], [ 1, 2, 4, 3 ], [ 4, 2, 1, 3 ],
  [ 2, 4, 1, 3 ], [ 3, 2, 1, 4 ], [ 1, 4, 2, 3 ], [ 4, 1, 2, 3 ], [ 2, 1, 4, 3 ], [ 3, 1, 2, 4 ], [ 1, 3, 2, 4 ],
  [ 4, 3, 2, 1 ], [ 2, 3, 4, 1 ], [ 3, 4, 2, 1 ] ]


text:
MultiFactorial := function(n, k)
    local r;
    r := 1;
    while n > 1 do
        r := r*n;
        n := n - k;
    od;
    return r;
end;

PrintArray(List([1 .. 10], n -> List([1 .. 5], k -> MultiFactorial(n, k))));
[ [        1,        1,        1,        1,        1 ],
  [        2,        2,        2,        2,        2 ],
  [        6,        3,        3,        3,        3 ],
  [       24,        8,        4,        4,        4 ],
  [      120,       15,       10,        5,        5 ],
  [      720,       48,       18,       12,        6 ],
  [     5040,      105,       28,       21,       14 ],
  [    40320,      384,       80,       32,       24 ],
  [   362880,      945,      162,       45,       36 ],
  [  3628800,     3840,      280,      120,       50 ] ]


text:
# Solution in '''RPN'''
check := function(x, y, z)
	local r, c, s, i, j, k, a, b, p;
	i := 0;
	j := 0;
	k := 0;
	s := [ ];
	r := "";
	for c in z do
		if c = 'x' then
			i := i + 1;
			k := k + 1;
			s[k] := x[i];
			Append(r, String(x[i]));
		else
			j := j + 1;
			b := s[k];
			k := k - 1;
			a := s[k];
			p := y[j];
			r[Size(r) + 1] := p;
			if p = '+' then
				a := a + b;
			elif p = '-' then
				a := a - b;
			elif p = '*' then
				a := a * b;
			elif p = '/' then
				if b = 0 then
					continue;
				else
					a := a / b;
				fi;
			else
				return fail;
			fi;
			s[k] := a;
		fi;
	od;
	if s[1] = 24 then
		return r;
	else
		return fail;
	fi;
end;

Player24 := function(digits)
	local u, v, w, x, y, z, r;
	u := PermutationsList(digits);
	v := Tuples("+-*/", 3);
	w := ["xx*x*x*", "xx*xx**", "xxx**x*", "xxx*x**", "xxxx***"];
	for x in u do
		for y in v do
			for z in w do
				r := check(x, y, z);
				if r <> fail then
					return r;
				fi;
			od;
		od;
	od;
	return fail;
end;

Player24([1,2,7,7]);
# "77*1-2/"
Player24([9,8,7,6]);
# "68*97-/"
Player24([1,1,7,7]);
# fail

# Solutions with only one distinct digit are found only for 3, 4, 5, 6:
Player24([3,3,3,3]);
# "33*3*3-"
Player24([4,4,4,4]);
# "44*4+4+"
Player24([5,5,5,5]);
# "55*55/-"
Player24([6,6,6,6]);
# "66*66+-"

# A tricky one:
Player24([3,3,8,8]);
"8383/-/"


text:
--
-- An instance of this template must have a $Export section and the export_terminals option
--
-- Macros that may be redefined in an instance of this template
--
--     $eof_token
--     $additional_interfaces
--     $super_stream_class -- subclass com.ibm.lpg.LpgLexStream for getKind
--     $prs_stream_class -- use /.PrsStream./ if not subclassing
--     $super_class
--
-- B E G I N N I N G   O F   T E M P L A T E   LexerTemplateF
--
%Options programming_language=java,margin=4
%Options table
%options action-block=("*.java", "/.", "./")
%options ParseTable=lpg.runtime.ParseTable
%Options prefix=Char_

--
-- This template requires that the name of the EOF token be set
-- to EOF and that the prefix be "Char_" to be consistent with
-- KeywordTemplateD.
--
%Eof
    EOF
%End

--
-- This template also requires that the name of the parser EOF
-- Token to be exported be set to EOF_TOKEN
--
%Export
    EOF_TOKEN
%End

%Define
    --
    -- Macros that are be needed in an instance of this template
    --
    $eof_token /.$_EOF_TOKEN./

    $additional_interfaces /../
    $super_stream_class /.$file_prefix$LpgLexStream./
    $prs_stream_class /.IPrsStream./
    $super_class /.Object./

    $prs_stream /. // macro prs_stream is deprecated. Use function getPrsStream
                  getPrsStream()./
    $setSym1 /. // macro setSym1 is deprecated. Use function setResult
               lexParser.setSym1./
    $setResult /. // macro setResult is deprecated. Use function setResult
                 lexParser.setSym1./
    $getSym /. // macro getSym is deprecated. Use function getLastToken
              lexParser.getSym./
    $getToken /. // macro getToken is deprecated. Use function getToken
                lexParser.getToken./
    $getLeftSpan /. // macro getLeftSpan is deprecated. Use function getLeftSpan
                   lexParser.getFirstToken./
    $getRightSpan /. // macro getRightSpan is deprecated. Use function getRightSpan
                    lexParser.getLastToken./

    --
    -- Macros useful for specifying actions
    --
    $Header
    /.
                //
                // Rule $rule_number:  $rule_text
                //
                ./

    $DefaultAction
    /.$Header$case $rule_number: { ./

    $BeginAction /.$DefaultAction./

    $EndAction
    /.            break;
                }./

    $BeginJava
    /.$BeginAction
                $symbol_declarations./

    $EndJava /.$EndAction./

    $NoAction
    /.$Header$case $rule_number:
                    break; ./

    $BeginActions
    /.
        public void ruleAction(int ruleNumber)
        {
            switch(ruleNumber)
            {./

    $SplitActions
    /.
                    default:
                        ruleAction$rule_number(ruleNumber);
                        break;
                }
                return;
            }

            public void ruleAction$rule_number(int ruleNumber)
            {
                switch (ruleNumber)
                {./

    $EndActions
    /.
                default:
                    break;
            }
            return;
        }./
%End

%Globals
    /.import lpg.runtime.*;
    ./
%End

%Headers
    /.
    public class $action_type extends $super_class implements RuleAction$additional_interfaces
    {
        private $super_stream_class lexStream;

        private static ParseTable prs = new $prs_type();
        public ParseTable getParseTable() { return prs; }

        private LexParser lexParser = new LexParser();
        public LexParser getParser() { return lexParser; }

        public int getToken(int i) { return lexParser.getToken(i); }
        public int getRhsFirstTokenIndex(int i) { return lexParser.getFirstToken(i); }
        public int getRhsLastTokenIndex(int i) { return lexParser.getLastToken(i); }

        public int getLeftSpan() { return lexParser.getToken(1); }
        public int getRightSpan() { return lexParser.getLastToken(); }

        public void resetKeywordLexer()
        {
            if (kwLexer == null)
                  this.kwLexer = new $kw_lexer_class(lexStream.getInputChars(), $_IDENTIFIER);
            else this.kwLexer.setInputChars(lexStream.getInputChars());
        }

        public void reset(String filename, int tab) throws java.io.IOException
        {
            lexStream = new $super_stream_class(filename, tab);
            lexParser.reset((ILexStream) lexStream, prs, (RuleAction) this);
            resetKeywordLexer();
        }

        public void reset(char[] input_chars, String filename)
        {
            reset(input_chars, filename, 1);
        }

        public void reset(char[] input_chars, String filename, int tab)
        {
            lexStream = new $super_stream_class(input_chars, filename, tab);
            lexParser.reset((ILexStream) lexStream, prs, (RuleAction) this);
            resetKeywordLexer();
        }

        public $action_type(String filename, int tab) throws java.io.IOException
        {
            reset(filename, tab);
        }

        public $action_type(char[] input_chars, String filename, int tab)
        {
            reset(input_chars, filename, tab);
        }

        public $action_type(char[] input_chars, String filename)
        {
            reset(input_chars, filename, 1);
        }

        public $action_type() {}

        public ILexStream getILexStream() { return lexStream; }

        /**
         * @deprecated replaced by {@link #getILexStream()}
         */
        public ILexStream getLexStream() { return lexStream; }

        private void initializeLexer($prs_stream_class prsStream, int start_offset, int end_offset)
        {
            if (lexStream.getInputChars() == null)
                throw new NullPointerException("LexStream was not initialized");
            lexStream.setPrsStream(prsStream);
            prsStream.makeToken(start_offset, end_offset, 0); // Token list must start with a bad token
        }

        private void addEOF($prs_stream_class prsStream, int end_offset)
        {
            prsStream.makeToken(end_offset, end_offset, $eof_token); // and end with the end of file token
            prsStream.setStreamLength(prsStream.getSize());
        }

        public void lexer($prs_stream_class prsStream)
        {
            lexer(null, prsStream);
        }

        public void lexer(Monitor monitor, $prs_stream_class prsStream)
        {
            initializeLexer(prsStream, 0, -1);
            lexParser.parseCharacters(monitor);  // Lex the input characters
            addEOF(prsStream, lexStream.getStreamIndex());
        }

        public void lexer($prs_stream_class prsStream, int start_offset, int end_offset)
        {
            lexer(null, prsStream, start_offset, end_offset);
        }

        public void lexer(Monitor monitor, $prs_stream_class prsStream, int start_offset, int end_offset)
        {
            if (start_offset <= 1)
                 initializeLexer(prsStream, 0, -1);
            else initializeLexer(prsStream, start_offset - 1, start_offset - 1);

            lexParser.parseCharacters(monitor, start_offset, end_offset);

            addEOF(prsStream, (end_offset >= lexStream.getStreamIndex() ? lexStream.getStreamIndex() : end_offset + 1));
        }

        public IPrsStream.Range incrementalLexer(char[] input_chars, int start_change_offset, int end_change_offset) {
            int offset_adjustment = input_chars.length - lexStream.getStreamLength();
//*System.out.println("The offset adjustment is " + offset_adjustment);
            if (start_change_offset <= 0 && start_change_offset < input_chars.length)
                throw new IndexOutOfBoundsException("The start offset " + start_change_offset +
                                                    " is out of bounds for range 0.." + (input_chars.length - 1));
            if (end_change_offset <= 0 && end_change_offset < input_chars.length)
                throw new IndexOutOfBoundsException("The end offset " + end_change_offset +
                                                    " is out of bounds for range 0.." + (input_chars.length - 1));

            //
            // Get the potential list of tokens to be rescanned
            //
            java.util.ArrayList<IToken> affected_tokens = lexStream.getIPrsStream().incrementalResetAtCharacterOffset(start_change_offset);

            //
            // If the change occured between the first two affected tokens (or adjunct) and not immediately
            // on the characted after the first token (or adjunct), restart the scanning after the first
            // affected token. Otherwise, rescan the first token.
            //
            int affected_index = 0;
            int repair_offset = start_change_offset;
            if (affected_tokens.size() > 0) {
                if (affected_tokens.get(0).getEndOffset() + 1 < start_change_offset) {
                     repair_offset = affected_tokens.get(0).getEndOffset() + 1;
                     if (affected_tokens.get(0) instanceof Token)
                         lexStream.getIPrsStream().makeToken(affected_tokens.get(0), 0);
                    else lexStream.getIPrsStream().makeAdjunct(affected_tokens.get(0), 0);
                    affected_index++;
                }
                else repair_offset = affected_tokens.get(0).getStartOffset();
            }

            lexStream.setInputChars(input_chars);
            lexStream.setStreamLength(input_chars.length);
            lexStream.computeLineOffsets(repair_offset);

            int first_new_token_index = lexStream.getIPrsStream().getTokens().size(),
                first_new_adjunct_index = lexStream.getIPrsStream().getAdjuncts().size();

            resetKeywordLexer();
            lexParser.resetTokenStream(repair_offset);
            int next_offset;
            do {
//*System.out.println("Scanning token starting at " + (lexStream.peek() - 1));
                next_offset = lexParser.incrementalParseCharacters();
//*System.out.print("***Remaining string: \"");
//*for (int i = next_offset; i < input_chars.length; i++)
//*System.out.print(input_chars[i]);
//*System.out.println("\"");
                while (affected_index < affected_tokens.size() &&
                       affected_tokens.get(affected_index).getStartOffset() + offset_adjustment < next_offset)
//*{
//*System.out.println("---Skipping token " + affected_index + ": \"" + affected_tokens.get(affected_index).toString() +
//*"\" starting at adjusted offset " + (affected_tokens.get(affected_index).getStartOffset() + offset_adjustment));
                    affected_index++;
//*}
            } while(next_offset <= end_change_offset &&          // still in the damage region and ...
                    (affected_index < affected_tokens.size() &&  // not resynchronized with a token in the list of affected tokens
                     affected_tokens.get(affected_index).getStartOffset() + offset_adjustment != next_offset));

            //
            // If any new tokens were added, compute the first and the last one.
            //
            IToken first_new_token = null,
                   last_new_token = null;
            if (first_new_token_index < lexStream.getIPrsStream().getTokens().size()) {
                first_new_token = lexStream.getIPrsStream().getTokenAt(first_new_token_index);
                last_new_token = lexStream.getIPrsStream().getTokenAt(lexStream.getIPrsStream().getTokens().size() - 1);
            }
            //
            // If an adjunct was added prior to the first real token, chose it instead as the first token.
            // Similarly, if adjucts were added after the last token, chose the last adjunct added as the last token.
            //
            if (first_new_adjunct_index < lexStream.getIPrsStream().getAdjuncts().size()) {
                if (first_new_token == null ||
                    lexStream.getIPrsStream().getAdjunctAt(first_new_adjunct_index).getStartOffset() <
                    first_new_token.getStartOffset()) {
                    first_new_token = lexStream.getIPrsStream().getAdjunctAt(first_new_adjunct_index);
                }
                if (last_new_token == null ||
                    lexStream.getIPrsStream().getAdjunctAt(lexStream.getIPrsStream().getAdjuncts().size() - 1).getEndOffset() >
                    last_new_token.getEndOffset()) {
                    last_new_token = lexStream.getIPrsStream().getAdjunctAt(lexStream.getIPrsStream().getAdjuncts().size() - 1);
                }
            }

            //
            // For all remainng tokens (and adjuncts) in the list of affected tokens add them to the
            // list of tokens (and adjuncts).
            //
            for (int i = affected_index; i < affected_tokens.size(); i++) {
                if (affected_tokens.get(i) instanceof Token)
                     lexStream.getIPrsStream().makeToken(affected_tokens.get(i), offset_adjustment);
                else lexStream.getIPrsStream().makeAdjunct(affected_tokens.get(i), offset_adjustment);
//*System.out.println("+++Added affected token " + i + ": \"" + affected_tokens.get(i).toString() +
//*"\" starting at adjusted offset " + (affected_tokens.get(i).getStartOffset() + offset_adjustment));
            }

            return new IPrsStream.Range(lexStream.getIPrsStream(), first_new_token, last_new_token);
        }

        /**
         * If a parse stream was not passed to this Lexical analyser then we
         * simply report a lexical error. Otherwise, we produce a bad token.
         */
        public void reportLexicalError(int startLoc, int endLoc) {
            IPrsStream prs_stream = lexStream.getIPrsStream();
            if (prs_stream == null)
                lexStream.reportLexicalError(startLoc, endLoc);
            else {
                //
                // Remove any token that may have been processed that fall in the
                // range of the lexical error... then add one error token that spans
                // the error range.
                //
                for (int i = prs_stream.getSize() - 1; i > 0; i--) {
                    if (prs_stream.getStartOffset(i) >= startLoc)
                         prs_stream.removeLastToken();
                    else break;
                }
                prs_stream.makeToken(startLoc, endLoc, 0); // add an error token to the prsStream
            }
        }
    ./
%End

%Rules
    /.$BeginActions./
%End

%Trailers
    /.
        $EndActions
    }
    ./
%End

--
-- E N D   O F   T E M P L A T E
--

max_stars_repo_name: kuafuwang/LPG-VScode

max_issues_repo_name: kuafuwang/LPG-VScode

max_forks_repo_name: kuafuwang/LPG-VScode


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

Class(CCMContextScratchUnparserProg, CScratchUnparserProg, rec(
	par_exec := (self,o,i,is) >> Print(Blanks(i), "parallel(&sub_cpu) \n",
                              Blanks(i), "{\n", self(o.cmds[1],i+is,is),
                              Blanks(i+is), "if(isFinished) {\n",
                              Blanks(i+is+is), "setFinished;\n",
                              Blanks(i), self(o.cmds[2],i+is,is),
                              Blanks(i+is),"}\n",
                              Blanks(i),"}\n"),
));


text:
--
-- An LPG Parser Template Using lpg.jar
--
-- Macros that may be redefined in an instance of this template
--
--     $additional_interfaces
--     $super_stream_class
--
-- B E G I N N I N G   O F   T E M P L A T E   dtUnifiedTemplateF
--
%Options programming_language=csharp
%Options table
%Options margin=4
%Options prefix=Char_
%Options action-block=("*.cs", "/.", "./")
%Options ParseTable=LPG2.Runtime.ParseTable

--
-- The EOF and ERROR symbols are assigned a default here as a
-- convenience.
--
%EOF
    EOF
%End

%Define
    $Header
    /.
                //
                // Rule $rule_number:  $rule_text
                //
                ./

    $BeginAction
    /.$Header$case $rule_number: {./

    $EndAction
    /.          break;
                }./

    $BeginJava
    /.$BeginAction
                    $symbol_declarations./

    $EndJava /.$EndAction./

    $NoAction
    /.$Header$case $rule_number:
                    break;./

    $NullAction
    /.$Header$case $rule_number:
                    $setResult(null);
                    break;./

    $BeginActions
    /.
        public void ruleAction(int ruleNumber)
        {
            switch (ruleNumber)
            {./

    $SplitActions
    /.
	            default:
	                ruleAction$rule_number(ruleNumber);
	                break;
	        }
	        return;
	    }

	    public void ruleAction$rule_number(int ruleNumber)
	    {
	        switch (ruleNumber)
	        {./

    $EndActions
    /.
                default:
                    break;
            }
            return;
        }./

    $additional_interfaces /../
    $super_stream_class /.LpgLexStream./
%End

%Globals
    /.
      using LPG2.Runtime;
      using System;
    ./
%End

%Headers
    /.
    public class $action_type : $super_stream_class , $sym_type, RuleAction$additional_interfaces
    {
        private static ParseTable prs = new $prs_type();
        private DeterministicParser dtParser;

        private void setResult(object _object) { dtParser.setSym1(_object); }
        public DeterministicParser getParser() { return dtParser; }
        public object getRhsSym(int i) { return dtParser.getSym(i); }
        public int getRhsTokenIndex(int i) { return dtParser.getToken(i); }
        public int getRhsFirstTokenIndex(int i) { return dtParser.getFirstToken(i); }
        public int getRhsLastTokenIndex(int i) { return dtParser.getLastToken(i); }

        public int getLeftSpan() { return dtParser.getFirstToken(); }
        public int getRightSpan() { return dtParser.getLastToken(); }

        public $action_type(string filename, int tab) :  base(filename, tab)
        {

        }

        public override string[] orderedExportedSymbols() { return orderedTerminalSymbols; }
        public int getEOFTokenKind() { return $prs_type.EOFT_SYMBOL; }

        public ILexStream getILexStream() { return ($super_stream_class) this; }

        /**
         * @deprecated replaced by {@link #getILexStream()}
         */
        public ILexStream getLexStream() { return ($super_stream_class) this; }

        public $ast_type parser()
        {
            return parser(null, 0);
        }

        public $ast_type parser(Monitor monitor)
        {
            return parser(monitor, 0);
        }

        public $ast_type parser(int error_repair_count)
        {
            return parser(null, error_repair_count);
        }

        public $ast_type parser(Monitor monitor, int error_repair_count)
        {
            try
            {
                dtParser = new DeterministicParser(this, prs, this);
            }
            catch (NotDeterministicParseTableException e)
            {
                 Console.Out.WriteLine("****Error: Regenerate $prs_type.cs with -NOBACKTRACK option");
                 return null;
            }
            catch (BadParseSymFileException e)
            {
                 Console.Out.WriteLine("****Error: Bad Parser Symbol File -- $sym_type.cs. Regenerate $prs_type.cs");
                 return null;
            }
            dtParser.setMonitor(monitor);

            try
            {
                return ($ast_type) dtParser.parse();
            }
            catch (BadParseException e)
            {
                reset(e.error_token); // point to error token

                 Console.Out.Write("Error detected on character " + e.error_token);
                if (e.error_token < getStreamLength())
                      Console.Out.Write(" at line " + getLine(e.error_token) + ", column " + getColumn(e.error_token));
                else  Console.Out.Write(" at end of file ");
                 Console.Out.WriteLine(" with kind " + getKind(e.error_token));
            }

            return null;
        }

    ./

%End

%Rules
    /.$BeginActions./
%End

%Trailers
    /.
        $EndActions
    }
    ./
%End

--
-- E N D   O F   T E M P L A T E
--


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

RulesFor(DFT, rec(
    DFT_CT_Inplace := rec(
	info          := "DFT(mn,k) -> DFT(m, k%m), DFT(n, k%n)",
	maxCodeletSize := 16,

	isApplicable := (self, P) >> P[1] > 2 and not IsPrime(P[1]),

	allChildren  := (self, P) >> Map2(
	    Filtered(DivisorPairs(P[1]), d -> d[1] <= self.maxCodeletSize),
	    (m,n) -> [
		DFT(m, P[2] mod m),
		DFT(n, P[2] mod n) ]),

	rule := (self,P,C) >> let(mn := P[1], m := Rows(C[1]), n := Rows(C[2]),
            di := fPrecompute(Tw1(mn, n, P[2])),

	    When(mn > self.maxCodeletSize, # why BB?
		Inplace(Tensor(C[1], I(n)) * Diag(di)),
		        Tensor(C[1], I(n)) * Diag(di)) *
	    Tensor(I(m), C[2]) *
	    L(mn, m))
    ),

    DFT_SplitRadix_Inplace := rec(
	info             := "DFT_n -> DFT_n/2, DFT_n/4, DFT_n/4",
	forTransposition := true,
	maxSize := 64,

	isApplicable := (self, P) >> let(N := P[1],
	    N >= 8 and N mod 4 = 0 and N <= self.maxSize),

	allChildren := P -> let(N := P[1], w := P[2],
	    [[ DFT(N/2, w), DFT(N/4, w) ]]),

	rule := (P, C) -> let(N := P[1], w := P[2],
	    Inplace(Tensor(F(2), I(N/2))) *
	    DirectSum(
		C[1],
		Inplace(BB(
			Tensor(Diag(1, E(4)^w) * F(2), I(N/4)) *
			Diag(Concat(List([0..N/4-1], i->E(N)^(w*i))),
			            List([0..N/4-1], i->E(N)^(3*w*i))))) *
	        Tensor(I(2), C[2])*L(N/2,2)
	    ) *
	    L(N, 2))
    ),

));