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

[rhettinger at projects.sourceforge.net]

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)