''' 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__