gridClass.gi

################################################################################
##
#M Row count method
##
## This method allows us to count negative indices in lists. It is useful for
## indexing gridding matices where the index of the entry/cell is associated with
## the coordinates in the x,y plot. So cols and rows are interchanged and rows
## are counted from bottom to top.
##
InstallMethod(ELM_LIST, [IsList and IsFinite , IsInt], function(l,x)if x > 0 then return l[x]; else return l[Length(l)+1+x]; fi; end);
################################################################################
##
#F  IsZeroPMOneMatrix(matrix)
##
## Checker whether the input matrix only consists of 0s, 1s and -1s.
##
InstallGlobalFunction(IsZeroPMOneMatrix, function(m)
local i,j;

for i in [1..Length(m)] do
    for j in [1..Length(m[1])] do
        if not(m[i][j] in [0,1,-1]) then
            return false;
        fi;
    od;
od;
return true;
end );

################################################################################
##
#F  TurnToPMM(matrix)
##
## Takes a 0/+1/-1 matrix and turns it into its partial multiplication matrix.
## Returns the PMM and its column and row signs.
##
InstallGlobalFunction(TurnToPMM, function(m)
local i,j,res,tmp1,tmp2,mat;

res:=[];
mat:=NullMat(Length(m)*2,Length(m[1])*2);

if not(IsZeroPMOneMatrix(m)) then
    return fail;
fi;
for i in [1..Length(m)] do
    for j in [1..Length(m[1])] do
        if m[i][j] = 1 then
            mat{[2*i-1..2*i]}{[2*j-1..2*j]}:=[[0,1],[1,0]];
        elif m[i][j] = 0 then
            mat{[2*i-1..2*i]}{[2*j-1..2*j]}:=[[0,0],[0,0]];
        elif m[i][j] = -1 then
            mat{[2*i-1..2*i]}{[2*j-1..2*j]}:=[[-1,0],[0,-1]];
        fi;
    od;
od;

tmp1:=[];
for i in [1..Length(mat[1])] do
    Add(tmp1,(-1)^i);
od;
tmp2:=[];
for i in [1..Length(mat)] do
    Add(tmp2, (-1)^i);
od;
Add(res,mat);
Add(res,tmp1);
Add(res,tmp2);
return res;

end );
################################################################################
##
#F  HasColumnRowSigns(matrix)
##
## Takes a 0/+1/-1 matrix and checkes whether it could be a partial
## multiplication matrix. HasColumnRowSigns returns column and row signs for mat.
##
InstallGlobalFunction(HasColumnRowSigns, function(mat)
local row, col, first, i, j, res;

row:=ListWithIdenticalEntries(Length(mat),0);
col:=ListWithIdenticalEntries(Length(mat[1]),0);

first:=PositionNonZero(mat[1]);

if mat[1][first] = 1 then
    col[first]:=1;
    row[1]:=1;
else
    col[first]:=-1;
    row[1]:=1;
fi;

for i in [1..Length(mat)] do
    for j in [1..Length(mat[1])] do
        if not(mat[i][j] = 0) then
            if mat[i][j] = 1 then
                if row[i] = 0 and col[j] = 0 then   #SPECIAL CASE when a possible second free choice
                                                    #could happen, but shouldn't.
                    if mat[i]{[j+1..Length(mat[1])]} = ListWithIdenticalEntries(Length(mat[1])-j,0) and
                       Flat(mat{[i+1..Length(mat)]}[j]) = ListWithIdenticalEntries(Length(mat)-i,0) then
                        row[i]:=1;
                        col[j]:=1;
                    elif not(mat[i]{[j+1..Length(mat[1])]} = ListWithIdenticalEntries(Length(mat[1])-j,0)) then
                        first:=PositionNonZero(col);
                        while first < Length(col) and mat[i][first] = 0 do
                            first:=PositionNonZero(col{[first+1..Length(col)]})+first;
                        od;
                        if first <= Length(col) and mat[i][first] = 1 then
                            row[i]:=col[first];
                            col[j]:=col[first];
                        elif first <= Length(col) and mat[i][first] = -1 then
                            row[i]:=-col[first];
                            col[j]:=-col[first];
                        elif first > Length(col) then
                            row[i]:=1;
                            col[j]:=1;
                        fi;
                    elif not(Flat(mat{[i+1..Length(mat)]}[j]) = ListWithIdenticalEntries(Length(mat)-i,0)) then
                        first:=PositionNonZero(row);
                        while first < Length(row) and mat[first][j] = 0 do
                            first:=PositionNonZero(row{[first+1..Length(row)]})+first;
                        od;
                        if first <= Length(row) and mat[first][j] = 1 then
                            row[i]:=row[first];
                            col[j]:=row[first];
                        elif first <= Length(row) and mat[first][j] = -1 then
                            row[i]:=-row[first];
                            col[j]:=-row[first];
                        elif first > Length(row) then
                            row[i]:=1;
                            col[j]:=1;
                        fi;
                    fi;
                elif row[i] = 0 and col[j] in [1,-1] then

                    row[i]:=col[j];
                elif col[j] = 0 and row[i] in [1,-1] then

                    col[j]:=row[i];
                elif not(row[i] = col[j]) and not(col[j] = 0 or row[i] = 0) then
                    return false;
                fi;
            else
                if row[i] = 0 and col[j] = 0 then   #SPECIAL CASE when a possible second free choice
                                                    #could happen, but shouldn't.
                    if mat[i]{[j+1..Length(mat[1])]} = ListWithIdenticalEntries(Length(mat[1])-j,0) and
                       Flat(mat{[i+1..Length(mat)]}[j]) = ListWithIdenticalEntries(Length(mat)-i,0) then
                        row[i]:=1;
                        col[j]:=-1;
                    elif not(mat[i]{[j+1..Length(mat[1])]} = ListWithIdenticalEntries(Length(mat[1])-j,0)) then
                        first:=PositionNonZero(col);
                        while first < Length(col) and mat[i][first] = 0 do
                            first:=PositionNonZero(col{[first+1..Length(col)]})+first;
                        od;
                        if first <= Length(col) and mat[i][first] = 1 then
                            row[i]:=col[first];
                            col[j]:=-col[first];
                        elif first <= Length(col) and mat[i][first] = -1 then
                            row[i]:=-col[first];
                            col[j]:=col[first];
                        elif first > Length(col) then
                            row[i]:=-1;
                            col[j]:=1;
                        fi;
                    elif not(Flat(mat{[i+1..Length(mat)]}[j]) = ListWithIdenticalEntries(Length(mat)-i,0)) then
                        first:=PositionNonZero(row);
                        while first < Length(row) and mat[first][j] = 0 do
                            first:=PositionNonZero(row{[first+1..Length(row)]})+first;
                        od;
                        if first <= Length(col) and mat[first][j] = 1 then
                            row[i]:=row[first];
                            col[j]:=-row[first];
                        elif first <= Length(col) and mat[i][first] = -1 then
                            row[i]:=-row[first];
                            col[j]:=row[first];
                        elif first > Length(row) then
                            row[i]:=-1;
                            col[j]:=1;
                        fi;
                    fi;
                elif row[i] = 0 and col[j] in [1,-1] then
                    row[i]:=-col[j];
                elif col[j] = 0 and row[i] in [1,-1] then
                    col[j]:=-row[i];
                elif row[i] = col[j] and not(col[j] = 0 or row[i] = 0) then
                    return false;
                fi;
            fi;
        fi;
    od;
od;

return [col,Reversed(row)];

end );


################################################################################
##
#F  IsPMMWithColRowSigns(pmm)
##
## Input is a list containing a 0/+1/-1 matrix and its column and row signs.
## It checkes whether the entries of the matrix correspond to the multiplication
## of the relevant signs or 0.
##
InstallGlobalFunction(IsPMMWithColRowSigns, function(pmm)
local i,j;

if not(IsZeroPMOneMatrix(pmm[1])) then
    return false;
fi;

for i in [1..Length(pmm[2])] do
    for j in [1..Length(pmm[3])] do
        if not((pmm[2][i]*pmm[3][j] = pmm[1][-j][i]) or (pmm[1][-j][i]=0)) then
            return false;
        fi;
    od;
od;

return true;

end );

################################################################################
##
#F  GridDecoding(matrix,word)
##
## Input is a 0/+1/-1 matrix, with or without colum/row signs and a word
## of the alphabet {[i,j] : M(i,j) in {1,-1} }. Using the decoding described in
## Geometric grid classes of permutations or On partial well-coder for monotone
## grid classes of permutations the result is a permutation.
##
##
InstallGlobalFunction(GridDecoding, function(matrix,word)
local matcr,index,i,values;

if IsPMMWithColRowSigns(matrix) then
    matcr:=StructuralCopy(matrix);
elif not(HasColumnRowSigns(matrix) = false) then
    matcr:=[StructuralCopy(matrix),HasColumnRowSigns(matrix)[1],HasColumnRowSigns(matrix)[2]];
else
    matcr:=TurnToPMM(matrix);
fi;

#
# If
##  COL = 1 then insert LEFT TO RIGHT
##  COL = -1 then insert RIGHT TO LEFT
# If
##  ROW = 1 then insert BOTTOM TO TOP
##  ROW = -1 then insert TOP TO BOTTOM

index:=[];
values:=[];
for i in [1..Length(word)] do
    if matcr[2][word[i][1]] = 1 then
        index[i]:=Length(Filtered(word{[1..Length(word)]}[1], x -> x <= word[i][1])) -
                Length(Filtered(word{[i+1..Length(word)]}[1], x -> x = word[i][1]));
    else
        index[i]:=Length(Filtered(word{[1..Length(word)]}[1], x -> x <= word[i][1])) -
                Length(Filtered(word{[1..i-1]}[1], x -> x = word[i][1]));
    fi;
    if matcr[3][word[i][2]] = 1 then
        values[i]:=Length(Filtered(word{[1..Length(word)]}[2], x -> x <= word[i][2])) -
                Length(Filtered(word{[i+1..Length(word)]}[2], x -> x = word[i][2]));
    else
        values[i]:=Length(Filtered(word{[1..Length(word)]}[2], x -> x <= word[i][2])) -
                Length(Filtered(word{[1..i-1]}[2], x -> x = word[i][2]));
    fi;
od;

return Permuted(values,SortingPerm(index));
end );

################################################################################
##
#F GridAut(matrix)
##
## Builds the automaton that accepts all words over the alphabet of the matrix.
## Where the alphabet is build by marking all non-empty entries of the matrix
## incrementally L->R T->B.
##
InstallGlobalFunction(GridAut, function(matrix)
local alph,i;

alph:=[];
for i in [1..Length(matrix)] do
    if not(Position(matrix[i],1) = fail) then
        Append(alph,Positions(matrix[i],1));
    elif not(Position(matrix[i],-1) = fail) then
        Append(alph,Positions(matrix[i],-1));
    fi;
od;

return Automaton("det",1,Length(alph),ListWithIdenticalEntries(Length(alph),[1]),[1],[1]);

end );

################################################################################
##
#F GridAlphabet(matrix)
##
## Technically just determines how many non-empty entries the matrix has and then
## sets up an alphabet on that number. It is a useful small function though.
## Convention of alphabet is L-R, T-B, rather than the 'normal', in sense of
## working through the cells in euclidian coordinate fashion.
##
InstallGlobalFunction(GridAlphabet, function(mat)
local alph,count,x,y,i,j;

count:=0;
for i in [1..Length(mat)] do
    for j in [1..Length(mat[1])] do
        if mat[i][j] <> 0 then
            count:=count+1;
        fi;
    od;
od;

return [1..count];

end );

################################################################################
##
#F CoordinatesToAlphabetInOrder(coordinates)
##
## Takes a list of coordinates and translates them into the the word in the
## alphabet (with the GridAlphabet convention) such that the Automaton can
## recognise the word.
##
InstallGlobalFunction(CoordinatesToAlphabetInOrder, function(coords)
local alph,count,x,y;

alph:=ListWithIdenticalEntries(Length(coords),0);
count:=1;
for y in [Maximum(coords{[1..Length(coords)]}[2]),Maximum(coords{[1..Length(coords)]}[2])-1..1] do
    for x in [1..Maximum(coords{[1..Length(coords)]}[1])] do
        if [x,y] in coords then
            alph[Position(coords,[x,y])]:=count;
            count:=count+1;
        fi;
    od;
od;

return alph;
end );

################################################################################
##
#F MatToCoordinates(matrix)
##
## Returns the 'coordinates'/indeces of the non-empty entries of the matrix.
##
InstallGlobalFunction(MatToCoordinates, function(mat)
local coords, i, j;

coords:=[];
for i in [1..Length(mat)] do
    for j in [1..Length(mat[1])] do
        if mat[i][j] <> 0 then
            Add(coords,[j,Length(mat)-i+1]);
        fi;
    od;
od;

return coords;
end );

################################################################################
##
#F WordToGridCoordinates(matrix,word)
##
## Translates the word over the automaton alphabet into the word over the indeces
## 'coordinates' of the non-empty entries of the matrix.
##
InstallGlobalFunction(WordToGridCoordinates, function(mat,word)
local coords,res,i;

coords:=MatToCoordinates(mat);

res:=[];

for i in [1..Length(word)] do
    Add(res,coords[word[i]]);
od;

return res;

end );

################################################################################
##
#F CoordinatesToWord(matrix,wordincoordinates)
##
## Translates the given word in coordinates to a word over the matrix automaton
## alphabet.
##
InstallGlobalFunction(CoordinatesToWord, function(mat,wcoords)
local coords, res, i;

coords:=MatToCoordinates(mat);

res:=[];
for i in [1..Length(wcoords)] do
    Add(res,Position(coords,wcoords[i]));
od;

return res;

end );

################################################################################
##
#F PMMTox3Mat(matrix)
##
## Turns a m x n partial multiplication matrix into the 3m x 3n equivalent matri
##
InstallGlobalFunction(PMMTox3Mat, function(mat)
local dims,resmat,i,j,colrow,rescr;

if HasColumnRowSigns(mat) = false then
    Print("Input matrix is not PMM.\n");
    return fail;
fi;

dims:=DimensionsMat(mat);
resmat:=NullMat(3*dims[1],3*dims[2]);

for i in [1..dims[1]] do
    for j in [1..dims[2]] do
        if mat[i][j] = 1 then
            resmat{[3*i-2..3*i]}{[3*j-2..3*j]}:=[[0,0,1],[0,1,0],[1,0,0]];
        elif mat[i][j] = -1 then
            resmat{[3*i-2..3*i]}{[3*j-2..3*j]}:=[[-1,0,0],[0,-1,0],[0,0,-1]];
        elif mat[i][j] = 0 then
            resmat{[3*i-2..3*i]}{[3*j-2..3*j]}:=[[0,0,0],[0,0,0],[0,0,0]];
        else
            Print("This matrix does not contain only 0,1,-1's.\n");
            return fail;
        fi;
    od;
od;

colrow:=HasColumnRowSigns(mat);
rescr:=[[],[]];
rescr[1]:=Flat(List(colrow[1], i-> [i,i,i]));
rescr[2]:=Flat(List(colrow[2], i-> [i,i,i]));


return [resmat,rescr[1],rescr[2]];
end );



################################################################################
##
#F PMMTox3Trans(matrix)
##
## Builds transducer that translates all words that correspond to the permutations,
## that are griddable by the input matrix, to the words over the x3 matrix alphabet.
##
InstallGlobalFunction(PMMTox3Trans, function(inmat)
local mat,signs,inalp,i,j,outalp,x,y,from,to,trans,count,aut;

if IsMatrix(inmat[1]) then
    mat:=inmat[1];
    signs:=[inmat[2],inmat[3]];
else
    mat:=inmat;
    signs:=HasColumnRowSigns(mat);
    if signs = false then
        Print("Input matrix is not a partial multiplication matrix\n");
        return fail;
    fi;
fi;

inalp:=[];
for i in [1..Length(mat)] do
    for j in [1..Length(mat[1])] do
        if mat[i][j] <> 0 then
            Add(inalp,[j,Length(mat)-i+1]);
        fi;
    od;
od;

outalp:=[];
for x in [1..Length(inalp)] do
    if signs[1][inalp[x][1]] = 1 then
        if signs[2][inalp[x][2]] = 1 then
            Append(outalp,[[3*inalp[x][1]-2,3*inalp[x][2]-2],
                           [3*inalp[x][1]-1,3*inalp[x][2]-1],
                           [3*inalp[x][1],3*inalp[x][2]]]);
        else
            Append(outalp,[[3*inalp[x][1]-2,3*inalp[x][2]],
                           [3*inalp[x][1]-1,3*inalp[x][2]-1],
                           [3*inalp[x][1],3*inalp[x][2]-2]]);
        fi;
    else
        if signs[2][inalp[x][2]] = 1 then
            Append(outalp,[[3*inalp[x][1],3*inalp[x][2]-2],
                           [3*inalp[x][1]-1,3*inalp[x][2]-1],
                           [3*inalp[x][1]-2,3*inalp[x][2]]]);
        else
            Append(outalp,[[3*inalp[x][1],3*inalp[x][2]],
                           [3*inalp[x][1]-1,3*inalp[x][2]-1],
                           [3*inalp[x][1]-2,3*inalp[x][2]-2]]);
        fi;
    fi;
od;

###
### We are not using GridAlphabetConvention on the out alphabet because
### we need it here in the specific order of insertion according to the
### matrix row and column signs.
###
count:=1;
for y in [3*Length(mat), 3*Length(mat)-1..1] do
    for x in [1..3*Length(mat[1])] do
        if [x,y] in outalp then
            outalp[Position(outalp,[x,y])] := count;
            count:=count+1;
        fi;
    od;
od;

inalp:=GridAlphabet(mat);

trans:=[];
for x in [1..Length(inalp)] do
    for y in [1..3] do
        to:=y+3*x-2;
        for from in [1..Length(outalp)+1] do
            if from <= to or from > 1+3*x then
                Add(trans,[inalp[x],outalp[to-1],from,to]);
            fi;
       od;
    od;
od;

return Transducer(Length(outalp)+1,1,trans,[1..Length(outalp)+1]);

end );

################################################################################
##
#F x3ToOffSetMat(matrixwithcolumnrowsigns)
##
## Takes the x3 matrix with row and column signs and returns the one point
## extension matrix, which allows for points to lie off the diagonal.
##
InstallGlobalFunction(x3ToOffSetMat, function(matcr)
local mat,resmat,i,j,col,row;

mat:=matcr[1];

resmat:=NullMat(Length(mat)*5/3,Length(mat[1])*5/3);

for i in [1..Length(mat)] do
    for j in [1..Length(mat[1])] do
        if not(mat[i][j] = 0) then
            if i mod 3 = 0 then
                if j mod 3 = 0 then
                    resmat[5*(i/3)][5*(j/3)]:=mat[i][j];
                elif j mod 3 = 1 then
                    resmat[5*(i/3)][1+5*((j-1)/3)]:=mat[i][j];
                else
                    resmat[5*(i/3)][3+5*((j-2)/3)]:=mat[i][j];
                fi;
            elif i mod 3 = 1 then
                if j mod 3 = 0 then
                    resmat[1+5*((i-1)/3)][5*(j/3)]:=mat[i][j];
                elif j mod 3 = 1 then
                    resmat[1+5*((i-1)/3)][1+5*((j-1)/3)]:=mat[i][j];
                else
                    resmat[1+5*((i-1)/3)][3+5*((j-2)/3)]:=mat[i][j];
                fi;
            else
                if j mod 3 = 0 then
                    resmat[3+5*((i-2)/3)][5*(j/3)]:=mat[i][j];
                elif j mod 3 = 1 then
                    resmat[3+5*((i-2)/3)][1+5*((j-1)/3)]:=mat[i][j];
                else
                    resmat[3+5*((i-2)/3)][3+5*((j-2)/3)]:=mat[i][j];
                fi;
            fi;
        fi;
    od;
od;

for i in [2,5..Length(mat)-1] do
    for j in [2,5..Length(mat[1])-1] do
        if mat[i][j] = 1 then
            resmat[2+5*((i-2)/3)][2+5*((j-2)/3)]:=1;
            resmat[4+5*((i-2)/3)][4+5*((j-2)/3)]:=1;
        elif mat[i][j] = -1 then
            resmat[2+5*((i-2)/3)][4+5*((j-2)/3)]:=1;
            resmat[4+5*((i-2)/3)][2+5*((j-2)/3)]:=1;
        else
            resmat[2+5*((i-2)/3)][2+5*((j-2)/3)]:=1;
            resmat[4+5*((i-2)/3)][4+5*((j-2)/3)]:=1;
            resmat[2+5*((i-2)/3)][4+5*((j-2)/3)]:=1;
            resmat[4+5*((i-2)/3)][2+5*((j-2)/3)]:=1;
        fi;
    od;
od;

col:=ShallowCopy(matcr[2]);
for i in [1..Length(resmat[1])] do
    if i mod 5 in [2,4] then
        Add(col,1,i);
    fi;
od;

row:=ShallowCopy(matcr[3]);
for j in [1..Length(resmat)] do
    if j mod 5 in [2,4] then
        Add(row,1,j);
    fi;
od;

return [resmat,col,row];

end );

################################################################################
##
#F  MatrixUnion(mats)
##
## Takes the input list of matrices mats and concatenates these matrices into
## a larger matrix that contains mats on its diagonal.
##
InstallGlobalFunction(MatrixUnion, function(args)
local res,tmp,i,j,sumdims,dims;

dims:=[];

for i in [1..Length(args)] do
    Add(dims, DimensionsMat(args[i]));
od;

sumdims:=[];
for i in [1..Length(dims)] do
    Add(sumdims,[Sum(dims{[1..i]}[1]),Sum(dims{[1..i]}[2])]);
od;

res:=NullMat(sumdims[Length(sumdims)][1],sumdims[Length(sumdims)][2]);

for i in [1..Length(args)] do
    if not(Length(args[i])=0) then
        res{[sumdims[-i][1]-dims[i][1]+1..sumdims[-i][1]]}{[(sumdims[i][2]-dims[i][2]+1)..sumdims[i][2]]}:=args[i];
    fi;
od;

return res;

end );

################################################################################
##
#F  Find22Mats(mat)
##
## Inspects all 2x2 blocks in the matrix mat if a [[0,1],[1,0]] is seen then
## in the returned matrix a 1 is written, for [[-1,0],[0,-1]] there is a -1, if
## [[0,0],[0,0]] then 0 else we write 9.
##
InstallGlobalFunction(Find22Mats, function(mat)
local searchmats,markedmat,i,j,tmp;

searchmats:=[ [[0,1],[1,0]] , [[-1,0],[0,-1]] , [[0,0],[0,0]] ];
markedmat:=[];

for i in [1..Length(mat)-1] do
    tmp:=[];
    for j in [1..Length(mat[1])-1] do
        if mat{[i..i+1]}{[j..j+1]} = searchmats[1] then
            Add(tmp,1);
        elif mat{[i..i+1]}{[j..j+1]} = searchmats[2] then
            Add(tmp,-1);
        elif mat{[i..i+1]}{[j..j+1]} = searchmats[3] then
            Add(tmp,0);
        else
            Add(tmp,9);
        fi;
    od;
    Add(markedmat,tmp);
od;

Add(markedmat,ListWithIdenticalEntries(Length(markedmat[1]),0));
for i in [1..Length(markedmat)] do
    Add(markedmat[i],0);
od;

markedmat[Length(markedmat)][Length(markedmat[1])] := 9;

return markedmat;
end );

################################################################################
##
#F  CheckMarkedMat(mat)
##
## CheckMarkedMat goes through the marked matrix returned by Find22Mats and
## notes which rows and columns do not contain consecutive 9's, only 0's & 9's
## and whether there is an entry on a row or column that could interfere with
## the collapsing of the 2x2 blocks.
##
InstallGlobalFunction(CheckMarkedMat, function(mat)
local tmp,i,j,check,res;

res:=[];

tmp:=[];
for i in [1..Length(mat)] do
    check:=true;
    for j in [1..Length(mat[1])-1] do
        if mat[i][j] = 9 and mat[i][j+1] = 9 then
            check:=false;
        fi;
    od;
    Add(tmp,check);
od;

Add(res,tmp);

tmp:=[];
for j in [1..Length(mat[1])] do
    check:=true;
    for i in [1..Length(mat)-1] do
        if mat[i][j] = 9 and mat[i+1][j] = 9 then
            check:=false;
        fi;
    od;
    Add(tmp,check);
od;
Add(res,tmp);

for i in [1..Length(mat)] do
    if res[1][i] and not(1 in mat[i] or -1 in mat[i]) and (9 in mat[i]) then
        res[1][i] := false;
    fi;
od;

for j in [1..Length(mat[1])] do
    if res[2][j] and not(1 in mat{[1..Length(mat)]}[j] or
            -1 in mat{[1..Length(mat)]}[j]) and (9 in mat{[1..Length(mat)]}[j]) then
        res[2][j] := false;
    fi;
od;

for i in [1..Length(mat)] do
    for j in [1..Length(mat[1])] do
        if mat[i][j] in [-1,1] and (not(res[1][i]) or not(res[2][j])) then
            res[1][i]:=false;
            res[2][j]:=false;
        fi;
    od;
od;

return res;
end );


################################################################################
##
#F  MatrixReduction(mat)
##
## MatrixReduction collapses 2x2 blocks with either 0's or other collapsable
## 2x2 on their cols and rows.
##
InstallGlobalFunction(MatrixReduction, function(mat)
local marked,checklist,newdims,res,tmp,i,j;

marked:=Find22Mats(mat);
checklist:=CheckMarkedMat(marked);

res:=StructuralCopy(mat);

for i in [Length(checklist[1]),Length(checklist[1])-1 .. 1] do
    if checklist[1][i] then
        Remove(marked,i+1);
        Remove(checklist[1],i+1);
        res[i]:=ListWithIdenticalEntries(Length(mat[1]),0);
        Remove(res,i+1);
    fi;
od;

for j in [Length(checklist[2]),Length(checklist[2])-1 .. 1] do
    if checklist[2][j] then
        Remove(checklist[2],j+1);
        res{[1..Length(res)]}{[j..j]}:=NullMat(Length(res),1);
        for i in [1..Length(marked)] do
            Remove(marked[i],j+1);
            Remove(res[i],j+1);
        od;
    fi;
od;

for i in [1..Length(checklist[1])] do
    if checklist[1][i] then
        for j in [1..Length(res[1])] do
            if marked[i][j] = 1 then
                res[i][j]:=1;
            elif marked[i][j] = -1 then
                res[i][j]:=-1;
            fi;
        od;
    fi;
od;
return res;
end );

################################################################################
##
#F  RemoveZeroColumnsRows(mat)
##
## RemoveZeroColumnsRows returns a matrix that contains no columns or rows with
## only 0 entries.
##
InstallGlobalFunction(RemoveZeroColumnsRows, function(mat)
local i,j,res,dims;

res:=StructuralCopy(mat);
dims:=[Length(res),Length(res[1])];
for i in [dims[1], dims[1]-1 .. 1 ] do
    if res[i] = ListWithIdenticalEntries(dims[2],0) then
        Remove(res,i);
    fi;
od;

dims:=[Length(res),Length(res[1])];
for j in [dims[2], dims[2]-1 .. 1] do
    if Flat(res{[1..dims[1]]}[j]) = ListWithIdenticalEntries(dims[1],0) then
        for i in [1..dims[1]] do
            Remove(res[i],j);
        od;
    fi;
od;


return res;

end );
################################################################################
##
#F  mover(grid,max)
##
## Helper function to move (increment) the grid lines by one.
##
InstallGlobalFunction(mover, function(list,max)
local n,ind;

n:=Length(list);
if list[n] = max then
    ind:=Position(list,max);
    if ind = 1 then
        return list;
    else
        list[ind-1]:=list[ind-1]+1;
        list{[ind..n]} := ListWithIdenticalEntries(n+1-ind,list[ind-1]);
    fi;
else
    list[n]:=list[n]+1;
fi;

return list;
end );

################################################################################
##
#F  IsInCell(perm,cell,cellval)
##
## Helper checker for a specific cell, where we are checking whether perm has
## values within the cell boundaries and whether these values are in the correct
## monotonicity, based on cellval.
##
InstallGlobalFunction(IsInCell, function(perm,cell,cellval)
local a,b,c,d,status,i;

a:=cell[1][1];
b:=cell[1][2];
c:=cell[2][1];
d:=cell[2][2];

status:=0;
#if a=b then
#    return true;
#fi;
for i in [a..b-1] do
    if c <= perm[i] and perm[i] < d then
        if status = 0 then
            status:=1;
            last:=perm[i];
        elif status = 1 then
            if perm[i] > last then
                status:=2;
                last:=perm[i];
            else
                status:=-2;
                last:=perm[i];
            fi;
        elif status = 2 then
            if perm[i] > last then
                last:=perm[i];
            else
                return false;
            fi;
        elif status = -2 then
            if perm[i] < last then
                last:=perm[i];
            else
                return false;
            fi;
        fi;
    fi;
od;

if (status = 1 and not(cellval = 0)) or
   (status / 2 = cellval) or
   (status = 0 and not(cellval=0)) then
    return true;
else
    return false;
fi;

end );

################################################################################
##
#F  IsInGrid(perm,grid,mat)
##
## Checks whether perm is griddable by a specific grid, with mat indicating the
## monotonicity in the cells.
##
InstallGlobalFunction(IsInGrid, function(perm,grid,mat)
local i,j,tmp;

tmp:=StructuralCopy(grid);

Add(tmp[1],1,1);
Add(tmp[1],Maximum(perm)+1);
Add(tmp[2],1,1);
Add(tmp[2],Maximum(perm)+1);


for i in [1..Length(tmp[1])-1] do
    for j in [1..Length(tmp[2])-1] do
        if not(IsInCell(perm,[[tmp[1][i],tmp[1][i+1]],[tmp[2][j],tmp[2][j+1]]],
           mat[-j][i])) then
            return false;
        fi;
    od;
od;

return true;

end );

################################################################################
##
#F  IsGriddable(perm,mat)
##
## Checkes whether a specific permutation perm is griddable by mat. This is based
## at the moment on a brute-force algorithm that goes through all possible
## griddings until a gridding is found.
##
InstallGlobalFunction(IsGriddable, function(perm,mat)
local hori,vert,max,res;

hori:=ListWithIdenticalEntries(Length(mat)-1,1);
max:=Maximum(perm)+1;
res:=false;
while not(res) and not(hori = ListWithIdenticalEntries(Length(hori),max)) do
    vert:=ListWithIdenticalEntries(Length(mat[1])-1,1);
    res:=IsInGrid(perm,[vert,hori],mat);
    while not(res) and not(vert = ListWithIdenticalEntries(Length(vert),max)) do
        mover(vert,max);
        res:=IsInGrid(perm,[vert,hori],mat);
    od;
    mover(hori,max);
od;

#res:=IsInGrid(perm,[vert,hori],mat);

return res;

end );

################################################################################
##
#F  BoundedGridPerms(mat,n)
##
## Outputs all permutations, of length n, gridded by mat. Currently brute-force
## algorithm, producing all permutations of length n. Checking all whether they
## are griddable by mat and then returns only the permutations that are.
##
InstallGlobalFunction(BoundedGridPerms, function(mat,n)
local list,bool;

list:=List(Elements(SymmetricGroup(n)), i -> ListPerm(i,n));

bool:=List(list, i -> IsGriddable(i,mat));
#a:=Positions(bool,true);
#qPrint(list,"\n");

return list{Positions(bool,true)};

end );

################################################################################
##
#F Griddings
##
## Returns all possible griddings (in form of gridline coordinates) of perm
## in mat.
InstallGlobalFunction(Griddings, function(perm,mat)
local hori,vert,max,grids,a,b;

hori:=ListWithIdenticalEntries(Length(mat)-1,1);
max:=Maximum(perm)+1;
grids:=[];

while not(hori = ListWithIdenticalEntries(Length(hori),max)) do
    vert:=ListWithIdenticalEntries(Length(mat[1])-1,1);
    if IsInGrid(perm,[vert,hori],mat) then
        a:=ShallowCopy(vert);
        b:=ShallowCopy(hori);
        Add(grids,[a,b]);
    fi;
    while not(vert = ListWithIdenticalEntries(Length(vert),max)) do
        mover(vert,max);
        if IsInGrid(perm,[vert,hori],mat) then
            a:=ShallowCopy(vert);
            b:=ShallowCopy(hori);
            Add(grids,[a,b]);
        fi;
    od;
    mover(hori,max);
od;


return grids;

end );