#############################################################################
##
#W  ideals-def.gi           Manuel Delgado <mdelgado@fc.up.pt>
#W                          Pedro Garcia-Sanchez <pedro@ugr.es>
#W                          Jose Morais <jjoao@netcabo.pt>
##
##
#H  @(#)$Id: ideals-def.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.
##
#############################################################################


#############################################################################
#####################        Defining Ideals           ######################
#############################################################################
##
#F IdealOfNumericalSemigroup(l,S)
##
## l is a list of integers and S a numerical semigroup
##
## returns the ideal of S generated by l.
##
#############################################################################
InstallGlobalFunction(IdealOfNumericalSemigroup, function(l,S)
    if not (IsNumericalSemigroup(S) and ForAll(l, i -> IsInt(i))) then
        Error("The arguments of IdealOfNumericalSemigroup must be a numerical semigroup and a list of integers.");
    fi;
    return(Objectify( IdealsOfNumericalSemigroupsType,
                  rec(sgp := S, generators := Set(l))));
end );


##############################################################################
## L is a list of integers and S a numerical semigroup
## L + S is an abbreviation for IdealOfNumericalSemigroup(L, S)
##
InstallMethod( \+, "for a list and a numerical semigroup", true,
        [IsList and IsAdditiveElement,
         IsNumericalSemigroup], 0,
        function( L,S )
    return(IdealOfNumericalSemigroup(L, S));
end);

##############################################################################
## n is an integer and S a numerical semigroup
## n + S is an abbreviation for IdealOfNumericalSemigroup([n], S)
## 
InstallMethod( \+, "for an integer and a numerical semigroup", true,
        [IsInt and IsAdditiveElement,
         IsNumericalSemigroup], 0,
        function( n,S )
    return(IdealOfNumericalSemigroup([n], S));
end);

#############################################################################
##
#M  PrintObj(S)
##
##  This method for ideals of numerical semigroups.
##
#############################################################################

InstallMethod( PrintObj,
        "prints an Ideal of a Numerical Semigroup",
        [ IsIdealOfNumericalSemigroup],
        function( I )
    Print(I!.generators," + NumericalSemigroup( ", GeneratorsOfNumericalSemigroup(I!.sgp), " )\n");
end);

#############################################################################
##
#M  ViewObj(S)
##
##  This method for ideals of numerical semigroups.
##
#############################################################################

InstallMethod( ViewObj,
        "prints an Ideal of a Numerical Semigroup",
        [ IsIdealOfNumericalSemigroup],
        function( I )
    Print("<Ideal of numerical semigroup>");
end);

#############################################################################
##
#M  DisplayObj(S)
##
##  This method for ideals of numerical semigroups.
##
#############################################################################
InstallMethod( Display,
        "displays an ideal of a numerical semigroup",
    [IsIdealOfNumericalSemigroup],
        function( I )
    local M, u, L, condensed;
    
    condensed := function(L)
        local c, C,j, n, search, bool;
        C := [];
        bool := true;
        j := 0;
        c := L[1];
        search := function(n) # searches the greatest subinterval starting in n 
            local i, k;
            k := 0;
            for i in [Position(L,n).. Length(L)-1] do
                if not (L[i]+1 = L[i+1]) then
                    c := L[i+1];
                    return [n..n+k];
                fi;
                k := k+1;
            od;
            bool := false;
            return [n..L[Length(L)]];
        end;
        while bool do
            Add(C,search(c));
        od;
        return C;
    end;
    ##  End of condensed()  --
    
    L := SmallElementsOfIdealOfNumericalSemigroup(I);
    M := condensed(L);
    u := [M[Length(M)][1],"->"];
    M[Length(M)] := u;
    return M;
end);


############################################################################
##
#M Methods for the comparison of ideals of a numerical semigroup. 
##
InstallMethod( \=,
        "for two ideals of a numerical semigroup",
        [IsIdealOfNumericalSemigroup,
         IsIdealOfNumericalSemigroup],
        function(I, J ) 

    if not AmbientNumericalSemigroupOfIdeal(I) 
       = AmbientNumericalSemigroupOfIdeal(J) then
        Error("The ambient numerical semigroup must be the same for both ideals.");
    fi;
    if HasMinimalGeneratingSystemOfIdealOfNumericalSemigroup(I) and HasMinimalGeneratingSystemOfIdealOfNumericalSemigroup(J) then
        return MinimalGeneratingSystemOfIdealOfNumericalSemigroup(I)
               = MinimalGeneratingSystemOfIdealOfNumericalSemigroup(J);
    fi;
    return SmallElementsOfIdealOfNumericalSemigroup(I)
           = SmallElementsOfIdealOfNumericalSemigroup(J);
end);      

InstallMethod( \<,
        "for two ideals of a numerical semigroups",
        [IsIdealOfNumericalSemigroup,IsIdealOfNumericalSemigroup],
        function(I, J ) 
    if not AmbientNumericalSemigroupOfIdeal(I) 
       = AmbientNumericalSemigroupOfIdeal(J) then
        Error("The ambient numerical semigroup must be the same for both ideals.");
    fi;
    return(SmallElementsOfIdealOfNumericalSemigroup(I) < SmallElementsOfIdealOfNumericalSemigroup(J)); 
end );


#############################################################################
##
#F  GeneratorsOfIdealOfNumericalSemigroup(I)
## 
##  Returns a set of generators of the ideal I. 
##  If a minimal generating system has already been computed, this
##  is the set returned.
############################################################################

InstallGlobalFunction(GeneratorsOfIdealOfNumericalSemigroup, function(I)
    if not IsIdealOfNumericalSemigroup(I) then
        Error("The argument must be an ideal of a numerical semigroup.");
    fi;
    if HasMinimalGeneratingSystemOfIdealOfNumericalSemigroup(I) then
        return (MinimalGeneratingSystemOfIdealOfNumericalSemigroup(I));
    fi;
    return(ShallowCopy(I!.generators));
end);


#############################################################################
##
#F  GeneratorsOfIdealOfNumericalSemigroupNC(I)
## 
##  Returns a set of generators of the ideal I. 
############################################################################
InstallGlobalFunction(GeneratorsOfIdealOfNumericalSemigroupNC, function(I)
    if not IsIdealOfNumericalSemigroup(I) then
        Error("The argument must be an ideal of a numerical semigroup.");
    fi;
    return(ShallowCopy(I!.generators));
end);

#############################################################################
##
#F AmbientNumericalSemigroupOfIdeal(I)
##
##  Returns the ambient semigroup of the ideal I. 
############################################################################
InstallGlobalFunction(AmbientNumericalSemigroupOfIdeal, function(I)
    if not IsIdealOfNumericalSemigroup(I) then
        Error("The argument must be an ideal of a numerical semigroup.");
    fi;
    return(ShallowCopy(I!.sgp));
end);

#############################################################################
##
#A SmallElementsOfIdealOfNumericalSemigroup
##
##  Returns the list of elements in the ideal I up to the last gap + 1.
##
#############################################################################
InstallMethod(SmallElementsOfIdealOfNumericalSemigroup,
        "Returns the list of elements in the ideal not greater that the last gap",
        [IsIdealOfNumericalSemigroup ],
        function(I)
    local g, gI, l, max, maxgap, min, smallS, l2;

    if not (IsIdealOfNumericalSemigroup(I)) then
        Error("The argument must be an ideal of a numerical semigroup");
    fi;

    smallS := SmallElementsOfNumericalSemigroup(AmbientNumericalSemigroupOfIdeal(I));
    g := smallS[Length(smallS)]; #Frobenius number + 1 
    gI := GeneratorsOfIdealOfNumericalSemigroup(I);

    l := Union(List(gI, i -> i+ smallS));

    min := Minimum(gI);

    l := Intersection(l,[min .. min+g]);
    
    l2 := Difference([min..min+g],l);
    if l2 = [] then
        return([min]);
    else
        maxgap := Maximum(Difference(l2,l));
        return(Intersection(l,[min..maxgap+1]));
    fi;
end);


#############################################################################
##
#F  BelongsToIdealOfNumericalSemigroup(n,I)
## 
##  Tests if the integer n belongs to the ideal I.
##
#############################################################################
InstallGlobalFunction(BelongsToIdealOfNumericalSemigroup, function(x, I)
    local gI, S, small;

    if not (IsIdealOfNumericalSemigroup(I) and IsInt(x)) then
        Error("The arguments must be an integer and an ideal of a numerical semigroup");
    fi;
    if HasSmallElementsOfIdealOfNumericalSemigroup(I) then
        small := SmallElementsOfIdealOfNumericalSemigroup(I);
        return( (x in small) or (x > Maximum(small))); 
    fi;    

    S := AmbientNumericalSemigroupOfIdeal(I);
    gI := GeneratorsOfIdealOfNumericalSemigroup(I);

    return(First(gI, n -> (BelongsToNumericalSemigroup(x-n,S))) <> fail);
end);
###########################################################
## n in I means BelongsToIdealOfNumericalSemigroup(n,I)
##########
InstallMethod( \in,
        "for ideals of numerical semigroups",
        [ IsInt, IsIdealOfNumericalSemigroup ],
        function( x, I )
    return BelongsToIdealOfNumericalSemigroup(x,I);
end);

#############################################################################
##
#A MinimalGeneratingSystemOfIdealOfNumericalSemigroup(I)
##
## The argument I is an ideal of a numerical semigroup
## returns the minimal generating system of I. 
## 
#############################################################################
InstallMethod(MinimalGeneratingSystemOfIdealOfNumericalSemigroup,
        "Returns the minimal generating system of an ideal",
        [IsIdealOfNumericalSemigroup],
        function(I)
    local gen, len, ngen, S;
    if not IsIdealOfNumericalSemigroup(I) then
        Error("I must be an ideal of a  numerical semigroup");
    fi;
    S := AmbientNumericalSemigroupOfIdeal(I);
    gen := GeneratorsOfIdealOfNumericalSemigroup(I);

    len := Length(gen);
    while len > 1 do
        ngen  := Difference(gen, [gen[len]]);
        if (First(gen{[1..len-1]}, n -> gen[len]-n in S) <> fail ) then
            gen := ngen;
            len := len - 1;
        else
            len := len -1;
        fi;
    od;
    return gen;
end);

#############################################################################
##
#F SumIdealsOfNumericalSemigroup(I,J)
##
## returns the sum of the ideals I and J (in the same ambient semigroup)
#############################################################################
InstallGlobalFunction(SumIdealsOfNumericalSemigroup, function(I, J)
    local l,i,j,l1,l2;

    if not (IsIdealOfNumericalSemigroup(I) and IsIdealOfNumericalSemigroup(J)) 
       or not AmbientNumericalSemigroupOfIdeal(I) 
       = AmbientNumericalSemigroupOfIdeal(J) then
        Error("The arguments must be ideals of the same numerical semigroup.");
    fi;

    l1:=GeneratorsOfIdealOfNumericalSemigroup(I);
    l2:=GeneratorsOfIdealOfNumericalSemigroup(J);
    l := Set(Cartesian(l1,l2),n -> Sum(n));
    return(IdealOfNumericalSemigroup(l,AmbientNumericalSemigroupOfIdeal(I)));
end);

###########################################################
## I + J means SumIdealsOfNumericalSemigroup(I,J)
##########

InstallMethod( \+, "for ideals of the same numerical semigroup", true,
        [IsIdealOfNumericalSemigroup, 
         IsIdealOfNumericalSemigroup], 0,
        function( I, J )
    return(SumIdealsOfNumericalSemigroup( I, J ));
end);

#############################################################################
##
#F SubtractIdealsOfNumericalSemigroup(I,J)
##
## returns the ideal I - J
#############################################################################
InstallGlobalFunction(SubtractIdealsOfNumericalSemigroup, function(I, J)
    local  i, ideal, j, g, gI, gJ, l, maxgap, mingen, s, l2;

    if not (IsIdealOfNumericalSemigroup(I) and IsIdealOfNumericalSemigroup(J)) 
       or not AmbientNumericalSemigroupOfIdeal(I) 
       = AmbientNumericalSemigroupOfIdeal(J) then
        Error("The arguments must be ideals of the same numerical semigroup.");
    fi;
    s := AmbientNumericalSemigroupOfIdeal(I);
    g := FrobeniusNumberOfNumericalSemigroup(s);
    gI := GeneratorsOfIdealOfNumericalSemigroup(I);
    gJ := GeneratorsOfIdealOfNumericalSemigroup(J);

    i := Minimum(gI);
    j := Minimum(gJ);

    l := Filtered([i-j..i-j+g+1], n -> ForAll(gJ, z-> BelongsToIdealOfNumericalSemigroup(z+n,I))); 
    
    

    l2 := Difference([i-j..i-j+g+1],l);
    if l2 = [] then    
        maxgap := i-j-1;
    else
        maxgap := Maximum(Difference(l2,l));
    fi;

    l := Intersection(l,[i-j..maxgap+1]);

    mingen := MinimalGeneratingSystemOfIdealOfNumericalSemigroup(l+s);

    ideal := mingen + s;

    Setter(SmallElementsOfIdealOfNumericalSemigroup)(ideal,l);

    return ideal;
end);     

###########################################################
## I - J means SubtractIdealsOfNumericalSemigroup(I,J)
##########

InstallMethod( \-, "for ideals of the same numerical semigroup", true,
        [IsIdealOfNumericalSemigroup, 
         IsIdealOfNumericalSemigroup], 0,
        function( I, J )
    return(SubtractIdealsOfNumericalSemigroup( I, J ));
end);



#############################################################################
##
#F DifferenceOfdealsOfNumericalSemigroup(I,J)
##
## returns the set difference I\J (J must be contained in I)
#############################################################################
InstallGlobalFunction(DifferenceOfIdealsOfNumericalSemigroup, function(I, J)
    local  sI, sJ, MI, MJ, M, SI, SJ;

    if not (IsIdealOfNumericalSemigroup(I) and IsIdealOfNumericalSemigroup(J)) 
       or not AmbientNumericalSemigroupOfIdeal(I) 
       = AmbientNumericalSemigroupOfIdeal(J) then
        Error("The arguments must be ideals of the same numerical semigroup.");
    fi;
    sI := SmallElementsOfIdealOfNumericalSemigroup(I);
    sJ := SmallElementsOfIdealOfNumericalSemigroup(J);
    MI := Maximum(sI);
    MJ := Maximum(sJ);
    M := Maximum(MI,MJ);
    SI := Union(sI,[MI..M]);
    SJ := Union(sJ,[MJ..M]);
    if not IsSubset(SI,SJ) then
        Error("The second ideal must be contained in the first");
    fi;
    return Difference(SI,SJ);
end);

#############################################################################
##
#F MultipleOfIdealOfNumericalSemigroup(n,I)
##
## n is a non negative integer and I is an ideal
## returns the multiple nI (I+...+I n times) of I 
#############################################################################
InstallGlobalFunction(MultipleOfIdealOfNumericalSemigroup, function(n,I)
    local i, II;
     if not (IsInt(n) and n >=0 and IsIdealOfNumericalSemigroup(I)) then
         Error("The arguments must be a non negative integer and an ideal.");
     fi;
     if n=0 then
         return [0]+AmbientNumericalSemigroupOfIdeal(I);
     elif n=1 then
         return I;
     fi;
     II:=I;
     for i in [1..n-1] do
         II := II+I;
     od;
     return II;
end);
###########################################################
## n is an integer and S a numerical semigroup
## n * I is an abbreviation for MultipleOfIdealOfNumericalSemigroup(n,I)
########## 
InstallMethod( \*, "for a non negative integer and an ideal of a numerical semigroup", true,
        [IsInt and IsMultiplicativeElement,
         IsIdealOfNumericalSemigroup], 999999990,
        function( n,I )
    return(MultipleOfIdealOfNumericalSemigroup(n, I));
end);


#############################################################################
##
#F HilbertFunctionOfIdealOfNumericalSemigroup(n,I)
##
## returns the value of the Hilbert function associated to I in n,
## that is, nI\(n+1)I. I must be an ideal included in its ambient semigroup.
#############################################################################
InstallGlobalFunction(HilbertFunctionOfIdealOfNumericalSemigroup, function(n,I)
    if not (IsInt(n) and n >=0 and IsIdealOfNumericalSemigroup(I)) then
        Error("The arguments must be a non negative integer and an ideal.");
    fi;
    return Length(DifferenceOfIdealsOfNumericalSemigroup(n*I,(n+1)*I));
end);

    
#############################################################################
##
#F BlowUpIdealOfNumericalSemigroup(I)
##
##
#############################################################################
InstallGlobalFunction(BlowUpIdealOfNumericalSemigroup, function(I)
    local n, bup, tmp;
    if not IsIdealOfNumericalSemigroup(I) then
        Error("The argument must be an ideal.");
    fi;
    
    n := 1;
    tmp := 0 + AmbientNumericalSemigroupOfIdeal(I);
    bup := I - I;
    while tmp <> bup do
        tmp := bup;
        n := n+1;
        bup := (n*I)-(n*I);
    od;
    return bup;
end);



#############################################################################
##
#F  MaximalIdealOfNumericalSemigroup(S)
##
##  Returns the maximal ideal of S.
##
#############################################################################
InstallGlobalFunction(MaximalIdealOfNumericalSemigroup, function(S)
    if not IsNumericalSemigroup(S) then
        Error("The argument must be a numerical semigroup.");
    fi;
    return MinimalGeneratingSystemOfNumericalSemigroup(S)+S;
end);
