My Pastes
Public Pastes
Layout Width
Share Pastebin
Guest
Public paste!

Zell_ff8

By: a guest | May 18th, 2009 | Syntax: Python | Size: 13.74 KB | Hits: 59 | Expires: Never
Download | Raw | Embed | Report abuse
Copy text to clipboard
  1. # -*- encoding: latin1 -*-
  2. #by zell_ff8
  3.  
  4. class _Nodo(object):
  5.     def __init__(self,x=None): self.dato,self.prox=x,None
  6.     def __str__(self):    return str(self.dato)
  7.     def __repr__(self):   return "_Nodo(%s)"%self.dato
  8.  
  9. #-------------------------------------------------------------------------------------
  10. # class Lista
  11. #-------------------------------------------------------------------------------------
  12. class Lista(object):
  13.     """Lista de nodos enlazados. Tiene todas las funciones de 'list' pero
  14. implementadas para este tipo de lista
  15.  
  16. Atributos:
  17.    self.prim => Referencia al primer nodo
  18.    self.len  => Cantidad de nodos
  19. """
  20.     #Basicas
  21.     def __init__(self,*x):
  22.         "Inicializa Lista"
  23.         self.prim=None
  24.         self.len=0
  25.         self.extend(x)
  26.  
  27.     def __len__(self):
  28.         "x.__len__() <==> x.len"
  29.         return self.len
  30.  
  31.     def __repr__(self):
  32.         "x.__repr__() <==> repr(x)"
  33.         if not self.len: return "Lista()"
  34.         s="Lista("
  35.         p=self.prim
  36.         while p:
  37.             s+=repr(p.dato)+","
  38.             p=p.prox
  39.         return s[:-1]+")"
  40.  
  41.     def __str__(self):
  42.         "x.__str__() <==> str(x)"
  43.         if not self.len: return "[] -Lista-"
  44.         s="["
  45.         p=self.prim
  46.         while p:
  47.             s+=str(p.dato)+", "
  48.             p=p.prox
  49.         return s[:-2]+"] -Lista-"
  50.  
  51.     #Iteradores
  52.     def __iter__(self):
  53.         "x.__iter__() <==> iter(x)"
  54.         p=self.prim
  55.         while p:
  56.             yield p.dato
  57.             p=p.prox
  58.         raise StopIteration
  59.  
  60.     def __reversed__(self):
  61.         """x.__reversed__() <==> x._invertir().__iter__()"""
  62.         return self._invertir().__iter__()
  63.  
  64.     #get/set/del item/slice
  65.     def __getitem__(self,i):
  66.         "x.__getitem__(i) <==> x[i]"
  67.         if i<0 and abs(i)<=self.len: i=self.len+i
  68.         if not 0<=i<self.len:
  69.             raise IndexError,"index out of range"        
  70.         p=self.prim
  71.         c=0
  72.         while c<i:
  73.             p=p.prox
  74.             c+=1
  75.         return p.dato
  76.  
  77.     def __getslice__(self,i,j):
  78.         "x.__getslice__(i, j) <==> x[i:j]"
  79.         c=0
  80.         s=self._null()()
  81.  
  82.         if i<0: i=0
  83.         if j>self.len: j=self.len
  84.         p=self.prim
  85.         while c<j:
  86.             if not p:
  87.                 break
  88.             if c>=i:
  89.                 s.append(p.dato)
  90.             p=p.prox
  91.             c+=1
  92.         return s
  93.  
  94.     def __delitem__(self,i):
  95.         "x.__delitem__(i) <==> del x[i]"
  96.         if i<0 and abs(i)<=self.len: i=self.len+i
  97.         if not 0<=i<self.len:
  98.             raise IndexError,"index out of range"
  99.         self.len-=1
  100.         if not i:
  101.             self.prim=self.prim.prox
  102.             return
  103.         c=1
  104.         p=self.prim
  105.         while c<i:
  106.             c+=1
  107.             p=p.prox
  108.         p.prox=p.prox.prox
  109.  
  110.     def __delslice__(self,i,j):
  111.         "x.__delslice__(i, j) <==> del x[i:j]"
  112.         if i<0:i=0
  113.         if j>=self.len: j=self.len
  114.         if i>j or i==j: return
  115.         c=0
  116.         p=self.prim
  117.         while c<j:
  118.             c+=1
  119.             if c==i:
  120.                 start=p
  121.             if c==j:
  122.                 end=p
  123.                 break
  124.             p=p.prox
  125.         if not i:
  126.             self.prim=end.prox
  127.         else:
  128.             start.prox=end.prox
  129.         self.len-=j-i
  130.  
  131.     def __setitem__(self,i,y):
  132.         "x.__setitem__(i, y) <==> x[i]=y"
  133.         if i<0 and abs(i)<=self.len: i=self.len+i
  134.         if not 0<=i<self.len:
  135.             raise IndexError,"index out of range"
  136.         p=self.prim
  137.         c=0
  138.         while c<i:
  139.             p=p.prox
  140.             c+=1
  141.         p.dato=y
  142.  
  143.     def __setslice__(self,i,j,y):
  144.         "x.__setslice__(i,j,y) <==> x[i:j]=y"
  145.         if i<0:i=0
  146.         if j<i:j=i
  147.         if j>self.len:j=self.len
  148.         c=0
  149.         p=self.prim
  150.         self.__delslice__(i,j)
  151.         while p.prox:
  152.             if c+1==i:
  153.                 break
  154.             c+=1
  155.             p=p.prox
  156.         end=p.prox
  157.  
  158.         for item in y:
  159.             if not self.prim or not i:
  160.                 self.prim=_Nodo(item)
  161.                 p=self.prim
  162.                 i=True
  163.                 continue
  164.             p.prox=_Nodo(item)
  165.             p=p.prox
  166.         p.prox=end
  167.         self.len+=len(y)
  168.        
  169.  
  170.     #Operadores
  171.     def __add__(self,y):
  172.         """x.__add__(y) <==> x+y
  173. Devuelve lista de igual tipo con 'x', 'y' concatenadas"""
  174.         if not isinstance(y,(Lista,list,tuple)):
  175.             raise TypeError,"can only concatenate iterable type to Lista"
  176.         s=self[:] #crea copia
  177.         for i in y:
  178.             s.append(i)
  179.         return s
  180.  
  181.     def __iadd__(self,y):
  182.         """x.__add__(y) <==> x+=y
  183. <Modifica x>"""
  184.         if not isinstance(y,(Lista,list,tuple)):
  185.             raise TypeError,"can only concatenate iterable type to Lista"
  186.        
  187.         if self is y: y=y[:] #fix de x+=x
  188.         for i in y:
  189.             self.append(i)
  190.         return self
  191.  
  192.     def __mul__(self,i):
  193.         """x.__mul__(y) <==> x*i
  194. Devuelve lista de igual tipo con 'x' concatenada 'i' veces."""
  195.         if type(i)!=int:
  196.             raise TypeError,"can't multiply sequence by non-int"
  197.         s=self._null()()
  198.        
  199.         if i<=0:
  200.             return s
  201.         for x in xrange(i):
  202.             s.extend(self)
  203.         return s
  204.  
  205.     def __imul__(self,i):
  206.         """x.__imul__(i) <==> x*=i
  207. <Modifica x>"""
  208.         if type(i)!=int:
  209.             raise TypeError,"can't multiply sequence by non-int"
  210.         s=self[:] #crea una copia
  211.         for x in xrange(i-1):
  212.             self.extend(s)
  213.         return self
  214.  
  215.     def __rmul__(self,n):
  216.         "x.__rmul__(n) <==> x.__mul__(n)"
  217.         return self.__mul__(n)
  218.  
  219.     def __eq__(self,y):
  220.         """x.__eq__(y) <==> x==y
  221. Lista se compara con cualquier iterable. Si x=Lista(...),
  222. x.__eq__(y)==True cuando 'y' es:
  223.    
  224.    list(x), tuple(x), ListaO(*x), Lista(*x)
  225. """
  226.         if len(self)!=len(y):
  227.             return False
  228.        
  229.         p1=iter(self)
  230.         p2=iter(y)
  231.         while 1:
  232.             try:
  233.                 if p1.next()!=p2.next():
  234.                     return False
  235.             except StopIteration:
  236.                 return True
  237.  
  238.     def __ne__(self,y):
  239.         "x.__ne__(y) <==> not x==y"
  240.         return not self.__eq__(y)
  241.  
  242.     def __contains__(self,y):
  243.         "x.__contains__(y) <==> y in x"
  244.         for dato in self:
  245.             if dato==y:
  246.                 return True
  247.         return False
  248.  
  249.     def __idiv__(self,i): #debug) x/=list == list(x)
  250.         "Usado para modificar tipo"
  251.         if i in [list,tuple]:return i(self)
  252.         return i(*self)
  253.  
  254.     #Internas
  255.     def _invertir(self):
  256.         "Devuelve una nueva 'Lista' en orden inverso."
  257.         revez=Lista()
  258.         p=self.prim
  259.         while p:
  260.             revez.insert(0,p.dato)
  261.             p=p.prox
  262.         return revez
  263.  
  264.     def _null(self):
  265.         "Devuelve la clase."
  266.         return Lista
  267.  
  268.     #Métodos
  269.     def append(self,x):
  270.         "Agrega 'x' al final de la Lista."
  271.         self.len+=1
  272.         if self.len==1:
  273.             self.prim=_Nodo(x)
  274.         else:
  275.             p=self.prim
  276.             while p.prox:
  277.                 p=p.prox
  278.             p.prox=_Nodo(x)
  279.         return
  280.  
  281.     def count(self,x):
  282.         "Devuelve cantidad de concurrencias de 'x' en la Lista."
  283.         c=0
  284.         p=self.prim
  285.         while p:
  286.             if p.dato==x:
  287.                 c+=1
  288.             p=p.prox
  289.         return c
  290.  
  291.     def extend(self,l):
  292.         "Agrega cada elemento de 'l' al final ('l' es un iterable)"
  293.         #for item in l: self.append(item) """ muchas operacines
  294.         if not len(l):
  295.             return
  296.  
  297.         #Caso lista vacia
  298.         if not self.prim:
  299.             self.prim=_Nodo(l[0])
  300.             s=1
  301.         else:
  302.             s=0
  303.  
  304.         #se ubica al final
  305.         p=self.prim
  306.         while p.prox:
  307.             p=p.prox
  308.  
  309.         #agrega
  310.         for i in xrange(s,len(l)):
  311.             p.prox=_Nodo(l[i])
  312.             p=p.prox
  313.  
  314.         self.len+=len(l)
  315.  
  316.     def find(self,x,start=0,stop=False):
  317.         """Devuelve posición de la primera aparición de 'x' en la Lista.
  318. Devuelve -1 si no se encuentra."""
  319.         try:
  320.             return self.index(x,start,stop)
  321.         except ValueError:
  322.             return -1
  323.  
  324.     def index(self,x,start=0,stop=False):
  325.         """Devuelve posición de la primera aparición de 'x' en la Lista.
  326. Levanta ValueError si no se encuentra."""
  327.         if not stop:
  328.             stop=self.len
  329.         c=0
  330.         p=self.prim
  331.         start=self._adjustIndex(start)
  332.         stop=self._adjustIndex(stop)
  333.         while p:
  334.             if c>=stop:
  335.                 break
  336.             if c>=start and p.dato==x:
  337.                 return c
  338.             c+=1
  339.             p=p.prox
  340.         raise ValueError,"x.index(x,start,stop): x not in Lista[%s:%s]"%(start,stop)
  341.  
  342.     def insert(self,i,x):
  343.         "Inserta 'x' antes de la posición 'i'."
  344.         n=_Nodo(x)
  345.         c=0        
  346.         self.len+=1
  347.  
  348.         #Primer elemento
  349.         if i<=0:
  350.             n.prox=self.prim
  351.             self.prim=n
  352.             return
  353.  
  354.         p=self.prim
  355.         while p:
  356.             if c+1==i or not p.prox:
  357.                 break
  358.             c+=1
  359.             p=p.prox
  360.         n.prox=p.prox
  361.         p.prox=n
  362.  
  363.     def pop(self,i=None):
  364.         """Devuelve el elemento en la posición 'i' y lo elimina de la lista.
  365. Por defecto toma el último elemento.
  366. x.pop()  -> extrae el último
  367. x.pop(0) -> extra el primero"""
  368.         if i==None:
  369.             i=self.len-1
  370.         else:
  371.             i=self._adjustIndex(i)
  372.             if not 0<=i<self.len:
  373.                 raise IndexError,"pop index out of range"
  374.         self.len-=1
  375.         p=self.prim
  376.         if not i:
  377.             self.prim=p.prox
  378.             return p.dato
  379.         c=1
  380.         while c<i:
  381.             c+=1
  382.             p=p.prox
  383.         s=p.prox.dato
  384.         p.prox=p.prox.prox
  385.         return s
  386.  
  387.     def remove(self,x):
  388.         """Elimina la primera aparicion de 'x' en la Lista.
  389. Levanta ValueError si 'x' no se encuentra."""
  390.         if self.prim:
  391.             if self.prim.dato==x:
  392.                 self.prim=self.prim.prox
  393.                 self.len-=1
  394.                 return
  395.  
  396.             p=self.prim
  397.             while p.prox:
  398.                 if p.prox.dato==x:
  399.                     p.prox=p.prox.prox
  400.                     self.len-=1
  401.                     return
  402.                 p=p.prox
  403.         raise ValueError,"x.remove(y): y not in x"
  404.  
  405.     def reverse(self):
  406.         """Invierte la Lista."""
  407.         self.prim=self._invertir().prim
  408.  
  409.     def sort(self):
  410.         """Ordena la Lista (en realidad crea una ListaO con los
  411. mismos valores y la transforma en Lista)
  412.  
  413.        x.sort() <==> x.prim=Lista(*ListaO(*x)).prim"""
  414.         self.prim=Lista(*ListaO(*self)).prim
  415.  
  416.  
  417.    
  418.  
  419. #-------------------------------------------------------------------------------------
  420. # class ListaO
  421. #-------------------------------------------------------------------------------------
  422. class ListaO(Lista):
  423.     """ListaO es una Lista que siempre está ordenada. El criterio de
  424. orden está en el atributo self.func=f
  425.  
  426. Siendo f una función que recibe 'a' y 'b', y que devuelve True cuando esta
  427. permitido insertar 'a' antes que 'b'.
  428.  
  429. Por defecto:
  430.        self.func=lambda a,b: a<b
  431.  
  432. Atributos:
  433.    self.prim => Referencia al primer nodo
  434.    self.len  => Cantidad de nodos
  435.    self.func => Criterio de orden
  436. """
  437.     #Basicas
  438.     def __init__(self,*x):
  439.         "Inicializa ListaO"
  440.         self.func=lambda a,b:a<b
  441.         Lista.__init__(self,*x)
  442.  
  443.     def __repr__(self):
  444.         "x.__repr__() <==> repr(x)"
  445.         if not self.len: return "ListaO()"
  446.         s="ListaO("
  447.         p=self.prim
  448.         while p:
  449.             s+=repr(p.dato)+","
  450.             p=p.prox
  451.         return s[:-1]+")"
  452.  
  453.     def __str__(self):
  454.         "x.__str__() <==> str(x)"
  455.         if not self.len: return "[] -ListaO-"
  456.         s="["
  457.         p=self.prim
  458.         while p:
  459.             s+=str(p.dato)+", "
  460.             p=p.prox
  461.         return s[:-2]+"] -ListaO-"
  462.  
  463.     #Internas
  464.     def _null(self):
  465.         "Devuelve la clase."
  466.         return ListaO
  467.  
  468.     #get/set/del item/slice
  469.     def __setitem__(self,i,y):
  470.         """Para mantener el orden, esta función realiza:
  471. self.__delitem__(i)
  472. self.insert(y)"""
  473.         self.__delitem__(i)
  474.         self.insert(y)
  475.  
  476.     def __setslice__(self,i,j,y):
  477.         """Para mantener el orden, esta función realiza:
  478. self.__delslice__(i,j)
  479. self.extend(y)"""
  480.         self.__delslice__(i,j)
  481.         self.extend(y)
  482.  
  483.     #Métodos
  484.     def append(self,x):
  485.         "Sin sentido en ListaO. Llama a self.insert(x) para mantener el orden."
  486.         self.insert(x)
  487.  
  488.     def extend(self,l):
  489.         "Agrega cada elemento de 'l' de manera ordenada ('l' es un iterable)"
  490.         for item in l: self.insert(item)
  491.    
  492.     def insert(self,x):
  493.         "Inserta 'x' en la ListaO (en orden según self.func)"
  494.         self.len+=1
  495.         n=_Nodo(x)
  496.         if self.len==1:
  497.             self.prim=n
  498.             return
  499.  
  500.         p=self.prim
  501.         if self.func(x,p.dato):
  502.             n.prox=p
  503.             self.prim=n
  504.             return
  505.  
  506.         while p.prox:
  507.             if self.func(x,p.prox.dato):
  508.                 break
  509.             p=p.prox
  510.            
  511.         n.prox=p.prox
  512.         p.prox=n
  513.  
  514.     def reverse(self):
  515.         """Invierte la ListaO.
  516. Para mantener el ordenamiento, cambia el criterio de ordenamiento a:
  517.    x=self.func
  518.    self.func=lambda a,b: not x(a,b)
  519. ...que puede no ser aplicable en todos los casos."""
  520.         Lista.reverse(self)
  521.         x=self.func
  522.         self.func=lambda a,b: not x(a,b)
  523.  
  524.     def sort(self):
  525.         "Redundante. ListaO siempre está ordenada :)"
  526.         pass
  527.        
  528. #------------------------------------------------------------
create new paste | create new version of this paste RAW Paste Data