← Back to branch summary

~ubuntu-branches/ubuntu/karmic/pypy/karmic

« back to all changes in this revision

Viewing changes to pypy/lib/collections.py

  • Committer: Bazaar Package Importer
  • Author(s): Alexandre Fayolle
  • Date: 2007-04-13 09:33:09 UTC
  • Revision ID: james.westby@ubuntu.com-20070413093309-yoojh4jcoocu2krz
Tags: upstream-1.0.0
Import upstream version 1.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
pypy/lib/collections.py
 
1
"""High performance data structures
 
2
"""
 
3
#
 
4
# Copied and completed from the sandbox of CPython
 
5
#   (nondist/sandbox/collections/pydeque.py rev 1.1, Raymond Hettinger)
 
6
#
 
7
 
 
8
import operator
 
9
try:
 
10
    from thread import get_ident as _thread_ident
 
11
except ImportError:
 
12
    def _thread_ident():
 
13
        return -1
 
14
 
 
15
 
 
16
n = 30
 
17
LFTLNK = n
 
18
RGTLNK = n+1
 
19
BLOCKSIZ = n+2
 
20
 
 
21
class deque(object):
 
22
 
 
23
    def __new__(cls, iterable=()):
 
24
        self = super(deque, cls).__new__(cls)
 
25
        self.clear()
 
26
        return self
 
27
 
 
28
    def __init__(self, iterable=()):
 
29
        add = self.append
 
30
        for elem in iterable:
 
31
            add(elem)
 
32
 
 
33
    def clear(self):
 
34
        self.right = self.left = [None] * BLOCKSIZ
 
35
        self.rightndx = n//2   # points to last written element
 
36
        self.leftndx = n//2+1
 
37
        self.length = 0
 
38
        self.state = 0
 
39
 
 
40
    def append(self, x):
 
41
        self.state += 1
 
42
        self.rightndx += 1
 
43
        if self.rightndx == n:
 
44
            newblock = [None] * BLOCKSIZ
 
45
            self.right[RGTLNK] = newblock
 
46
            newblock[LFTLNK] = self.right
 
47
            self.right = newblock
 
48
            self.rightndx = 0
 
49
        self.length += 1
 
50
        self.right[self.rightndx] = x
 
51
 
 
52
    def appendleft(self, x):
 
53
        self.state += 1
 
54
        self.leftndx -= 1
 
55
        if self.leftndx == -1:
 
56
            newblock = [None] * BLOCKSIZ
 
57
            self.left[LFTLNK] = newblock
 
58
            newblock[RGTLNK] = self.left
 
59
            self.left = newblock
 
60
            self.leftndx = n-1
 
61
        self.length += 1
 
62
        self.left[self.leftndx] = x
 
63
 
 
64
    def extend(self, iterable):
 
65
        for elem in iterable:
 
66
            self.append(elem)
 
67
 
 
68
    def extendleft(self, iterable):
 
69
        for elem in iterable:
 
70
            self.appendleft(elem)
 
71
 
 
72
    def pop(self):
 
73
        if self.left is self.right and self.leftndx > self.rightndx:
 
74
            raise IndexError, "pop from an empty deque"
 
75
        x = self.right[self.rightndx]
 
76
        self.right[self.rightndx] = None
 
77
        self.length -= 1
 
78
        self.rightndx -= 1
 
79
        self.state += 1
 
80
        if self.rightndx == -1:
 
81
            prevblock = self.right[LFTLNK]
 
82
            if prevblock is None:
 
83
                # the deque has become empty; recenter instead of freeing block
 
84
                self.rightndx = n//2
 
85
                self.leftndx = n//2+1
 
86
            else:
 
87
                prevblock[RGTLNK] = None
 
88
                self.right[LFTLNK] = None
 
89
                self.right = prevblock
 
90
                self.rightndx = n-1
 
91
        return x
 
92
 
 
93
    def popleft(self):
 
94
        if self.left is self.right and self.leftndx > self.rightndx:
 
95
            raise IndexError, "pop from an empty deque"
 
96
        x = self.left[self.leftndx]
 
97
        self.left[self.leftndx] = None
 
98
        self.length -= 1
 
99
        self.leftndx += 1
 
100
        self.state += 1
 
101
        if self.leftndx == n:
 
102
            prevblock = self.left[RGTLNK]
 
103
            if prevblock is None:
 
104
                # the deque has become empty; recenter instead of freeing block
 
105
                self.rightndx = n//2
 
106
                self.leftndx = n//2+1
 
107
            else:
 
108
                prevblock[LFTLNK] = None
 
109
                self.left[RGTLNK] = None
 
110
                self.left = prevblock
 
111
                self.leftndx = 0
 
112
        return x
 
113
 
 
114
    def remove(self, value):
 
115
        del self[operator.indexOf(self, value)]
 
116
 
 
117
    def rotate(self, n=1):
 
118
        length = len(self)
 
119
        if length == 0:
 
120
            return
 
121
        halflen = (length+1) >> 1
 
122
        if n > halflen or n < -halflen:
 
123
            n %= length
 
124
            if n > halflen:
 
125
                n -= length
 
126
            elif n < -halflen:
 
127
                n += length
 
128
        while n > 0:
 
129
            self.appendleft(self.pop())
 
130
            n -= 1
 
131
        while n < 0:
 
132
            self.append(self.popleft())
 
133
            n += 1
 
134
 
 
135
    def __repr__(self):
 
136
        threadlocalattr = '__repr' + str(_thread_ident())
 
137
        if threadlocalattr in self.__dict__:
 
138
            return 'deque([...])'
 
139
        else:
 
140
            self.__dict__[threadlocalattr] = True
 
141
            try:
 
142
                return 'deque(%r)' % (list(self),)
 
143
            finally:
 
144
                del self.__dict__[threadlocalattr]
 
145
 
 
146
    def __iter__(self):
 
147
        return deque_iterator(self, self._iter_impl)
 
148
 
 
149
    def _iter_impl(self, original_state, giveup):
 
150
        if self.state != original_state:
 
151
            giveup()
 
152
        block = self.left
 
153
        while block:
 
154
            l, r = 0, n
 
155
            if block is self.left:
 
156
                l = self.leftndx
 
157
            if block is self.right:
 
158
                r = self.rightndx + 1
 
159
            for elem in block[l:r]:
 
160
                yield elem
 
161
                if self.state != original_state:
 
162
                    giveup()
 
163
            block = block[RGTLNK]
 
164
 
 
165
    def __reversed__(self):
 
166
        return deque_iterator(self, self._reversed_impl)
 
167
 
 
168
    def _reversed_impl(self, original_state, giveup):
 
169
        if self.state != original_state:
 
170
            giveup()
 
171
        block = self.right
 
172
        while block:
 
173
            l, r = 0, n
 
174
            if block is self.left:
 
175
                l = self.leftndx
 
176
            if block is self.right:
 
177
                r = self.rightndx + 1
 
178
            for elem in reversed(block[l:r]):
 
179
                yield elem
 
180
                if self.state != original_state:
 
181
                    giveup()
 
182
            block = block[LFTLNK]
 
183
 
 
184
    def __len__(self):
 
185
        #sum = 0
 
186
        #block = self.left
 
187
        #while block:
 
188
        #    sum += n
 
189
        #    block = block[RGTLNK]
 
190
        #return sum + self.rightndx - self.leftndx + 1 - n
 
191
        return self.length
 
192
 
 
193
    def __getref(self, index):
 
194
        if index >= 0:
 
195
            block = self.left
 
196
            while block:
 
197
                l, r = 0, n
 
198
                if block is self.left:
 
199
                    l = self.leftndx
 
200
                if block is self.right:
 
201
                    r = self.rightndx + 1
 
202
                span = r-l
 
203
                if index < span:
 
204
                    return block, l+index
 
205
                index -= span
 
206
                block = block[RGTLNK]
 
207
        else:
 
208
            block = self.right
 
209
            while block:
 
210
                l, r = 0, n
 
211
                if block is self.left:
 
212
                    l = self.leftndx
 
213
                if block is self.right:
 
214
                    r = self.rightndx + 1
 
215
                negative_span = l-r
 
216
                if index >= negative_span:
 
217
                    return block, r+index
 
218
                index -= negative_span
 
219
                block = block[LFTLNK]
 
220
        raise IndexError("deque index out of range")
 
221
 
 
222
    def __getitem__(self, index):
 
223
        block, index = self.__getref(index)
 
224
        return block[index]
 
225
 
 
226
    def __setitem__(self, index, value):
 
227
        block, index = self.__getref(index)
 
228
        block[index] = value
 
229
 
 
230
    def __delitem__(self, index):
 
231
        length = len(self)
 
232
        if index >= 0:
 
233
            if index >= length:
 
234
                raise IndexError("deque index out of range")
 
235
            self.rotate(-index)
 
236
            self.popleft()
 
237
            self.rotate(index)
 
238
        else:
 
239
            index = ~index
 
240
            if index >= length:
 
241
                raise IndexError("deque index out of range")
 
242
            self.rotate(index)
 
243
            self.pop()
 
244
            self.rotate(-index)
 
245
 
 
246
    def __reduce_ex__(self, proto):
 
247
        return type(self), (), self.__dict__, iter(self), None
 
248
 
 
249
    def __hash__(self):
 
250
        raise TypeError, "deque objects are unhashable"
 
251
 
 
252
    def __copy__(self):
 
253
        return self.__class__(self)
 
254
 
 
255
    # XXX make comparison more efficient
 
256
    def __eq__(self, other):
 
257
        if isinstance(other, deque):
 
258
            return list(self) == list(other)
 
259
        else:
 
260
            return NotImplemented
 
261
 
 
262
    def __ne__(self, other):
 
263
        if isinstance(other, deque):
 
264
            return list(self) != list(other)
 
265
        else:
 
266
            return NotImplemented
 
267
 
 
268
    def __lt__(self, other):
 
269
        if isinstance(other, deque):
 
270
            return list(self) < list(other)
 
271
        else:
 
272
            return NotImplemented
 
273
 
 
274
    def __le__(self, other):
 
275
        if isinstance(other, deque):
 
276
            return list(self) <= list(other)
 
277
        else:
 
278
            return NotImplemented
 
279
 
 
280
    def __gt__(self, other):
 
281
        if isinstance(other, deque):
 
282
            return list(self) > list(other)
 
283
        else:
 
284
            return NotImplemented
 
285
 
 
286
    def __ge__(self, other):
 
287
        if isinstance(other, deque):
 
288
            return list(self) >= list(other)
 
289
        else:
 
290
            return NotImplemented
 
291
 
 
292
class deque_iterator(object):
 
293
 
 
294
    def __init__(self, deq, itergen):
 
295
        self.counter = len(deq)
 
296
        def giveup():
 
297
            self.counter = 0
 
298
            raise RuntimeError, "deque mutated during iteration"
 
299
        self._gen = itergen(deq.state, giveup)
 
300
 
 
301
    def next(self):
 
302
        res =  self._gen.next()
 
303
        self.counter -= 1
 
304
        return res
 
305
 
 
306
    def __iter__(self):
 
307
        return self
 
308
 
 
309
    def __len__(self):
 
310
        return self.counter
 
311