r"""This module gives Viennot-type algorithms for the RSK and dual RSK correspondence.

These are generalizations of the correspondences given in the paper titled "Une forme Geometrique de la correspondance de Robinson-Schensted" by G. Viennot (Combinatoire et representation du groupe symmetrique, Strasbourg, 1976). In this article Viennot gives a geometric description for the Robinson-Schensted correspondence between permutation matrices and pairs of standard Young tableaux of the same shape. This algorithm can be easily modified in two slightly different ways to give the two correspondences of Knuth's paper "Permutations, Matrices, and Generalized Young Tableau", Pacific Journal of Mathematics, 1970.

AUTHOR: 
    - Amritanshu Prasad (2012-09-03)
"""


#*****************************************************************************
#       Copyright (C) 2012 AMRITANSHU PRASAD <amri@imsc.res.in>
#
#  Distributed under the terms of the GNU General Public License (GPL)
#  as published by the Free Software Foundation; either version 2 of
#  the License.
#                  http://www.gnu.org/licenses/
#*****************************************************************************



def path(A, row=-1, column=-1):
    """Return the list of maximal non-zero entries, left to right for RSK.
    
    INPUT:
    
    - ``A``      -- a matrix.
    - ``row``    -- (default: -1) an integer such that 1 <= row <= number of rows of A.
                 if -1, it is replaced by the number of rows of A.
    - ``column`` -- (default: -1) an integer such that -1<= column < number of columns of A.
    
    OUPUT:
        
    - A list consisting of maximal non-zero entries of the submatrix of A consisting of rows
      numbers <= row-1, columns numbers > column, with column numbers in strictly
      increasing order. Maximality is determined with respect to the partial order:
    
                       (i,j)>=(k,l) if i<=k and j<=l.
                       
    EXAMPLES::
        
        sage: A = matrix(); A
        []
        sage: path(A)
        []
    """
    if row == -1:
        row=A.nrows()
    for j in range(column+1, A.ncols()):
        for i in range(0,row):
            if A[i,j]:
                return [[i,j]] + path(A,i,j)
    return []

# dual_path(A) returns a list of positions (i_1,j_1),(i_2,j_2),... which are maximal
# with respect to the partial order "(i,j)>(k,l) if and only if i<=k and j<l" among
# the non-zero entries of A. These entries are arranged so that j_1<j_2<...
def dual_path(A):#, row=-1, column=-1):
    """Return the list of maximal non-zero entries, bottom to top for dual RSK.
    
    INPUT:
    
    - ``A``      -- a matrix.
    
    OUPUT:
        
    - A list consisting of maximal non-zero entries of A with row numbers in strictly
      decreasing order. Maximality is determined with respect to the partial order:
    
                       (i,j)> (k,l) if i <= k and j < l.
                       
    EXAMPLES::
        
        sage: A = matrix(3, 3, [0, 0, 1, 0, 1, 0, 0, 1, 1])
    
        sage: A
    
        [0 0 1]
        [0 1 0]
        [0 1 1]
    
        sage: dual_path(A)
    
        [[2, 1], [1, 1], [0, 2]]
    """
    row=A.nrows()
    column = -1
    path = list()
    for j in range(column+1, A.ncols()):
        if A.submatrix(nrows = row).column(j):
            for i in range(row-1,-1,-1):
                if A[i,j]:
                    path.append([i,j])
                    row = i
    return path


# on input a list of pairs (i_0,j_0),(i_1,j_1),...,(i_k,j_k), this function returns
# the list of pairs (i_0,j_1),(i_1,j_2),...,(i_(k-1),j_k)
def shadow(entries):
    """Return the shadow points of entries."""
    output = []
    for i in range(1,len(entries)):
        output.append([entries[i-1][0],entries[i][1]])
    return output

# this function subtracts 1 from each entry of A in path(A) and adds 1 to each entry
# of S in shadow(path(A)). It appends j_0 + 1 to P and i_k + 1 to Q
def viennot_step(A,S,row_P,row_Q):
    """Return modified matrix, modified shadow, and one entry of P and Q"""
    entries=path(A)
    for entry in entries:
        A[entry[0],entry[1]] = A[entry[0],entry[1]]-1
    for entry in shadow(entries):
        S[entry[0],entry[1]] = S[entry[0],entry[1]]+1
    row_P.append(entries[0][1] + 1)
    row_Q.append(entries[-1][0] + 1)
    return A, S, row_P, row_Q


# this function subtracts 1 from each entry of A in dual_path(A) and adds 1 to each entry
# of S in shadow(dual_path(A)). It appends j_0 + 1 to P and i_k + 1 to Q
def dual_viennot_step(A,S,row_P,row_Q):
    """Return modified matrix, modified shadow, and one entry of P and Q"""
    entries=dual_path(A)
    for entry in entries:
        A[entry[0],entry[1]] = A[entry[0],entry[1]]-1
    for entry in shadow(entries):
        S[entry[0],entry[1]] = S[entry[0],entry[1]]+1
    row_P.append(entries[0][1] + 1)
    row_Q.append(entries[-1][0] + 1)
    return A, S, row_P, row_Q
    
# this function iterates viennot_step on A until A is reduced to 0 and returns S, row_P,
# and row_Q.
def rsk_row(A):
    """Return shadow and one line of P and Q"""
    S = matrix(A.nrows(), A.ncols()) # Initialize S to be the zero matrix
    row_P = list(); row_Q = list()
    V = A, S, row_P, row_Q
    while A: # run viennot_step until left with zero matrix
         V = viennot_step(*V)
    return V[1], V[2], V[3]

# this function iterates dual_viennot_step on A until A is reduced to 0 and returns S, row_P,
# and row_Q.
def dual_rsk_row(A):
    """Return shadow and one line of P and Q"""
    S = matrix(A.nrows(), A.ncols()) # Initialize S to be the zero matrix
    row_P = list(); row_Q = list()
    V = A, S, row_P, row_Q
    while A: # run viennot_step until left with zero matrix
         V = dual_viennot_step(*V)
    return V[1], V[2], V[3]
        
    
def rsk(A):
    """Return two semistandard Young tableaux of the same shape associated to A by the RSK correspondence"""
    A = copy(A) # so that the function will not change the matrix given to it
    P = list()
    Q = list()
    while A: # keep producing rows until left with zero matrix
        R = rsk_row(A)
        A = R[0] # replaces A by its shadow
        P.append(R[1])
        Q.append(R[2])
    return Tableau(P), Tableau(Q)

def transpose_tableau(T):
    """Return the transpose of the tableau T"""
    if T == []:
        return []
    transpose = list()
    for i in range(0,len(T[0])):
        row_of_transpose = list()
        for row in T:
            if len(row) > i:
                row_of_transpose.append(row[i])
        transpose.append(row_of_transpose)
    return transpose

def dual_rsk(A):
    """Return two semistandard Young tableaux of transpose shapes associated to A by the dual RSK correspondence"""
    A = copy(A) # so that the function will not change the matrix given to it
    P = list()
    Q = list()
    while A: # keep producing rows until left with zero matrix
        R = dual_rsk_row(A)
        A = R[0] # replaces A by its shadow
        P.append(R[1])
        Q.append(R[2])
    return Tableau(P).conjugate(), Tableau(Q)

def reverse_path(S, p, q, rows = -1, cols = -1):
    """Return the extremal reverse path starting in column p and ending in row q"""
    if rows == -1: # start from last row
        rows = S.nrows()
    if cols == -1: # start from last column
        cols = S.ncols()
    for i in range(rows-1,q-1,-1):
        for j in range(cols-1, p-1,-1):
            if S[i,j]:
                return [[i,j]] + reverse_path(S, j+1, q, rows = i+1, cols = -1)
    return list()

def reverse_shadow(entries, p, q):
    """Return the reverse shadow of entries with terminal (col, row) = (p,q)"""
    if entries == []:
        return [[q-1,p-1]]
    output = [[entries[0][0],p-1]]
    for i in range(0, len(entries)-1):
        output.append([entries[i+1][0],entries[i][1]])
    output.append([q-1, entries[-1][1]])
    return output

def reverse_viennot_step(A, S, row_P, row_Q):
    path = reverse_path(S,row_P[-1],row_Q[-1])
    for entry in path:
        S[entry[0], entry[1]] = S[entry[0], entry[1]] - 1
    for entry in  reverse_shadow(path, row_P[-1], row_Q[-1]):
        A[entry[0], entry[1]] = A[entry[0], entry[1]] + 1
    row_P = row_P[:-1]; row_Q = row_Q[:-1]
    return A, S, row_P, row_Q

def inverse_rsk_row(S, row_P, row_Q):
    """Return the matrix which produces shadow S and row_P, row_Q under rsk_row"""
    A = matrix(S.nrows(),S.ncols())
    V = A, S, row_P, row_Q
    while row_P:
        V = reverse_viennot_step(*V)
        row_P = V[2]
    return V[0]
    
def tableau_max(T):
    """Return the maximum entry of T"""
    return max(map(max,T))

def inverse_rsk(P, Q):
    """Return the integer matrix which outputs SSYT P and Q of same shape under rsk."""
    if P == []:
        return matrix(0,0)
    P = copy(P); Q = copy(Q)
    ncols = tableau_max(P); nrows = tableau_max(Q)
    A = matrix(nrows, ncols)
    while P:
        A = inverse_rsk_row(A, P[-1], Q[-1])
        P = P[:-1]; Q = Q[:-1]
    return A

def reverse_dual_path(S, p, q, last_column = -1):
    """Return the extremal reverse dual path starting in column p and ending in row q"""
    if last_column == -1:
        last_column = S.ncols()
    if not(S.submatrix(row = q, col = p-1, ncols = last_column - p + 1)):
        return list()
    col_path = list()
    rownum = q-1
    if q == S.nrows():
        return list()
    for j in range(last_column-1, p-2, -1):
        if S.submatrix(row = q).column(j):
            break
    for i in range(q, S.nrows()):
        if S[i,j]:
            col_path = [[i,j]] + col_path
            rownum = i
    return reverse_dual_path(S, p, rownum + 1, last_column = j+1) + col_path 

def reverse_dual_viennot_step(A, S, row_P, row_Q):
    path = reverse_dual_path(S,row_P[-1],row_Q[-1])
    for entry in path:
        S[entry[0], entry[1]] = S[entry[0], entry[1]] - 1
    for entry in  reverse_shadow(path, row_P[-1], row_Q[-1]):
        A[entry[0], entry[1]] = A[entry[0], entry[1]] + 1
    row_P = row_P[:-1]; row_Q = row_Q[:-1]
    return A, S, row_P, row_Q
    
def inverse_dual_rsk_row(S, row_P, row_Q):
    """Return the matrix which produces shadow S and row_P, row_Q under dual_rsk_row"""
    A = matrix(S.nrows(),S.ncols())
    V = A, S, row_P, row_Q
    while row_P:
        V = reverse_dual_viennot_step(*V)
        row_P = V[2]
    return V[0]
    
def inverse_dual_rsk(P,Q):
    """Return the 0-1 matrix which outputs SSYT P and Q of transpose shapes under dual rsk."""
    if P == []:
        return matrix(0,0)
    P = copy(P); Q = copy(Q)
    P = transpose_tableau(P)
    ncols = tableau_max(P); nrows = tableau_max(Q)
    A = matrix(nrows, ncols)
    while P:
        A = inverse_dual_rsk_row(A, P[-1], Q[-1])
        P = P[:-1]; Q = Q[:-1]
    return A

#############################
#PLAYING WITH DUAL RSK
#############################

def random_zero_one_matrix(m, n):
    return Matrix(ZZ, [[randint(0, 1) for i in range(m)] for j in range(n)])

def random_sym_zero_one_trace_zero(n):
    A = Matrix(ZZ, [[int(i>j)*randint(0, 1) for i in range(n)] for j in range(n)])
    return A + A.transpose()