#############################################################################
##
#W  basics.gi               Manuel Delgado <mdelgado@fc.up.pt>
#W                          Pedro Garcia-Sanchez <pedro@ugr.es>
#W                          Jose Morais <jjoao@netcabo.pt>
##
##
#H  @(#)$Id: basics.gi,v 0.92 $
##
#Y  Copyright 2005 by Manuel Delgado, 
#Y  Pedro Garcia-Sanchez and Jose Joao Morais
#Y  We adopt the copyright regulations of GAP as detailed in the 
#Y  copyright notice in the GAP manual.
##
#############################################################################
        
#############################################################################
##
#A  MultiplicityOfNumericalSemigroup(S)
## 
##  Returns the multiplicity of the numerical
##  semigroup S.
##
#############################################################################
InstallMethod(MultiplicityOfNumericalSemigroup,
        "Returns the multiplicity of a numerical semigroup",
        [IsNumericalSemigroup and IsNumericalSemigroupByGenerators],10,
        function(S)
    return GeneratorsOfNumericalSemigroup(S)[1];
end);   

InstallMethod(MultiplicityOfNumericalSemigroup,
        "Returns the multiplicity of a numerical semigroup",
        [IsNumericalSemigroup and IsNumericalSemigroupByAperyList],1,
        function(S)
    return Minimum(Difference(S!.aperylist,[0]),Length(S!.aperylist));
end);   

InstallMethod(MultiplicityOfNumericalSemigroup,
        "Returns the multiplicity of a modular numerical semigroup",
        [IsNumericalSemigroup and IsModularNumericalSemigroup],
         function(S)
     local a, b, i;
     a := S!.modularcondition[1];
     b := S!.modularcondition[2];
     return First([1..b], i-> a*i mod b <= i);
 end);   
  
InstallMethod(MultiplicityOfNumericalSemigroup,
        "Returns the multiplicity of a proportionally modular numerical semigroup",
        [IsNumericalSemigroup and IsProportionallyModularNumericalSemigroup],
         function(S)
     local a, b, c, i;
     a := S!.proportionallymodularcondition[1];
     b := S!.proportionallymodularcondition[2];
     c := S!.proportionallymodularcondition[3];
     return First([1..b], i-> a*i mod b <= c*i);
 end);   

InstallMethod(MultiplicityOfNumericalSemigroup,
        "Returns the multiplicity of a numerical semigroup",
        [IsNumericalSemigroup],
        function(S)
    if Length(SmallElementsOfNumericalSemigroup(S)) > 1 then
        return SmallElementsOfNumericalSemigroup(S)[2];
    else
        return 1;
    fi;
end);   

#############################################################################
##
#A  FrobeniusNumberOfNumericalSemigroup(S)
## 
##  Returns the Frobenius number of the numerical
##  semigroup S.
##
#############################################################################
InstallMethod(FrobeniusNumberOfNumericalSemigroup,
       "Returns the Frobenius Number of the numerical sgp",
        [IsNumericalSemigroup and IsNumericalSemigroupByAperyList],
        function(S)
    return(Maximum(S!.aperylist)-Length(S!.aperylist));
end);

InstallMethod(FrobeniusNumberOfNumericalSemigroup,
       "Returns the Frobenius Number of the numerical sgp",
        [IsNumericalSemigroup and IsNumericalSemigroupByGaps],
        function(S)
    return(S!.gaps[Length(S!.gaps)]);
end);
 
InstallMethod(FrobeniusNumberOfNumericalSemigroup,
       "Returns the Frobenius Number of the numerical sgp",
        [IsNumericalSemigroup and IsNumericalSemigroupBySmallElements],
        function(S)
    return(S!.elements[Length(S!.elements)] - 1);
end);

InstallMethod(FrobeniusNumberOfNumericalSemigroup,
       "Returns the Frobenius Number of the numerical sgp",
        [IsNumericalSemigroup],
        function(S)
    local set, len;
    ## Sylvester's formula
    if IsNumericalSemigroupByGenerators(S) and 
       IsBound(S!.minimalgenerators) and
       Length(MinimalGeneratingSystemOfNumericalSemigroup(S)) = 2 then
        return(S!.minimalgenerators[1] * S!.minimalgenerators[2] - 
               S!.minimalgenerators[1] - S!.minimalgenerators[2]);
    fi;
    set := SmallElementsOfNumericalSemigroup(S);
    len := Length(set);
    return(set[len] - 1);
end);

InstallMethod(FrobeniusNumberOfNumericalSemigroup,
       "Returns the Frobenius Number of the numerical sgp",
        [IsNumericalSemigroup and IsModularNumericalSemigroup],
        function(S)
    local j, k, a, b, m;
    a := S!.modularcondition[1];
    m := S!.modularcondition[2];
    k:= First([1..a-1], j-> j > ((a-1)*(a - (j*m) mod a))/m);
    return m-(Int(k*m/a)+1);
end);

#The algorithm used here was recently obtained by Delgado&Rosales
InstallMethod(FrobeniusNumberOfNumericalSemigroup,
       "Returns the Frobenius Number of the numerical sgp",
        [IsNumericalSemigroup and IsProportionallyModularNumericalSemigroup],
        function(S)
    local j, k, a, b, c;
    a := S!.proportionallymodularcondition[1];
    b := S!.proportionallymodularcondition[2];
    c := S!.proportionallymodularcondition[3];
    
    if a <= c then
        return -1;
    fi;
    a := a mod b;
    if a = 0 then 
         return -1;
    fi;
    if a > (b+c)/2 then
        a := b+c-a;
    fi;
    j := CeilingOfRational(a-a/c-a/b+(2*a)/(c*b));
    
    while ((j*b) mod a + Int((j*b)/a)*c <= (c-1)*b+a-c) do
        j := j+1;
    od;
    return b-Int((j*b)/a) -1;
end);



#############################################################################
##
#F  GeneratorsOfNumericalSemigroup(S)
## 
##  Returns a set of generators of the numerical
##  semigroup S. If a minimal generating system has already been computed, this
##  is the set returned.
##
#############################################################################
InstallGlobalFunction( GeneratorsOfNumericalSemigroup, function(S)
    if IsBound(S!.minimalgenerators) then
        return(S!.minimalgenerators);
    elif IsBound(S!.generators) then
        return(S!.generators);
    fi;
    return(MinimalGeneratingSystemOfNumericalSemigroup(S));
end);



#############################################################################
##
#F  GeneratorsOfNumericalSemigroupNC(S)
## 
##  Returns a set of generators of the numerical
##  semigroup S.
##
#############################################################################
InstallGlobalFunction( GeneratorsOfNumericalSemigroupNC, function(S)
    if IsBound(S!.generators) then
        return(S!.generators);
    fi;
    return(MinimalGeneratingSystemOfNumericalSemigroup(S));
end);



#############################################################################
##
#A  MinimalGeneratingSystemOfNumericalSemigroup(S)
## 
##  Returns the minimal generating system of the numerical
##  semigroup S.
##
#############################################################################
InstallMethod( MinimalGeneratingSystemOfNumericalSemigroup,
        "method for a numerical semigroup",
        true,
        [IsNumericalSemigroup],0,
        function(S)
    local g, gen, i, ngen, Elm, T, sumNS, ss, sss, ssss;
    #####################################################
    # Computes the sum of subsets of numerical semigroups
    sumNS := function(S,T)
        local mm, s, t, R;
        R := [];
        mm := Minimum(Maximum(S),Maximum(T));
        for s in S do
            for t in T do
                if s+t > mm then
                    break;
                else
                    AddSet(R,s+t);
                fi;
            od;
        od;
        return R;
    end;

    if IsBound(S!.minimalgenerators) then
        return S!.minimalgenerators;
    elif IsBound(S!.generators) then
        if 1 in S!.generators then
            return [1]; 
        fi;
        gen := ShallowCopy(S!.generators);
        # a naive reduction of the number of generators
        ss := sumNS(gen,gen);
        gen := Difference(gen,ss);
        if ss <> [] then
            sss := sumNS(ss,gen);
            gen := Difference(gen,sss);
            if sss <> [] then
                ssss := sumNS(sss,gen);
                gen := Difference(gen,ssss);
            fi;
        fi;
        if Length(gen) = 2 then
            return gen;
        fi;
        i := Length(gen);
        while i >= 2 do
            ngen := Difference(gen, [gen[i]]);
            if Gcd(ngen) = 1 and 
               BelongsToNumericalSemigroup(gen[i], NumericalSemigroup(ngen)) then
                gen := ngen;
                i := i - 1;
            else
                
                i := i - 1;
            fi;
        od;
        S!.minimalgenerators := gen;
        return gen;

    else
        Elm := SmallElementsOfNumericalSemigroup(S); 
        if Elm = [0] then
            S!.minimalgenerators := [1];
            return ShallowCopy(S!.minimalgenerators);
        fi;
        g := FrobeniusNumberOfNumericalSemigroup(S);    
        T:=Union(Elm{[2..Length(Elm)]},[Elm[Length(Elm)]..Elm[Length(Elm)]+Elm[2]]);
        S!.minimalgenerators := Difference(T,sumNS(T,T));
        return ShallowCopy(S!.minimalgenerators);
    fi;
end);         


#############################################################################
##
#A  FundamentalGapsOfNumericalSemigroup(S)
## 
##  Returns the fundamental gaps of the numerical
##  semigroup S.
##
#############################################################################
InstallMethod( FundamentalGapsOfNumericalSemigroup,
        "returns the list of fundamental gaps",
        true,
        [IsNumericalSemigroup],
        function(S)
    local i, j, h, fh;
    if IsBound(S!.fundamentalgaps) then
        return S!.fundamentalgaps;
    fi;
    h := GapsOfNumericalSemigroup(S);
    fh := []; 
    for i in h do
        if Filtered(h, j-> j mod i = 0) = [i] then
            Add(fh, i);
        fi;

    od;
    S!.fundamentalgaps := fh;
    return fh;
end);



#############################################################################
##
#A  PseudoFrobeniusOfNumericalSemigroup(S)
## 
##  Returns the pseudo Frobenius number of the numerical
##  semigroup S.
##
#############################################################################
InstallMethod( PseudoFrobeniusOfNumericalSemigroup,
        "returns a list of the pseudo Frobenius numbers of a  numerical semigroup",
        true,
        [IsNumericalSemigroup],
        function(S)
    local hs, x, ehs, s, S0, SE;
    hs := GapsOfNumericalSemigroup(S);
    if hs = [] then                 # S is N
        return [-1];
    fi;
    ehs := [];
    SE := SmallElementsOfNumericalSemigroup(S);
    S0 := SE{[2..Length(SE)]};
    for x in hs do
        if ForAll(S0, s-> BelongsToNumericalSemigroup(x+s,S)) then
            Add(ehs, x);
        fi;
    od;
    return ehs;
end);



#############################################################################
##
#A  SpecialGapsOfNumericalSemigroup(S)
## 
##  Returns the special gaps of the numerical
##  semigroup S.
##
#############################################################################
InstallMethod( SpecialGapsOfNumericalSemigroup,
        "returns the list of special gaps",
        true,
        [IsNumericalSemigroup],
        function(S)
    local y, Y;
    Y := [];
    for y in GapsOfNumericalSemigroup(S) do
        if BelongsToNumericalSemigroup(2*y,S) then
            Add(Y,y);
        fi;
    od;
    
    return Intersection(PseudoFrobeniusOfNumericalSemigroup(S),Y);
end);



 
#############################################################################
##
#O  BelongsToNumericalSemigroup(n,S)
## 
##  Tests if the integer n belongs to the numerical
##  semigroup S.
##
#############################################################################
InstallMethod( \in,
    "for numerical semigroups",
    [ IsInt, IsNumericalSemigroup ],
        function( x, s )
    return BelongsToNumericalSemigroup(x,s);
end);


InstallMethod( BelongsToNumericalSemigroup,
        "To test whether an integer belongs to a numerical semigroup",
        true,
        [IsInt,IsNumericalSemigroup and HasSmallElementsOfNumericalSemigroup],100,
        function(n,S)
    local f, s;
    s := SmallElementsOfNumericalSemigroup(S);
    f := FrobeniusNumberOfNumericalSemigroup(S);
    return (n in s) or (n > f);
end);

InstallMethod( BelongsToNumericalSemigroup,
        "To test whether an integer belongs to a numerical semigroup",
        true,
        [IsInt,IsNumericalSemigroup and IsNumericalSemigroupByAperyList],
        function(n,S)
    local ap, f, i, m, s;
    ap := S!.aperylist;
    m := Length(ap);
    if First([1..m], i-> (n mod m = i-1) and n >= ap[i]) <> fail then
        return true;
    else
        return false;
    fi;
end);

InstallMethod( BelongsToNumericalSemigroup,
        "To test whether an integer belongs to a numerical semigroup",
        true,
        [IsInt,IsNumericalSemigroup and HasFundamentalGapsOfNumericalSemigroup],
        function(n,S)
    local f, i;
    f := FundamentalGapsOfNumericalSemigroup(S);
    return First(f, i -> i mod n =0) = fail;
end);

InstallMethod( BelongsToNumericalSemigroup,
        "To test whether an integer belongs to a numerical semigroup",
        true,
        [IsInt,IsNumericalSemigroup and IsModularNumericalSemigroup],
        function(n,S)
    local a,b;
    a := S!.modularcondition[1];
    b := S!.modularcondition[2];
    return a*n mod b <= n;
end);

InstallMethod( BelongsToNumericalSemigroup,
        "To test whether an integer belongs to a numerical semigroup",
        true,
        [IsInt,IsNumericalSemigroup and IsProportionallyModularNumericalSemigroup],
        function(n,S)
    local a,b,c;
     a := S!.propmodularcondition[1];
     b := S!.propmodularcondition[2];
     c := S!.propmodularcondition[3];
    return a*n mod b <= c*n;
end);

InstallMethod( BelongsToNumericalSemigroup,
        "To test whether an integer belongs to a numerical semigroup",
        true,
        [IsInt,IsNumericalSemigroup and IsNumericalSemigroupByGenerators],
        function(n,S)
    local gen, ss, sumNS;
    #####################################################
    # Computes the sum of subsets of numerical semigroups
    sumNS := function(S,T)
        local mm, s, t, R;
        R := [S[1]+T[1]];
        mm := Minimum(Maximum(S),Maximum(T));
        for s in S do
            for t in T do
                if s+t > mm then
                    break;
                else
                    AddSet(R,s+t);
                fi;
            od;
        od;
        return R;
    end;
    if n in S!.generators then
        return true;
    fi;
    if IsBound(S!.minimalgenerators) then
        gen := S!.minimalgenerators;
    else 
        gen := S!.generators;
    fi;
    ss := sumNS(gen,gen);
    if n < Minimum(ss) then
        return false;
    else
        TryNextMethod();
    fi;
end);

InstallMethod( BelongsToNumericalSemigroup,
        "To test whether an integer belongs to a numerical semigroup",
        true,
        [IsInt,IsNumericalSemigroup],
        function(n,S)
    local ap, f, i, m, s;
    m := MultiplicityOfNumericalSemigroup(S);
    ap := AperyListOfNumericalSemigroupWRTElement(S,m);
    if First([1..m], i-> (n mod m = i-1) and n >= ap[i]) <> fail then
        return true;
    else
        return false;
    fi;
end);



#############################################################################
##
#O  AperyListOfNumericalSemigroupWRTElement(S,n)
## 
##  Returns the Apery list of the numerical
##  semigroup S with respect to n.
##
#############################################################################
InstallMethod( AperyListOfNumericalSemigroupWRTElement,
        "returns the Apery list of a  numerical semigroup with respect to a nunzero element of the semigroup",
        true,
        [IsNumericalSemigroup,IsInt],
        function(S,n)
    local Ap, i, j, f, max, Lmax;
#    if IsBound(S!.aperylist) and Length(S!.aperylist) = n then
#        return S!.aperylist;
#    elif not BelongsToNumericalSemigroup(n,S) then
    if not BelongsToNumericalSemigroup(n,S) then
        Error("n must be an element of S in AperyListOfNumericalSemigroupWRTElement");
    else
        Ap := [0];
        f := FrobeniusNumberOfNumericalSemigroup(S);
        max := f + n; #see proposition 10.4 (book)
        for i in [1..n-1] do
            Add(Ap, First(Difference([1..max],GapsOfNumericalSemigroup(S)), j -> j mod n = i));
        od;
        if n =MultiplicityOfNumericalSemigroup(S) then
            S!.aperylist := Ap; #
        fi;
    fi;
    Setter(IsNumericalSemigroupByAperyList)(S,true);
    return Ap;
end);



#############################################################################
##
#F  DrawAperyListOfNumericalSemigroup(ap)
## 
##  <ap> is the Apéry set of a numerical semigroup.
##  This function draws a graph whose vertices are
##  the elements of <ap> and the arrow u -> v exists
##  iff v - u is in <ap>.
##
#############################################################################
InstallGlobalFunction(DrawAperyListOfNumericalSemigroup, function(ap)
    local i, j, E, ap2, e, path, name, gv, str, dot;
    
    if not IsAperyListOfNumericalSemigroup(ap) then
        Error("The argument must be the Apery set of a numerical semigroup");
    fi;
    
    # Compute the set of edges of the digraph
    ap2 := Set(ap);
    E := [];
    for i in ap do
        for j in ap do
            if j-i in ap2 then
                Add(E, [i,j]);
            fi;
        od;
    od;
    
    
    # The file where dot graph will be written
    name := Filename(DirectoryTemporary(), Concatenation("aperygraph", ".dot"));
    PrintTo(name, "digraph  AperyGraph{\n");
    
    
    # Search for evince or ggv to display .ps
    path := DirectoriesSystemPrograms();
    gv := Filename( path, "evince" );
    if gv = fail then
        gv := Filename( path, "ggv" );
        if gv = fail then
            Error("Please install evince or ggv");
        fi;
    fi;
    gv := Concatenation(gv, " ");
    
    dot := Filename( path, "dot" );
    if dot = fail then
        Error("Please install GraphViz (http://www.graphviz.org )");
    fi;
    
    
    
    # Write the dot file to a string
    str := "";
    for e in E do
        Append(str, Concatenation(String(e[1]), " -> ", String(e[2]), ";\n"));
    od;
    for i in ap2 do
        Append(str, Concatenation(String(i), ";\n"));
    od;
    Append(str, "}\n");
    
    
    # Write the string to the file
    AppendTo(name, str);
    
    # Run dot and display graph
    Exec(Concatenation(dot, " -Tps ", name, " -o ", name, ".ps"));
    Exec(Concatenation(gv, name, ".ps 2>/dev/null &"));
end);



#############################################################################
##
#F  AperyListOfNumericalSemigroupAsGraph(ap)
## 
##  <ap> is the Apéry set of a numerical semigroup.
##  This function returns the adjacency list of the graph 
##  whose vertices are
##  the elements of <ap> and the arrow u -> v exists
##  iff v - u is in <ap>.
##  The 0 is ignored.
##
#############################################################################
InstallGlobalFunction(AperyListOfNumericalSemigroupAsGraph, function(ap)
    local i, j, E, ap2, G, e;
    
    if not IsAperyListOfNumericalSemigroup(ap) then
        Error("The argument must be the Apery set of a numerical semigroup");
    fi;
    
    # Compute the set of edges of the digraph
    ap2 := Set(ap);
    E := [];
    for i in ap do
        for j in ap do
            if j-i in ap2 then
                Add(E, [i,j]);
            fi;
        od;
    od;
    
    # Build the adjacency list
    G := [];
    for e in E do
        if not (e[1] = 0 or e[2] = 0) then
        if not IsBound(G[e[1]]) then
            G[e[1]] :=[];
        fi;
        AddSet(G[e[1]], e[2]);
        fi;
    od;
    
    return G;
end);

