knots.py

Aller à la documentation de ce fichier.

#!/usr/bin/env python
# -*- coding: latin-1 -*-
##\package DSPython.knots Théorie des \htmlonly nœuds\endhtmlonly
#
# Cf. \htmlonly <a href="http://www.opimedia.be/Bruno_Marchal/index.htm#Liens" target="_blank">
#   <tt>http://www.opimedia.be/Bruno_Marchal/index.htm#Liens</tt></a>\endhtmlonly

##\file
# Théorie des \htmlonly n&oelig;uds\endhtmlonly
#
# Cf. \htmlonly <a href="http://www.opimedia.be/Bruno_Marchal/index.htm#Liens" target="_blank">
#   <tt>http://www.opimedia.be/Bruno_Marchal/index.htm#Liens</tt></a>\endhtmlonly

# (c) Olivier Pirson --- DragonSoft
# http://www.opimedia.be/DS/
# Débuté le 3 mars 2007
####################################
from __future__ import print_function

## Date du dernier changement pour ce module
VERSION = 'knots --- 2010 April 12'

import copy, functools, numbers

import DSPython
import DSPython.natural as natural
import DSPython.polynomial as polynomial



# ############
# Constantes #
##############
## Caractère pour un espacement vide
EMPTY = ' '

## Caractère pour un brin à gauche
LEFT = ')'

## Caractère pour un brin à droite
RIGHT = '('

## Caractère pour un brin en haut
TOP = '^'

## Caractère pour un brin en bas
BOTTOM = '_'

## Caractère pour un brin diagonal montant
UP = '/'

## Caractère pour un brin diagonal descendant
DOWN = '\\'

##\brief Caractère pour deux brins verticaux
# (notamment l'état non labellisé d'un croisement CROSSUP A ou CROSSDOWN B)
VERT = '"'

##\brief Caractère pour deux brins horizontaux
# (notamment l'état non labellisé d'un croisement CROSSUP B ou CROSSDOWN A
HORI = '='

## Caractère pour un croisement dont le brin diagonal montant passe au-dessus
CROSSUP = '%'

## Caractère pour un croisement dont le brin diagonal descendant passe au-dessus
CROSSDOWN = '&'


## Caractère pour l'état labellisé A d'un croisement CROSSUP
CROSSUPA = 'A'

## Caractère pour l'état labellisé B d'un croisement CROSSUP
CROSSUPB = 'B'

## Caractère pour l'état labellisé A d'un croisement CROSSDOWN
CROSSDOWNA = 'a'

## Caractère pour l'état labellisé B d'un croisement CROSSDOWN
CROSSDOWNB = 'b'


##\brief Caractère pour un croisement non "orienté"
# (croisement dans l'univers du \htmlonly n&oelig;ud\endhtmlonly)
CROSS = 'x'


## Caractères permis pour constituer un \htmlonly n&oelig;ud\endhtmlonly
KNOTCHARS = EMPTY + LEFT + RIGHT + TOP + BOTTOM + UP + DOWN + VERT + HORI + CROSSUP + CROSSDOWN

## Caractères permis pour constituer un état labellisé
LABELSTATECHARS = EMPTY + LEFT + RIGHT + TOP + BOTTOM + UP + DOWN + VERT + HORI \
                  + CROSSUPA + CROSSUPB + CROSSDOWNA + CROSSDOWNB

## Caractères permis pour constituer un état non labellisé
STATECHARS = EMPTY + LEFT + RIGHT + TOP + BOTTOM + UP + DOWN + VERT + HORI

## Caractères permis pour constituer l'univers d'un \htmlonly n&oelig;ud\endhtmlonly
UNIVERSECHARS = EMPTY + LEFT + RIGHT + TOP + BOTTOM + UP + DOWN + VERT + HORI + CROSS


##\brief <a class="relative" href="piecesknots.png" target="_blank">Caractères permis</a>
# (<a class="relative" href="piecesknots.eps" target="_blank">.eps</a>) pour constituer un espace
# \htmlonly <a class="relative" href="piecesknots.png" target="_blank"><img
# src="piecesknots_th.png" border="0" align="top" alt="[piecesknots_th.png]"></a>\endhtmlonly
SPACECHARS = KNOTCHARS + CROSSUPA + CROSSUPB + CROSSDOWNA + CROSSDOWNB + CROSS


##\brief Dictionnaire qui pour chaque type d'élément
# contient la description des bouts de \htmlonly n&oelig;ud\endhtmlonly dans le coin considéré :
# None si le coin est vide,
# sinon un couple (x, y) avec x et y == -1, 0 ou 1
# indiquant la direction du bout de \htmlonly n&oelig;ud\endhtmlonly
CORNERS = {}
CORNERS[EMPTY] = ((None, None),
                  (None, None))
CORNERS[LEFT] = (((0, 1), None),
                 ((0, -1), None))
CORNERS[RIGHT] = ((None, (0, 1)),
                  (None, (0, -1)))
CORNERS[TOP] = (((1, 0), (-1, 0)),
                (None, None))
CORNERS[BOTTOM] = ((None, None),
                   ((1, 0), (-1, 0)))
CORNERS[UP] = ((None, (-1, 1)),
               ((1, -1), None))
CORNERS[DOWN] = (((1, 1), None),
                 (None, (-1, -1)))
CORNERS[CROSS] = (((1, 1), (-1, 1)),
                  ((1, -1), (-1, -1)))
CORNERS[CROSSUP] = CORNERS[CROSS]
CORNERS[CROSSDOWN] = CORNERS[CROSS]

CORNERS[VERT] = (((0, 1), (0, 1)),
                 ((0, -1), (0, -1)))
CORNERS[HORI] = (((1, 0), (-1, 0)),
                 ((1, 0), (-1, 0)))
CORNERS[CROSSUPA] = CORNERS[VERT]
CORNERS[CROSSUPB] = CORNERS[HORI]
CORNERS[CROSSDOWNA] = CORNERS[HORI]
CORNERS[CROSSDOWNB] = CORNERS[VERT]


##\brief Dictionnaire de dictionnaires contenant
# les premiers \htmlonly n&oelig;uds\endhtmlonly premiers 0<sub>1</sub>,
# 3<sub>1</sub>, 4<sub>1</sub>, 5<sub>1</sub>, 5<sub>2</sub>,
# 6<sub>1</sub>, 6<sub>2</sub>, 6<sub>3</sub>, 7<sub>1</sub>
PRIMEKNOTS = {}
PRIMEKNOTS[0] = {}
PRIMEKNOTS[0][1] = ['()']
PRIMEKNOTS[3] = {}
PRIMEKNOTS[3][1] = [' /%\\',
                    '(( &',
                    ' \\%/']
PRIMEKNOTS[4] = {}
PRIMEKNOTS[4][1] = ['   _',
                    ' /% \\',
                    '(( &&',
                    ' \\% /',
                    '   ^']
PRIMEKNOTS[5] = {}
PRIMEKNOTS[5][1] = ['   _',
                    ' /% %\\',
                    '(( ^ ))',
                    ' \\%%%/']
PRIMEKNOTS[5][2] = ['  _',
                    '/% \\',
                    '& &&',
                    '\\% /',
                    '  ^']
PRIMEKNOTS[6] = {}
PRIMEKNOTS[6][1] = ['   ___',
                    ' /%   \\',
                    '(( &&&&',
                    ' \\%   /',
                    '   ^^^']
PRIMEKNOTS[6][2] = ['  _',
                    ' /_\\',
                    ' & &',
                    '( % )',
                    ' & &',
                    ' \\%/']
PRIMEKNOTS[6][2] = ['   _',
                    ' /% %\\',
                    '(( & &',
                    ' \\% %/',
                    '   ^']
PRIMEKNOTS[6][3] = ['   _',
                    ' /& &\\',
                    '(( % %',
                    '( & ^/',
                    ' \\& /',
                    '   ^']
PRIMEKNOTS[7] = {}
PRIMEKNOTS[7][1] = [' _____',
                    '/     \\',
                    '%%%%%%%',
                    '\\     /',
                    ' ^^^^^']


##\brief \htmlonly N&oelig;ud\endhtmlonly borroméen
# (un lien de 3 \htmlonly n&oelig;uds\endhtmlonly entremêlés)
BORROMEAN = ['  /&\\',
             ' //_\\\\',
             '( & & )',
             ' % % %',
             ' \\^ ^/',
             '  ^^^']



# ###########
# Fonctions #
#############
## Modifie l'espace s en lui ajoutant l'espace a à droite
def addtoright(s, a):
    """Modifie l'espace s en lui ajoutant l'espace a à droite

    Pre: s: space
         a: space

    Result: None

    O(s) = ..."""
    assert space_is(s), s
    assert space_is(a), a

    m = 0  # plus grande longueur
    for y in range(min(len(s), len(a))):
        m = max(m, len(s[y]))
    for y in range(min(len(s), len(a))):
        s[y] += EMPTY*(m - len(s[y])) + a[y]
    if len(s) < len(a):
        for y in range(len(s), len(a)):
            s.append(EMPTY*m + a[y])


## Tous les cycles de l'espace s sont fermés ?
def closed_is(s):
    """Renvoie True si tous les cycles de l'espace s sont fermés,
    False sinon

    Pre: s: space

    Result: boolean

    O(s) = ..."""
    assert space_is(s), s

    prev = ''  # avant-première ligne vide
    for line in s + ['']:  # avec une après-dernière ligne vide
        line_src = line + EMPTY  # ajoute un après-dernier élément vide
        if len(prev) > len(line):
            line += EMPTY * (len(prev) - len(line))
        elif len(prev) < len(line):
            prev += EMPTY * (len(line) - len(prev))
        prev_c = EMPTY  # avant-premier élément vide pour la ligne précédente
        line_c = EMPTY  # avant-premier élément vide pour la ligne courante
        for i in range(len(line)):
            #  prev_c | prev[i]
            # -------- --------- le coin courant
            #  line_c | line[i]
            nb = ((CORNERS[prev_c][1][1] != None) + (CORNERS[prev[i]][1][0] != None)
                  + (CORNERS[line_c][0][1] != None) + (CORNERS[line[i]][0][0] != None))
            if (nb != 0) and (nb != 2):
                assert nb == 1, (i, nb, line)

                return False
            prev_c = prev[i]
            line_c = line[i]
        prev = line_src
    return True


## s est de type knots ?
def knots_is(s):
    """Renvoie True si l'espace s est de type knots
    (un espace vide ou contenant des noeuds),
    False sinon

    Pre: s: space

    Result: boolean

    O(s) = ..."""
    assert space_is(s), s

    return links_is(s)#???


## Renvoie la liste ordonnée des combinaisons possibles de labels A et B pour nb croisements
def labels_list(nb):
    """Renvoie la liste ordonnée des combinaisons possibles de labels A et B
    pour nb croisements
    (Si nb == 0 alors renvoie ['']
     Si nb == 1 alors renvoie ['A', 'B']
     Si nb == 2 alors renvoie ['AA', 'AB', 'BA', 'BB']
     Si nb == 2 alors renvoie ['AAA', 'AAB', 'ABA', 'ABB',
                               'BAA', 'BAB', 'BBA', 'BBB']
     ...)

    Pre: nb: naturel

    Result: liste de 2**n string de 'A' et 'B' de longueur n

    O(nb) = ..."""
    assert DSPython.natural_is(nb), nb

    if nb > 0:
        l = []
        for s in labels_list(nb - 1):
            l.append(s + 'A')
            l.append(s + 'B')
        return l
    else:
        return ['']


## s est de type labelstates ?
def labelstates_is(s):
    """Renvoie True si l'espace s est de type labelstates
    (un espace vide ou contenant des états labellisés de noeuds),
    False sinon

    Pre: s: space

    Result: boolean

    O(s) = ..."""
    assert space_is(s), s

    if not isinstance(s, list):
        return False
    for line in s:
        if not isinstance(line, str):
            return False
        for c in line:
            if c not in LABELSTATECHARS:
                return False
    return True


## s est de type links ?
def links_is(s):
    """Renvoie True si l'espace s est de type links
    (un espace vide ou contenant des liens),
    False sinon

    Pre: s: space

    Result: boolean

    O(s) = ..."""
    assert space_is(s), s

    if not isinstance(s, list):
        return False
    for line in s:
        if not isinstance(line, str):
            return False
        for c in line:
            if c not in KNOTCHARS:
                return False
    return True


##\brief Modifie l'espace s pour que toutes les lignes aient même longueur
# en ajoutant des add à droite
def make_egalwidth(s, add=EMPTY):
    """ Modifie l'espace s pour que toutes les lignes aient même longueur
    en ajoutant des add à droite
    !!! Le résultat n'est pas forcément un space

    Pre: s: space
         add: caractère de SPACECHARS

    Result: None

    O(s) = ..."""
    assert space_is(s), s
    assert isinstance(add, str), add
    assert len(add) == 1, add
    assert add in SPACECHARS, add

    m = functools.reduce(lambda m, line: max(m, len(line)), s, 0)  # plus grande longueur
    for y in range(len(s)):
        s[y] += add*(m - len(s[y]))


## Renvoie l'image miroir de l'espace s
def mirror(s):
    """Renvoie l'image miroir de l'espace s

    Pre: s: space

    Result: space

    O(s) = ..."""
    assert space_is(s), s

    CONV = {}
    CONV[EMPTY] = EMPTY
    CONV[LEFT]  = LEFT
    CONV[RIGHT] = RIGHT
    CONV[TOP]    = TOP
    CONV[BOTTOM] = BOTTOM
    CONV[UP]   = UP
    CONV[DOWN] = DOWN
    CONV[VERT] = HORI
    CONV[HORI] = VERT
    CONV[CROSSUP]   = CROSSDOWN
    CONV[CROSSDOWN] = CROSSUP
    CONV[CROSSUPA]   = CROSSDOWNA
    CONV[CROSSDOWNA] = CROSSUPA
    CONV[CROSSUPB]   = CROSSDOWNB
    CONV[CROSSDOWNB] = CROSSUPB
    CONV[CROSS] = CROSS

    r = []
    for line in s:
        new_line = ''
        for c in line:
            new_line += CONV[c]
        r.append(new_line)

    assert space_is(r), r

    return r


## Renvoie le nombre d'états A (croisements up ou down) de l'espace d'états labellisés s
def nb_A(s):
    """Renvoie le nombre d'états A (croisements up ou down)
    de l'espace d'états labellisés s

    Pre: s: labelstates

    Result: naturel

    O(s) = ..."""
    assert labelstates_is(s), s

    return nb_items(s, CROSSUPA + CROSSDOWNA)


## Renvoie le nombre d'états B (croisements up ou down) de l'espace d'états labellisés s
def nb_B(s):
    """Renvoie le nombre d'états B (croisements up ou down)
    de l'espace d'états labellisés s

    Pre: s: labelstates

    Result: naturel

    O(s) = ..."""
    assert labelstates_is(s), s

    return nb_items(s, CROSSUPB + CROSSDOWNB)


##\brief Renvoie le nombre de croisements (up, down ou non "orientés")
# et d'états de croisements labellisés de l'espace s
def nb_cross(s):
    """Renvoie le nombre de croisements (up, down ou non "orientés")
    et d'états de croisements labellisés de l'espace s

    Pre: s: space

    Result: naturel

    O(s) = ..."""
    assert space_is(s), s

    return nb_items(s, CROSSUP + CROSSDOWN + CROSSUPA + CROSSUPB + CROSSDOWNA + CROSSDOWNB + CROSS)


## Renvoie (nombre de cycles, nombre de cycles ouverts) de l'espace s
def nb_cycle(s):
    """Renvoie (nombre de cycles, nombre de cycles ouverts) de l'espace s

    Pre: s: space

    Result: (naturel, naturel)

    O(s) = ..."""
    assert space_is(s), s

    return Corners(s).nb_cycle()


## Renvoie le nombre d'éléments de l'espace s qui sont dans items
def nb_items(s, items):
    """Renvoie le nombre d'éléments de l'espace s qui sont dans items

    Pre: s: space
         items: string de caractères appartenant à SPACECHARS

    Result: naturel

    O(s) = ..."""
    assert space_is(s), s
    assert isinstance(items, str), items
    if __debug__:
        for c in items:
            assert c in SPACECHARS, (c, items)

    nb = 0
    if items != '':
        for line in s:
            for c in line:
                if c in items:
                    nb += 1
    return nb


## Renvoie le polynôme invariant de Kauffman pour l'espace de \htmlonly n&oelig;uds\endhtmlonly s
def poly_Kauffman(s):
    """Renvoie le polynôme invariant de Kauffman pour l'espace de noeuds s,
    c.-à-d. (-A^(-3))^writhe(s) * poly_Kauffman_A(s)
    (invariant pour les isotopies :
    mouvements 0, I, II et III de Reidemeister)

    Pre: s: knots non vide

    Result: Polynomial

    O(s) = ..."""
    assert knots_is(s), s
    if __debug__:
        nb = nb_cycle(s)
        assert nb[0] > 0, nb[0]
        assert nb[1] == 0, nb[1]

    p = poly_Kauffman_A(s)
    w = writhe(s)
    r = polynomial.Polynomial()
    if w%2 == 0:
        for k in p:
            r[polynomial.Term((k[0] - 3*w, ))] = p[k]
    else:
        for k in p:
            r[polynomial.Term((k[0] - 3*w, ))] = -p[k]
    return r


## Renvoie le polynôme A de Kauffman pour l'espace de \htmlonly n&oelig;uds\endhtmlonly s
def poly_Kauffman_A(s):
    """Renvoie le polynôme A de Kauffman pour l'espace de noeuds s,
    c.-à-d. le polynôme ABd de Kauffman avec B = A^-1 et d = -A^2 - A^-2
    (invariant pour les isotopies régulières :
    mouvements 0, II et III de Reidemeister)

    Pre: s: knots non vide

    Result: Polynomial

    O(s) = ..."""
    assert knots_is(s), s
    if __debug__:
        nb = nb_cycle(s)
        assert nb[0] > 0, nb[0]
        assert nb[1] == 0, nb[1]

    p = polynomial.Polynomial(varsstr='A')
    for labels in labels_list(nb_cross(s)):
        st = to_labelstates(s, labels)
        d_e = nb_cycle(st)[0] - 1
        e = nb_A(st) - nb_B(st) - d_e*2
        sign = (1 if d_e%2 == 0
                else -1)
        for i in range(d_e + 1):
            p.__iadd__(polynomial.Term((e + i*4, )), coef=natural.binom(d_e, i)*sign)
    return p


## Renvoie le polynôme ABd de Kauffman pour l'espace de \htmlonly n&oelig;uds\endhtmlonly s
def poly_Kauffman_ABd(s):
    """Renvoie le polynôme ABd de Kauffman pour l'espace de noeuds s
    = somme sur tous les états labellisés de s
      du produit des labels A et B
                 et de d^(nombre de cycles fermés - 1) de l'état

    Pre: s: knots

    Result: Polynomial

    O(s) = ..."""
    assert knots_is(s), s
    assert nb_cycle(s)[1] == 0, nb_cycle(s)[1]

    p = polynomial.Polynomial(varsstr='ABd')
    for labels in labels_list(nb_cross(s)):
        st = to_labelstates(s, labels)
        p += polynomial.Term((nb_A(st), nb_B(st), nb_cycle(st)[0] - 1))
    return p


## Renvoie le \htmlonly n&oelig;ud\endhtmlonly premier n<sub>1</sub>
def primeknots_even_1(n):
    """Renvoie le noeud premier n_1

    Pre: n: naturel pair >= 4

    Result: knots

    O(n) = ..."""
    assert n >= 4, n

    n -= 3
    k = ['   ' + '_'*n,
         ' /%' + ' '*n + '\\',
         '(( &' + '&'*n,
         ' \\%' + ' '*n + '/',
         '   ' + '^'*n]
    return k


## Renvoie l'espace lu dans le fichier f
def read(f):
    """Renvoie l'espace lu dans le fichier f

    Pre: f: fichier (texte) ouvert en lecture

    Result: list de string (qui n'est pas forcément un space !!!)

    O(f) = ..."""
#    assert isinstance(f, file), type(f)

    l = f.read().splitlines()
    r = []
    for s in l:
        if s != '':
            r.append(s)
    return r


## Renvoie l'espace s avec une rotation de nb*90° dans le sens anti-horloger
def rotate(s, nb=1):
    """Renvoie l'espace s avec une rotation de nb*90°
      dans le sens anti-horloger

    Pre: s: space
         nb: Integral

    Result: space

    O(s) = ..."""
    assert space_is(s), s
    assert isinstance(nb, numbers.Integral), nb

    CONV = {}
    CONV[EMPTY] = EMPTY
    CONV[LEFT]  = BOTTOM
    CONV[RIGHT] = TOP
    CONV[TOP]    = LEFT
    CONV[BOTTOM] = RIGHT
    CONV[UP]   = DOWN
    CONV[DOWN] = UP
    CONV[VERT] = HORI
    CONV[HORI] = VERT
    CONV[CROSSUP]   = CROSSDOWN
    CONV[CROSSDOWN] = CROSSUP
    CONV[CROSSUPA]   = CROSSDOWNA
    CONV[CROSSDOWNA] = CROSSUPA
    CONV[CROSSUPB]   = CROSSDOWNB
    CONV[CROSSDOWNB] = CROSSUPB
    CONV[CROSS] = CROSS

    nb %= 4
    m = functools.reduce(lambda m, line: max(m, len(line)), s, 0)  # plus grande longueur
    while nb > 0:
        r = [''] * m  # m colonnes donne m lignes
        for y in range(len(s)):
            line = s[y] + EMPTY*(m - len(s[y]))
            for x in range(len(line)):
                r[m - 1 - x] += CONV[line[x]]

        assert space_is(r), r

        m = len(s)
        s = r
        nb -= 1
    return s


## s est de type space ?
def space_is(s):
    """Renvoie True si s est de type space
    (un espace vide ou contenant des noeuds,
    états de noeuds (labellisés ou non) et univers de noeuds),
    False sinon

    Pre: s: object quelconque

    Result: boolean

    O(s) = ..."""
    if not isinstance(s, list):
        return False
    prev = ''  # avant-première ligne vide
    for line in s + ['']:  # avec une après-dernière ligne vide
        if not isinstance(line, str):
            return False
        line_src = line + EMPTY  # ajoute un après-dernier élément vide
        if len(prev) > len(line):
            line += EMPTY * (len(prev) - len(line))
        elif len(prev) < len(line):
            prev += EMPTY * (len(line) - len(prev))
        prev_c = EMPTY  # avant-premier élément vide pour la ligne précédente
        line_c = EMPTY  # avant-premier élément vide pour la ligne courante
        if line_c not in SPACECHARS:
            return False
        for i in range(len(line)):
            if line[i] not in SPACECHARS:
                return False
            #  prev_c | prev[i]
            # -------- --------- le coin courant
            #  line_c | line[i]
            nb = ((CORNERS[prev_c][1][1] != None) + (CORNERS[prev[i]][1][0] != None)
                  + (CORNERS[line_c][0][1] != None) + (CORNERS[line[i]][0][0] != None))
            if nb > 2:
                return False
            prev_c = prev[i]
            line_c = line[i]
        prev = line_src
    return True


## s est de type states ?
def states_is(s):
    """Renvoie True si l'espace s est de type states
    (un espace vide ou contenant des états non labellisés de noeuds),
    False sinon

    Pre: s: space

    Result: boolean

    O(s) = ..."""
    assert space_is(s), s

    if not isinstance(s, list):
        return False
    for line in s:
        if not isinstance(line, str):
            return False
        for c in line:
            if c not in STATECHARS:
                return False
    return True


## Renvoie l'état labellisé de l'espace s de \htmlonly n&oelig;uds\endhtmlonly ou d'états labellisés
def to_labelstates(s, labels=''):
    """Renvoie l'état labellisé de l'espace s de noeuds ou d'états labellisés
    Le parcours de s se fait de la gauche vers la droite,
    du haut vers le bas.
    Chaque croisement est alors remplacé par son état labellisé
    en fonction du 'A' ou 'B' dans labels.
    Lorsque les caractères de labels sont épuisés,
    c'est l'état A qui est choisi.

    Pre: s: knots ou labelstates
            (ou space mélange des deux,
            mais ne contenant pas d'état non labellisé
            ou de croisement non "orienté")
         labels: string de 'A' et 'B'

    Result: labelstates

    O(s) = ..."""
    assert space_is(s), s

    new_s = []
    for line in s:
        new_line = ''
        for c in line:
            assert c != CROSS

            if c in CROSSUP + CROSSUPA + CROSSUPB :
                new_line += (CROSSUPA if (labels == '') or (labels[0] == 'A')
                             else CROSSUPB)
                labels = labels[1:]
            elif c in CROSSDOWN + CROSSDOWNA + CROSSDOWNB:
                new_line += (CROSSDOWNA if (labels == '') or (labels[0] == 'A')
                             else CROSSDOWNB)
                labels = labels[1:]
            else:
                new_line += c
        new_s.append(new_line)
    return new_s


##\brief Renvoie un string contenant le code L<sup>A</sup>T<sub>E</sub>X
# (pour le module Knots.sty) de la représentation de l'espace s

## Module L<sup>A</sup>T<sub>E</sub>X :
# <a class="relative" href="latex/Knots.sty" target="_blank">Knots.sty</a>\n
# Documentation et exemples :
# <a class="relative" href="latex/Knots.tex" target="_blank">Knots.tex</a>,
# <a class="relative" href="latex/Knots.ps" target="_blank">Knots.ps</a>
def to_LaTeX(s, length=None, shape=None, grid=None):
    """Renvoie un string contenant le code LaTeX
    (pour le module Knots.sty :
     http://www.opimedia.be/DS/DSPython/)
    de la représentation de l'espace s
    length : taille du quadrillage
             (si None alors utilise la valeur de Knots.sty : par défaut 20)
    shape : détermine la forme des arrondis
            (si None alors utilise la valeur de Knots.sty : par défaut 5)
    grid : Si True alors affiche le quadrillage, sinon pas
           (si None
           alors utilise la valeur de Knots.sty : par défaut False)

    Pre: s: space
         length: None ou naturel > 0
         shape: None ou naturel > 0
         grid: None ou boolean

    Result: string

    O(s, ...) = ..."""
    assert space_is(s), s
    assert length == None or DSPython.natural_is(length), length
    assert length == None or length > 0, length
    assert shape == None or DSPython.natural_is(shape), shape
    assert shape == None or shape > 0, shape

    r = ['\\Knots{{{0}}}{{{1}}}{{%\n'
         .format(functools.reduce(lambda m, line: max(m, len(line)), s, 0),
                 len(s))]

    if length != None:
        r.append('  \\setcounter{{Knotslen}}{0}%\n'.format(length))
    if shape != None:
        r.append('  \\setcounter{{Knotsshape}}{{\\theKnotslen/{0}}}%\n'.format(shape))
    if grid != None:
        r.append('  \\Kgridtrue\n' if grid
                 else '  \\Kgridfalse\n')

    CONV = {}  # dictionnaire pour convertir les éléments de la grille en leur équivalant LaTeX
    CONV[EMPTY] = r'\e'
    CONV[LEFT]   = r'\)'
    CONV[RIGHT]  = r'\('
    CONV[TOP]    = r'\^'
    CONV[BOTTOM] = r'\_'
    CONV[UP]   = r'\/'
    CONV[DOWN] = r'\\'
    CONV[VERT] = r'\''
    CONV[HORI] = r'\='
    CONV[CROSSUP]   = r'\%'
    CONV[CROSSDOWN] = r'\&'
    CONV[CROSSUPA] = r'\A'
    CONV[CROSSUPB] = r'\B'
    CONV[CROSSDOWNA] = r'\a'
    CONV[CROSSDOWNB] = r'\b'
    CONV[CROSS] = r'\x'

    for line in s:
        r.append('  ')
        for c in line:
            r.append(CONV[c])
        r += '\\n\n'
    r.append('}')
    return ''.join(r)


## Renvoie un string contenant le code PostScript de la représentation de l'espace s
def to_PS(s, length=30, margin=10, shape=5, grid=False):
    """Renvoie un string contenant le code PostScript
      de la représentation de l'espace s
    length : taille du quadrillage
    margin : taille des marges
    shape : détermine la forme des arrondis
    grid : Si True alors affiche le quadrillage, sinon pas

    Pre: s: space
         length: naturel > 0
         margin: naturel
         shape: réel != 0
         grid: boolean

    Result: string

    O(s, ...) = ..."""
    assert space_is(s), s
    assert DSPython.natural_is(length), length
    assert length > 0, length
    assert DSPython.natural_is(margin), margin
    assert isinstance(shape, numbers.Real), shape
    assert shape != 0, shape

    grid = ('true' if grid
            else 'false')

    r = ["""%!PS-Adobe-3.0 EPSF-3.0
%%BoundingBox: 0 0 {0} {1}
""".format(functools.reduce(lambda m, line: max(m, len(line)), s, 0)*length + margin*2,
           len(s)*length + margin*2),
         """%%Creator: DSPython --- http://www.opimedia.be/DS/DSPython/
%%EndComments

% Procedures
%%%%%%%%%%%%%
/bottom {
    grid { lightbox } if
    currentpoint
    /y exch def
    /x exch def
    x y
    x y shape add
    x len add y shape add
    x len add y curveto
    stroke
} def

/cross {
    grid { lightbox } if
    len len rlineto
    0 len neg rmoveto
    len neg len rlineto
    stroke
} def

/crossdown {
    grid { lightbox } if
    len 1.9 mul 5 div dup rlineto
    len 1.2 mul 5 div dup rmoveto
    len 1.9 mul 5 div dup rlineto
    0 len neg rmoveto
    len neg len rlineto
    stroke
} def

/crossdownA {
    grid { lightbox } if
    currentpoint
    gsave
        .7 setgray
        .3 setlinewidth
        len 2 div shape .8 mul rmoveto
        0 len shape 1.6 mul sub rlineto
        stroke
    grestore
    hori
    moveto
    len size sub 2 div dup len sub rmoveto
    (A) show
} def

/crossdownB {
    grid { lightbox } if
    currentpoint
    gsave
        .7 setgray
        .3 setlinewidth
        shape .8 mul len 2 div rmoveto
        len shape 1.6 mul sub 0 rlineto
        stroke
    grestore
    vert
    moveto
    len size sub 2 div dup exch len sub exch rmoveto
    (B) show
} def

/crossup {
    grid { lightbox } if
    len len rlineto
    0 len neg rmoveto
    len 1.9 mul 5 div neg dup neg rlineto
    len 1.2 mul 5 div neg dup neg rmoveto
    len 1.9 mul 5 div neg dup neg rlineto
    stroke
} def

/crossupA {
    grid { lightbox } if
    currentpoint
    gsave
        .7 setgray
        .3 setlinewidth
        shape .8 mul len 2 div rmoveto
        len shape 1.6 mul sub 0 rlineto
        stroke
    grestore
    vert
    moveto
    len size sub 2 div dup exch len sub exch rmoveto
    (A) show
} def

/crossupB {
    grid { lightbox } if
    currentpoint
    gsave
        .7 setgray
        .3 setlinewidth
        len 2 div shape .8 mul rmoveto
        0 len shape 1.6 mul sub rlineto
        stroke
    grestore
    hori
    moveto
    len size sub 2 div dup len sub rmoveto
    (B) show
} def

/down {
    grid { lightbox } if
    0 len rmoveto
    len len neg rlineto
    stroke
} def

/frame {
    /h exch def
    /w exch def
    w 0 rlineto
    0 h rlineto
    w neg 0 rlineto
    0 h neg rlineto
} def

/hori {
    grid { lightbox } if
    currentpoint
    bottom
    moveto
    top
} def

/left {
    grid { lightbox } if
    currentpoint
    /y exch def
    /x exch def
    x y
    x shape add y
    x shape add y len add
    x y len add curveto
    stroke
} def

/lightbox {
    gsave
        .7 setgray
        .3 setlinewidth
        len len frame
        stroke
    grestore
} def

/right {
    grid { lightbox } if
    len 0 rmoveto
    currentpoint
    /y exch def
    /x exch def
    x y
    x shape sub y
    x shape sub y len add
    x y len add curveto
    stroke
} def

/top {
    grid { lightbox } if
    0 len rmoveto
    currentpoint
    /y exch def
    /x exch def
    x y
    x y shape sub
    x len add y shape sub
    x len add y curveto
    stroke
} def

/up {
    grid { lightbox } if
    len len rlineto
    stroke
} def

/vert {
    grid { lightbox } if
    currentpoint
    left
    moveto
    right
} def

% Variables globales
%%%%%%%%%%%%%%%%%%%%%
""",
         """/grid {0} def  % si true alors affiche les cadres en gris, sinon ne les affiche pas
/len {1} def  % taille des cadres
/shape len {2} div def  % taille pour l'arrondi
""".format(grid, length, shape),
         """/size len 2 div 1.5 div def  % taille de la police de caracteres

% Main
%%%%%%%
/Times-Roman findfont
size 1.5 mul scalefont
setfont
1 setlinecap

"""]

    CONV = {}  # dictionnaire pour convertir les éléments de la grille en leur équivalant PostScript
    CONV[EMPTY] = 'grid { lightbox } if'
    CONV[LEFT]  = 'left'
    CONV[RIGHT] = 'right'
    CONV[TOP]    = 'top'
    CONV[BOTTOM] = 'bottom'
    CONV[UP]   = 'up'
    CONV[DOWN] = 'down'
    CONV[VERT] = 'vert'
    CONV[HORI] = 'hori'
    CONV[CROSSUP]   = 'crossup'
    CONV[CROSSDOWN] = 'crossdown'
    CONV[CROSSUPA] = 'crossupA'
    CONV[CROSSUPB] = 'crossupB'
    CONV[CROSSDOWNA] = 'crossdownA'
    CONV[CROSSDOWNB] = 'crossdownB'
    CONV[CROSS] = 'cross'

    y = len(s)*length + margin
    for line in s:
        y -= length
        x = margin
        for c in line:
            r.append('{0} {1} moveto '.format(x, y) + CONV[c] + '\n')
            x += length
        r += '\n'
    r.append("""showpage
%%EOF""")
    return ''.join(r)


##\brief Renvoie l'état non labellisé de l'espace s de \htmlonly n&oelig;uds\endhtmlonly
# ou d'états (labellisés ou non)
def to_states(s, labels=''):
    """Renvoie l'état non labellisé de l'espace s
    de noeuds ou d'états (labellisés ou non).
    Le parcours de s se fait de la gauche vers la droite,
    du haut vers le bas.
    Chaque croisement est alors remplacé par son état non labellisé
    en fonction du 'A' ou 'B' dans labels.
    Lorsque les caractères de labels sont épuisés,
    c'est l'état A qui est choisi.

    Pre: s: noeuds, labelstates ou states
            (ou space mélange des trois,
            mais ne contenant pas de croisement non "orienté")
         labels: string de 'A' et 'B'

    Result: states

    O(s) = ..."""
    assert space_is(s), s

    new_s = []
    for line in s:
        new_line = ''
        for c in line:
            assert c != CROSS

            if c in CROSSUP + CROSSUPA + CROSSUPB :
                new_line += (VERT if (labels == '') or (labels[0] == 'A')
                             else HORI)
                labels = labels[1:]
            elif c in CROSSDOWN + CROSSDOWNA + CROSSDOWNB:
                new_line += (HORI if (labels == '') or (labels[0] == 'A')
                             else VERT)
                labels = labels[1:]
            else:
                new_line += c
        new_s.append(new_line)
    return new_s


## Renvoie l'espace s dans un string avec retour à la ligne
def to_str(s):
    """Renvoie l'espace s dans un string avec retour à la ligne

    Pre: s: space

    Result: string

    O(s) = ..."""
    assert space_is(s), s

    return '\n'.join(s)


## Renvoie l'univers des \htmlonly n&oelig;uds\endhtmlonly de l'espace s
def to_universes(s):
    """Renvoie l'univers des noeuds de l'espace s

    Pre: s: space

    Result: universes

    O(s) = ..."""
    assert space_is(s), s

    new_s = []
    for line in s:
        new_line = ''
        for c in line:
            new_line += (CROSS if c in CROSSUP + CROSSDOWN + CROSSUPA + CROSSUPB
                         + CROSSDOWNA + CROSSDOWNB
                         else c)
        new_s.append(new_line)
    return new_s


## s est de type universes ?
def universes_is(s):
    """Renvoie True si l'espace s est de type universes
    (un espace vide ou contenant des univers de noeud),
    False sinon

    Pre: s: space

    Result: boolean

    O(s) = ..."""
    assert space_is(s), s

    if not isinstance(s, list):
        return False
    for line in s:
        if not isinstance(line, str):
            return False
        for c in line:
            if c not in UNIVERSECHARS:
                return False
    return True


## Écrit l'espace s dans le fichier f
def write(f, s):
    """Écrit l'espace s dans le fichier f

    Pre: f: fichier (texte) ouvert en écriture
         s: space

    Result: None

    O(f, s) = ..."""
#    assert isinstance(f, file), type(f)
    assert space_is(s), s

    f.writelines([l + '\n' for l in s])


## Renvoie le degré de torsion du space s
def writhe(s):
    """Renvoie le degré de torsion du space s,
    c.-à-d. la somme des degrés de torsion pour tous ses croisements

    Pre: s: knots dont tous les croisements sont dans 1 ou 2 cycles fermés

    Result: Integral

    O(s) = ..."""
    assert knots_is(s), s

    a = Corners(s)
    w = 0
    for y in range(len(s)):
        line = s[y]
        for x in range(len(line)):
            c = line[x]
            if (c == CROSSUP) or (c == CROSSDOWN):
                w += a.writhe_cross(x, y, c == CROSSUP)
    return w


## Renvoie le degré de torsion du croisement "orienté" placé en (x, y) du space s
def writhe_cross(s, x, y):
    """Renvoie le degré de torsion du croisement "orienté"
      placé en (x, y) du space s.
    Si les deux brins du croisement
      font partie de 2 cycles différents alors renvoie 0,
    sinon renvoie -1 ou 1.

    Pre: s: space tel que s[y][x] == CROSSUP ou CROSSDOWN
              dans 1 ou 2 cycles fermés
         x: natural
         y: natural

    Result: -1, 0 ou 1

    O(s) = ..."""
    assert space_is(s), s
    assert DSPython.natural_is(x), x
    assert DSPython.natural_is(y), y
    assert s[y][x] == CROSSUP or s[y][x] == CROSSDOWN, (x, y, s[y][x])

    return Corners(s).writhe_cross(x, y, s[y][x] == CROSSUP)



# ########
# Classe #
##########
##\brief Tableau (list de list) "des coins" d'un space.
# Pour chaque coin, un list de couples (x, y) avec x et y == -1, 0 ou 1.
class Corners(list):
    """Tableau (list de list) "des coins" d'un space.
    Pour chaque coin, un list de couples (x, y) avec x et y == -1, 0 ou 1"""

    ## Initialise le Corners à partir du space value
    def __init__(self, value):
        """Initialise le Corners à partir du space value

        Pre: value: space

        Result: None

        O() = ..."""
        assert space_is(value), value

        nb = functools.reduce(lambda m, line: max(m, len(line)),
                              value, 0) + 1  # plus grande longueur + 1
        list.__init__(self, [None] * (len(value) + 1))  # tableau de (len(value) + 1) lignes

        # Première ligne du Corners initialisée avec nb éléments list
        self[0] = [None] * nb
        for x in range(nb):
            self[0][x] = []

        # Parcourt chaque ligne du space et construit le Corners
        for y in range(len(value)):
            # Ligne suivante du Corners initialisée avec nb éléments list
            self[y + 1] = [None] * nb
            for x in range(nb):
                self[y + 1][x] = []

            # Pour chaque élément de la ligne du space
            line = value[y]
            for x in range(len(line)):
                c = CORNERS[line[x]]
                if c[0][0] != None:
                    self[y][x].append(c[0][0])
                if c[0][1] != None:
                    self[y][x + 1].append(c[0][1])
                if c[1][0] != None:
                    self[y + 1][x].append(c[1][0])
                if c[1][1] != None:
                    self[y + 1][x + 1].append(c[1][1])


    ##\brief Si le coin (x, y) est vide ou passe par un cycle fermé alors renvoie (x, y),
    # sinon renvoie les coordonnées d'une extrémité du cycle ouvert passant par (x, y)
    def extremity(self, x, y):
        """Si le coin (x, y) est vide ou passe par un cycle fermé
          alors renvoie (x, y),
        sinon renvoie les coordonnées d'une extrémité
          du cycle ouvert passant par (x, y)

        Pre: x: naturel
             y: naturel

        Result: (naturel, naturel)

        O(s) = ..."""
        assert DSPython.natural_is(x), x
        assert DSPython.natural_is(y), y

        # Fait le tour du cycle s'il est fermé, sinon s'arrête sur une extrémité
        add_x, add_y = self[y][x][0]
        moving_x = x + add_x
        moving_y = y + add_y
        while (moving_x != x or moving_y != y) and len(self[moving_y][moving_x]) != 1:
            assert len(self[moving_y][moving_x]) == 2, \
                   (x, y, moving_x, moving_y, self[moving_y][moving_x])

            add_x, add_y = (self[moving_y][moving_x][
                # self[moving_y][moving_x][0] est le "brin réciproque"
                1 if ((self[moving_y][moving_x][0][0] == -add_x)
                      and (self[moving_y][moving_x][0][1] == -add_y))
                # self[moving_y][moving_x][0] n'est pas le "brin réciproque"
                else 0])
            moving_x += add_x
            moving_y += add_y
        x = moving_x
        y = moving_y
        return (x, y)


    ## Renvoie (nombre de cycles, nombre de cycles ouverts) du Corners
    def nb_cycle(self):
        """Renvoie (nombre de cycles, nombre de cycles ouverts) du Corners

        Result: (naturel, naturel)

        O(s) = ..."""
        a = copy.deepcopy(self)
        # Parcourt le Corners en comptabilisant les cycles et les cycles ouverts
        nb = 0       # nombre de cycles
        nb_open = 0  # nombre de cycles ouverts
        for y in range(len(a)):
            for x in range(len(a[y])):
                if a[y][x] == []:
                    continue
                (x, y) = a.extremity(x, y)

                assert a[y][x] != [], (x, y)

                # Suit le cycle jusqu'à avoir fait le tour ou qu'il se termine,
                #   en enlevant les brins parcourus
                add_x, add_y = a[y][x][0]
                a[y][x] = a[y][x][1:]
                moving_x = x + add_x
                moving_y = y + add_y
                i = a[moving_y][moving_x].index((-add_x, -add_y))  # cherche le "brin réciproque"
                a[moving_y][moving_x] = a[moving_y][moving_x][:i] + a[moving_y][moving_x][i + 1:]
                while (moving_x != x or moving_y != y) and a[moving_y][moving_x] != []:
                    add_x, add_y = a[moving_y][moving_x][0]
                    a[moving_y][moving_x] = a[moving_y][moving_x][1:]
                    moving_x += add_x
                    moving_y += add_y
                    i = a[moving_y][moving_x].index((-add_x, -add_y)) # cherche le "brin réciproque"
                    a[moving_y][moving_x] = (a[moving_y][moving_x][:i]
                                             + a[moving_y][moving_x][i + 1:])
                if (moving_x == x) and (moving_y == y):  # on a fait un tour complet
                    nb += 1
                else:                                    # on est arrivé sur une extrémité
                    nb_open += 1

                assert a[y][x] == [], (x, y, a[y][x])

        return (nb, nb_open)


    ## Renvoie le degré de torsion du croisement "orienté" placé entre (x, y) et (x + 1, y + 1)
    def writhe_cross(self, x, y, crossup):
        """Renvoie le degré de torsion du croisement "orienté"
          placé entre (x, y) et (x + 1, y + 1).
        Si les deux brins du croisement font partie
          de 2 cycles différents alors renvoie 0,
        sinon renvoie -1 ou 1.

        Pre: l'élément entre (x, y) et (x + 1, y + 1)
               est un CROSSUP si crossup == True
               ou un CROSSDOWN si crossup == False,
               faisant partie de 1 ou de 2 cycles fermés
             x: natural
             y: natural
             crossup: boolean

        Result: -1, 0 ou 1

        O(s) = ..."""

        assert DSPython.natural_is(x), x
        assert DSPython.natural_is(y), y
        assert self.extremity(x, y) == (x, y), (self.extremity(x, y), (x, y))

        # Fait un presque tour du cycle jusqu'à retomber sur le croisement
        add_x, add_y = self[y][x][# le mouvement self[y][x][0] traverse le croisement
                                  1 if self[y][x][0] == (1, 1)
                                  # le mouvement self[y][x][0] quitte le croisement
                                  else 0]
        moving_x = x + add_x
        moving_y = y + add_y
        while not (0 <= moving_x - x <= 1 and 0 <= moving_y - y <= 1):
            assert len(self[moving_y][moving_x]) == 2, \
                   (x, y, moving_x, moving_y, self[moving_y][moving_x])

            add_x, add_y = self[moving_y][moving_x][
                # self[moving_y][moving_x][0] est le "brin réciproque"
                1 if ((self[moving_y][moving_x][0][0] == -add_x)
                      and (self[moving_y][moving_x][0][1] == -add_y))
                # self[moving_y][moving_x][0] n'est pas le "brin réciproque"
                else 0]
            moving_x += add_x
            moving_y += add_y
        add_x = moving_x - x
        add_y = moving_y - y

        assert add_x == 0 or add_x == 1, add_x
        assert add_y == 0 or add_y == 1, add_y
        assert add_x == 1 or add_y == 1, (add_x, add_y)

        if (add_x == 0) or (add_y == 0):  # le croisement fait partie d'un seul cycle
            if crossup:
                return (1 if add_x == 0
                        else -1)
            else:
                return (-1 if add_x == 0
                        else 1)
        else:                             # le croisement fait partie de deux cycles
            return 0



# ######\cond MAINTEST
# Main #
########
if __name__ == '__main__':
    def main_test():
        """Test du module"""
        import os, sys, tempfile

        try:
            if not 'profile' in dir():
                import psyco
                psyco.full()
        except ImportError:
            pass

        import DSPython.debug as debug

        debug.test_begin(VERSION, __debug__)

        print("SPACECHARS == '{0}'".format(SPACECHARS)); sys.stdout.flush()
        for c in SPACECHARS:
            assert 32 <= ord(c) <= 127, c

        print("KNOTCHARS == '{0}'".format(KNOTCHARS)); sys.stdout.flush()
        print("LABELSTATECHARS == '{0}'".format(LABELSTATECHARS)); sys.stdout.flush()
        print("STATECHARS == '{0}'".format(STATECHARS)); sys.stdout.flush()
        print("UNIVERSECHARS == '{0}'".format(UNIVERSECHARS)); sys.stdout.flush()


        print('CORNERS...', end=''); sys.stdout.flush()
        assert len(CORNERS) == len(SPACECHARS), (len(CORNERS), len(SPACECHARS))
        for i in SPACECHARS:
            assert isinstance(CORNERS[i], tuple)
            assert len(CORNERS[i]) == 2, (i, CORNERS[i])
            nb = 0
            for y in range(2):
                assert len(CORNERS[i][y]) == 2, (i, y, CORNERS[i][y])
                for x in range(2):
                    c = CORNERS[i][y][x]
                    assert c == None or len(c) == 2, (i, y, x, c)
                    if c != None:
                        assert c != (0, 0), (i, y, x, c)
                        t = CORNERS[i][y + c[1]][x + c[0]]
                        assert t[0] == -c[0], (i, y, x, c, t)
                        assert t[1] == -c[1], (i, y, x, c, t)
                        nb += 1
            if i == EMPTY:
                assert nb == 0, (i, nb, CORNERS[i])
            elif i in (LEFT, RIGHT, TOP, BOTTOM, UP, DOWN):
                assert nb == 2, (i, nb, CORNERS[i])
            else:
                assert nb == 4, (i, nb, CORNERS[i])
        print('ok'); sys.stdout.flush()


        print('PRIMEKNOTS...', end=''); sys.stdout.flush()
        assert isinstance(PRIMEKNOTS, dict)
        assert len(PRIMEKNOTS) == 6, len(PRIMEKNOTS)
        for nb in PRIMEKNOTS:
            assert len(PRIMEKNOTS[nb]) >0, (nb, len(PRIMEKNOTS[nb]))
            for i in PRIMEKNOTS[nb]:
                assert knots_is(PRIMEKNOTS[nb][i]), (nb, i, PRIMEKNOTS[nb][i])
                assert closed_is(PRIMEKNOTS[nb][i]), (nb, i, PRIMEKNOTS[nb][i])
                assert nb_cycle(PRIMEKNOTS[nb][i]) == (1, 0), \
                       (nb, i, nb_cycle(PRIMEKNOTS[nb][i]), PRIMEKNOTS[nb][i])
        print('ok'); sys.stdout.flush()


        print('BORROMEAN...', end=''); sys.stdout.flush()
        assert knots_is(BORROMEAN), BORROMEAN
        assert closed_is(BORROMEAN), BORROMEAN
        assert nb_cycle(BORROMEAN) == (3, 0), nb_cycle(BORROMEAN)
        print('ok'); sys.stdout.flush()


        print()
        print('addtoright()...', end=''); sys.stdout.flush()
        s = []
        assert addtoright(s, []) == None
        assert s == [], s
        s = [' _', '( )', '^ ^']
        assert addtoright(s, ['_', '%', '%', '^']) == None
        assert s == [' _ _', '( )%', '^ ^%', '   ^'], s
        assert not space_is(s), s
        for nb in PRIMEKNOTS:
            for i in PRIMEKNOTS[nb]:
                s = []
                assert addtoright(s, PRIMEKNOTS[nb][i]) == None, (nb, i)
                assert s == PRIMEKNOTS[nb][i], (nb, i, s)
                s = ['']
                assert addtoright(s, PRIMEKNOTS[nb][i]) == None, (nb, i)
                assert s == PRIMEKNOTS[nb][i], (nb, i, s)
                s = []
                s += PRIMEKNOTS[nb][i]
                assert addtoright(s, []) == None, (nb, i)
                assert s == PRIMEKNOTS[nb][i], (nb, i, s)
                s = []
                s += PRIMEKNOTS[nb][i]
                assert addtoright(s, ['']) == None, (nb, i)
                assert s == PRIMEKNOTS[nb][i], (nb, i, s)
        print('ok'); sys.stdout.flush()


        print('closed_is()...', end=''); sys.stdout.flush()
        assert closed_is([])
        assert closed_is([EMPTY, ''])
        assert closed_is(['()'])
        assert closed_is(['(%&)'])
        assert closed_is(['(&&)'])
        assert not closed_is([')('])
        assert closed_is([' _',
                          '( )',
                          ' ^'])
        assert not closed_is([' _',
                              '( )',
                              ' _'])
        assert closed_is([' _',
                          '( )',
                          '(_)'])
        assert not closed_is([' _',
                              '( )',
                              '(_('])
        for c in SPACECHARS:
            if c == EMPTY:
                assert closed_is([c]), c
            else:
                assert not closed_is([c]), c
        for nb in PRIMEKNOTS:
            for i in PRIMEKNOTS[nb]:
                assert closed_is(PRIMEKNOTS[nb][i]), (nb, i, PRIMEKNOTS[nb][i])
                for labels in labels_list(nb_cross(PRIMEKNOTS[nb][i])):
                    assert closed_is(to_labelstates(PRIMEKNOTS[nb][i], labels)), \
                           (nb, i, to_labelstates(PRIMEKNOTS[nb][i], labels))
                    assert closed_is(to_states(PRIMEKNOTS[nb][i], labels)), \
                           (nb, i, to_states(PRIMEKNOTS[nb][i], labels))
                assert closed_is(to_universes(PRIMEKNOTS[nb][i])), \
                       (nb, i, to_universes(PRIMEKNOTS[nb][i]))
        print('ok'); sys.stdout.flush()


        print('knots_is()...', end=''); sys.stdout.flush()
        assert knots_is([])
        assert knots_is([EMPTY, ''])
        for c in KNOTCHARS:
            assert knots_is([c])
        for i in range(256):
            c = chr(i)
            if c in KNOTCHARS:
                assert knots_is([c])
        for nb in PRIMEKNOTS:
            for i in PRIMEKNOTS[nb]:
                assert knots_is(PRIMEKNOTS[nb][i]), (nb, i, PRIMEKNOTS[nb][i])
            if nb > 0:
                for i in PRIMEKNOTS[nb]:
                    for labels in labels_list(nb_cross(PRIMEKNOTS[nb][i])):
                        assert not knots_is(to_labelstates(PRIMEKNOTS[nb][i], labels)), \
                               (nb, i, labels, PRIMEKNOTS[nb][i],
                                to_labelstates(PRIMEKNOTS[nb][i], labels))
                        assert knots_is(to_states(PRIMEKNOTS[nb][i], labels)), \
                               (nb, i, labels, PRIMEKNOTS[nb][i],
                                to_states(PRIMEKNOTS[nb][i], labels))
                    assert not knots_is(to_universes(PRIMEKNOTS[nb][i])), \
                           (nb, i, PRIMEKNOTS[nb][i], to_universes(PRIMEKNOTS[nb][i]))
        print('ok'); sys.stdout.flush()


        print('labels_list()...', end=''); sys.stdout.flush()
        assert labels_list(0) == [''], labels_list(0)
        assert labels_list(1) == ['A', 'B'], labels_list(1)
        assert labels_list(2) == ['AA', 'AB', 'BA', 'BB'], labels_list(2)
        assert labels_list(3) == ['AAA', 'AAB', 'ABA', 'ABB', 'BAA', 'BAB', 'BBA', 'BBB'], \
               labels_list(3)
        for n in range(10):
            l = labels_list(n)
            assert len(l) == 2**n, (n, len(l))
            for s in l:
                assert len(s) == n, (n, len(s))
                assert s.count('A') + s.count('B') == n, (n, s.count('A'), s.count('B'))
        print('ok'); sys.stdout.flush()


        print('labelstates_is()...', end=''); sys.stdout.flush()
        assert labelstates_is([])
        assert labelstates_is([EMPTY, ''])
        for c in LABELSTATECHARS:
            assert labelstates_is([c])
        for i in range(256):
            c = chr(i)
            if c in LABELSTATECHARS:
                assert labelstates_is([c])
        for nb in PRIMEKNOTS:
            for i in PRIMEKNOTS[nb]:
                for labels in labels_list(nb_cross(PRIMEKNOTS[nb][i])):
                    assert labelstates_is(to_labelstates(PRIMEKNOTS[nb][i], labels)), \
                           (nb, i, PRIMEKNOTS[nb][i],
                            labels, to_labelstates(PRIMEKNOTS[nb][i], labels))
            if nb > 0:
                for i in PRIMEKNOTS[nb]:
                    assert not labelstates_is(PRIMEKNOTS[nb][i]), (nb, i, PRIMEKNOTS[nb][i])
                    for labels in labels_list(nb_cross(PRIMEKNOTS[nb][i])):
                        assert labelstates_is(to_states(PRIMEKNOTS[nb][i], labels)), \
                               (nb, i, PRIMEKNOTS[nb][i],
                                labels, to_states(PRIMEKNOTS[nb][i], labels))
                    assert not labelstates_is(to_universes(PRIMEKNOTS[nb][i])), \
                           (nb, i, to_universes(PRIMEKNOTS[nb][i]))
        print('ok'); sys.stdout.flush()


        print('links_is()...', end=''); sys.stdout.flush()
        print('???', end='')
        print('ok'); sys.stdout.flush()


        print('make_egalwidth()...', end=''); sys.stdout.flush()
        s = []
        assert make_egalwidth(s) == None
        assert s == [], s
        s = ['']
        assert make_egalwidth(s) == None
        assert s == [''], s
        s = ['(%)']
        assert make_egalwidth(s) == None
        assert s == ['(%)'], s
        s = ['(%%)', '', '(%)']
        assert make_egalwidth(s) == None
        assert s == ['(%%)', '    ', '(%) '], s
        s = ['', '()', '', '(%)']
        assert make_egalwidth(s) == None
        assert s == ['   ', '() ', '   ', '(%)'], s
        s = ['', '()', '', '(%)']
        assert make_egalwidth(s, UP) == None
        assert s == ['///', '()/', '///', '(%)'], s
        print('ok'); sys.stdout.flush()


        print('mirror()...', end=''); sys.stdout.flush()
        assert mirror([]) == [], mirror([])
        assert mirror(['']) == [''], mirror([''])
        assert mirror([LEFT]) == [LEFT], mirror([LEFT])
        assert mirror(['()']) == ['()'], mirror(['()'])
        assert mirror(['/^^', ')']) == ['/^^', ')'], mirror(['/^^', ')'])
        assert mirror(['(%)']) == ['(&)'], mirror(['(%)'])
        assert mirror(['(', '%', ')']) == ['(', '&', ')'], mirror(['(', '%', ')'])
        for nb in PRIMEKNOTS:
            for i in PRIMEKNOTS[nb]:
                assert mirror(mirror(PRIMEKNOTS[nb][i])) == PRIMEKNOTS[nb][i], \
                       (nb, i, mirror(mirror(PRIMEKNOTS[nb][i])))
                for labels in labels_list(nb_cross(PRIMEKNOTS[nb][i])):
                    assert to_states(mirror(PRIMEKNOTS[nb][i]), labels) \
                           == mirror(to_states(PRIMEKNOTS[nb][i], labels)), \
                           (nb, i, to_states(PRIMEKNOTS[nb][i], labels),
                            mirror(to_states(PRIMEKNOTS[nb][i]), labels))
                    assert to_labelstates(mirror(PRIMEKNOTS[nb][i]), labels) \
                           == mirror(to_labelstates(PRIMEKNOTS[nb][i], labels)), \
                           (nb, i, to_labelstates(PRIMEKNOTS[nb][i], labels),
                            mirror(to_labelstates(PRIMEKNOTS[nb][i]), labels))
                assert to_universes(mirror(PRIMEKNOTS[nb][i])) \
                       == mirror(to_universes(PRIMEKNOTS[nb][i])), \
                       (nb, i, to_universes(mirror(PRIMEKNOTS[nb][i])),
                        mirror(to_universes(PRIMEKNOTS[nb][i])))
        print('ok'); sys.stdout.flush()


        print('nb_A()...', end=''); sys.stdout.flush()
        assert nb_A([]) == 0, nb_A([])
        assert nb_A([CROSSUPA, '']) == 1, nb_A([CROSSUPA, ''])
        assert nb_A([CROSSDOWNA, '']) == 1, nb_A([c, CROSSDOWNA])
        for c in LABELSTATECHARS.replace(CROSSUPA, EMPTY).replace(CROSSDOWNA, EMPTY):
            assert nb_A([c, '']) == 0, (c, nb_A([c, '']))
        for nb in PRIMEKNOTS:
            for i in PRIMEKNOTS[nb]:
                for labels in labels_list(nb_cross(PRIMEKNOTS[nb][i])):
                    assert nb_A(to_labelstates(PRIMEKNOTS[nb][i], labels)) == labels.count('A'), \
                           (nb, i, PRIMEKNOTS[nb][i],
                            nb_A(to_labelstates(PRIMEKNOTS[nb][i], labels)),
                            labels.count('A'), labels, to_labelstates(PRIMEKNOTS[nb][i], labels))
                    assert nb_A(to_labelstates(PRIMEKNOTS[nb][i], labels)) \
                           == nb_items(to_labelstates(PRIMEKNOTS[nb][i], labels), CROSSUPA) \
                           + nb_items(to_labelstates(PRIMEKNOTS[nb][i], labels) , CROSSDOWNA), \
                           (nb, i, PRIMEKNOTS[nb][i],
                            nb_A(to_labelstates(PRIMEKNOTS[nb][i], labels)),
                            nb_items(to_labelstates(PRIMEKNOTS[nb][i], labels), CROSSUPA),
                            nb_items(to_labelstates(PRIMEKNOTS[nb][i], labels), CROSSDOWNA),
                            labels, to_labelstates(PRIMEKNOTS[nb][i], labels))
        print('ok'); sys.stdout.flush()


        print('nb_B()...', end=''); sys.stdout.flush()
        assert nb_B([]) == 0, nb_B([])
        assert nb_B([CROSSUPB, '']) == 1, nb_B([CROSSUPB, ''])
        assert nb_B([CROSSDOWNB, '']) == 1, nb_B([CROSSDOWNB, ''])
        for c in LABELSTATECHARS.replace(CROSSUPB, EMPTY).replace(CROSSDOWNB, EMPTY):
            assert nb_B([c, '']) == 0, (c, nb_B([c, '']))
        for nb in PRIMEKNOTS:
            for i in PRIMEKNOTS[nb]:
                for labels in labels_list(nb_cross(PRIMEKNOTS[nb][i])):
                    assert nb_B(to_labelstates(PRIMEKNOTS[nb][i], labels)) == labels.count('B'), \
                           (nb, i, PRIMEKNOTS[nb][i],
                            nb_B(to_labelstates(PRIMEKNOTS[nb][i], labels)),
                            labels.count('B'), labels, to_labelstates(PRIMEKNOTS[nb][i], labels))
                    assert nb_B(to_labelstates(PRIMEKNOTS[nb][i], labels)) \
                           == nb_items(to_labelstates(PRIMEKNOTS[nb][i], labels), CROSSUPB) \
                           + nb_items(to_labelstates(PRIMEKNOTS[nb][i], labels) , CROSSDOWNB), \
                           (nb, i, PRIMEKNOTS[nb][i],
                            nb_B(to_labelstates(PRIMEKNOTS[nb][i], labels)),
                            nb_items(to_labelstates(PRIMEKNOTS[nb][i], labels), CROSSUPB),
                            nb_items(to_labelstates(PRIMEKNOTS[nb][i], labels), CROSSDOWNB),
                            labels, to_labelstates(PRIMEKNOTS[nb][i], labels))
        print('ok'); sys.stdout.flush()


        print('nb_cross()...', end=''); sys.stdout.flush()
        assert nb_cross([]) == 0, nb_cross([])
        assert nb_cross([VERT, '']) == 0, nb_cross([VERT, ''])
        assert nb_cross([HORI, '']) == 0, nb_cross([HORI, ''])
        assert nb_cross([CROSSUP, '']) == 1, nb_cross([CROSSUP, ''])
        assert nb_cross([CROSSDOWN, '']) == 1, nb_cross([CROSSDOWN, ''])
        assert nb_cross([CROSSUPA, '']) == 1, nb_cross([CROSSUPA, ''])
        assert nb_cross([CROSSUPB, '']) == 1, nb_cross([CROSSUPB, ''])
        assert nb_cross([CROSSDOWNA, '']) == 1, nb_cross([CROSSDOWNA, ''])
        assert nb_cross([CROSSDOWNB, '']) == 1, nb_cross([CROSSDOWNB, ''])
        assert nb_cross([CROSS, '']) == 1, nb_cross([CROSS, ''])
        for c in KNOTCHARS.replace(CROSSUP, EMPTY).replace(CROSSDOWN, EMPTY):
          assert nb_cross([c, '']) == 0, (c, nb_cross([c, '']))
        for nb in PRIMEKNOTS:
            for i in PRIMEKNOTS[nb]:
                assert nb_cross(PRIMEKNOTS[nb][i]) == nb, \
                       (nb, i, nb_cross(PRIMEKNOTS[nb][i]), PRIMEKNOTS[nb][i])
                assert nb_cross(PRIMEKNOTS[nb][i]) \
                       == nb_items(PRIMEKNOTS[nb][i], CROSSUP) \
                       + nb_items(PRIMEKNOTS[nb][i], CROSSDOWN), \
                       (nb, i, nb_cross(PRIMEKNOTS[nb][i]),
                        nb_items(PRIMEKNOTS[nb][i], CROSSUP),
                        nb_items(PRIMEKNOTS[nb][i], CROSSDOWN),
                        PRIMEKNOTS[nb][i])
                assert nb_cross(to_universes(PRIMEKNOTS[nb][i])) == nb, \
                       (nb, i, to_universes(nb_cross(PRIMEKNOTS[nb][i])),
                        to_universes(PRIMEKNOTS[nb][i]))
                assert nb_cross(to_universes(PRIMEKNOTS[nb][i])) \
                       == nb_items(to_universes(PRIMEKNOTS[nb][i]), CROSS), \
                       (nb, i, to_universes(nb_cross(PRIMEKNOTS[nb][i])),
                        nb_items(to_universes(PRIMEKNOTS[nb][i]), CROSS),
                        to_universes(PRIMEKNOTS[nb][i]))
                assert nb_cross(to_states(PRIMEKNOTS[nb][i])) <= nb, \
                       (nb, i, to_states(nb_cross(PRIMEKNOTS[nb][i])),
                        to_universes(PRIMEKNOTS[nb][i]))
        print('ok'); sys.stdout.flush()


        print('nb_cycle()...', end=''); sys.stdout.flush()
        assert nb_cycle([]) == (0, 0), nb_cycle([])
        assert nb_cycle([EMPTY, '']) == (0, 0), nb_cycle([EMPTY, ''])
        assert nb_cycle(['()']) == (1, 0), nb_cycle(['()'])
        assert nb_cycle([')(']) == (0, 2), nb_cycle([')('])
        assert nb_cycle([' _',
                         '( )',
                         ' ^']) == (1, 0), nb_cycle([' _', '( )', ' ^'])
        assert nb_cycle(['_',
                         ' )',
                         '_']) == (0, 2), nb_cycle(['_', ' )', '_'])
        assert nb_cycle([' _',
                         '( )',
                         ' _']) == (0, 2), nb_cycle([' _', '( )', ' _'])
        assert nb_cycle([' _  _',
                         '( )( )',
                         ' _  ^']) == (1, 2), nb_cycle([' _  _', '( )( )', ' _  ^'])
        assert nb_cycle(['   _  _ _',
                         '  ( )( )%',
                         '() _  ^ ^']) == (3, 2), \
                         nb_cycle(['   _  _ _', '  ( )( )%', '() _  ^ ^'])
        for c in KNOTCHARS.replace(VERT,
                                   EMPTY).replace(HORI,
                                                  EMPTY).replace(CROSSUP,
                                                                 EMPTY).replace(CROSSDOWN, EMPTY):
            if c == EMPTY:
                assert nb_cycle([c]) == (0, 0), (c, nb_cycle([c]))
            else:
                assert nb_cycle([c]) == (0, 1), (c, nb_cycle([c]))
        for c in VERT + HORI + CROSSUP + CROSSDOWN + CROSSUPA + CROSSUPB + CROSSDOWNA + CROSSDOWNB:
            assert nb_cycle([c]) == (0, 2), (c, nb_cycle([c]))
        for nb in PRIMEKNOTS:
            for i in PRIMEKNOTS[nb]:
                assert nb_cycle(PRIMEKNOTS[nb][i]) == (1, 0), \
                       (nb, i, nb_cycle(PRIMEKNOTS[nb][i]), PRIMEKNOTS[nb][i])
                assert nb_cycle(to_universes(PRIMEKNOTS[nb][i])) == (1, 0), \
                       (nb, i, nb_cycle(to_universes(PRIMEKNOTS[nb][i])),
                        to_universes(PRIMEKNOTS[nb][i]))
        print('ok'); sys.stdout.flush()


        print('nb_items()...', end=''); sys.stdout.flush()
        assert nb_items([], EMPTY) == 0, nb_items([], EMPTY)
        assert nb_items([EMPTY, ''], EMPTY) == 1, nb_items([EMPTY, ''], EMPTY)
        for c in SPACECHARS:
          assert nb_items([c, ''], c) == 1, (c, nb_items([c, ''], c))
        for nb in PRIMEKNOTS:
            for i in PRIMEKNOTS[nb]:
                assert nb_items(PRIMEKNOTS[nb][i], '') == 0, \
                       (nb, i, nb_items(PRIMEKNOTS[nb][i], ''), PRIMEKNOTS[nb][i])
                assert nb_items(PRIMEKNOTS[nb][i], CROSSUP + CROSSDOWN) == nb, \
                       (nb, i, nb_items(PRIMEKNOTS[nb][i], CROSSUP + CROSSDOWN), PRIMEKNOTS[nb][i])
                for labels in labels_list(nb_cross(PRIMEKNOTS[nb][i])):
                    assert nb_items(to_labelstates(PRIMEKNOTS[nb][i], labels),
                                    CROSSUPA + CROSSDOWNA) == labels.count('A'), \
                           (nb, i, PRIMEKNOTS[nb][i],
                            nb_items(to_labelstates(PRIMEKNOTS[nb][i], labels),
                                     CROSSUPA + CROSSDOWNA),
                            labels.count('A'), labels, to_labelstates(PRIMEKNOTS[nb][i], labels))
                    assert nb_items(to_labelstates(PRIMEKNOTS[nb][i], labels),
                                    CROSSUPB + CROSSDOWNB) == labels.count('B'), \
                           (nb, i, PRIMEKNOTS[nb][i],
                            nb_items(to_labelstates(PRIMEKNOTS[nb][i], labels),
                                     CROSSUPB + CROSSDOWNB),
                            labels.count('B'), labels, to_labelstates(PRIMEKNOTS[nb][i], labels))
                assert nb_items(to_universes(PRIMEKNOTS[nb][i]), CROSS) == nb, \
                       (nb, i, PRIMEKNOTS[nb][i], nb_items(to_universes(PRIMEKNOTS[nb][i]), CROSS),
                        to_universes(PRIMEKNOTS[nb][i]))
                assert nb_items(to_universes(PRIMEKNOTS[nb][i]), CROSSUP + CROSSDOWN) == 0, \
                       (nb, i, PRIMEKNOTS[nb][i],
                        nb_items(to_universes(PRIMEKNOTS[nb][i]), CROSSUP + CROSSDOWN),
                        to_universes(PRIMEKNOTS[nb][i]))
        print('ok'); sys.stdout.flush()


        print('poly_Kauffman()...', end=''); sys.stdout.flush()
        p = polynomial.Polynomial(polynomial.Term((0, )), coef=1, varsstr='A')
        assert poly_Kauffman(['()']) == p, (poly_Kauffman(['()']), p)
        assert poly_Kauffman(['()',
                              ' ']) == p, (poly_Kauffman(['()', ' ']), p)
        assert poly_Kauffman([' _',
                              '( )',
                              ' ^']) == p, (poly_Kauffman([' _', '( )', ' ^'], p))
        assert poly_Kauffman(['(%)']) == p, (poly_Kauffman(['(%)']), p)
        assert poly_Kauffman(['(&)']) == p, (poly_Kauffman(['(&)']), p)

        p = polynomial.Polynomial({polynomial.Term((4, )): 1,
                                   polynomial.Term((12, )): 1,
                                   polynomial.Term((16, )): -1}, varsstr='A')
        assert poly_Kauffman(PRIMEKNOTS[3][1]) == p, (poly_Kauffman(PRIMEKNOTS[3][1]), p)
        assert p.eval((-1)) == 1, p.eval((-1))

        p = polynomial.Polynomial({polynomial.Term((-16, )): -1,
                                   polynomial.Term((-12, )): 1,
                                   polynomial.Term((-4, )): 1}, varsstr='A')
        assert poly_Kauffman([' _ _',
                              '( & )',
                              ' % %',
                              '( ^ )',
                              ' ^^^']) == p, \
                              (poly_Kauffman([' _ _',
                                              '( & )',
                                              ' % %',
                                              '( ^ )',
                                              ' ^^^']), p)
        assert poly_Kauffman([' _ _',
                              '( & )',
                              ' % %',
                              '( ^ %)',
                              ' ^^^']) == p, \
                              (poly_Kauffman([' _ _',
                                              '( & )',
                                              ' % %',
                                              '( ^ %)',
                                              ' ^^^']), p)
        assert p.eval((-1)) == 1, p.eval((-1))

        p = polynomial.Polynomial({polynomial.Term((-8, )): 1,
                                   polynomial.Term((-4, )): -1,
                                   polynomial.Term((0, )): 1,
                                   polynomial.Term((4, )): -1,
                                   polynomial.Term((8, )): 1}, varsstr='A')
        assert poly_Kauffman(PRIMEKNOTS[4][1]) == p, (poly_Kauffman(PRIMEKNOTS[4][1]), p)
        assert p.eval((-1)) == 1, p.eval((-1))

        for nb in PRIMEKNOTS:
            for i in PRIMEKNOTS[nb]:
                assert poly_Kauffman(PRIMEKNOTS[nb][i]).eval((-1)) == 1, \
                       poly_Kauffman(PRIMEKNOTS[nb][i]).eval((-1))

        # Lien de Hopf
        p = polynomial.Polynomial({polynomial.Term((-4, )):- 1,
                                   polynomial.Term((4, )): -1}, varsstr='A')
        assert poly_Kauffman(['/%\\',
                              '\\%/']) == p, (poly_Kauffman(['/%\\', '\\%/']), p)
        assert poly_Kauffman(['/%^%)',
                              '\\%/']) == p, (poly_Kauffman(['/%^%)', '\\%/']), p)
        assert poly_Kauffman(['/&\\',
                              '\\&/']) == p, (poly_Kauffman(['/&\\', '\\&/']), p)
        assert poly_Kauffman(['/&^%)',
                              '\\&/']) == p, (poly_Kauffman(['/&^%)', '\\&/']), p)
        assert p.eval((-1)) == -2, p.eval((-1))

        # Deux noeuds triviaux superposés
        p = polynomial.Polynomial({polynomial.Term((-2, )): -1,
                                   polynomial.Term((2, )): -1}, varsstr='A')
        assert poly_Kauffman(['/%\\',
                              '\\&/']) == p, (poly_Kauffman(['/%\\', '\\&/']), p)
        assert poly_Kauffman(['/%^%)',
                              '\\&/']) == p, (poly_Kauffman(['/%^%)', '\\&/']), p)
        assert p.eval((-1)) == -2, p.eval((-1))

        # k noeuds triviaux séparés
        p = polynomial.Polynomial({polynomial.Term((-2, )): -1,
                                   polynomial.Term((2, )): -1}, varsstr='A')
        assert poly_Kauffman(['()'*2]) == p, (poly_Kauffman(['()'*2]), p)
        assert poly_Kauffman(['()',
                              ' ']*2) == p, (poly_Kauffman(['()', ' ']*2), p)
        assert poly_Kauffman(['(%)'*2]) == p, (poly_Kauffman(['(%)'*2]), p)
        assert poly_Kauffman(['(%%)'*2]) == p, (poly_Kauffman(['(%%)'*2]), p)
        assert poly_Kauffman(['(%&)'*2]) == p, (poly_Kauffman(['(%&)'*2]), p)

        p = polynomial.Polynomial({polynomial.Term((-4, )): 1,
                                   polynomial.Term((0, )): 2,
                                   polynomial.Term((4, )): 1,}, varsstr='A')
        assert poly_Kauffman(['()'*3]) == p, (poly_Kauffman(['()'*3]), p)
        assert poly_Kauffman(['()',
                              ' ']*3) == p, (poly_Kauffman(['()', ' ']*3), p)
        assert poly_Kauffman(['(%)'*3]) == p, (poly_Kauffman(['(%)'*3]), p)
        assert poly_Kauffman(['(%%)'*3]) == p, (poly_Kauffman(['(%%)'*3]), p)
        assert poly_Kauffman(['(%&)'*3]) == p, (poly_Kauffman(['(%&)'*3]), p)

        for k in range(1, 10 if debug.assertspeed >= debug.ASSERT_NORMAL else 5):
            assert poly_Kauffman(['()'*k]).eval(-1) == (-2)**(k - 1), \
                   (k, poly_Kauffman(['()'*k]).eval(-1), (-2)**(k - 1))
            assert poly_Kauffman(['()',
                                  ' ']*k).eval(-1) == (-2)**(k - 1), \
                                  (k, poly_Kauffman(['()', ' ']*k).eval(-1), (-2)**(k - 1))
            assert poly_Kauffman(['(%)'*k]).eval(-1) == (-2)**(k - 1), \
                   (k, poly_Kauffman(['(%)'*k]).eval(-1), (-2)**(k - 1))
        if debug.assertspeed < debug.ASSERT_NORMAL:
            print(debug.assertspeed_str(), end='')
        print('ok'); sys.stdout.flush()


        print('poly_Kauffman_A()...', end=''); sys.stdout.flush()
        p = polynomial.Polynomial(polynomial.Term((0, )), varsstr='A')
        assert poly_Kauffman_A(['()']) == p, (poly_Kauffman_A(['()']), p)
        assert poly_Kauffman_A(['()',
                                ' ']) == p, (poly_Kauffman_A(['()', ' ']), p)
        assert poly_Kauffman_A([' _',
                                '( )',
                                ' ^']) == p, (poly_Kauffman_A([' _', '( )', ' ^'], p))
        assert p.eval((-1)) == 1, p.eval((-1))

        p = polynomial.Polynomial({polynomial.Term((-5, )): -1,
                                   polynomial.Term((3, )): -1,
                                   polynomial.Term((7, )): 1}, varsstr='A')
        assert poly_Kauffman_A(PRIMEKNOTS[3][1]) == p, (poly_Kauffman_A(PRIMEKNOTS[3][1]), p)
        assert p.eval((-1)) == 1, p.eval((-1))

        p = polynomial.Polynomial({polynomial.Term((-7, )): 1,
                                   polynomial.Term((-3, )): -1,
                                   polynomial.Term((5, )): -1}, varsstr='A')
        assert poly_Kauffman_A([' _ _',
                                '( & )',
                                ' % %',
                                '( ^ )',
                                ' ^^^']) == p, \
                                (poly_Kauffman_A([' _ _',
                                                  '( & )',
                                                  ' % %',
                                                  '( ^ )',
                                                  ' ^^^']), p)
        assert p.eval((-1)) == 1, p.eval((-1))

        p = polynomial.Polynomial({polynomial.Term((-8, )): 1,
                                   polynomial.Term((-4, )): -1,
                                   polynomial.Term((0, )): 1,
                                   polynomial.Term((4, )): -1,
                                   polynomial.Term((8, )): 1}, varsstr='A')
        assert poly_Kauffman_A(PRIMEKNOTS[4][1]) == p, (poly_Kauffman_A(PRIMEKNOTS[4][1]), p)
        assert p.eval((-1)) == 1, p.eval((-1))

        for nb in PRIMEKNOTS:
            for i in PRIMEKNOTS[nb]:
                assert poly_Kauffman_A(PRIMEKNOTS[nb][i]).eval((-1)) == 1, \
                       poly_Kauffman_A(PRIMEKNOTS[nb][i]).eval((-1))

        # Lien de Hopf
        p = polynomial.Polynomial({polynomial.Term((-4, )):- 1,
                                   polynomial.Term((4, )): -1}, varsstr='A')
        assert poly_Kauffman_A(['/%\\',
                                  '\\%/']) == p, (poly_Kauffman_A(['/%\\', '\\%/']), p)
        assert poly_Kauffman_A(['/&\\',
                                  '\\&/']) == p, (poly_Kauffman_A(['/&\\', '\\&/']), p)
        assert p.eval((-1)) == -2, p.eval((-1))

        # Deux noeuds triviaux superposés
        p = polynomial.Polynomial({polynomial.Term((-2, )): -1,
                                   polynomial.Term((2, )): -1}, varsstr='A')
        assert poly_Kauffman_A(['/%\\',
                                  '\\&/']) == p, (poly_Kauffman_A(['/%\\', '\\&/']), p)
        assert p.eval((-1)) == -2, p.eval((-1))

        # k noeuds triviaux séparés
        p = polynomial.Polynomial({polynomial.Term((-2, )): -1,
                                   polynomial.Term((2, )): -1}, varsstr='A')
        assert poly_Kauffman_A(['()'*2]) == p, (poly_Kauffman_A(['()'*2]), p)
        assert poly_Kauffman_A(['()',
                                ' ']*2) == p, (poly_Kauffman_A(['()', ' ']*2), p)

        p = polynomial.Polynomial({polynomial.Term((-4, )): 1,
                                   polynomial.Term((0, )): 2,
                                   polynomial.Term((4, )): 1,}, varsstr='A')
        assert poly_Kauffman_A(['()'*3]) == p, (poly_Kauffman_A(['()'*3]), p)
        assert poly_Kauffman_A(['()',
                                ' ']*3) == p, (poly_Kauffman_A(['()', ' ']*3), p)

        for k in range(1, 10):
            assert poly_Kauffman_A(['()'*k]).eval(-1) == (-2)**(k - 1), \
                   (k, poly_Kauffman_A(['()'*k]).eval(-1), (-2)**(k - 1))
            assert poly_Kauffman_A(['()',
                                    ' ']*k).eval(-1) == (-2)**(k - 1), \
                                    (k, poly_Kauffman_A(['()', ' ']*k).eval(-1), (-2)**(k - 1))
        print('ok'); sys.stdout.flush()


        print('poly_Kauffman_ABd()...', end=''); sys.stdout.flush()
        p = polynomial.Polynomial(polynomial.Term((0, 0, -1)), varsstr='ABd')
        assert poly_Kauffman_ABd([]) == p, (poly_Kauffman_ABd([]), p)
        assert p.eval((-1, -1, -2)) == -.5, p.eval((-1, -1, -2))

        p = polynomial.Polynomial(polynomial.Term((0, 0, 0)), varsstr='ABd')
        assert poly_Kauffman_ABd(['()']) == p, (poly_Kauffman_ABd(['()']), p)
        assert poly_Kauffman_ABd([' _',
                                  '( )',
                                  ' ^']) == p, (poly_Kauffman_ABd([' _', '( )', ' ^'], p))
        assert p.eval((-1, -1, -2)) == 1, p.eval((-1, -1, -2))

        p = polynomial.Polynomial({polynomial.Term((0, 3, 1)): 1,
                                   polynomial.Term((1, 2, 0)): 3,
                                   polynomial.Term((2, 1, 1)): 3,
                                   polynomial.Term((3, 0, 2)): 1}, varsstr='ABd')
        assert poly_Kauffman_ABd(PRIMEKNOTS[3][1]) == p, (poly_Kauffman_ABd(PRIMEKNOTS[3][1]), p)
        assert p.eval((-1, -1, -2)) == 1, p.eval((-1, -1, -2))

        p = polynomial.Polynomial({polynomial.Term((3, 0, 1)): 1,
                                   polynomial.Term((2, 1, 0)): 3,
                                   polynomial.Term((1, 2, 1)): 3,
                                   polynomial.Term((0, 3, 2)): 1}, varsstr='ABd')
        assert poly_Kauffman_ABd([' _ _',
                                  '( & )',
                                  ' % %',
                                  '( ^ )',
                                  ' ^^^']) == p, \
                                  (poly_Kauffman_ABd([' _ _',
                                                      '( & )',
                                                      ' % %',
                                                      '( ^ )',
                                                      ' ^^^']), p)
        assert p.eval((-1, -1, -2)) == 1, p.eval((-1, -1, -2))

        p = polynomial.Polynomial({polynomial.Term((0, 4, 2)): 1,
                                   polynomial.Term((1, 3, 1)): 4,
                                   polynomial.Term((2, 2, 0)): 5,
                                   polynomial.Term((2, 2, 2)): 1,
                                   polynomial.Term((3, 1, 1)): 4,
                                   polynomial.Term((4, 0, 2)): 1}, varsstr='ABd')
        assert poly_Kauffman_ABd(PRIMEKNOTS[4][1]) == p, (poly_Kauffman_ABd(PRIMEKNOTS[4][1]), p)
        assert p.eval((-1, -1, -2)) == 1, p.eval((-1, -1, -2))

        for nb in PRIMEKNOTS:
            for i in PRIMEKNOTS[nb]:
                assert poly_Kauffman_ABd(PRIMEKNOTS[nb][i]).eval((-1, -1, -2)) == 1, \
                       poly_Kauffman_ABd(PRIMEKNOTS[nb][i]).eval((-1, -1, -2))

        # Lien de Hopf
        p = polynomial.Polynomial({polynomial.Term((0, 2, 1)): 1,
                                   polynomial.Term((1, 1, 0)): 2,
                                   polynomial.Term((2, 0, 1)): 1}, varsstr='ABd')
        assert poly_Kauffman_ABd(['/%\\',
                                  '\\%/']) == p, (poly_Kauffman_ABd(['/%\\', '\\%/']), p)
        assert poly_Kauffman_ABd(['/&\\',
                                  '\\&/']) == p, (poly_Kauffman_ABd(['/&\\', '\\&/']), p)
        assert p.eval((-1, -1, -2)) == -2, p.eval((-1, -1, -2))

        # Deux noeuds triviaux superposés
        p = polynomial.Polynomial({polynomial.Term((0, 2, 0)): 1,
                                   polynomial.Term((1, 1, 1)): 2,
                                   polynomial.Term((2, 0, 0)): 1}, varsstr='ABd')
        assert poly_Kauffman_ABd(['/%\\',
                                  '\\&/']) == p, (poly_Kauffman_ABd(['/%\\', '\\&/']), p)
        assert p.eval((-1, -1, -2)) == -2, p.eval((-1, -1, -2))

        # k noeuds triviaux séparés
        for k in range(1, 10):
            p = polynomial.Polynomial({polynomial.Term((0, 0, k - 1)): 1}, varsstr='ABd')
            assert poly_Kauffman_ABd(['()'*k]) == p, (k, poly_Kauffman_ABd(['()'*k]), p)
            assert poly_Kauffman_ABd(['()',
                                      ' ']*k) == p, (k, poly_Kauffman_ABd(['()', ' ']*k), p)
            assert p.eval((-1, -1, -2)) == (-2)**(k - 1), (k, p.eval((-1, -1, -2), (-2)**(k - 1)))
        print('ok'); sys.stdout.flush()


        print('primeknots_even_1()...', end=''); sys.stdout.flush()
        assert primeknots_even_1(4) == PRIMEKNOTS[4][1], (primeknots_even_1(4), PRIMEKNOTS[4][1])
        assert primeknots_even_1(6) == PRIMEKNOTS[6][1], (primeknots_even_1(6), PRIMEKNOTS[6][1])
        for n in range(4, 50, 2):
            assert knots_is(primeknots_even_1(n)), (n, primeknots_even_1(n))
            assert closed_is(primeknots_even_1(n)), (n, primeknots_even_1(n))
            assert nb_cycle(primeknots_even_1(n)) == (1, 0), (n, nb_cycle(primeknots_even_1(n)))
            assert nb_cross(primeknots_even_1(n)) == n, nb_cross(primeknots_even_1(n))
        print('???', end='')
        print('ok'); sys.stdout.flush()


        print('read()...', end=''); sys.stdout.flush()
        for nb in PRIMEKNOTS:
            for i in PRIMEKNOTS[nb]:
                f = tempfile.NamedTemporaryFile(mode='w', suffix='.txt',
                                                prefix='DSPython_test_read_knots_{0}_{1}__'
                                                       .format(nb, i),
                                                delete=False)
                write(f, PRIMEKNOTS[nb][i])
                f.close()

                f = open(f.name)
                s = read(f)
                f.close()
                os.remove(f.name)
                assert s == PRIMEKNOTS[nb][i], (nb, i, PRIMEKNOTS[nb][i], s)
        print('ok'); sys.stdout.flush()


        print('rotate()...', end=''); sys.stdout.flush()
        assert rotate([]) == [], rotate([])
        assert rotate(['']) == [], rotate([''])
        assert rotate(['', '']) == [], rotate(['', ''])
        assert rotate([LEFT]) == [BOTTOM], rotate([LEFT])
        assert rotate(['()']) == ['_', '^'], rotate(['()'])
        assert rotate(['/^^', ')']) == [') ', ') ', '\\_'], rotate(['/^^', ')'])
        assert rotate(['/^^', '', ')']) == [')  ', ')  ', '\\ _'], rotate(['/^^', '', ')'])
        assert rotate(['/^^', ')'], 2) == ['  (', '__/'], rotate(['/^^', ')'], 2)
        assert rotate(['/^^', ')'], 3) == ['^\\', ' (', ' ('], rotate(['/^^', ')'], 3)
        assert rotate(['/^^', ')'], 4) == ['/^^', ')'], rotate(['/^^', ')'], 4)
        assert rotate(['/^^', ')'], -1) == ['^\\', ' (', ' ('], rotate(['/^^', ')'], -1)
        assert rotate(['/^^', ')'], -2) == ['  (', '__/'], rotate(['/^^', ')'], -2)
        assert rotate(['/^^', ')'], -3) == [') ', ') ', '\\_'], rotate(['/^^', ')'], -3)
        for nb in PRIMEKNOTS:
            for i in PRIMEKNOTS[nb]:
                assert rotate(PRIMEKNOTS[nb][i]) == rotate(PRIMEKNOTS[nb][i], -3), \
                       (nb, i, rotate(PRIMEKNOTS[nb][i]), rotate(PRIMEKNOTS[nb][i], -3))
                assert rotate(PRIMEKNOTS[nb][i], 2) == rotate(PRIMEKNOTS[nb][i], -2), \
                       (nb, i, rotate(PRIMEKNOTS[nb][i], 2), rotate(PRIMEKNOTS[nb][i], -2))
                assert rotate(PRIMEKNOTS[nb][i], 3) == rotate(PRIMEKNOTS[nb][i], -1), \
                       (nb, i, rotate(PRIMEKNOTS[nb][i], 3), rotate(PRIMEKNOTS[nb][i], -1))
                assert rotate(PRIMEKNOTS[nb][i], 4) == PRIMEKNOTS[nb][i], \
                       (nb, i, rotate(PRIMEKNOTS[nb][i]), 4)
                assert rotate(PRIMEKNOTS[nb][i], 12) == PRIMEKNOTS[nb][i], \
                       (nb, i, rotate(PRIMEKNOTS[nb][i]), 12)
                assert rotate(PRIMEKNOTS[nb][i], -4) == PRIMEKNOTS[nb][i], \
                       (nb, i, rotate(PRIMEKNOTS[nb][i]), -4)

                s_egalwidth = []
                s_egalwidth += PRIMEKNOTS[nb][i]
                make_egalwidth(s_egalwidth)
                s = []
                s += PRIMEKNOTS[nb][i]
                s = rotate(s, 0)
                assert s == PRIMEKNOTS[nb][i], (nb, i, s_egalwidth)
                s = rotate(s, 12)
                assert s == PRIMEKNOTS[nb][i], (nb, i, s_egalwidth)
                s = rotate(s, -12)
                assert s == PRIMEKNOTS[nb][i], (nb, i, s_egalwidth)
                s = rotate(s)
                s = rotate(s, 3)
                assert s == s_egalwidth, (nb, i, s_egalwidth)
                s = []
                s += PRIMEKNOTS[nb][i]
                s = rotate(s, 2)
                s = rotate(s, 2)
                assert s == s_egalwidth, (nb, i, s_egalwidth)
                s = []
                s += PRIMEKNOTS[nb][i]
                s = rotate(s, -1)
                t = []
                t += PRIMEKNOTS[nb][i]
                t = rotate(t, 3)
                assert s == t, (nb, i, s, t)

                for labels in ['A'*nb, 'B'*nb]:
                    assert to_labelstates(rotate(PRIMEKNOTS[nb][i]), labels) \
                           == rotate(to_labelstates(PRIMEKNOTS[nb][i], labels)), \
                           (nb, i, to_labelstates(rotate(PRIMEKNOTS[nb][i]), labels),
                            rotate(to_labelstates(PRIMEKNOTS[nb][i], labels)))
                    assert to_states(rotate(PRIMEKNOTS[nb][i]), labels) \
                           == rotate(to_states(PRIMEKNOTS[nb][i], labels)), \
                           (nb, i, to_states(rotate(PRIMEKNOTS[nb][i]), labels),
                            rotate(to_states(PRIMEKNOTS[nb][i], labels)))
                assert to_universes(rotate(PRIMEKNOTS[nb][i])) \
                       == rotate(to_universes(PRIMEKNOTS[nb][i])), \
                       (nb, i, to_universes(rotate(PRIMEKNOTS[nb][i])),
                        rotate(to_universes(PRIMEKNOTS[nb][i])))
        print('ok'); sys.stdout.flush()


        print('space_is()...', end=''); sys.stdout.flush()
        assert space_is([])
        assert not space_is(())
        assert space_is([EMPTY, ''])
        assert not space_is([EMPTY, 666, ''])
        assert space_is([' _',
                         '( )',
                         ' ^'])
        assert not space_is([' _',
                             '( )',
                             ' ^)'])
        for c in SPACECHARS:
            assert space_is([c])
        for i in range(256):
            c = chr(i)
            if c in SPACECHARS:
                assert space_is([c])
            else:
                assert not space_is([c])
        for nb in PRIMEKNOTS:
            for i in PRIMEKNOTS[nb]:
                assert space_is(PRIMEKNOTS[nb][i]), (nb, i, PRIMEKNOTS[nb][i])
                for labels in labels_list(nb_cross(PRIMEKNOTS[nb][i])):
                    assert space_is(to_labelstates(PRIMEKNOTS[nb][i], labels)), \
                           (nb, i, to_labelstates(PRIMEKNOTS[nb][i], labels))
                    assert space_is(to_states(PRIMEKNOTS[nb][i], labels)), \
                           (nb, i, to_states(PRIMEKNOTS[nb][i], labels))
                assert space_is(to_universes(PRIMEKNOTS[nb][i])), \
                       (nb, i, to_universes(PRIMEKNOTS[nb][i]))
        print('ok'); sys.stdout.flush()


        print('states_is()...', end=''); sys.stdout.flush()
        assert states_is([])
        assert states_is([EMPTY, ''])
        for c in STATECHARS:
            assert states_is([c])
        for i in range(256):
            c = chr(i)
            if c in STATECHARS:
                assert states_is([c])
        for nb in PRIMEKNOTS:
            for i in PRIMEKNOTS[nb]:
                for labels in labels_list(nb_cross(PRIMEKNOTS[nb][i])):
                    assert states_is(to_states(PRIMEKNOTS[nb][i], labels)), \
                           (nb, i, PRIMEKNOTS[nb][i], labels, to_states(PRIMEKNOTS[nb][i]))
            if nb > 0:
                for i in PRIMEKNOTS[nb]:
                    assert not states_is(PRIMEKNOTS[nb][i]), (nb, i, PRIMEKNOTS[nb][i])
                    for labels in labels_list(nb_cross(PRIMEKNOTS[nb][i])):
                        assert not states_is(to_labelstates(PRIMEKNOTS[nb][i], labels)), \
                               (nb, i, PRIMEKNOTS[nb][i], labels,
                                to_labelstates(PRIMEKNOTS[nb][i], labels))
                    assert not states_is(to_universes(PRIMEKNOTS[nb][i])), \
                           (nb, i, PRIMEKNOTS[nb][i], to_universes(PRIMEKNOTS[nb][i]))
        print('ok'); sys.stdout.flush()


        print('to_labelstates()...', end=''); sys.stdout.flush()
        assert to_labelstates([]) == [], to_labelstates([])
        assert to_labelstates([CROSSUP, '']) == [CROSSUPA, ''], to_labelstates([CROSSUP, ''])
        assert to_labelstates([CROSSUP, ''], 'B') == [CROSSUPB, ''], \
               to_labelstates([CROSSUP, ''], 'B')
        assert to_labelstates([CROSSDOWN, '']) == [CROSSDOWNA, ''], to_labelstates([CROSSDOWN, ''])
        assert to_labelstates([CROSSDOWN, ''], 'B') == [CROSSDOWNB, ''], \
               to_labelstates([CROSSDOWN, ''], 'B')
        assert to_labelstates([CROSSUPA, '']) == [CROSSUPA, ''], to_labelstates([CROSSUPA, ''])
        assert to_labelstates([CROSSUPA, ''], 'B') == [CROSSUPB, ''], \
               to_labelstates([CROSSUPA, ''], 'B')
        assert to_labelstates([CROSSDOWNA, '']) == [CROSSDOWNA, ''], \
               to_labelstates([CROSSDOWNA, ''])
        assert to_labelstates([CROSSDOWNA, ''], 'B') == [CROSSDOWNB, ''], \
               to_labelstates([CROSSDOWNA, ''], 'B')
        for c in KNOTCHARS.replace(CROSSUP, EMPTY).replace(CROSSDOWN, EMPTY):
            for labels in labels_list(nb_cross(PRIMEKNOTS[nb][i])):
                assert to_labelstates([c, ''], labels) == [c, ''], \
                       (c, labels, to_labelstates([c, ''], labels))
        assert to_labelstates(PRIMEKNOTS[0][1]) == PRIMEKNOTS[0][1], \
               to_labelstates(PRIMEKNOTS[0][1])
        assert to_labelstates(PRIMEKNOTS[3][1]) == [' /A\\', '(( a', ' \\A/'], \
               to_labelstates(PRIMEKNOTS[3][1])
        assert to_labelstates(PRIMEKNOTS[3][1], 'B') == [' /B\\', '(( a', ' \\A/'], \
               to_labelstates(PRIMEKNOTS[3][1], 'B')
        assert to_labelstates(PRIMEKNOTS[3][1], 'AAA') == [' /A\\', '(( a', ' \\A/'], \
               to_labelstates(PRIMEKNOTS[3][1], 'AAA')
        assert to_labelstates(PRIMEKNOTS[3][1], 'AAB') == [' /A\\', '(( a', ' \\B/'], \
               to_labelstates(PRIMEKNOTS[3][1], 'AAB')
        assert to_labelstates(PRIMEKNOTS[3][1], 'ABA') == [' /A\\', '(( b', ' \\A/'], \
               to_labelstates(PRIMEKNOTS[3][1], 'ABA')
        assert to_labelstates(PRIMEKNOTS[3][1], 'ABB') == [' /A\\', '(( b', ' \\B/'], \
               to_labelstates(PRIMEKNOTS[3][1], 'ABB')
        assert to_labelstates(PRIMEKNOTS[3][1], 'BAA') == [' /B\\', '(( a', ' \\A/'], \
               to_labelstates(PRIMEKNOTS[3][1], 'BAA')
        assert to_labelstates(PRIMEKNOTS[3][1], 'BAB') == [' /B\\', '(( a', ' \\B/'], \
               to_labelstates(PRIMEKNOTS[3][1], 'BAB')
        assert to_labelstates(PRIMEKNOTS[3][1], 'BBA') == [' /B\\', '(( b', ' \\A/'], \
               to_labelstates(PRIMEKNOTS[3][1], 'BBA')
        assert to_labelstates(PRIMEKNOTS[3][1], 'BBB') == [' /B\\', '(( b', ' \\B/'], \
               to_labelstates(PRIMEKNOTS[3][1], 'BBB')
        assert to_labelstates(PRIMEKNOTS[7][1]) \
               == [' _____', '/     \\', 'AAAAAAA', '\\     /', ' ^^^^^'], \
               to_labelstates(PRIMEKNOTS[7][1])
        for labels in labels_list(nb_cross(PRIMEKNOTS[7][1])):
            assert to_labelstates(PRIMEKNOTS[7][1], labels) \
                   == [' _____', '/     \\', labels, '\\     /', ' ^^^^^'], \
                   (labels, to_labelstates(PRIMEKNOTS[7][1]))
        for nb in PRIMEKNOTS:
            for i in PRIMEKNOTS[nb]:
                for labels in labels_list(nb_cross(PRIMEKNOTS[nb][i])):
                    s = to_labelstates(PRIMEKNOTS[nb][i], labels)
                    assert labelstates_is(s), (nb, i, labels, PRIMEKNOTS[nb][i], s)
                    assert s == to_labelstates(s, labels), \
                           (nb, i, labels, s, to_labelstates(s, labels))
                    assert s == to_labelstates(to_labelstates(PRIMEKNOTS[nb][i]), labels), \
                           (nb, i, labels, s,
                            to_labelstates(to_labelstates(PRIMEKNOTS[nb][i]), labels))
                    assert s == to_labelstates(to_labelstates(PRIMEKNOTS[nb][i], 'BA'*4), labels),\
                           (nb, i, labels, s,
                            to_labelstates(to_labelstates(PRIMEKNOTS[nb][i], 'BA'*4), labels))
        print('ok'); sys.stdout.flush()


        print('to_LaTeX()...', end=''); sys.stdout.flush()
        assert isinstance(to_LaTeX([]), str)
        assert isinstance(to_LaTeX(['']), str)
        assert isinstance(to_LaTeX([]), str)
        for nb in PRIMEKNOTS:
            for i in PRIMEKNOTS[nb]:
                assert isinstance(to_LaTeX(PRIMEKNOTS[nb][i]), str), (nb, i)
                assert isinstance(to_LaTeX(PRIMEKNOTS[nb][i],
                                           length=20, shape=5, grid=True), str), (nb, i)
        print('ok'); sys.stdout.flush()


        print('to_PS()...', end=''); sys.stdout.flush()
        assert isinstance(to_PS([]), str)
        assert isinstance(to_PS(['']), str)
        assert isinstance(to_PS([]), str)
        for nb in PRIMEKNOTS:
            for i in PRIMEKNOTS[nb]:
                assert isinstance(to_PS(PRIMEKNOTS[nb][i]), str), (nb, i)
                assert isinstance(to_PS(PRIMEKNOTS[nb][i],
                                        length=20, margin=0, shape=5, grid=True), str), (nb, i)
        print('ok'); sys.stdout.flush()


        print('to_states()...', end=''); sys.stdout.flush()
        assert to_states([]) == [], to_states([])
        assert to_states([CROSSUP, '']) == [VERT, ''], to_states([CROSSUP, ''])
        assert to_states([CROSSUP, ''], 'B') == [HORI, ''], \
               to_states([CROSSUP, ''], 'B')
        assert to_states([CROSSDOWN, '']) == [HORI, ''], to_states([CROSSDOWN, ''])
        assert to_states([CROSSDOWN, ''], 'B') == [VERT, ''], \
               to_states([CROSSDOWN, ''], 'B')
        assert to_states([CROSSUPA, '']) == [VERT, ''], to_states([CROSSUPA, ''])
        assert to_states([CROSSUPA, ''], 'B') == [HORI, ''], \
               to_states([CROSSUPA, ''], 'B')
        assert to_states([CROSSDOWNA, '']) == [HORI, ''], to_states([CROSSDOWNA, ''])
        assert to_states([CROSSDOWNA, ''], 'B') == [VERT, ''], \
               to_states([CROSSDOWNA, ''], 'B')
        for c in (KNOTCHARS + VERT + HORI) \
                .replace(CROSSUP, EMPTY).replace(CROSSDOWN, EMPTY):
            for labels in labels_list(nb_cross(PRIMEKNOTS[nb][i])):
                assert to_states([c, ''], labels) == [c, ''], \
                       (c, labels, to_states([c, ''], labels))
        assert to_states(PRIMEKNOTS[0][1]) == PRIMEKNOTS[0][1], to_states(PRIMEKNOTS[0][1])
        assert to_states(PRIMEKNOTS[3][1]) == [' /"\\', '(( =', ' \\"/'], \
               to_states(PRIMEKNOTS[3][1])
        assert to_states(PRIMEKNOTS[3][1], 'B') == [' /=\\', '(( =', ' \\"/'], \
               to_states(PRIMEKNOTS[3][1], 'B')
        assert to_states(PRIMEKNOTS[3][1], 'AAA') == [' /"\\', '(( =', ' \\"/'], \
               to_states(PRIMEKNOTS[3][1], 'AAA')
        assert to_states(PRIMEKNOTS[3][1], 'AAB') == [' /"\\', '(( =', ' \\=/'], \
               to_states(PRIMEKNOTS[3][1], 'AAB')
        assert to_states(PRIMEKNOTS[3][1], 'ABA') == [' /"\\', '(( "', ' \\"/'], \
               to_states(PRIMEKNOTS[3][1], 'ABA')
        assert to_states(PRIMEKNOTS[3][1], 'ABB') == [' /"\\', '(( "', ' \\=/'], \
               to_states(PRIMEKNOTS[3][1], 'ABB')
        assert to_states(PRIMEKNOTS[3][1], 'BAA') == [' /=\\', '(( =', ' \\"/'], \
               to_states(PRIMEKNOTS[3][1], 'BAA')
        assert to_states(PRIMEKNOTS[3][1], 'BAB') == [' /=\\', '(( =', ' \\=/'], \
               to_states(PRIMEKNOTS[3][1], 'BAB')
        assert to_states(PRIMEKNOTS[3][1], 'BBA') == [' /=\\', '(( "', ' \\"/'], \
               to_states(PRIMEKNOTS[3][1], 'BBA')
        assert to_states(PRIMEKNOTS[3][1], 'BBB') == [' /=\\', '(( "', ' \\=/'], \
               to_states(PRIMEKNOTS[3][1], 'BBB')
        assert to_states(PRIMEKNOTS[7][1]) \
               == [' _____', '/     \\', '"""""""', '\\     /', ' ^^^^^'], \
               to_states(PRIMEKNOTS[7][1])
        for labels in labels_list(nb_cross(PRIMEKNOTS[7][1])):
            assert to_states(PRIMEKNOTS[7][1], labels) \
                   == [' _____', '/     \\', labels.replace('A', '"').replace('B', '='),
                   '\\     /', ' ^^^^^'], (labels, to_states(PRIMEKNOTS[7][1]))
        for nb in PRIMEKNOTS:
            for i in PRIMEKNOTS[nb]:
                for labels in labels_list(nb_cross(PRIMEKNOTS[nb][i])):
                    s = to_states(PRIMEKNOTS[nb][i], labels)
                    assert states_is(s), (nb, i, labels, PRIMEKNOTS[nb][i], s)
                    assert s == to_states(s, labels), (nb, i, labels, s, to_states(s, labels))
                    assert s == to_states(s), (nb, i, labels, s, to_states(s))
                    assert s == to_states(s, 'BA'*4), (nb, i, labels, s, to_states(s, 'BA'*4))
                    assert s == to_states(to_labelstates(PRIMEKNOTS[nb][i], labels), labels), \
                           (nb, i, labels, s,
                            to_states(to_labelstates(PRIMEKNOTS[nb][i], labels), labels))
                    assert s == to_states(to_labelstates(PRIMEKNOTS[nb][i]), labels), \
                           (nb, i, labels, s,
                            to_states(to_labelstates(PRIMEKNOTS[nb][i]), labels))
                    assert s == to_states(to_labelstates(PRIMEKNOTS[nb][i], 'BA'*4), labels), \
                           (nb, i, labels, s,
                            to_states(to_labelstates(PRIMEKNOTS[nb][i], 'BA'*4), labels))
        print('ok'); sys.stdout.flush()


        print('to_str()...', end=''); sys.stdout.flush()
        assert to_str([]) == '', to_str([])
        for c in SPACECHARS:
            assert to_str([c, '']) == c + '\n', (c, to_str([c, '']))
            assert to_str([c, c]) == c + '\n' + c, (c, to_str([c, c]))
        assert to_str(PRIMEKNOTS[0][1]) == '()', to_str(PRIMEKNOTS[0][1])
        assert to_str(PRIMEKNOTS[7][1]) == ' _____\n/     \\\n%%%%%%%\n\\     /\n ^^^^^', \
               to_str(PRIMEKNOTS[7][1])
        for labels in labels_list(nb_cross(PRIMEKNOTS[7][1])):
            assert to_str(to_labelstates(PRIMEKNOTS[7][1], labels)) \
                   == ' _____\n/     \\\n{0}\n\\     /\n ^^^^^'.format(labels), \
                   to_str(to_labelstates(PRIMEKNOTS[7][1], labels))
            assert to_str(to_states(PRIMEKNOTS[7][1], labels)) \
                   == ' _____\n/     \\\n{0}\n\\     /\n ^^^^^' \
                   .format(labels.replace('A', '"').replace('B', '=')), \
                   to_str(to_states(PRIMEKNOTS[7][1], labels))
        assert to_str(to_universes(PRIMEKNOTS[7][1])) \
               == ' _____\n/     \\\nxxxxxxx\n\\     /\n ^^^^^', \
               to_str(to_universes(PRIMEKNOTS[7][1]))
        print('ok'); sys.stdout.flush()


        print('to_universes()...', end=''); sys.stdout.flush()
        assert to_universes([]) == [], to_universes([])
        for c in KNOTCHARS.replace(CROSSUP, EMPTY).replace(CROSSDOWN, EMPTY):
            assert to_universes([c, '']) == [c, ''], (c, to_universes([c, '']))
        assert to_universes([CROSSUP, '']) == [CROSS, ''], to_universes([CROSSUP, ''])
        assert to_universes([CROSSDOWN, '']) == [CROSS, ''], to_universes([CROSSDOWN, ''])
        assert to_universes([CROSSUPA, '']) == [CROSS, ''], to_universes([CROSSUPA, ''])
        assert to_universes([CROSSDOWNA, '']) == [CROSS, ''], to_universes([CROSSDOWNA, ''])
        assert to_universes([CROSSUPB, '']) == [CROSS, ''], to_universes([CROSSUPB, ''])
        assert to_universes([CROSSDOWNB, '']) == [CROSS, ''], to_universes([CROSSDOWNB, ''])
        assert to_universes(PRIMEKNOTS[0][1]) == PRIMEKNOTS[0][1], to_universes(PRIMEKNOTS[0][1])
        assert to_universes(PRIMEKNOTS[3][1]) == [' /x\\', '(( x', ' \\x/'], \
               to_universes(PRIMEKNOTS[3][1])
        assert to_universes(PRIMEKNOTS[7][1]) \
               == [' _____', '/     \\', 'xxxxxxx', '\\     /', ' ^^^^^'], \
               to_universes(PRIMEKNOTS[7][1])
        for nb in PRIMEKNOTS:
            for i in PRIMEKNOTS[nb]:
                u = to_universes(PRIMEKNOTS[nb][i])
                assert universes_is(u), (nb, i, PRIMEKNOTS[nb][i], u)
                assert u == to_universes(u), (nb, i, labels, u, to_universes(u))
                for labels in labels_list(nb_cross(PRIMEKNOTS[nb][i])):
                    if nb == 0:
                        assert u == to_universes(to_states(PRIMEKNOTS[nb][i], labels)), \
                               (nb, i, labels, u,
                                to_universes(to_states(PRIMEKNOTS[nb][i], labels)))
                    else:
                        assert u != to_universes(to_states(PRIMEKNOTS[nb][i], labels)), \
                               (nb, i, labels, u,
                                to_universes(to_states(PRIMEKNOTS[nb][i], labels)))
                    assert u == to_universes(to_labelstates(PRIMEKNOTS[nb][i], labels)), \
                           (nb, i, labels, u,
                            to_universes(to_labelstates(PRIMEKNOTS[nb][i], labels)))
        print('ok'); sys.stdout.flush()


        print('universes_is()...', end=''); sys.stdout.flush()
        assert universes_is([])
        assert universes_is([EMPTY, ''])
        for c in UNIVERSECHARS:
            assert universes_is([c])
        for i in range(256):
            c = chr(i)
            if c in UNIVERSECHARS:
                assert universes_is([c])
        for nb in PRIMEKNOTS:
            for i in PRIMEKNOTS[nb]:
                assert universes_is(to_universes(PRIMEKNOTS[nb][i])), \
                       (nb, i, PRIMEKNOTS[nb][i], to_universes(PRIMEKNOTS[nb][i]))
            if nb > 0:
                for i in PRIMEKNOTS[nb]:
                    for labels in labels_list(nb_cross(PRIMEKNOTS[nb][i])):
                        assert not universes_is(to_labelstates(PRIMEKNOTS[nb][i], labels)), \
                               (nb, i, PRIMEKNOTS[nb][i], labels,
                                to_labelstates(PRIMEKNOTS[nb][i], labels))
                        assert universes_is(to_states(PRIMEKNOTS[nb][i], labels)), \
                               (nb, i, PRIMEKNOTS[nb][i], labels,
                                to_states(PRIMEKNOTS[nb][i], labels))
                    assert not universes_is(PRIMEKNOTS[nb][i]), (nb, i, PRIMEKNOTS[nb][i])
        print('ok'); sys.stdout.flush()


        print('write()...', end=''); sys.stdout.flush()
        s = []
        f = tempfile.NamedTemporaryFile(mode='w', suffix='.txt',
                                        prefix='DSPython_test_write_knots_{0}_{1}__'.format(nb, i),
                                        delete=False)
        for nb in PRIMEKNOTS:
            for i in PRIMEKNOTS[nb]:
                write(f, PRIMEKNOTS[nb][i])
                s += PRIMEKNOTS[nb][i]
        f.close()

        f = open(f.name)
        r = read(f)
        f.close()
        os.remove(f.name)
        assert r == s, (r, s)
        print('ok'); sys.stdout.flush()


        print('writhe()...', end=''); sys.stdout.flush()
        assert writhe([]) == 0, writhe([])
        assert writhe([EMPTY]) == 0, writhe([EMPTY])
        assert writhe(['(%)']) == 1, writhe(['(%)'])
        assert writhe(['(&)']) == -1, writhe(['(&)'])
        for nb in PRIMEKNOTS:
            for i in PRIMEKNOTS[nb]:
                assert -nb <= writhe(PRIMEKNOTS[nb][i]) <= nb, (nb, i, writhe(PRIMEKNOTS[nb][i]))
                assert writhe(PRIMEKNOTS[nb][i]) == -writhe(mirror(PRIMEKNOTS[nb][i])), \
                       (nb, i, writhe(PRIMEKNOTS[nb][i]), writhe(mirror(PRIMEKNOTS[nb][i])))
        print('???', end='')
        print('ok'); sys.stdout.flush()


        print('writhe_cross()...', end=''); sys.stdout.flush()
        assert writhe_cross(['(%)'], 1, 0) == 1, writhe_cross(['(%)'], 1, 0)
        assert writhe_cross(['(&)'], 1, 0) == -1, writhe_cross(['(&)'], 1, 0)
        s = ['_',
             '%',
             '^']
        assert writhe_cross(s, 0, 1) == -1, writhe_cross(s, 0, 1)
        s = ['_',
             '&',
             '^']
        assert writhe_cross(s, 0, 1) == 1, writhe_cross(s, 0, 1)
        s = ['/%\\',
             '%//',
             '\\/']
        assert writhe_cross(s, 1, 0) == 0, a.writhe_cross(s, 1, 0)
        assert writhe_cross(s, 0, 1) == 0, a.writhe_cross(s, 0, 1)
        s = ['/%\\',
             '&//',
             '\\/']
        assert writhe_cross(s, 1, 0) == 0, a.writhe_cross(s, 1, 0)
        assert writhe_cross(s, 0, 1) == 0, a.writhe_cross(s, 0, 1)
        s = ['/%\\',
             '\\^/',
             ' ^']
        assert writhe_cross(s, 1, 0) == -1, writhe_cross(s, 1, 0)
        s = ['/&\\',
             '\\^/',
             ' ^']
        assert writhe_cross(s, 1, 0) == 1, writhe_cross(s, 1, 0)
        print('ok'); sys.stdout.flush()


        print()
        print('Corners()...', end=''); sys.stdout.flush()
        print('???', end='')
        print('ok'); sys.stdout.flush()


        print('Corners.extremity()...', end=''); sys.stdout.flush()
        print('???', end='')
        print('ok'); sys.stdout.flush()


        print('Corners.nb_cycle()...', end=''); sys.stdout.flush()
        assert Corners([]).nb_cycle() == (0, 0), Corners([]).nb_cycle()
        assert Corners([EMPTY, '']).nb_cycle() == (0, 0), Corners([EMPTY, '']).nb_cycle()
        assert Corners(['()']).nb_cycle() == (1, 0), Corners(['()']).nb_cycle()
        assert Corners([')(']).nb_cycle() == (0, 2), Corners([')(']).nb_cycle()
        assert Corners([' _',
                        '( )',
                        ' ^']).nb_cycle() == (1, 0), Corners([' _', '( )', ' ^']).nb_cycle()
        assert Corners(['_',
                        ' )',
                        '_']).nb_cycle() == (0, 2), Corners(['_', ' )', '_']).nb_cycle()
        assert Corners([' _',
                        '( )',
                        ' _']).nb_cycle() == (0, 2), Corners([' _', '( )', ' _']).nb_cycle()
        assert Corners([' _  _',
                        '( )( )',
                        ' _  ^']).nb_cycle() == (1, 2), \
                        Corners([' _  _', '( )( )', ' _  ^']).nb_cycle()
        assert Corners(['   _  _ _',
                        '  ( )( )%',
                        '() _  ^ ^']).nb_cycle() == (3, 2), \
                        Corners(['   _  _ _', '  ( )( )%', '() _  ^ ^']).nb_cycle()
        for c in KNOTCHARS.replace(VERT, EMPTY).replace(HORI, EMPTY) \
                .replace(CROSSUP, EMPTY).replace(CROSSDOWN, EMPTY):
            if c == EMPTY:
                assert Corners([c]).nb_cycle() == (0, 0), (c, Corners([c]).nb_cycle())
            else:
                assert Corners([c]).nb_cycle() == (0, 1), (c, Corners([c]).nb_cycle())
        for c in VERT + HORI + CROSSUP + CROSSDOWN + CROSSUPA + CROSSUPB + CROSSDOWNA + CROSSDOWNB:
            assert Corners([c]).nb_cycle() == (0, 2), (c, Corners([c]).nb_cycle())
        for nb in PRIMEKNOTS:
            for i in PRIMEKNOTS[nb]:
                assert Corners(PRIMEKNOTS[nb][i]).nb_cycle() == (1, 0), \
                       (nb, i, Corners(PRIMEKNOTS[nb][i]).nb_cycle(), PRIMEKNOTS[nb][i])
                assert Corners(to_universes(PRIMEKNOTS[nb][i])).nb_cycle() == (1, 0), \
                       (nb, i, Corners(to_universes(PRIMEKNOTS[nb][i])).nb_cycle(),
                        to_universes(PRIMEKNOTS[nb][i]))
        print('ok'); sys.stdout.flush()


        print('Corners.writhe_cross()...', end=''); sys.stdout.flush()
        a = Corners(['(%)'])
        assert a.writhe_cross(1, 0, True) == 1, a.writhe_cross(1, 0, True)
        assert a.writhe_cross(1, 0, False) == -1, a.writhe_cross(1, 0, False)
        a = Corners(['_',
                     '%',
                     '^'])
        assert a.writhe_cross(0, 1, True) == -1, a.writhe_cross(0, 1, True)
        assert a.writhe_cross(0, 1, False) == 1, a.writhe_cross(0, 1, False)
        a = Corners(['/%\\',
                     '%//',
                     '\\/'])
        assert a.writhe_cross(1, 0, True) == 0, a.writhe_cross(1, 0, True)
        assert a.writhe_cross(1, 0, False) == 0, a.writhe_cross(1, 0, False)
        assert a.writhe_cross(0, 1, True) == 0, a.writhe_cross(0, 1, True)
        assert a.writhe_cross(0, 1, False) == 0, a.writhe_cross(0, 1, False)
        a = Corners(['/%\\',
                     '&//',
                     '\\/'])
        assert a.writhe_cross(1, 0, True) == 0, a.writhe_cross(1, 0, True)
        assert a.writhe_cross(1, 0, False) == 0, a.writhe_cross(1, 0, False)
        assert a.writhe_cross(0, 1, True) == 0, a.writhe_cross(0, 1, True)
        assert a.writhe_cross(0, 1, False) == 0, a.writhe_cross(0, 1, False)
        a = Corners(['/%\\',
                     '\\^/',
                     ' ^'])
        assert a.writhe_cross(1, 0, True) == -1, a.writhe_cross(1, 0, True)
        assert a.writhe_cross(1, 0, False) == 1, a.writhe_cross(1, 0, False)
        print('ok'); sys.stdout.flush()
        debug.test_end()

    main_test()
##\endcond MAINTEST