Welcome, guest | Sign In | My Account | Store | Cart
2

Pure python drop in replacement for collections.deque() from Py2.4. See documentation at: http://www.python.org/dev/doc/devel/lib/module-collections.html <br> Uses a dictionary as the underlying data structure for the deque (pronounced "deck", short for "double-ended queue", a generalization of stacks and queues) which provides O(1) performance for appends and pops from either end. <br> Runs on PyPy, Jython, and older Pythons.

Python, 116 lines
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
class deque(object):

    def __init__(self, iterable=(), maxsize=-1):
        if not hasattr(self, 'data'):
            self.left = self.right = 0
            self.data = {}
        self.maxsize = maxsize
        self.extend(iterable)

    def append(self, x):
        self.data[self.right] = x
        self.right += 1
        if self.maxsize != -1 and len(self) > self.maxsize:
            self.popleft()
        
    def appendleft(self, x):
        self.left -= 1        
        self.data[self.left] = x
        if self.maxsize != -1 and len(self) > self.maxsize:
            self.pop()      
        
    def pop(self):
        if self.left == self.right:
            raise IndexError('cannot pop from empty deque')
        self.right -= 1
        elem = self.data[self.right]
        del self.data[self.right]         
        return elem
    
    def popleft(self):
        if self.left == self.right:
            raise IndexError('cannot pop from empty deque')
        elem = self.data[self.left]
        del self.data[self.left]
        self.left += 1
        return elem

    def clear(self):
        self.data.clear()
        self.left = self.right = 0

    def extend(self, iterable):
        for elem in iterable:
            self.append(elem)

    def extendleft(self, iterable):
        for elem in iterable:
            self.appendleft(elem)

    def rotate(self, n=1):
        if self:
            n %= len(self)
            for i in xrange(n):
                self.appendleft(self.pop())

    def __getitem__(self, i):
        if i < 0:
            i += len(self)
        try:
            return self.data[i + self.left]
        except KeyError:
            raise IndexError

    def __setitem__(self, i, value):
        if i < 0:
            i += len(self)        
        try:
            self.data[i + self.left] = value
        except KeyError:
            raise IndexError

    def __delitem__(self, i):
        size = len(self)
        if not (-size <= i < size):
            raise IndexError
        data = self.data
        if i < 0:
            i += size
        for j in xrange(self.left+i, self.right-1):
            data[j] = data[j+1]
        self.pop()
    
    def __len__(self):
        return self.right - self.left

    def __cmp__(self, other):
        if type(self) != type(other):
            return cmp(type(self), type(other))
        return cmp(list(self), list(other))
            
    def __repr__(self, _track=[]):
        if id(self) in _track:
            return '...'
        _track.append(id(self))
        r = 'deque(%r)' % (list(self),)
        _track.remove(id(self))
        return r
    
    def __getstate__(self):
        return (tuple(self),)
    
    def __setstate__(self, s):
        self.__init__(s[0])
        
    def __hash__(self):
        raise TypeError
    
    def __copy__(self):
        return self.__class__(self)
    
    def __deepcopy__(self, memo={}):
        from copy import deepcopy
        result = self.__class__()
        memo[id(self)] = result
        result.__init__(deepcopy(tuple(self), memo))
        return result

Provides a reasonably fast alternative to Py2.4's C implementation of collections.deque(). Matches the API of the C implementation but without thread safety.

Also includes a Py2.6 feature for bounded length deques that provide functionality similar to the Unix tail filter. Bounded length deques are also useful for tracking recent transactions or other rolling history logs.

1 comment

Connelly Barnes 12 years, 1 month ago  # | flag

Comments on runtime. In theory, a single append() or pop() has O(logN) amortized time, where N is the total number of operations made on the deque since instantiation. This is because as N grows very large, self.left and self.right can take up to O(log(N)) words as long ints.

In practice, you could call this "O(1) amortized time," since for any N that I can achieve on my 2005-era computer, the time spent incrementing, decrementing, and hashing integers is insignificant.

Cool, practicality beats purity!

Add a comment

Sign in to comment