# -*- coding: iso-8859-1 -*-
# Copyright 20003 - 2008: Julien Bourdaillet (julien.bourdaillet@lip6.fr), Jean-Gabriel Ganascia (jean-gabriel.ganascia@lip6.fr)
# This file is part of MEDITE.
#
#    MEDITE is free software; you can redistribute it and/or modify
#    it under the terms of the GNU General Public License as published by
#    the Free Software Foundation; either version 2 of the License, or
#    (at your option) any later version.
#
#    MEDITE is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#    GNU General Public License for more details.
#
#    You should have received a copy of the GNU General Public License
#    along with Foobar; if not, write to the Free Software
#    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

import copy, logging, bisect

class Alignement:
    def alignement(self,L1,L2,texte1,texte2,lt1):
        raise NotImplementedError

class AlignGlouton (Alignement):

    def alignement(self,L1,L2,texte1,texte2,lt1):
        """ Alignement Glouton entre les 2 séquences
        pre: isinstance(L1,list) and isinstance(L2,list) and isinstance(texte1,str) and isinstance(texte2,str)
        post: (len(__return__[0])==len(__return__[1])) or (len(__return__[0])==len(__return__[1])+1) or \
              (len(__return__[0])+1==len(__return__[1]))
        """
        # dicoPos1 stocke pour chaque bloc de L1 ses positions dans cette liste
        logging.log(5,"debut _appelGlouton")
        llh1 = []
        llh2 = []
        i=0
        for bloc in L1:
            cle = hash(texte1[bloc[0]:bloc[1]])
            llh1.append([bloc[1]-bloc[0],cle,i])
            i += 1

#        logging.log(5,'init L1 done')
        i = 0
        for bloc in L2:
           cle = hash(texte2[bloc[0]-lt1:bloc[1]-lt1])
           llh2.append([bloc[1]-bloc[0],cle,i])
           i +=1

#        logging.log(5,'init L2 done')
        r1,r2 = self._gloutonRecur(llh1,llh2)
        res1=[]
        res2=[]
        r1.sort()
        r2.sort()


        #formatage des listes de retour pour les deplacements
        lastkey = 0
        for key in r1 :
            l = []
            for i in xrange(lastkey,key):
                l.append(L1[i])
            res1.append((L1[key],l))
            lastkey = key+1
        if lastkey < len(L1) :
            l = []
            for i in xrange(lastkey,len(L1)):
                l.append(L1[i])
            res1.append((None,l))

        lastkey = 0
        for key in r2 :
            l = []
            for i in xrange(lastkey,key):
                l.append(L2[i])
            res2.append((L2[key],l))
            lastkey = key+1
        if lastkey < len(L2) :
            l = []
            for i in xrange(lastkey,len(L2)):
                l.append(L2[i])
            res2.append((None,l))

        return res1,res2

    def _gloutonSplit(self,l1,l2):
        """ Identifie les positions du bloc le plus long commun aux deux listes
        @type l1: list
        @param l1: liste de liste de blocs au format suivant [longueur du bloc,hash du bloc, position du bloc dans la liste initaiale des blocs]
        @type l2: list
        @param l2: liste de liste de blocs au format suivant [longueur du bloc,hash du bloc, position du bloc dans la liste initaiale des blocs]
        @rtype:   list
        @return:  les 2 éléments communs si on les trouve, None,None sinon
        """

        #On copie les listes afins de ne pas modifier les listes initiales
        l1Copy=copy.copy(l1)
        l2Copy=copy.copy(l2)
        # tri des listes par taille des blocs croissants
        l1Copy.sort()
        l2Copy.sort()
        #on inverse pour avoir un tri par taille de blocs décroissants
        l1Copy.reverse()
        l2Copy.reverse()
        trouve = False
        i = 0

        #tant que l'on a pas trouvé l'élément commun ou que tous les éléments de l1Copy ont été parcourus
        while trouve == False and i < (len(l1Copy)):
            j = 0

            #on cherche l'élément de la liste l2Copy de hash egal a l'element actuel
            #on boucle tant qu'on a un élément dont la taille du bloc est inférieur ou egale a l'éléemnt de l12 auquel on compare puisque les listes sont triées
            while l1Copy[i][1] != l2Copy[j][1] and j < (len(l2Copy))-1 and l1Copy[i][0]<=l2Copy[j][0] :
                j+=1

            #position du plus garnd bloc commun trouvée
            if l1Copy[i][1] == l2Copy[j][1]:
                trouve = True
            else :
                i+=1

        if trouve == False :
            return None,None
        else :
             return l1Copy[i],l2Copy[j]

    def _gloutonRecur(self,lenHashPos1,lenHashPos2):
        """ Appel recursif pour l'algorithme glouton
        @type lenHashPos1: list
        @param lenHashPos1: liste de liste de blocs au format suivant [longueur du bloc,hash du bloc, position du bloc dans la liste initaiale des blocs]
        @type lenHashPos2: list
        @param lenHashPos2: liste de liste de blocs au format suivant [longueur du bloc,hash du bloc, position du bloc dans la liste initaiale des blocs]
        @rtype:   list
        @return:  les positions des plus longs blocs communs, None,None si il n'y en a pas
        """
        #une liste vide : condition d'arret de la recusion
        if (len(lenHashPos1) != 0 and len(lenHashPos2) != 0) :
            #recuperation des objets représentant le bloc commun le plus long au deux listes
            blocSplit1,blocSplit2=self._gloutonSplit(lenHashPos1, lenHashPos2)

            #pas de bloc commun trouvé
            if (blocSplit1 == None or blocSplit2 == None) :
                return [],[]
            #position des objets représentant le bloc commun le plus long dans les listes placées en parametre afin de scinder celles-ci au bon endroit
            posSplit1 = lenHashPos1.index(blocSplit1)
            posSplit2 = lenHashPos2.index(blocSplit2)

            #recherche a gauche
            blocAlignesGauche1,blocAlignesGauche2= self._gloutonRecur(lenHashPos1[:posSplit1],lenHashPos2[:posSplit2])

            #recherche a droite
            blocAlignesDroite1,blocAlignesDroite2= self._gloutonRecur(lenHashPos1[posSplit1+1:],lenHashPos2[posSplit2+1:])


            #on concatene les resultat (on ne peut pas faire None.extend()
            if len(blocAlignesGauche1) == 0 or blocAlignesGauche1 == None:
                #pas de resultat a gauche
                if blocAlignesDroite1 == None : blocAlignesDroite1 = []
                #on concatene le resultat actuel  au resultat de la recherche a droite
                res1 = [blocSplit1[2]]
                res1.extend(blocAlignesDroite1)
            else :
                if blocAlignesDroite1 == None : blocAlignesDroite1 = []
                #concatenation resultat recherche gauche, resultat actuel, resultat recherche droite
                res1 = blocAlignesGauche1
                res1.extend([blocSplit1[2]])
                res1.extend(blocAlignesDroite1)


            if len(blocAlignesGauche2) == 0 or blocAlignesGauche2 == None:
                #pas de resultat a gauche
                if blocAlignesDroite2 == None : blocAlignesDroite2 = []
                #on concatene le resultat actuel  au resultat de la recherche a droite
                res2 = [blocSplit2[2]]
                res2.extend(blocAlignesDroite2)
            else :
                if blocAlignesDroite2 == None : blocAlignesDroite2 = []
                #concatenation resultat recherche gauche, resultat actuel, resultat recherche droite
                res2 = blocAlignesGauche2
                res2.extend([blocSplit2[2]])
                res2.extend(blocAlignesDroite2)

            return res1,res2

        else :
            return [],[]


class AlignLIS (Alignement):

    def _couverture(self,pi):
        """Calcule la couverture d'une liste d'entiers
        @type pi: list
        @param pi: la liste d'entiers dont on veut calculer la couverture
        @rtype:   list of list
        @return:  la couverture de pi
        """
        tailleCouverture = 0
        couverture=[]
        couvertureLast=[]
        for i in xrange(len(pi)):
            j=0
    
            while (j < tailleCouverture) and (pi[i][0] > couvertureLast[j]) :
                #recherche de l'endroit ou il faut inserer l'element
                   j+=1
            #insertion de l'élément dans la couverture
            if j == tailleCouverture :
                #on doit créer une nouvelle sequence dans la couverture
                tailleCouverture+=1
                couverture.append([pi[i]])
                couvertureLast.append(pi[i][0])               
            else :
                couverture[j].append(pi[i])
                couvertureLast[j]=pi[i][0]

        return couverture
    
    def _lcis(self,couverture):
        """Calcule la plus longue sous séquence améliorante d'une liste a partir de sa couverture 
        @type couverture: list of list
        @param couverture: la couverture
        @rtype: list
        @return: la plus longue sous séquence améliorante
        @see: #couverture
        """
        i = len(couverture)-1
        if i<0 : return []
        I = []
        #
        #si on a une couverture de taille i, la plus longue sous sequence comune aura i blocs
        #si la derniere séquence de la couverture a plusieurs éléments, c'est qu'on peut trouver autant de sous sequences communes aux deux textes qu'il n'y a d'éléments dans cette derniere séquence
        #on choisit r le plus petit possible afin d'obtenir la sous séquence la plus décalée vers la gauche du texte
        
        #initialisation
        #r = random.randint(0,len(couverture[i])-1)
        r = len(couverture[i])-1
        #r = 0
        
        x = couverture[i][r]
        I.append(x)
        while (i > 0) :
            trouve = False
            j = 0
            #on cherche l'élément de position maximal précédent le dernier élément placé dans la plus longue sous-séquence commune
            #(les éléments sont triés par ordre de position décroissante dans les séquences de la couverture)
            while trouve == False :
                if couverture[i-1][j][0] < x[0] :
                    y = couverture[i-1][j]
                    trouve = True
                else :
                    j+=1
            x = y
            i-=1
            I.append(x)
            
        I.reverse()
        return I
    
    
    def _posOcurrences(self,c,l,posC):
        """
        cherche les positions de c dans la liste l, le resultat est renvoyé dans l'ordre décroissant des indexes
        @type c: object
        @param c: l'objet dont on cherche la position des occurences
        @type l: list
        @param l: la liste dans laquelle on cherche les positions de c
        @rtype : list
        @return: positions auxquelles on a trouvé c dans l
        """
        r = []
        for i in xrange(len(l)) :
            if c == l[i] : 
                r.append((i,posC))
            
        r.reverse()
        return r
    
    def _creerPi(self,S1,S2):
        """Crée la liste PI(S1,S2), liste des positions de chaque élément de S1 dans S2 dans l'ordre décroissant        
        @type S1: list
        @param S1: liste d'objets
        @type S2: list
        @param S2: list d'objets
        @rtype : list
        @return : liste des positions de chaque élément de S1 dans S2 dans l'ordre décroissant
        """
        PI = []
        for i in xrange(len(S1)) :
            PI.extend(self._posOcurrences(S1[i],S2,i))
        return PI
    
    
    def _init_alignement(self,L1,L2,texte1,texte2,lt1):
        """ Transformation en un alphabet ordonné """
        Lkey1 = []
        Lkey2 = []
        
        #création des listes de hash
        
        for bloc in L1:
            cle = hash(texte1[bloc[0]:bloc[1]])
            Lkey1.append((cle,0))
         
        for bloc in L2:
            cle = hash(texte2[bloc[0]-lt1:bloc[1]-lt1])
            Lkey2.append((cle,0))
            
        return Lkey1, Lkey2
        
    def alignement(self,L1,L2,texte1,texte2,lt1):
        """ Alignement LIS entre les 2 séquences 
        pre: isinstance(L1,list) and isinstance(L2,list) and isinstance(texte1,str) and isinstance(texte2,str)
        post: (len(__return__[0])==len(__return__[1])) or (len(__return__[0])==len(__return__[1])+1) or \
              (len(__return__[0])+1==len(__return__[1]))
        """
        Lkey1, Lkey2 = self._init_alignement(L1,L2,texte1,texte2,lt1)
        #création des listes PI    
        PI = self._creerPi(Lkey2,Lkey1)
        #recherche de la plus longue sous-sequence améliorante 
        lcis = self._lcis(self._couverture(PI))


        key1=[]
        key2=[]
        for i in xrange(len(lcis)) :
            key2.append(lcis[i][1])
            key1.append(lcis[i][0])

        key1.sort()
        key2.sort()
        #on recrée la liste des bloc correspondants
        res1=[]
        res2=[]

        lastkey=0
        for key in key2 :
            l = []
            for i in xrange(lastkey,key):
                l.append(L2[i])
            res1.append((L2[key],l))
            lastkey = key+1
        if lastkey < len(L2) :
            l = []
            for i in xrange(lastkey,len(L2)):
                l.append(L2[i])
            res1.append((None,l))
      
      
        lastkey=0  
        for key in key1 :
            l = []
            for i in xrange(lastkey,key):
                l.append(L1[i])
            res2.append((L1[key],l))
            lastkey=key+1
            
        if lastkey < len(L1) :
            l = []
            for i in xrange(lastkey,len(L1)):
                l.append(L1[i])
            res2.append((None,l))
            
        #print res2,res1
        return res2,res1

class AlignHIS (AlignLIS):
    def _posOcurrences(self,c,l,posC):
        """
        cherche les positions de c dans la liste l, le resultat est renvoyé dans l'ordre décroissant des indexes
        @type c: object
        @param c: l'objet dont on cherche la position des occurences
        @type l: list
        @param l: la liste dans laquelle on cherche les positions de c
        @rtype : list
        @return: positions auxquelles on a trouvé c dans l
        """
        r = []
        for i in xrange(len(l)) :
            if c == l[i] : 
                r.append((i,posC,c))
            
        r.reverse()
        return r
        
    def _init_alignement(self,L1,L2,texte1,texte2,lt1):
        """ Transformation en un alphabet ordonné """
        Lkey1 = []
        Lkey2 = []
        
        #création des listes de hash
        
        for bloc in L1:
            cle = hash(texte1[bloc[0]:bloc[1]])
            longueur = bloc[1] - bloc[0]
            Lkey1.append((cle, longueur))
         
        for bloc in L2:
            cle = hash(texte2[bloc[0]-lt1:bloc[1]-lt1])
            longueur = bloc[1] - bloc[0]
            Lkey2.append((cle,longueur))
            
        return Lkey1, Lkey2
    
    def _lcis(self,couverture):
        """Calcule la plus longue sous séquence améliorante d'une liste a partir de sa couverture 
        @type couverture: list of list
        @param couverture: la couverture
        @rtype: list
        @return: la plus longue sous séquence améliorante
        @see: #couverture
        """
        i = len(couverture)-1
        if i<0 : return []
        I = []
        #
        #si on a une couverture de taille i, la plus longue sous sequence comune aura i blocs
        #si la derniere séquence de la couverture a plusieurs éléments, c'est qu'on peut trouver autant de sous sequences communes aux deux textes qu'il n'y a d'éléments dans cette derniere séquence
        #on choisit r le plus petit possible afin d'obtenir la sous séquence la plus décalée vers la gauche du texte
        
        #initialisation
        #r = random.randint(0,len(couverture[i])-1)
        r = len(couverture[i])-1
        #r = 0
        debug = False
        x = couverture[i][r]
        if debug: print x
        I.append(x)
        while (i > 0) :
            trouve = False
            j = 0
            liste_y = []
            #on cherche l'élément de position maximal précédent le dernier élément placé dans la plus longue sous-séquence commune
            #(les éléments sont triés par ordre de position décroissante dans les séquences de la couverture)
            if debug: print couverture[i-1]
            while j < len(couverture[i-1]): #trouve == False :
                element = couverture[i-1][j]
                pos = element[0] ; pos2 = element[1] ; poids = element[2][1]
                if pos < x[0] and pos2 < x[1]:
                    liste_y.append( element)
                    j += 1
                else :
                    j+=1
            assert len(liste_y) > 0
            if debug: print liste_y
            max_y = 0
            for candy in liste_y:
                poids = candy[2][1]
                if poids > max_y:
                    y = candy
                    max_y = poids
            x = y
            i-=1
            I.append(x)
            if debug: print x
            if debug: print '-------------'
        if debug: print '===================='
        assert len(I) == len(couverture)    
        I.reverse()
        if debug: print I
        return I

class AlignHISCont(AlignHIS):
    """HIS + contraintes de non chevauchement entre blocs de la lcs
    car recouvrement non résolus précédemment """
    def alignement(self,L1,L2,texte1,texte2,lt1):
        """ Alignement LIS entre les 2 séquences 
        pre: isinstance(L1,list) and isinstance(L2,list) and isinstance(texte1,str) and isinstance(texte2,str)
        post: (len(__return__[0])==len(__return__[1])) or (len(__return__[0])==len(__return__[1])+1) or \
              (len(__return__[0])+1==len(__return__[1]))
        """
        Lkey1, Lkey2 = self._init_alignement(L1,L2,texte1,texte2,lt1)
        #création des listes PI    
        PI = self._creerPi(Lkey2,Lkey1)
        #recherche de la plus longue sous-sequence améliorante 
        lcis = self._lcis(self._couverture(PI))

        key1=[]
        key2=[]
        for i in xrange(len(lcis)) :
            key2.append((lcis[i][1],L2[i][0],L2[i][1]))
            key1.append((lcis[i][0],L1[i][0],L1[i][1]))

        key1.sort()
        key2.sort()
        #print key1,key2
        k1 = [] ; k2 = []
        end1 = end2 = -1
        for b1,b2 in zip(key1,key2):
            c1, d1, f1 = b1
            c2, d2, f2 = b2
            if end1 <= d1 and end2 <= d2:
                k1.append(c1)
                k2.append(c2)
                end1 = f1
                end2 = f2
        key1 = k1
        key2 = k2
        #on recrée la liste des bloc correspondants
        res1=[]
        res2=[]

        lastkey=0
        for key in key2 :
            l = []
            for i in xrange(lastkey,key):
                l.append(L2[i])
            res1.append((L2[key],l))
            lastkey = key+1
        if lastkey < len(L2) :
            l = []
            for i in xrange(lastkey,len(L2)):
                l.append(L2[i])
            res1.append((None,l))
      
      
        lastkey=0  
        for key in key1 :
            l = []
            for i in xrange(lastkey,key):
                l.append(L1[i])
            res2.append((L1[key],l))
            lastkey=key+1
            
        if lastkey < len(L1) :
            l = []
            for i in xrange(lastkey,len(L1)):
                l.append(L1[i])
            res2.append((None,l))
            
        #print res2,res1
        return res2,res1
        
class AlignHISVo (AlignHIS):
    def _init_alignement(self,L1,L2,texte1,texte2,lt1):
        """ Transformation en un alphabet ordonné """
        Lkey1 = []
        Lkey2 = []
        dicoKey = {}
        #création des listes de hash
        num = 0
        for bloc in L1:
            cle = hash(texte1[bloc[0]:bloc[1]])
            longueur = bloc[1] - bloc[0]
            
            if not dicoKey.has_key(cle):
                dicoKey[cle] = num
                numero = num
                num += 1
            else:
                numero = dicoKey[cle]
            Lkey1.append((numero, longueur, cle))
            
        j = 0            
        for bloc in L2:
            cle = hash(texte2[bloc[0]-lt1:bloc[1]-lt1])
            longueur = bloc[1] - bloc[0]
            Lkey2.append((dicoKey[cle],j,longueur, cle))
            j += 1
            
        return Lkey1, Lkey2, dicoKey
     
    def _lis(self,Lkey1, Lkey2, dicoKey):   
        L = liste_vo()
        node = {}
        for i in xrange(len(Lkey2)):
            car = Lkey2[i]
            #print car,L.liste
            pos = L.prev(car)
            if pos is not None:
                s = L.liste[pos]
            else: s = None
            
            pos = L.next(s)
            if pos is not None:
                t = L.liste[pos]
            else: t = None
            
            if t is not None:
                L.delete(pos)
            L.insert(pos, car)
            if s is None: val = None
            else: val = s
            node[car] = (car, val)
        #print L.liste
        #print node
        
        maxi = 0
        for car in node.iterkeys():
            maxi = max(maxi, car)
        liste = []
        car = maxi
        while car is not None:
            liste.append(car)
            car2, car3 = node[car]
            assert car2 == car
            car = car3
        return liste
            
    def _his(self,Lkey1, Lkey2, dicoKey):   
        L = liste_vo()
        node = {}
        for i in xrange(len(Lkey2)):
            car = Lkey2[i]
            longueur = car[2]
            #print car,L.liste
            pos = L.prev(car)
            if pos is not None:
                s = L.liste[pos]
                v = s[2]
            else: s = None ; v = 0
            
            pos = L.next(s)
            if pos is not None:
                t = L.liste[pos]
                w = t[2]
            else: t = None ; w = 0
            
            while t is not None:
                if v + longueur  < w:
                    break
                L.delete(pos)
                pos = L.next(t)
                if pos is not None:
                    t = L.liste[pos]
                    w = t[2]
                else: t = None ; w = 0
                
            if t is None or car[0] < t:
                car = car[0],car[1] , car[2] + v, car[3]                
                L.insert(pos, car)
                if s is None: val = None
                else: val = s
                node[car] = (car, val)
        #print L.liste
        #print node
        
        maxi = 0
        for car in node.iterkeys():
            maxi = max(maxi, car)
        liste = []
        car = maxi
        while car is not None:
            liste.append(car)
            car2, car3 = node[car]
            assert car2 == car
            car = car3
        return liste 
        
    def alignement(self,L1,L2,texte1,texte2,lt1):
        """ Alignement LIS entre les 2 séquences 
        pre: isinstance(L1,list) and isinstance(L2,list) and isinstance(texte1,str) and isinstance(texte2,str)
        post: (len(__return__[0])==len(__return__[1])) or (len(__return__[0])==len(__return__[1])+1) or \
              (len(__return__[0])+1==len(__return__[1]))
        """
        Lkey1, Lkey2, dicoKey = self._init_alignement(L1,L2,texte1,texte2,lt1)
        lcis = self._his(Lkey1, Lkey2, dicoKey)
        #print lcis, len(Lkey1), len(Lkey2)

        key1=[]
        key2=[]
        for i in xrange(len(lcis)) :
            key2.append(lcis[i][1])
            key1.append(lcis[i][0])

        key1.sort()
        key2.sort()
        #on recrée la liste des bloc correspondants
        res1=[]
        res2=[]

        lastkey=0
        for key in key2 :
            l = []
            for i in xrange(lastkey,key):
                l.append(L2[i])
            res1.append((L2[key],l))
            lastkey = key+1
        if lastkey < len(L2) :
            l = []
            for i in xrange(lastkey,len(L2)):
                l.append(L2[i])
            res1.append((None,l))
      
      
        lastkey=0  
        for key in key1 :
            l = []
            for i in xrange(lastkey,key):
                l.append(L1[i])
            res2.append((L1[key],l))
            lastkey=key+1
            
        if lastkey < len(L1) :
            l = []
            for i in xrange(lastkey,len(L1)):
                l.append(L1[i])
            res2.append((None,l))
            
        #print res2,res1
        return res2,res1

class liste_vo(object):
    def __init__(self):
        self.liste = []
    def prev(self, car):
        if len(self.liste) == 0 or car == None:
            return None
        else:
            pos = bisect.bisect_left(self.liste, car) - 1 
            return pos
    def next(self, car):
        if len(self.liste) == 0 or car == None:
            return None
        else:
            pos = bisect.bisect_right(self.liste, car)
            if pos == len(self.liste): 
                return None
            else: return pos
    def delete(self, pos):
        assert pos < len(self.liste)
        del self.liste[pos]
    def insert(self, pos,car ):
        if len(self.liste) > 0:
            assert pos <= len(self.liste)
            #assert self.liste[pos-1] <= car <= self.liste[pos], (self.liste[pos-1] , car , self.liste[pos])
        else: pos = 0
        if  pos == None: self.liste.append(car)
        else: self.liste.insert(pos, car)
        #assert self.liste[pos-1] <= car <= self.liste[pos], (self.liste[pos-1] , car , self.liste[pos])
        
class Node:
    def __init__(self, key):
        self.key = key
        self.left = self.right = None

    def equals(self, node):
        return self.key == node.key

class SplayTree:
    def __init__(self):
        self.root = None
        self.header = Node(None) #For splay()

    def insert(self, key):
        if (self.root == None):
            self.root = Node(key)
            return

        self.splay(key)
        if self.root.key == key:
            # If the key is already there in the tree, don't do anything.
            return

        n = Node(key)
        if key < self.root.key:
            n.left = self.root.left
            n.right = self.root
            self.root.left = None
        else:
            n.right = self.root.right
            n.left = self.root
            self.root.right = None
        self.root = n

    def remove(self, key):
        self.splay(key)
        if key != self.root.key:
            raise 'key not found in tree'

        # Now delete the root.
        if self.root.left== None:
            self.root = self.root.right
        else:
            x = self.root.right
            self.root = self.root.left
            self.splay(key)
            self.root.right = x

    def findMin(self):
        if self.root == None:
            return None
        x = self.root
        while x.left != None:
            x = x.left
        self.splay(x.key)
        return x.key

    def findMax(self):
        if self.root == None:
            return None
        x = self.root
        while (x.right != None):
            x = x.right
        self.splay(x.key)
        return x.key

    def find(self, key):
        if self.root == None:
            return None
        self.splay(key)
        if self.root.key != key:
            return None
        return self.root.key

    def isEmpty(self):
        return self.root == None
    
    def splay(self, key):
        l = r = self.header
        t = self.root
        self.header.left = self.header.right = None
        while True:
            if key < t.key:
                if t.left == None:
                    break
                if key < t.left.key:
                    y = t.left
                    t.left = y.right
                    y.right = t
                    t = y
                    if t.left == None:
                        break
                r.left = t
                r = t
                t = t.left
            elif key > t.key:
                if t.right == None:
                    break
                if key > t.right.key:
                    y = t.right
                    t.right = y.left
                    y.left = t
                    t = y
                    if t.right == None:
                        break
                l.right = t
                l = t
                t = t.right
            else:
                break
        l.right = t.left
        r.left = t.right
        t.left = self.header.right
        t.right = self.header.left
        self.root = t

        
class AlignProgDyn (Alignement):

    def alignement(self,L1,L2,texte1,texte2,lt1):
        """ Alignement par programmation dynamique entre les 2 séquences
        pre: isinstance(L1,list) and isinstance(L2,list) and isinstance(texte1,str) and isinstance(texte2,str)
        post: (len(__return__[0])==len(__return__[1])) or (len(__return__[0])==len(__return__[1])+1) or \
              (len(__return__[0])+1==len(__return__[1]))
        """

        logging.log(10, "debut _appelProgDyn")
        LH1 = [] ; LH2 = []
        for bloc in L1:
            cle = hash(texte1[bloc[0]:bloc[1]])
       #     print 'hash : ', cle, ' texte : ',texte1[bloc[0]:bloc[1]]
            LH1.append((cle, bloc[0], bloc[1]))
        logging.log(10, 'init LH1 done')
        #print 'taille LH1 : ', len(LH1)
        for bloc in L2:
            cle = hash(texte2[bloc[0]-lt1:bloc[1]-lt1])
        #    print 'hash : ', cle, ' texte : ',texte2[bloc[0]-lt1:bloc[1]-lt1]
            LH2.append((cle, bloc[0], bloc[1]))
        logging.log(10, 'init LH2 done')
        #print 'taille LH2 : ', len(LH2)


        range_n = xrange(len(LH1))
        range_m = xrange(len(LH2))

        nb1 = 0
        nb2 = 0

        # Création de la liste des caractères
        cars = {}
        for i in xrange(len(L1)) :
            if not(cars.has_key(LH1[i][0])) :
                cars[LH1[i][0]] = []
        #print "cars : ",cars
        AIP = []
        AP = {}
        for i in range_n :
            for j in range_m :
                # on est sur un appariement ou on est à la fin du texte, dans ce dernier cas on ajoute l'appariement d'office.
                if LH1[i][0]==LH2[j][0] or (i==len(LH1)-1 and j==len(LH2)-1)  :
               #     print "i : ", i
               #     print "\tj : ", j
               #     if i==len(LH1)-1 and j==len(LH2)-1 :
               #         nb1 = i
               #         nb2 = j
               #     else :
                    nb1 = i-1
                    nb2 = j-1

                    del AIP[:]

                    for c in cars :
                        k = None
                        l = None
                        cout_c = None
                        if len(cars[c])!=0 or c == LH1[i][0] :
                            k_l, k,l = self.lookup_max_kl(cars[c],nb1,nb2)
                        #    print "\t\tcars[",c,"] : ", cars[c]," nb1 : ",nb1," nb2 : ",nb2
                            # on a pas de prédécesseur.
                            if k_l == None and k == None and l == None :
                                # soit le caractère courant est le caractère que l'on étudie
                                # on doit donc l'ajouter car c'est un des premiers appariement du texte
                                if  c == LH1[i][0] :
                                #    print "\t\tPas de prédecesseur."
                                #    cout_c = self.calcul_breche(0, 0, LH1[i][1], LH2[j][1]-lt1)
                                    # on calcule la breche par rapport au début du texte
                                    cout_c = self.calcul_breche2(LH1[0:i-1], LH2[0:j-1])
                                    k = i
                                    l = j
                                # Soit ce caractère n'est pas présent avant, on ne l'ajoute pas à la liste.
                                else : 
                                    continue
                            # on a un prédecesseur
                            else :
                            #    print "\t\tPrédecesseur : k : ",k," l : ",l," k_l : ",k_l
                            #    cout_c = self.calcul_breche(LH1[k][2], LH2[l][2]-lt1, LH1[i][1], LH2[j][1]-lt1) + AP[(k,l)][0]
                                cout_c = self.calcul_breche2(LH1[k+1:i-1], LH2[l+1:j-1]) + AP[(k,l)][0]
                            bisect.insort_left(AIP,(cout_c,k,l))
                            #print "\t\tAIP[(",i,",",j,")] : ", AIP
                    cout_c,k,l = AIP[0]
                    AP[(i,j)] = (cout_c,(k,l))
                    #print "\tAP : ", AP
                    bisect.insort_left(cars[LH1[i][0]], (i+j,i,j))
                    #print "\tcars i : ",i," j : ",j," : ",cars,"\n"
                # Fin si
            # Fin pour
        # Fin pour

        # Récursion pour le cout minimal
        index = (len(LH1)-1,len(LH2)-1)

        s1 = []
        s2 = []
       # print "Construction des liste retournées"
        moving = True
        while moving:
           # print "LH1[",index[0],"] : ",LH1[index[0]][0], "LH2[",index[1],"] : ",LH2[index[1]][0]
            # si on est pas à la fin du texte ou que les deux blocs courant sont égaux
            # permet de prendre en compte le dernier appariement que l'on a ajouté d'office, seulement si c'est un vrai appariement
            if index != (len(LH1)-1,len(LH2)-1) or LH1[index[0]][0] == LH2[index[1]][0] :
                deplacement1 = []
                deplacement2 = []
                range1 = 0
                range2 = 0
                # on construit les range pour les déplacements.
                if AP[index][1] != index :
                    range1 = xrange(AP[index][1][0]+1,index[0])
                    range2 = xrange(AP[index][1][1]+1,index[1])
                else : # blocs au début des textes
                    range1 = xrange(0,index[0])
                    range2 = xrange(0,index[1])
                for bloc in range1 :
                    deplacement1.append(L1[bloc])
                for bloc in range2 :
                    deplacement2.append(L2[bloc])
                s1.append((L1[index[0]], deplacement1))
                s2.append((L2[index[1]], deplacement2))
            #    print 's1 : ',s1
            #    print 's1 : ',s2
            if AP[index][1] != index :
                index = AP[index][1]
            else :
                moving = False
        #print "s1 : ", s1
        #print "s2 : ", s2
        s1.reverse()
        s2.reverse()
        logging.log(10,"Fin _appelProgDyn")
        return s1,s2

    def lookup_max_kl(self, liste_couples_anterieurs, nb1, nb2):
        """ Renvoie le premier couple de valeur compris dans liste_couples_anterieurs tel que leurs composantes soient strictement inférieures à nb1 et nb2
        @type liste_couples_anterieurs: list
        @param liste_couples_anterieurs : liste de coordonnées
        @type nb1: number
        @param nb1: valeur minimum de la premiere composante du couple étudié
        @type nb2: number
        @param nb2: valeur minimum de la deuxieme composante du couple étudié
        @rtype : list
        @return : une liste comprenant la somme des composantes du couple de valeur suivis du couple de valeur ou trois fois None si on a pas trouvé de couple strictement inférieur à nb1 et nb2
        """
        k_l = None
        k = None
        l = None
        found = False
        for i in xrange(len(liste_couples_anterieurs),0,-1):
            k_l, k,l = liste_couples_anterieurs[i-1]
            if k <= nb1 and l <= nb2:
                found = True
                break
        # on avait des couples antérieurs, mais aucun n'est placé strictement avant (nb1,nb2)
        if found == False :
            k_l = None
            k = None
            l = None
        return (k_l, k,l)

    def calcul_breche(self, k,l,i,j):
        """Calcule la brèche entre deux blocs, se calcule basiquement en faisant i-k+j-l.
        @type number
        @param k:Coordonée sur le premier texte du premier bloc
        @type number
        @param l:Coordonée sur le deuxième texte du premier bloc
        @type number
        @param i:Coordonée sur le premier texte du deuxième bloc
        @type number
        @param j:Coordonée sur le deuxième texte du deuxième bloc
		@rtype : number
		@return La valeur de la brèche
        """
       # print "calcul de brèche : k , l , i , j : ",k," ",l," ",i," ",j
        breche = 0
        if k<=i and l<=j:
            breche = i-k+j-l
        elif k>i and l>j :
            breche = k-i+l-j
        return breche
        
    def calcul_breche2(self, l1, l2):
        """Calcule la brèche entre deux blocs, 
           on somme la taille de chaque bloc de l1
           on y ajoute ensuite la somme de la taille de chaque bloc de l2
        @type list
        @param l1: Liste de blocs de la forme (caractère, indice de début, indice de fin)
        @type list
        @param l2: Liste de blocs de la forme (caractère, indice de début, indice de fin)
        @rtype : number
		@return La valeur de la brèche
        """
        breche = 0
        for i in range(len(l1)) :
            breche += l1[i][2] - l1[i][1]
        for j in range(len(l2)) :
            breche += l2[j][2] - l2[j][1]
        return breche
        
class AlignProgDyn2 (AlignProgDyn):

    def alignement(self,L1,L2,texte1,texte2,lt1):
        """ Alignement par programmation dynamique entre les 2 séquences
        pre: isinstance(L1,list) and isinstance(L2,list) and isinstance(texte1,str) and isinstance(texte2,str)
        post: (len(__return__[0])==len(__return__[1])) or (len(__return__[0])==len(__return__[1])+1) or \
              (len(__return__[0])+1==len(__return__[1]))
        """

        logging.log(10, "debut _appelProgDyn")
        LH1 = [] ; LH2 = []
        for bloc in L1:
            cle = hash(texte1[bloc[0]:bloc[1]])
       #     print 'hash : ', cle, ' texte : ',texte1[bloc[0]:bloc[1]]
            LH1.append((cle, bloc[0], bloc[1]))
        logging.log(10, 'init LH1 done')
        #print 'taille LH1 : ', len(LH1)
        for bloc in L2:
            cle = hash(texte2[bloc[0]-lt1:bloc[1]-lt1])
        #    print 'hash : ', cle, ' texte : ',texte2[bloc[0]-lt1:bloc[1]-lt1]
            LH2.append((cle, bloc[0], bloc[1]))
        logging.log(10, 'init LH2 done')
        #print 'taille LH2 : ', len(LH2)


        range_n = xrange(len(LH1))
        range_m = xrange(len(LH2))

        nb1 = 0
        nb2 = 0

        # Création de la liste des caractères
        cars = {}
        for i in xrange(len(L1)) :
            if not(cars.has_key(LH1[i][0])) :
                cars[LH1[i][0]] = []
        #print "cars : ",cars
        AIP = []
        AP = {}
        for i in range_n :
            for j in range_m :
                if LH1[i][0]==LH2[j][0] or (i==len(LH1)-1 and j==len(LH2)-1)  :
                    if i==len(LH1)-1 and j==len(LH2)-1 :
                        nb1 = i
                        nb2 = j
                    else :
                        nb1 = i-1
                        nb2 = j-1

                    del AIP[:]

                    for c in cars :
                        k = None
                        l = None
                        min_cout = None
                        cout_c = None
                        if len(cars[c])!=0 or c == LH1[i][0] :
                            if cars[c] != [] :
                                min_cout, k,l = cars[c][0]
                        #    print "\t\tcars[",c,"] : ", cars[c]," nb1 : ",nb1," nb2 : ",nb2
                            if min_cout == None and k == None and l == None : # pas de prédecesseurs
                                if  c == LH1[i][0] :
                                #    print "\t\tPas de prédecesseur."
                                    cout_c = self.calcul_breche2(LH1[0:i-1], LH2[0:j-1])
                                    #cout_c = self.calcul_breche2(0, 0, LH1[i][1], LH2[j][1]-lt1)
                                    k = i
                                    l = j
                                else : # ce caractère n'est pas présent avant, on ne l'ajoute pas à la liste.
                                    continue
                            else :
                            #    print "\t\tPrédecesseur : k : ",k," l : ",l," k_l : ",k_l
                                cout_c = self.calcul_breche2(LH1[k+1:i-1], LH2[l+1:j-1]) + AP[(k,l)][0]
                                #cout_c = self.calcul_breche2(LH1[k][2], LH2[l][2]-lt1, LH1[i][1], LH2[j][1]-lt1) + AP[(k,l)][0]
                            bisect.insort_left(AIP,(cout_c,k,l))
                        #    print "\t\tAIP[(",i,",",j,")] : ", AIP
                    cout_c,k,l = AIP[0]
                    AP[(i,j)] = (cout_c,(k,l))
                #    print "\tAP : ", AP
                    bisect.insort_left(cars[LH1[i][0]], (cout_c,i,j))
                #    print "\tcars i : ",i," j : ",j," : ",cars,"\n"
                # Fin si
            # Fin pour
        # Fin pour

        # Récursion pour le cout minimal
        index = (len(LH1)-1,len(LH2)-1)

        s1 = []
        s2 = []
        #print "Construction des liste retournées"
        moving = True
        while moving:
        #    print "LH1[",index[0],"] : ",LH1[index[0]][0], "LH2[",index[1],"] : ",LH2[index[1]][0]
            if index != (len(LH1)-1,len(LH2)-1) or LH1[index[0]][0] == LH2[index[1]][0] :
                deplacement1 = []
                deplacement2 = []
                range1 = 0
                range2 = 0
                if AP[index][1] != index :
                    range1 = xrange(AP[index][1][0]+1,index[0])
                    range2 = xrange(AP[index][1][1]+1,index[1])
                else :
                    range1 = xrange(0,index[0])
                    range2 = xrange(0,index[1])
                for bloc in range1 :
                    deplacement1.append(L1[bloc])
                for bloc in range2 :
                    deplacement2.append(L2[bloc])
                s1.append((L1[index[0]], deplacement1))
                s2.append((L2[index[1]], deplacement2))
            #    print 's1 : ',s1
            #    print 's1 : ',s2
            if AP[index][1] != index :
                index = AP[index][1]
            else :
                moving = False
        #print "s1 : ", s1
        #print "s2 : ", s2
        s1.reverse()
        s2.reverse()
        logging.log(10,"Fin _appelProgDyn")
        return s1,s2

import unittest, random
        
class TestCase(unittest.TestCase):
    def setUp(self):
        self.liste = liste_vo()
        
    def testInsert(self):
        self.liste.insert(0, 5)
        
        nb = 7 
        pos = self.liste.next(nb)
        self.liste.insert(pos, nb)
        
        nb = 8
        pos = self.liste.next(nb)
        self.liste.insert(pos, nb)
        
        taille = 20
        random.seed(10)
        for id in xrange(taille):
            nb = random.randint(1,10)
            if nb % 2 == 0:
                pos = self.liste.next(nb)
            else: pos = self.liste.prev(nb)
            
            self.liste.insert(pos, nb)
            
        print self.liste.liste
        for i in xrange(len(self.liste.liste)-2):
            assert self.liste.liste[i] <= self.liste.liste[i+1]
        
    def test2(self):
        a = AlignHISVo()
        L1 = [()]
        
class TestCase__(unittest.TestCase):
    def setUp(self):
        self.keys = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        self.t = SplayTree()
        for key in self.keys:
            self.t.insert(key)
        
    def testInsert(self):
        for key in self.keys:
            self.assertEquals(key, self.t.find(key))

    def testRemove(self):
        for key in self.keys:
            self.t.remove(key)
            self.assertEquals(self.t.find(key), None)

    def testLargeInserts(self):
        t = SplayTree()
        nums = 40#000
        gap = 307
        i = gap
        while i != 0:
            t.insert(i)
            i = (i + gap) % nums

    def testIsEmpty(self):
        self.assertFalse(self.t.isEmpty())
        t = SplayTree()
        self.assertTrue(t.isEmpty())

    def testMinMax(self):
        self.assertEquals(self.t.findMin(), 0)
        self.assertEquals(self.t.findMax(), 9)

        
    def testFind(self):
        print self.t.find(5)
        
if __name__ == "__main__":
    unittest.main()