pastebin - collaborative debugging

# -*- encoding: latin1 -*-
#by zell_ff8

class _Nodo(object):
    def __init__(self,x=None): self.dato,self.prox=x,None
    def __str__(self):    return str(self.dato)
    def __repr__(self):   return "_Nodo(%s)"%self.dato

#-------------------------------------------------------------------------------------
# class Lista
#-------------------------------------------------------------------------------------
class Lista(object):
    """Lista de nodos enlazados. Tiene todas las funciones de 'list' pero
implementadas para este tipo de lista

Atributos:
    self.prim => Referencia al primer nodo
    self.len  => Cantidad de nodos
"""
    #Basicas
    def __init__(self,*x):
        "Inicializa Lista"
        self.prim=None
        self.len=0
        self.extend(x)

    def __len__(self):
        "x.__len__() <==> x.len"
        return self.len

    def __repr__(self):
        "x.__repr__() <==> repr(x)"
        if not self.len: return "Lista()"
        s="Lista("
        p=self.prim
        while p:
            s+=repr(p.dato)+","
            p=p.prox
        return s[:-1]+")"

    def __str__(self):
        "x.__str__() <==> str(x)"
        if not self.len: return "[] -Lista-"
        s="["
        p=self.prim
        while p:
            s+=str(p.dato)+", "
            p=p.prox
        return s[:-2]+"] -Lista-"

    #Iteradores
    def __iter__(self):
        "x.__iter__() <==> iter(x)"
        p=self.prim
        while p:
            yield p.dato
            p=p.prox
        raise StopIteration

    def __reversed__(self):
        """x.__reversed__() <==> x._invertir().__iter__()"""
        return self._invertir().__iter__()

    #get/set/del item/slice
    def __getitem__(self,i):
        "x.__getitem__(i) <==> x[i]"
        if i<0 and abs(i)<=self.len: i=self.len+i
        if not 0<=i<self.len:
            raise IndexError,"index out of range"
        p=self.prim
        c=0
        while c<i:
            p=p.prox
            c+=1
        return p.dato

    def __getslice__(self,i,j):
        "x.__getslice__(i, j) <==> x[i:j]"
        c=0
        s=self._null()()

        if i<0: i=0
        if j>self.len: j=self.len
        p=self.prim
        while c<j:
            if not p:
                break
            if c>=i:
                s.append(p.dato)
            p=p.prox
            c+=1
        return s

    def __delitem__(self,i):
        "x.__delitem__(i) <==> del x[i]"
        if i<0 and abs(i)<=self.len: i=self.len+i
        if not 0<=i<self.len:
            raise IndexError,"index out of range"
        self.len-=1
        if not i:
            self.prim=self.prim.prox
            return
        c=1
        p=self.prim
        while c<i:
            c+=1
            p=p.prox
        p.prox=p.prox.prox

    def __delslice__(self,i,j):
        "x.__delslice__(i, j) <==> del x[i:j]"
        if i<0:i=0
        if j>=self.len: j=self.len
        if i>j or i==j: return
        c=0
        p=self.prim
        while c<j:
            c+=1
            if c==i:
                start=p
            if c==j:
                end=p
                break
            p=p.prox
        if not i:
            self.prim=end.prox
        else:
            start.prox=end.prox
        self.len-=j-i

    def __setitem__(self,i,y):
        "x.__setitem__(i, y) <==> x[i]=y"
        if i<0 and abs(i)<=self.len: i=self.len+i
        if not 0<=i<self.len:
            raise IndexError,"index out of range"
        p=self.prim
        c=0
        while c<i:
            p=p.prox
            c+=1
        p.dato=y

    def __setslice__(self,i,j,y):
        "x.__setslice__(i,j,y) <==> x[i:j]=y"
        if i<0:i=0
        if j<i:j=i
        if j>self.len:j=self.len
        c=0
        p=self.prim
        self.__delslice__(i,j)
        while p.prox:
            if c+1==i:
                break
            c+=1
            p=p.prox
        end=p.prox

        for item in y:
            if not self.prim or not i:
                self.prim=_Nodo(item)
                p=self.prim
                i=True
                continue
            p.prox=_Nodo(item)
            p=p.prox
        p.prox=end
        self.len+=len(y)


    #Operadores
    def __add__(self,y):
        """x.__add__(y) <==> x+y
Devuelve lista de igual tipo con 'x', 'y' concatenadas"""
        if not isinstance(y,(Lista,list,tuple)):
            raise TypeError,"can only concatenate iterable type to Lista"
        s=self[:] #crea copia
        for i in y:
            s.append(i)
        return s

    def __iadd__(self,y):
        """x.__add__(y) <==> x+=y
<Modifica x>"""
        if not isinstance(y,(Lista,list,tuple)):
            raise TypeError,"can only concatenate iterable type to Lista"

        if self is y: y=y[:] #fix de x+=x
        for i in y:
            self.append(i)
        return self

    def __mul__(self,i):
        """x.__mul__(y) <==> x*i
Devuelve lista de igual tipo con 'x' concatenada 'i' veces."""
        if type(i)!=int:
            raise TypeError,"can't multiply sequence by non-int"
        s=self._null()()

        if i<=0:
            return s
        for x in xrange(i):
            s.extend(self)
        return s

    def __imul__(self,i):
        """x.__imul__(i) <==> x*=i
<Modifica x>"""
        if type(i)!=int:
            raise TypeError,"can't multiply sequence by non-int"
        s=self[:] #crea una copia
        for x in xrange(i-1):
            self.extend(s)
        return self

    def __rmul__(self,n):
        "x.__rmul__(n) <==> x.__mul__(n)"
        return self.__mul__(n)

    def __eq__(self,y):
        """x.__eq__(y) <==> x==y
Lista se compara con cualquier iterable. Si x=Lista(...),
x.__eq__(y)==True cuando 'y' es:

    list(x), tuple(x), ListaO(*x), Lista(*x)
"""
        if len(self)!=len(y):
            return False

        p1=iter(self)
        p2=iter(y)
        while 1:
            try:
                if p1.next()!=p2.next():
                    return False
            except StopIteration:
                return True

    def __ne__(self,y):
        "x.__ne__(y) <==> not x==y"
        return not self.__eq__(y)

    def __contains__(self,y):
        "x.__contains__(y) <==> y in x"
        for dato in self:
            if dato==y:
                return True
        return False

    def __idiv__(self,i): #debug) x/=list == list(x)
        "Usado para modificar tipo"
        if i in [list,tuple]:return i(self)
        return i(*self)

    #Internas
    def _invertir(self):
        "Devuelve una nueva 'Lista' en orden inverso."
        revez=Lista()
        p=self.prim
        while p:
            revez.insert(0,p.dato)
            p=p.prox
        return revez

    def _null(self):
        "Devuelve la clase."
        return Lista

    #Métodos
    def append(self,x):
        "Agrega 'x' al final de la Lista."
        self.len+=1
        if self.len==1:
            self.prim=_Nodo(x)
        else:
            p=self.prim
            while p.prox:
                p=p.prox
            p.prox=_Nodo(x)
        return

    def count(self,x):
        "Devuelve cantidad de concurrencias de 'x' en la Lista."
        c=0
        p=self.prim
        while p:
            if p.dato==x:
                c+=1
            p=p.prox
        return c

    def extend(self,l):
        "Agrega cada elemento de 'l' al final ('l' es un iterable)"
        #for item in l: self.append(item) """ muchas operacines
        if not len(l):
            return

        #Caso lista vacia
        if not self.prim:
            self.prim=_Nodo(l[0])
            s=1
        else:
            s=0

        #se ubica al final
        p=self.prim
        while p.prox:
            p=p.prox

        #agrega
        for i in xrange(s,len(l)):
            p.prox=_Nodo(l[i])
            p=p.prox

        self.len+=len(l)

    def find(self,x,start=0,stop=False):
        """Devuelve posición de la primera aparición de 'x' en la Lista.
Devuelve -1 si no se encuentra."""
        try:
            return self.index(x,start,stop)
        except ValueError:
            return -1

    def index(self,x,start=0,stop=False):
        """Devuelve posición de la primera aparición de 'x' en la Lista.
Levanta ValueError si no se encuentra."""
        if not stop:
            stop=self.len
        c=0
        p=self.prim
        start=self._adjustIndex(start)
        stop=self._adjustIndex(stop)
        while p:
            if c>=stop:
                break
            if c>=start and p.dato==x:
                return c
            c+=1
            p=p.prox
        raise ValueError,"x.index(x,start,stop): x not in Lista[%s:%s]"%(start,stop)

    def insert(self,i,x):
        "Inserta 'x' antes de la posición 'i'."
        n=_Nodo(x)
        c=0
        self.len+=1

        #Primer elemento
        if i<=0:
            n.prox=self.prim
            self.prim=n
            return

        p=self.prim
        while p:
            if c+1==i or not p.prox:
                break
            c+=1
            p=p.prox
        n.prox=p.prox
        p.prox=n

    def pop(self,i=None):
        """Devuelve el elemento en la posición 'i' y lo elimina de la lista.
Por defecto toma el último elemento.
x.pop()  -> extrae el último
x.pop(0) -> extra el primero"""
        if i==None:
            i=self.len-1
        else:
            i=self._adjustIndex(i)
            if not 0<=i<self.len:
                raise IndexError,"pop index out of range"
        self.len-=1
        p=self.prim
        if not i:
            self.prim=p.prox
            return p.dato
        c=1
        while c<i:
            c+=1
            p=p.prox
        s=p.prox.dato
        p.prox=p.prox.prox
        return s

    def remove(self,x):
        """Elimina la primera aparicion de 'x' en la Lista.
Levanta ValueError si 'x' no se encuentra."""
        if self.prim:
            if self.prim.dato==x:
                self.prim=self.prim.prox
                self.len-=1
                return

            p=self.prim
            while p.prox:
                if p.prox.dato==x:
                    p.prox=p.prox.prox
                    self.len-=1
                    return
                p=p.prox
        raise ValueError,"x.remove(y): y not in x"

    def reverse(self):
        """Invierte la Lista."""
        self.prim=self._invertir().prim

    def sort(self):
        """Ordena la Lista (en realidad crea una ListaO con los
mismos valores y la transforma en Lista)

        x.sort() <==> x.prim=Lista(*ListaO(*x)).prim"""
        self.prim=Lista(*ListaO(*self)).prim


#-------------------------------------------------------------------------------------
# class ListaO
#-------------------------------------------------------------------------------------
class ListaO(Lista):
    """ListaO es una Lista que siempre está ordenada. El criterio de
orden está en el atributo self.func=f

Siendo f una función que recibe 'a' y 'b', y que devuelve True cuando esta
permitido insertar 'a' antes que 'b'.

Por defecto:
        self.func=lambda a,b: a<b

Atributos:
    self.prim => Referencia al primer nodo
    self.len  => Cantidad de nodos
    self.func => Criterio de orden
"""
    #Basicas
    def __init__(self,*x):
        "Inicializa ListaO"
        self.func=lambda a,b:a<b
        Lista.__init__(self,*x)

    def __repr__(self):
        "x.__repr__() <==> repr(x)"
        if not self.len: return "ListaO()"
        s="ListaO("
        p=self.prim
        while p:
            s+=repr(p.dato)+","
            p=p.prox
        return s[:-1]+")"

    def __str__(self):
        "x.__str__() <==> str(x)"
        if not self.len: return "[] -ListaO-"
        s="["
        p=self.prim
        while p:
            s+=str(p.dato)+", "
            p=p.prox
        return s[:-2]+"] -ListaO-"

    #Internas
    def _null(self):
        "Devuelve la clase."
        return ListaO

    #get/set/del item/slice
    def __setitem__(self,i,y):
        """Para mantener el orden, esta función realiza:
self.__delitem__(i)
self.insert(y)"""
        self.__delitem__(i)
        self.insert(y)

    def __setslice__(self,i,j,y):
        """Para mantener el orden, esta función realiza:
self.__delslice__(i,j)
self.extend(y)"""
        self.__delslice__(i,j)
        self.extend(y)

    #Métodos
    def append(self,x):
        "Sin sentido en ListaO. Llama a self.insert(x) para mantener el orden."
        self.insert(x)

    def extend(self,l):
        "Agrega cada elemento de 'l' de manera ordenada ('l' es un iterable)"
        for item in l: self.insert(item)

    def insert(self,x):
        "Inserta 'x' en la ListaO (en orden según self.func)"
        self.len+=1
        n=_Nodo(x)
        if self.len==1:
            self.prim=n
            return

        p=self.prim
        if self.func(x,p.dato):
            n.prox=p
            self.prim=n
            return

        while p.prox:
            if self.func(x,p.prox.dato):
                break
            p=p.prox

        n.prox=p.prox
        p.prox=n

    def reverse(self):
        """Invierte la ListaO.
Para mantener el ordenamiento, cambia el criterio de ordenamiento a:
    x=self.func
    self.func=lambda a,b: not x(a,b)
...que puede no ser aplicable en todos los casos."""
        Lista.reverse(self)
        x=self.func
        self.func=lambda a,b: not x(a,b)

    def sort(self):
        "Redundante. ListaO siempre está ordenada :)"
        pass

#------------------------------------------------------------