[Python-checkins] python/nondist/sandbox/collections pydeque.py, NONE, 1.1

Mon Jan 26 12:49:37 EST 2004

Update of /cvsroot/python/python/nondist/sandbox/collections
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv3186
Added Files:
	pydeque.py 
Log Message:
Add pure python version to aid review.
--- NEW FILE: pydeque.py ---
n = 30
LFTLNK = n
RGTLNK = n+1
BLOCKSIZ = n+2
class deque(object):
 def __init__(self, iterable=()):
 self.right = self.left = [None] * BLOCKSIZ
 self.rightndx = n//2 # points to last written element
 self.leftndx = n//2+1
 add = self.append
 for elem in iterable:
 add(elem)
 def append(self, x):
 self.rightndx += 1
 if self.rightndx == n:
 newblock = [None] * BLOCKSIZ
 self.right[RGTLNK] = newblock
 newblock[LFTLNK] = self.right
 self.right = newblock
 self.rightndx = 0
 self.right[self.rightndx] = x
 def appendleft(self, x):
 self.leftndx -= 1
 if self.leftndx == -1:
 newblock = [None] * BLOCKSIZ
 self.left[LFTLNK] = newblock
 newblock[RGTLNK] = self.left
 self.left = newblock
 self.leftndx = n-1
 self.left[self.leftndx] = x
 def pop(self):
 if self.left is self.right and self.leftndx > self.rightndx:
 raise IndexError
 x = self.right[self.rightndx]
 self.right[self.rightndx] = None
 self.rightndx -= 1
 if self.rightndx == -1:
 prevblock = self.right[LFTLNK]
 prevblock[RGTLNK] = None
 self.right[LFTLNK] = None
 self.right = prevblock
 self.rightndx = n-1
 return x
 def popleft(self):
 if self.left is self.right and self.leftndx > self.rightndx:
 raise IndexError
 x = self.left[self.leftndx]
 self.left[self.leftndx] = None
 self.leftndx += 1
 if self.leftndx == n:
 prevblock = self.left[RGTLNK]
 prevblock[LFTLNK] = None
 self.left[RGTLNK] = None
 self.left = prevblock
 self.leftndx = 0
 return x
 def __repr__(self):
 return 'deque(%r)' % (list(self),)
 def __iter__(self):
 block = self.left
 while block:
 l, r = 0, n
 if block is self.left:
 l = self.leftndx
 if block is self.right:
 r = self.rightndx + 1
 for elem in block[l:r]:
 yield elem
 block = block[RGTLNK]
 def __len__(self):
 sum = 0
 block = self.left
 while block:
 sum += n
 block = block[RGTLNK]
 return sum + self.rightndx - self.leftndx + 1 - n
 def __reduce__(self):
 return (type(self), tuple(self))
 def __hash__(self):
 raise TypeError
 def __copy__(self):
 return self.__class__(self)
if __name__ == '__main__':
 a = deque()
 for i in xrange(10):
 a.append(i)
 for i in [-1, -2, -3, -4, -5, -6, -7, -8, -9, -10, -11]:
 a.appendleft(i)
 print a, len(a)
 print list(a)
 b = deque(a)
 for i in xrange(18):
 print a.popleft()
 print a, len(a)
 print b, len(b)