"""

Implemented in this module are simple routines to help compute with 
qqr and lqr codes.

Let $R = \fff [x]/(x^p - 1)$ and $r_S \in R$ denotes the
polynomial 

\[
r_S(x) =\sum_{i\in S} x^i,
\]
where $S\subseteq GF(p)$. By convention, if $S=\emptyset$ is the 
empty set, $r_S=0$. We call $|S|$ the {\it weight} of $r_S$, denoted 
$\wt(r_S)$.
For the set $Q$ of quadratic residues in $GF(p)^\times$ and the set 
$N$ of non-quadratic residues in $GF(p)^\times$, we have 
$\wt(r_Q)=\wt(r_N)=(p-1)/2$.
If $S \subseteq GF(p)$, let 
$f_S(x) = \prod_{a\in S}(x - a) \in GF(p)[x]$. 
Let $\chi = (\frac{\ }{p})$ be the quadratic
residue character, which is $1$ on the 
quadratic residues $Q\subset GF(p)^\times$, 
$-1$ on the non-quadratic residues $N\subset GF(p)^\times$, 
and is $0$ on $0\in GF(p)$.

Define 
\[
C_{NQ}=\{(r_N r_S, r_Q r_S) \ |\  S \subseteq GF(p)\}, 
\]
where $N,Q$ are as above. (We identify in the obvious way
each pair $(r_N r_S, r_Q r_S)$ with an element of $\fff^{2p}$.
In particular, when $S$ is the empty set, $(r_N r_S, r_Q r_S)$ 
is associated with the the zero vector in $\fff^{2p}$.) 
We call this a {\it QQR code} (or a {\it quasi-quadratic residue code}). 
Let
\[
C=\lbrace ({r}_N r_S, {r}_Q r_S, {r}_N r_S^*, {r}_Q r_S^*)\ |\
S\subseteq GF(p)\rbrace .
\]
We call this a {\it long quadratic residue code} or
{\it LQR code} for short.


AUTHOR:
        -- David Joyner (2006-08), initial implementation.


REFERENCES:
 [1] D. Joyner, ``On quadratic residue codes and hyperelliptic curves,''
to appear in Discrete Mathematics & Theoretical Computer Science
http://www.dmtcs.org/
 [2] L. Bazzi and S. Mitter,
{\it Some constructions of codes from group actions}, preprint, 2001.
(available from Mitter's MIT website)

"""

#*****************************************************************************
#       Copyright (C) 2006 David Joyner <wdjoyner@gmail.com>, 
#                     2006 William Stein <wstein@gmail.com>
#
#  Distributed under the terms of the GNU General Public License (GPL)
#
#    This code is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
#    General Public License for more details.
#
#  The full text of the GPL is available at:
#
#                  http://www.gnu.org/licenses/
#*****************************************************************************

from sage.interfaces.all import gap
from sage.rings.all import QQ, RR
from sage.matrix.matrix_space import MatrixSpace

def qr(p):
    """
    EXAMPLES:
        sage: nqr(11)
        [2, 6, 7, 8, 10]
        sage: qr(11)
        [1, 3, 4, 5, 9]
        sage: set(qr(11)).union(set(nqr(11)))
        set([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
    """
    ans = quadratic_residues(p)
    ans.remove(0)
    return ans

def nqr(p):
    L = quadratic_residues(p)
    ans = [x for x in range(p) if not(x in L)]
    return ans
 
def qr_polycodeword(p,S):
    """

    """
    Rx = PolynomialRing(GF(2),"x")
    x = Rx.gen()  ## not really needed
    RX = Rx.quotient(x^p-1, 'X')
    X = RX.gen()
    return add([X^i for i in S])

def rNrQ(p):
    Q = qr(p)
    N = nqr(p)
    rQ = qr_polycodeword(p,Q)
    rN = qr_polycodeword(p,N)
    return rQ*rN

def qqr_polycodeword(p,S):
    """

    """
    rS = qr_polycodeword(p,S)
    Q = qr(p)
    N = nqr(p)
    rN = qr_polycodeword(p,N)
    rQ = qr_polycodeword(p,Q)
    return [rS*rN,rS*rQ]

def qqr_vectorcodeword(p,S):
    """
    EXAMPLES:
        sage: qqr_vectorcodeword(11,[1,2,3])
        [[0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0],[1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1]]
        sage: c = qqr_polycodeword(11,[1,2,3,4]); qqr_vectorcodeword(11,[1,2,3,4]); qqr_wt(c)
        [[1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1], [1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1]]
        16
        sage: char_sum(11,[1,2,3,4])
        -5

    """
    poly = qqr_polycodeword(p,S)
    return [poly[i].list() for i in range(2)]

def lqr_polycodeword(p,S):
    """

    """
    rS = qr_polycodeword(p,S)
    Q = qr(p)
    N = nqr(p)
    rN = qr_polycodeword(p,N)
    rQ = qr_polycodeword(p,Q)
    Sc = [x for x in range(p) if not(x in S)]
    rSc = qr_polycodeword(p,Sc)
    return [rS*rN,rS*rQ,rSc*rN,rSc*rQ]

#r = lqr_polycodeword

def lqr_vectorcodeword(p,S):
    """
    EXAMPLES:
        sage: lqr_vectorcodeword(11,[1,2,3])
        [[0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0],
         [1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1],
         [1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1],
         [0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0]]

    """
    poly = lqr_polycodeword(p,S)
    return [poly[i].list() for i in range(4)]

def lqr_gen_mat(p,form=None):
    """
    If form = "verbatim" then the matrix is returned in the form computed.
    Otherwise, the row reduced echelon form is returned.

    EXAMPLES:
        sage: lqr_gen_mat(5)
        [1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0]
        [0 1 0 0 1 0 1 1 1 1 0 1 0 0 1 0 1 1 1 1]
        [0 0 1 0 1 1 1 1 0 1 0 0 1 0 1 1 1 1 0 1]
        [0 0 0 1 1 1 0 1 0 0 0 0 0 1 1 1 0 1 0 0]

    """
    mat = []
    if p%4==1:
        for i in range(p-1):
            row = lqr_vectorcodeword(p,[i])
            row = row[0] + row[1] + row[2] + row[3]
            mat.append(row)
        n = len(mat[0])
        k = len(mat)
        MS = MatrixSpace(GF(2),k,n)
        ans = MS(mat)
        #print p,ans
        if form=="verbatim":
            return ans
    if p%4==3:
        for i in range(p):
            row = lqr_vectorcodeword(p,[i])
            row = row[0] + row[1] + row[2] + row[3]
            mat.append(row)
        for i in range(1):
            row = lqr_vectorcodeword(p,[i])
            row = row[0] + row[1] + row[0] + row[1]
            mat.append(row)
        n = len(mat[0])
        k = len(mat)
        MS = MatrixSpace(GF(2),k,n)
        ans = MS(mat)
        #print p,ans
        if form=="verbatim":
            return ans
    return ans.echelon_form()
    
def qqr_gen_mat(p):
    """
    The row reduced echelon form is returned.

    EXAMPLES:
        sage: qqr_gen_mat(5)
        [1 0 0 0 1 0 1 0 1 0]
        [0 1 0 0 1 0 1 1 1 1]
        [0 0 1 0 1 1 1 1 0 1]
        [0 0 0 1 1 1 0 1 0 0]
        sage: qqr_gen_mat(7)
        [1 0 0 0 1 0 1 0 0 0 1 1 0 1]
        [0 1 0 0 1 1 1 0 0 0 0 0 0 0]
        [0 0 1 0 1 1 0 0 0 0 1 1 0 1]
        [0 0 0 1 0 1 1 0 0 0 1 1 0 1]
        [0 0 0 0 0 0 0 1 0 0 1 0 1 1]
        [0 0 0 0 0 0 0 0 1 0 1 1 1 0]
        [0 0 0 0 0 0 0 0 0 1 0 1 1 1]


    """
    G0 = lqr_gen_mat(p,"verbatim")
    G1 = G0.matrix_from_columns(list(range(2*p)))
    k = G1.rank()
    G = G1.matrix_from_rows(list(range(k)))
    return G.echelon_form()

def lqr_code(p):
    """
    EXAMPLES:
        sage: lqr_code(7)
        Linear code of length 28, dimension 8 over Finite Field of size 2
        sage: C = lqr_code(7)
        sage: C.minimum_distance()
        8
        sage: lqr_code(11)
        Linear code of length 44, dimension 12 over Finite Field of size 2
        sage: lqr_code(13)
        Linear code of length 52, dimension 12 over Finite Field of size 2

    """
    G = lqr_gen_mat(p)
    return LinearCode(G)

def qqr_code(p):
    """
    EXAMPLES:
        sage: qqr_code(7)
        Linear code of length 14, dimension 7 over Finite Field of size 2
        sage: C = qqr_code(7)
        sage: C.minimum_distance()
        4
        sage: qqr_code(11)
        Linear code of length 44, dimension 12 over Finite Field of size 2
        sage: qqr_code(13)
        Linear code of length 52, dimension 12 over Finite Field of size 2

    """
    G = qqr_gen_mat(p)
    return LinearCode(G)

def polywt(r): 
    coeffs = r.list()
    return add([int(x) for x in coeffs]) 

def lqr_wt(c): 
    """
    EXAMPLES:
        sage: c = lqr_polycodeword(11,[1,2,3])
        sage: lqr_wt(c)
        22
    """
    return add([polywt(c[i]) for i in range(4)]) 

def qqr_wt(c): 
    """
    QUESTION: How many S \subset GF(p) are there such that
    |S*N| = k? How many S \subset GF(p) are there such that
    |S*Q| = k? How many S \subset GF(p) are there such that
    |S*N| + |S*Q| = k?
 
    EXAMPLES:
        sage: c = qqr_polycodeword(11,[1,2,3])
        sage: qqr_wt(c)
        22
        sage: p = 7; P = powerset(range(p))
        sage: Cpoly = [qqr_polycodeword(p,S) for S in P]
        sage: Cpolywts = [qqr_wt(c) for c in Cpoly]
        sage: Swts = [[S for S in P if qqr_wt(qqr_polycodeword(p,S)==k] for k in range(p)]
    """
    return add([polywt(c[i]) for i in range(2)]) 

def char_sum(p,S):
    """
    Returns the value of 
    \sum_{a\in GF(p)} \left(\frac{f_{S} (a)}{p}\right).

    EXAMPLES:

    """
    if S==[]:
        return p
    R = PolynomialRing(GF(p),"x")
    x = R.gen() 
    fS = prod([x - s for s in S])
    ans = add([kronecker_symbol(int(fS(a)),p) for a in GF(p)])
    return ans

"""
EXAMPLE:
p = 7
L = range(p)
C = [combinations(L,i) for i in range(1,p)]
vals = [max([char_sum(p,S) for S in C[i]]) for i in range(p-1)]
vals
## [0, -1, 4, 3, 0, -1]

p = 11
L = range(p)
C = [combinations(L,i) for i in range(1,p)]
vals = [max([char_sum(p,S) for S in C[i]]) for i in range(p-1)]
vals
## [0, -1, 4, 3, 4, 3, 4, 3, 0, -1]

p = 13
L = range(p)
C = [combinations(L,i) for i in range(1,p)]
vals = [max([char_sum(p,S) for S in C[i]]) for i in range(p-1)]
vals
## [0, -1, 6, 5, 4, 3, 6, 5, 4, 3, 2, 1]

p = 17
L = range(p)
C = [combinations(L,i) for i in range(1,p)]
vals = [max([char_sum(p,S) for S in C[i]]) for i in range(p-1)]
vals
## [0, -1, 6, 5, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

p = 19
L = range(p)
C = [combinations(L,i) for i in range(1,p)]
vals = [max([char_sum(p,S) for S in C[i]]) for i in range(p-1)]
vals
## [0, -1, 8, 7, 8, 7, 12, 11, 8, 7, 8, 7, 4, 3, 4, 3, 0, -1]

p = 23
L = range(p)
C = [combinations(L,i) for i in range(1,p)]
vals = [max([char_sum(p,S) for S in C[i]]) for i in range(p-1)]
vals

def comb(items, n=None):
    if n is None:
        n = len(items)    
    for i in range(len(items)):
        v = items[i:i+1]
        if n == 1:
            yield v
        else:
            rest = items[i+1:]
            for c in comb(rest, n-1):
                yield v + c

p = 29
L = range(p)
C = [comb(L,i) for i in range(1,p)]
vals = [max([char_sum(p,S) for S in C[i]]) for i in range(p-1)]
vals

"""