Want more features on Pastebin? Sign Up, it's FREE!
Guest

boris_g

By: a guest on Oct 26th, 2008  |  syntax: Python  |  size: 10.71 KB  |  views: 29  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. ''' Linked list
  2.  
  3. This is a copy of
  4. http://www.koders.com/python/fid6EF9B028CDDCE7D42E690DD3ADD1BB39E7869ED2.aspx
  5. Project site is here: http://code.google.com/p/gsakkis-utils/
  6. The project site state that the license of this code is LGPL
  7. '''
  8.  
  9.  
  10. from itertools import izip
  11.  
  12. __author__ = "George Sakkis <gsakkis@rutgers.edu>"
  13. __all__ = ["LinkedList"]
  14.  
  15.  
  16. class LinkedList(object):
  17.     ''' Linked list class '''
  18.  
  19.     __slots__ = '_start', '_end', '_size'
  20.  
  21.     #------- constructor / destructor ----------------------------------------
  22.  
  23.     def __init__(self,sequence=()):
  24.         self._size = 0
  25.         self._start = self._end = None
  26.         self += sequence
  27.  
  28.     def __del__(self):
  29.         current = self._start
  30.         while current != None:
  31.             # cut the link to the previous node so that this can be released
  32.             current.previous = None
  33.             current = current.next
  34.  
  35.     #------- accesors --------------------------------------------------------
  36.  
  37.     def __len__(self):
  38.         return self._size
  39.  
  40.     def __iter__(self):
  41.         current = self._start
  42.         while current != None:
  43.             yield current.item
  44.             current = current.next
  45.  
  46.     def __getitem__(self,index):
  47.         if not isinstance(index,slice):
  48.             return self._getnode(index).item
  49.         else:  # slice object
  50.             result = LinkedList()
  51.             for i in self._iterslice(index):
  52.                 result.append(i.item)
  53.             return result
  54.  
  55.     def count(self,item):
  56.         counter = 0
  57.         for i in self:
  58.             if i==item: counter +=1
  59.         return counter
  60.  
  61.     def index(self,item):
  62.         counter = 0
  63.         for i in self:
  64.             if i==item: return counter
  65.             counter += 1
  66.         selftype = _typename(self)
  67.         raise ValueError("%s.index(x): x not in list" % _typename(self))
  68.  
  69.     #------- factories -------------------------------------------------------
  70.  
  71.     def __add__(self,other):
  72.         if isinstance(other,LinkedList):
  73.             result = LinkedList(self)
  74.             result += other
  75.             return result
  76.         else:
  77.             selftype = _typename(self)
  78.             raise TypeError('can only concatenate %s (not "%s") to '
  79.                             '%s' % (selftype,_typename(other),selftype))
  80.  
  81.     def __mul__(self,num):
  82.         if not isinstance(num,int):
  83.             raise TypeError("can't multiply sequence to non-int")
  84.         result = LinkedList(self)
  85.         result *= num
  86.         return result
  87.  
  88.     #------- mutators --------------------------------------------------------
  89.  
  90.     def __setitem__(self,index,item):
  91.         if not isinstance(index,slice):
  92.             self._getnode(index).item = item
  93.         else:  # slice object
  94.             try:
  95.                 if index.step == None:  # non extended slice
  96.                     sliceiter = self._iterslice(index)
  97.                     seqiter = iter(item)
  98.                     currentNode = None
  99.                     while True:
  100.                         try:
  101.                             currentNode = sliceiter.next()
  102.                             try: # perform assignments as long as both
  103.                                  # iterators are not done
  104.                                 currentItem = seqiter.next()
  105.                                 currentNode.item = currentItem
  106.                             except StopIteration:
  107.                                 # seqiter.next() is done; remove the rest
  108.                                 # nodes returned by sliceiter
  109.                                 self._removenode(currentNode)
  110.                         except StopIteration: # sliceiter.next() is done
  111.                              # insert the rest items returned by seqiter
  112.                             if currentNode!=None: # non-empty slice
  113.                                 while True:
  114.                                     try:
  115.                                         currentItem = seqiter.next()
  116.                                         self._insertnode(currentItem,
  117.                                                          currentNode,
  118.                                                          setAfter=True)
  119.                                         currentNode = currentNode.next
  120.                                     except StopIteration: return
  121.                             else: # empty slice
  122.                                 size = self._size
  123.                                 start = index.start!=None and index.start or 0
  124.                                 if start < 0: start += size
  125.                                 if start > size: start = size
  126.                                 elif start < 0: start = 0
  127.                                 while True:
  128.                                     try:
  129.                                         currentItem = seqiter.next()
  130.                                         self.insert(start, currentItem)
  131.                                         start += 1
  132.                                     except StopIteration: return
  133.                 else:   # extended slice
  134.                     slicenodes = list(self._iterslice(index))
  135.                     if len(slicenodes) != len(item):
  136.                         raise ValueError("attempt to assign sequence of size "
  137.                                          "%d to extended slice of size %d" %
  138.                                          (len(item),len(slicenodes)))
  139.                     else:
  140.                         it = iter(slicenodes)
  141.                         for i in item: it.next().item = i
  142.             except TypeError:
  143.                 raise TypeError('must assign sequence (not "%s") to slice'
  144.                                 % _typename(item))
  145.  
  146.     def __delitem__(self,index):
  147.         if not isinstance(index,slice):
  148.             self.pop(index)
  149.         else:  # slice object
  150.             for node in self._iterslice(index): self._removenode(node)
  151.  
  152.     def __iadd__(self,other):
  153.         for item in other: self.append(item)
  154.         return self
  155.  
  156.     extend = __iadd__
  157.  
  158.     def __imul__(self,num):
  159.         if not isinstance(num,int):
  160.             raise TypeError("can't multiply sequence to non-int")
  161.         initSize = self._size
  162.         num -= 1
  163.         for i in xrange(num):
  164.             it = iter(self)
  165.             for j in xrange(initSize):
  166.                 self.append(it.next())
  167.         return self
  168.  
  169.     def append(self,item):
  170.         self._insertnode(item,self._end,setAfter=True)
  171.  
  172.     def insert(self,index,item):
  173.         try:
  174.             next = self._getnode(index)
  175.             self._insertnode(item,next,setAfter=False)
  176.         except IndexError:
  177.             if index >= self._size: self.append(item)
  178.             else: self.insert(0,item)
  179.  
  180.     def pop(self,index=-1):
  181.         node = self._getnode(index)
  182.         self._removenode(node)
  183.         return node.item
  184.  
  185.     def remove(self,item):
  186.         for node in self._iternode():
  187.             if node.item==item: return self._removenode(node)
  188.         raise ValueError("%s.remove(x): x not in list" % _typename(self))
  189.  
  190.     def reverse(self):
  191.         middle = self._size // 2
  192.         bottom = self._start; top = self._end
  193.         for i in xrange(middle):
  194.             tmp = top.item
  195.             top.item = bottom.item
  196.             bottom.item = tmp
  197.             bottom = bottom.next; top = top.previous
  198.  
  199.     def sort(self,f=cmp):
  200.         array = list(self)
  201.         array.sort(f)
  202.         i = 0
  203.         for node in self._iternode():
  204.             node.item = array[i]
  205.             i += 1
  206.  
  207.     #------- (in)equality, str, repr -----------------------------------------
  208.  
  209.     def __eq__(self,other):
  210.         if not isinstance(other,LinkedList) or len(self) != len(other):
  211.             return False
  212.         for i,j in izip(self,other):
  213.             if i!=j:
  214.                 return False
  215.         return True
  216.  
  217.     def __ne__(self,other):
  218.         return not self.__eq__(other)
  219.  
  220.     def __str__(self):
  221.         return "[%s]" % ', '.join(map(repr,self))
  222.  
  223.     def __repr__(self):
  224.         return "LinkedList(%s)" % self
  225.  
  226.     #------- 'private' members -----------------------------------------------
  227.  
  228.     def _getnode(self,index):
  229.         if isinstance(index,int):
  230.             if index < 0: index += self._size
  231.             if 0 <= index < self._size:
  232.                 current = self._start
  233.                 for i in xrange(index): current = current.next
  234.                 return current
  235.             else:
  236.                 raise IndexError("list index out of range")
  237.         else:
  238.             raise TypeError("list indices must be integer")
  239.  
  240.     def _insertnode(self,item,node,setAfter):
  241.         if node==None:
  242.             newnode = self._Node(item,prevNode=None,nextNode=None)
  243.         else:
  244.             if setAfter:
  245.                 newnode = self._Node(item,prevNode=node,nextNode=node.next)
  246.             else:
  247.                 newnode = self._Node(item,prevNode=node.previous,nextNode=node)
  248.         if newnode.previous==None: self._start = newnode
  249.         if newnode.next==None: self._end = newnode
  250.         self._size += 1
  251.  
  252.     def _removenode(self,node):
  253.         if node.previous==None: # first Node
  254.             self._start = node.next
  255.         else:                   # non-first Node
  256.             node.previous.next = node.next
  257.         if node.next==None:     # last Node
  258.             self._end = node.previous
  259.         else:                   # non-last Node
  260.             node.next.previous = node.previous
  261.         self._size -= 1
  262.  
  263.     def _iternode(self):
  264.         current = self._start
  265.         while current != None:
  266.             yield current
  267.             current = current.next
  268.  
  269.     def _iterslice(self,slice):
  270.         start,stop,step = slice.indices(len(self))
  271.         #print start,stop,step
  272.         if step > 0:
  273.             updateNode = lambda node: node.next
  274.         else:
  275.             updateNode = lambda node: node.previous
  276.         if (stop-start)*step <= 0:
  277.             return
  278.         stop = abs(start-stop)
  279.         step = abs(step)
  280.         currentNode = self._getnode(start)
  281.         currentIndex = 0;
  282.         while currentIndex < stop:
  283.             if currentIndex % step == 0:
  284.                 yield currentNode
  285.             currentNode = updateNode(currentNode)
  286.             currentIndex += 1
  287.  
  288.     class _Node(object):
  289.  
  290.         __slots__ = 'item', 'next', 'previous'
  291.  
  292.         def __init__(self,item,nextNode=None,prevNode=None):
  293.             self.item = item
  294.             self.next = nextNode
  295.             self.previous = prevNode
  296.             if nextNode!=None: nextNode.previous = self
  297.             if prevNode!=None: prevNode.next = self
  298.         #def __del__(self): print "deleting", self
  299.  
  300.  
  301. def _typename(obj):
  302.     '''Return the name of the object's type.'''
  303.    try: return obj.__class__.__name__
  304.    except AttributeError:
  305.        return type(obj).__name__
clone this paste RAW Paste Data