"""
Not AT ALL efficient (but easy to read) implementation of our generation tree.
Permutations are represented as set of cycles.
They are canonically represented as an ordered list of lists, starting with the minimum element.
Ex: [[1, 2], [3]] is the permutation ((1 2)(3)) = 213.
Python 3.4.
"""

from random import randint
from itertools import chain
import sys

k = 2

# Permutation Utils

def size(sigma):
    return sum(len(cycle) for cycle in sigma)

def index_element(t,a):
    return next(((i,j) for i in range(len(t)) for j in range(len(t[i])) if t[i][j] == a), None)

def cycleof(sigma, i):
    x, y = index_element(sigma,i)
    return sigma[x]

def antecedent(sigma,i):
    x, y = index_element(sigma,i)
    return sigma[x][y-1]

def image(sigma, i):
    x, y = index_element(sigma,i)
    return sigma[x][(y+1)%len(sigma[x])]

def iterated_images(sigma, i, length):
    x,y = index_element(sigma,i)
    return sigma[x][y+1:y+length+1]

def normalize(sigma):
    return sorted((c[m:]+c[:m] for c,m in ((c,c.index(min(c))) for c in sigma if len(c)>0)))

# Cycle Manipulations

def remove(sigma, i):
    x, y = index_element(sigma,i)
    return normalize(chain((c for c in sigma if c != sigma[x]),[sigma[x][:y]+sigma[x][y+1:]]))

def insert_inplace(sigma, a, b):
    index_b = index_element(sigma,b)
    if index_b:
        del sigma[index_b[0]][index_b[1]]
    if a == b:
        sigma += [[b]]
    else:
        i, j = index_element(sigma, a)
        sigma[i].insert(j+1, b)
    return sigma

def insert(sigma, a, b):
    return normalize(insert_inplace([c[:] for c in sigma], a, b))

def split(sigma, a, b):
    sigmaprime = [cycle[:] for cycle in sigma]
    a_i, a_j = index_element(sigmaprime, a)
    b_i, b_j = index_element(sigmaprime, b)
    if a_i == b_i:
        m, M = min(a_j,b_j), max(a_j,b_j)
        del sigmaprime[a_i]
        sigmaprime.append(sigma[a_i][m:M])
        sigmaprime.append(sigma[a_i][:m]+sigma[a_i][M:])
    return normalize(sigmaprime)

def append(sigma, a, b):
    sigmaprime = [cycle[:] for cycle in sigma]
    a_i, a_j = index_element(sigmaprime, a)
    b_i, b_j = index_element(sigmaprime, b)
    if a_i != b_i:
        del sigmaprime[a_i]
        new_b_i, j = index_element(sigmaprime, b)
        del sigmaprime[new_b_i]
        sigmaprime.append(sigma[a_i][a_j:]+sigma[a_i][:a_j]+sigma[b_i][b_j:]+sigma[b_i][:b_j])
    return normalize(sigmaprime)

# K-cycles preserving generation tree

def largest_non_kcycles(sigma):
    return max((max(cycle) for cycle in sigma if len(cycle) != k), default=0)

def special_cycle(sigma):
    return next((cycle for cycle in sigma if len(cycle) < k), [])

def minimum_special_cycle(sigma):
    return min(special_cycle(sigma), default=0)

def non_critical_cycles(sigma):
    cycles = [c for c in sigma if len(c) != k]
    for i in range(len(cycles)):
        if len(cycles[i]) == 2*k:
            if i==len(cycles)-1 and cycles[i][k] == min(cycles[i][k:]):
                continue
            if i<len(cycles)-1 and cycles[i][k] == min(cycles[i][k:]+[cycles[i+1][0]]):
                continue
        return cycles[i:]
    return []

def critical_elements(sigma):
    return list(cycle[i] for cycle in sigma if len(cycle) == 2*k for i in [0,k])

def pop(sigma,i):
    c_i, i_j = index_element(sigma, i)
    gamma = sigma[c_i][(i_j+1)%len(sigma[c_i])]
    non_critics = non_critical_cycles(sigma)
    p_cyc, p = non_critics[0], non_critics[0][0]
    
    L = lambda j: len(cycleof(sigma, j))

    if len(p_cyc) >= k+1:
        x = p_cyc[k-1]
        y = p_cyc[k]
        
        sigma_1 = insert(sigma, gamma, x)
        sigma_2 = insert(sigma, gamma, y)

        remel = p_cyc[k-1:]
        if non_critics[1:]:
            remel += [non_critics[1][0]]
            
        p_prime = min([x for x in remel if x != p])
        p_second = min([x for x in remel if x != p and x != p_prime])

    if L(p) == 2*k+1:
        if x == p_prime and y == p_second:
            return split(sigma_1, p, p_second)
        if y == p_prime:
            return split(sigma_1, p, p_prime)

    
    if L(p) != k+1:
        return insert(sigma, gamma, p_cyc[-1])

    if x == p_prime:
        if y == p_second :
            return insert(sigma_1, p_second, p_second)
        if L(p_second) != k-1:
            return insert(sigma_1, p_second, y)
        return append(sigma_2, p , p_second)

    if y == p_prime:
        return insert(sigma_1, p_prime, p_prime)
    if L(p_prime) != k-1:
        return insert(sigma_1, p_prime, y)
    return append(sigma_2, p, p_prime)

def joinkcycles(cyclesk):
    cycles2k = []
    for i in range(0,len(cyclesk),2):
        cycles2k += [cyclesk[i]+cyclesk[i+1]]
    return cycles2k

def join(cycles2k, cyclesk):
    return normalize(joinkcycles(sorted(cycles2k))+cyclesk)

def splet_2kcycles(sigma):
    cycles2k = [c for c in sigma if len(c) == 2*k]  
    return [c[:k] for c in cycles2k] + [c[k:] for c in cycles2k] 
    

def hide_and_shift(sigma,i):
    n = size(sigma)
    cycleskothers = [c for c in sigma if len(c) == k if n not in c and i not in c]
    cycles = [cycleof(sigma,n), cycleof(sigma,i)] + splet_2kcycles(sigma)
    return join(cycles, cycleskothers)

def split_and_shift(tau):
    gamma = largest_non_kcycles(tau)
    
    cycles2k = splet_2kcycles(tau)
    
    cycle_gamma = next(cycle for cycle in cycles2k if gamma in cycle)
    cycles2k.remove(cycle_gamma)

    cyclesk = [c for c in tau if len(c) == k] + [cycle_gamma, cycles2k[-1]]

    sigmaprime = join(cycles2k[:-1], cyclesk)

    return insert(sigmaprime, gamma, cycles2k[-1][1])

def shift(tau):
    gamma = largest_non_kcycles(tau)
    i = antecedent(tau, gamma)
    
    sigma = remove(tau, gamma)
    minsc = minimum_special_cycle(sigma)
    delta = minsc if minsc != 0 else i

    P = critical_elements(sigma)

    if i not in P:
        return insert(tau, delta, i)

    y = P.index(i)
    
    for l in range(y+1,len(P)):
        if P[l] > min(iterated_images(sigma,P[l-1],k-1)):
            break
    else:
        l = len(P)

    h = l-y
    a = min(iterated_images(sigma,P[l-1],k))

    sigmaprime = insert(tau, a, gamma)
    sigmaprime = insert(sigmaprime, P[l-1], a)
    
    for j in range(l-1,l-h,-1):
        sigmaprime = insert(sigmaprime, P[j-1], P[j])

    return insert(sigmaprime, delta, i)
  
def inverse_shift(sigma):
    delta = minimum_special_cycle(sigma)
    gamma = largest_non_kcycles(sigma)
    i = image(sigma,delta)
    n = size(sigma)

    P = [0] + critical_elements(sigma)
    y = next((l for l in range(1,len(P)) if gamma in iterated_images(sigma,P[l],k-1)))
    
    if i > P[y]:
        return insert(sigma, antecedent(sigma, n), i)

    l = next(l for l in range(1,y+1) if P[l-1] < i < P[l])
    
    sigmaprime = insert(sigma, antecedent(sigma, P[l]), i)

    for j in range(l, y):
        sigmaprime = insert(sigmaprime, P[j+1], P[j])

    sigmaprime = insert(sigmaprime, n, P[y])
    return insert(sigmaprime, i, n)
    
#### Generation Tree

def is_critical(sigma):
    return size(sigma) % k == 0 and not non_critical_cycles(sigma)

def is_special(sigma):
    if size(sigma) % k != 0:
        sc = [cycle for cycle in sigma if len(cycle) < k]
        return len(sc) == 1 and not non_critical_cycles(cycle for cycle in sigma if cycle != sc[0])
    return not non_critical_cycles(sigma)

def generation_tree(sigma, i):
    n = size(sigma)+1
    tau = insert(sigma, i, n)
    gamma = largest_non_kcycles(sigma)
    minsc = minimum_special_cycle(sigma)
    delta = minsc if minsc != 0 else i

    L = lambda i: 0 if i == n else len(cycleof(sigma,i))

    if L(i) != k:
        l = L(i)
        zeta = tau
    elif L(i) == k and i < gamma:
        l = L(gamma)
        zeta = insert(tau, antecedent(sigma, gamma), i)
    else:
        l = 0
        zeta = insert(tau, i, i)
        
    if l == k-1 and not is_special(sigma):
        return pop(zeta,i)

    if l == 2*k-1 and is_special(zeta) and n%k != 0:
        return inverse_shift(zeta)

    if l == 2*k-1 and is_special(zeta):
        return split_and_shift(zeta)

    if l == 2*k and is_special(sigma) and i > minimum_special_cycle(sigma) and n%k != 0:
        if L(i) == 2*k:
            return shift(zeta)
        return insert(tau, delta, i)

    if l == k-1 and is_special(sigma):
        if L(i) == k-1:
            return zeta
        return hide_and_shift(zeta,i)

    return zeta    

#### Random Generation

def generate_random_permutation(n):
    sigma = []
    for i in range(1,n+1):
        sigma = generation_tree(sigma, randint(1,i))
    return sigma

#### Classical Generation Trees
# A permutation is just a list of values, ex: [2,1,3] for (1 2)(3).

def last_value_insertion(sigma, i):
    sigma = sigma[:]+[i]
    for j in range(len(sigma)-1):
        if sigma[j] >= i:
            sigma[j] += 1 
    return sigma
    
def knuth_shuffle(sigma, i):
    n = len(sigma)+1
    if i != n:
        sigma = sigma[:] + [sigma[i-1]]
        sigma[i-1] = n
    else:
        sigma = sigma[:] + [n]
    return sigma

### Tikz tree generation

def cycle_str(perm):
    return ''.join('('+''.join(map(str,c))+')' for c in perm)

def table2cycle(perm):
    cycles = []
    n = len(perm)
    visited = [False]*n
    for i in range(1,n+1):
        if not visited[i-1]:
            visited[i-1] = True
            c = [i]
            while perm[c[-1]-1] != i:
                visited[perm[c[-1]-1]-1] = True
                c += [perm[c[-1]-1]]
            cycles += [c]
    return cycles

def print_tex_begin(f):
    print(r"\documentclass{standalone}", file=f)
    print(r"\usepackage{tikz-qtree}", file=f)
    print(r"\begin{document}", file=f)

def print_tex_end(f):
    print("", file=f)
    print(r"\end{tikzpicture}", file=f)
    print(r"\end{document}", file=f)
    
def print_tikz_preembule(n, f):
    print_tex_begin(f)
    print(r"\begin{tikzpicture}[grow=right, level distance=20mm]", file=f)
    print(r"\tikzset{every tree node/.style={font=\tiny}}", file=f)
    print(r"\tikzstyle{level 1}=[sibling distance=-1mm] ", file=f)
    print(r"\tikzstyle{level 2}=[sibling distance=-1.5mm]", file=f)
    print(r"\tikzstyle{level 3}=[sibling distance=-1.8mm]", file=f)
    print(r"\tikzstyle{level 4}=[sibling distance=-2.01mm]", file=f)
    print(r"\tikzstyle{level 5}=[sibling distance=-2.2mm]", file=f)
    print(r"\draw node at (0.5, "+str(0.1344*n*n)+r") {\underline{$k="+str(k)+"$}};", file=f)
                
def print_tikz_generation_tree(n, borderlevel=False, f=sys.stdout):
    print_tikz_preembule(n, f)
    
    print(r"\tikzstyle{critical} = [color=red, font=\tiny \bfseries]", file=f)
    print(r"\tikzstyle{special} = [color=red]", file=f)
    print(r"\Tree", file=f)

    def print_tree_rec(p):
      if size(p) <= n :
        permstr = cycle_str(p) if size(p) != n and borderlevel else '.'
        
        if is_critical(p) :
            print(r"[.\node[critical]{"+permstr+"}; ", end="", file=f)
        elif is_special(p) :
            print(r"[.\node[special]{"+permstr+"}; ", end="", file=f)
        else:
            print("[.{"+permstr+"} ", end="", file=f)
        
        for i in range(1,size(p)+2):
          print_tree_rec(generation_tree(p, i))
          
        print("]", end="", file=f)
        
    print_tree_rec([[1]])

    print_tex_end(f)
    

def print_tikz_classical_tree(n, tree, borderlevel=False, f=sys.stdout):
    print_tikz_preembule(n,f)

    print(r"\tikzstyle{changing} = [red, font=\tiny \bfseries]", file=f)
    print(r"\Tree", file=f)
    
    def nb_kcycles(sigma):
        return len([cycle for cycle in sigma if len(cycle)==k])

    def print_tree_rec(p):
      if len(p) < n :
        kp = nb_kcycles(table2cycle(p))
        for i in range(1,len(p)+2):
            child = tree(p, i)
            child_cycles = table2cycle(child)
            permstr = cycle_str(child_cycles) if len(child) != n and borderlevel else '.'
            
            if kp != nb_kcycles(child_cycles) :
                print(r"[.\node[changing]{"+permstr+"}; ", end="", file=f)
            else:
                print("[.{"+permstr+"} ", end="", file=f)

            print_tree_rec(child)
            
            print("]", end="", file=f)

    print(r"[.\node[changing]{(1)}; ",end="", file=f)
    print_tree_rec([1])
    print(r"] ", end="", file=f)

    print_tex_end(f)


def gentree(n, tree=generation_tree):
  allperm = [[] for j in range(n+1)]
  allperm[1].append(((1,),))
  
  for m in range(1,n+1):
    for p in allperm[m]:
      for i in range(1,n+2):
        allperm[m+1].append( tree(p,i) )
        print(p)

from subprocess import call
from sys import stdout
def tikz_permutation(perm, scale=0.8, f=sys.stdout):
    print(r"\begin{tikzpicture}[thick, scale="+str(scale)+"]", file=f)
    i = 0
    length = [1,1.75,2,3,4,4]
    offsets = [[(0,0)],[(0,1),(0,-1)],[(-0.75,0),(0.25,1),(0.25,-1)],[(-1,0),(0,1),(1,0),(0,-1)],\
               [(-1.5,0),(-0.75,1),(0.75,1),(1.5,0),(0,-1)],\
               [(-1.5,0),(-0.75,1),(0.75,1),(1.5,0),(0.75,-1),(-0.75,-1)]]
    
    for cycle in normalize(perm):
        l = len(cycle)
        i += length[l-1]/2

        if l == 1:
            print(r"\node ("+str(cycle[0])+") at ("+str(i)+",0) {$"+str(cycle[0])+"$};", file=f)
            print(r"\draw[->] ("+str(cycle[0])+") edge [loop, looseness=5] ("+str(cycle[0])+");", file=f)

        else:
            for j in range(len(cycle)):
                pos = (i+offsets[l-1][j][0], offsets[l-1][j][1])
                print(r"\node ("+str(cycle[j])+") at "+str(pos)+" {$"+str(cycle[j])+"$};", file=f)
            for j in range(len(cycle)):
                print(r"\draw[->] ("+str(cycle[j-1])+") edge [bend left] ("+str(cycle[j])+");", file=f)

        i += length[l-1]/2
        
    print(r"\end{tikzpicture}", file=f)
    
def tikz_permutations(perms, name="perm.tex", scale=0.8):
    f = open(name, 'w')
    print(r"\documentclass[varwidth]{standalone}", file=f)
    print(r"\usepackage{tikz-qtree}", file=f)
    print(r"\begin{document}", file=f)
    print(r"\begin{center}", file=f)
    for p in perms:
        tikz_permutation(p,scale,f)
        print(r"", file=f)
    print(r"\end{center}", file=f)
    print(r"\end{document}", file=f)
    f.close()
    call(["pdflatex","-interaction=batchmode", name])

def tikz_tree(n,K=1,algo=1,name="tree.tex"):
    f = open(name, 'w')
    global k
    k=K
    if algo == 1:
        print_tikz_generation_tree(n, True, f)
    elif algo == 2:
        print_tikz_classical_tree(n, last_value_insertion, True, f)
    else:
        print_tikz_classical_tree(n, knuth_shuffle, True, f)
    f.close()
    call(["pdflatex","-interaction=batchmode", name])
    
# New names
merge = hide_and_shift
cut = split_and_shift