Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ''' Linked list
- This is a copy of
- http://www.koders.com/python/fid6EF9B028CDDCE7D42E690DD3ADD1BB39E7869ED2.aspx
- Project site is here: http://code.google.com/p/gsakkis-utils/
- The project site state that the license of this code is LGPL
- '''
- from itertools import izip
- __author__ = "George Sakkis <gsakkis@rutgers.edu>"
- __all__ = ["LinkedList"]
- class LinkedList(object):
- ''' Linked list class '''
- __slots__ = '_start', '_end', '_size'
- #------- constructor / destructor ----------------------------------------
- def __init__(self,sequence=()):
- self._size = 0
- self._start = self._end = None
- self += sequence
- def __del__(self):
- current = self._start
- while current != None:
- # cut the link to the previous node so that this can be released
- current.previous = None
- current = current.next
- #------- accesors --------------------------------------------------------
- def __len__(self):
- return self._size
- def __iter__(self):
- current = self._start
- while current != None:
- yield current.item
- current = current.next
- def __getitem__(self,index):
- if not isinstance(index,slice):
- return self._getnode(index).item
- else: # slice object
- result = LinkedList()
- for i in self._iterslice(index):
- result.append(i.item)
- return result
- def count(self,item):
- counter = 0
- for i in self:
- if i==item: counter +=1
- return counter
- def index(self,item):
- counter = 0
- for i in self:
- if i==item: return counter
- counter += 1
- selftype = _typename(self)
- raise ValueError("%s.index(x): x not in list" % _typename(self))
- #------- factories -------------------------------------------------------
- def __add__(self,other):
- if isinstance(other,LinkedList):
- result = LinkedList(self)
- result += other
- return result
- else:
- selftype = _typename(self)
- raise TypeError('can only concatenate %s (not "%s") to '
- '%s' % (selftype,_typename(other),selftype))
- def __mul__(self,num):
- if not isinstance(num,int):
- raise TypeError("can't multiply sequence to non-int")
- result = LinkedList(self)
- result *= num
- return result
- #------- mutators --------------------------------------------------------
- def __setitem__(self,index,item):
- if not isinstance(index,slice):
- self._getnode(index).item = item
- else: # slice object
- try:
- if index.step == None: # non extended slice
- sliceiter = self._iterslice(index)
- seqiter = iter(item)
- currentNode = None
- while True:
- try:
- currentNode = sliceiter.next()
- try: # perform assignments as long as both
- # iterators are not done
- currentItem = seqiter.next()
- currentNode.item = currentItem
- except StopIteration:
- # seqiter.next() is done; remove the rest
- # nodes returned by sliceiter
- self._removenode(currentNode)
- except StopIteration: # sliceiter.next() is done
- # insert the rest items returned by seqiter
- if currentNode!=None: # non-empty slice
- while True:
- try:
- currentItem = seqiter.next()
- self._insertnode(currentItem,
- currentNode,
- setAfter=True)
- currentNode = currentNode.next
- except StopIteration: return
- else: # empty slice
- size = self._size
- start = index.start!=None and index.start or 0
- if start < 0: start += size
- if start > size: start = size
- elif start < 0: start = 0
- while True:
- try:
- currentItem = seqiter.next()
- self.insert(start, currentItem)
- start += 1
- except StopIteration: return
- else: # extended slice
- slicenodes = list(self._iterslice(index))
- if len(slicenodes) != len(item):
- raise ValueError("attempt to assign sequence of size "
- "%d to extended slice of size %d" %
- (len(item),len(slicenodes)))
- else:
- it = iter(slicenodes)
- for i in item: it.next().item = i
- except TypeError:
- raise TypeError('must assign sequence (not "%s") to slice'
- % _typename(item))
- def __delitem__(self,index):
- if not isinstance(index,slice):
- self.pop(index)
- else: # slice object
- for node in self._iterslice(index): self._removenode(node)
- def __iadd__(self,other):
- for item in other: self.append(item)
- return self
- extend = __iadd__
- def __imul__(self,num):
- if not isinstance(num,int):
- raise TypeError("can't multiply sequence to non-int")
- initSize = self._size
- num -= 1
- for i in xrange(num):
- it = iter(self)
- for j in xrange(initSize):
- self.append(it.next())
- return self
- def append(self,item):
- self._insertnode(item,self._end,setAfter=True)
- def insert(self,index,item):
- try:
- next = self._getnode(index)
- self._insertnode(item,next,setAfter=False)
- except IndexError:
- if index >= self._size: self.append(item)
- else: self.insert(0,item)
- def pop(self,index=-1):
- node = self._getnode(index)
- self._removenode(node)
- return node.item
- def remove(self,item):
- for node in self._iternode():
- if node.item==item: return self._removenode(node)
- raise ValueError("%s.remove(x): x not in list" % _typename(self))
- def reverse(self):
- middle = self._size // 2
- bottom = self._start; top = self._end
- for i in xrange(middle):
- tmp = top.item
- top.item = bottom.item
- bottom.item = tmp
- bottom = bottom.next; top = top.previous
- def sort(self,f=cmp):
- array = list(self)
- array.sort(f)
- i = 0
- for node in self._iternode():
- node.item = array[i]
- i += 1
- #------- (in)equality, str, repr -----------------------------------------
- def __eq__(self,other):
- if not isinstance(other,LinkedList) or len(self) != len(other):
- return False
- for i,j in izip(self,other):
- if i!=j:
- return False
- return True
- def __ne__(self,other):
- return not self.__eq__(other)
- def __str__(self):
- return "[%s]" % ', '.join(map(repr,self))
- def __repr__(self):
- return "LinkedList(%s)" % self
- #------- 'private' members -----------------------------------------------
- def _getnode(self,index):
- if isinstance(index,int):
- if index < 0: index += self._size
- if 0 <= index < self._size:
- current = self._start
- for i in xrange(index): current = current.next
- return current
- else:
- raise IndexError("list index out of range")
- else:
- raise TypeError("list indices must be integer")
- def _insertnode(self,item,node,setAfter):
- if node==None:
- newnode = self._Node(item,prevNode=None,nextNode=None)
- else:
- if setAfter:
- newnode = self._Node(item,prevNode=node,nextNode=node.next)
- else:
- newnode = self._Node(item,prevNode=node.previous,nextNode=node)
- if newnode.previous==None: self._start = newnode
- if newnode.next==None: self._end = newnode
- self._size += 1
- def _removenode(self,node):
- if node.previous==None: # first Node
- self._start = node.next
- else: # non-first Node
- node.previous.next = node.next
- if node.next==None: # last Node
- self._end = node.previous
- else: # non-last Node
- node.next.previous = node.previous
- self._size -= 1
- def _iternode(self):
- current = self._start
- while current != None:
- yield current
- current = current.next
- def _iterslice(self,slice):
- start,stop,step = slice.indices(len(self))
- #print start,stop,step
- if step > 0:
- updateNode = lambda node: node.next
- else:
- updateNode = lambda node: node.previous
- if (stop-start)*step <= 0:
- return
- stop = abs(start-stop)
- step = abs(step)
- currentNode = self._getnode(start)
- currentIndex = 0;
- while currentIndex < stop:
- if currentIndex % step == 0:
- yield currentNode
- currentNode = updateNode(currentNode)
- currentIndex += 1
- class _Node(object):
- __slots__ = 'item', 'next', 'previous'
- def __init__(self,item,nextNode=None,prevNode=None):
- self.item = item
- self.next = nextNode
- self.previous = prevNode
- if nextNode!=None: nextNode.previous = self
- if prevNode!=None: prevNode.next = self
- #def __del__(self): print "deleting", self
- def _typename(obj):
- '''Return the name of the object's type.'''
- try: return obj.__class__.__name__
- except AttributeError:
- return type(obj).__name__
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement