diff options
author | Benjamin Peterson <benjamin@python.org> | 2010-06-24 16:00:01 +0000 |
---|---|---|
committer | Benjamin Peterson <benjamin@python.org> | 2010-06-24 16:00:01 +0000 |
commit | d8b76533f6f2dd76691bde5bbcbdcba54427d6e9 (patch) | |
tree | 53404af3e3487dc64d889dbcaa4e27916afc1428 /lib_pypy/_collections.py | |
parent | ignore platform:ERROR things (diff) | |
download | pypy-d8b76533f6f2dd76691bde5bbcbdcba54427d6e9.tar.gz pypy-d8b76533f6f2dd76691bde5bbcbdcba54427d6e9.tar.bz2 pypy-d8b76533f6f2dd76691bde5bbcbdcba54427d6e9.zip |
merge from trunk
Diffstat (limited to 'lib_pypy/_collections.py')
-rw-r--r-- | lib_pypy/_collections.py | 360 |
1 files changed, 360 insertions, 0 deletions
diff --git a/lib_pypy/_collections.py b/lib_pypy/_collections.py new file mode 100644 index 0000000000..da5b21424c --- /dev/null +++ b/lib_pypy/_collections.py @@ -0,0 +1,360 @@ +"""High performance data structures +""" +# +# Copied and completed from the sandbox of CPython +# (nondist/sandbox/collections/pydeque.py rev 1.1, Raymond Hettinger) +# + +import operator +try: + from thread import get_ident as _thread_ident +except ImportError: + def _thread_ident(): + return -1 + + +n = 30 +LFTLNK = n +RGTLNK = n+1 +BLOCKSIZ = n+2 + +class deque(object): + + def __new__(cls, iterable=(), *args, **kw): + self = super(deque, cls).__new__(cls, *args, **kw) + self.clear() + return self + + def __init__(self, iterable=()): + add = self.append + for elem in iterable: + add(elem) + + def clear(self): + self.right = self.left = [None] * BLOCKSIZ + self.rightndx = n//2 # points to last written element + self.leftndx = n//2+1 + self.length = 0 + self.state = 0 + + def append(self, x): + self.state += 1 + 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.length += 1 + self.right[self.rightndx] = x + + def appendleft(self, x): + self.state += 1 + 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.length += 1 + self.left[self.leftndx] = x + + def extend(self, iterable): + for elem in iterable: + self.append(elem) + + def extendleft(self, iterable): + for elem in iterable: + self.appendleft(elem) + + def pop(self): + if self.left is self.right and self.leftndx > self.rightndx: + raise IndexError, "pop from an empty deque" + x = self.right[self.rightndx] + self.right[self.rightndx] = None + self.length -= 1 + self.rightndx -= 1 + self.state += 1 + if self.rightndx == -1: + prevblock = self.right[LFTLNK] + if prevblock is None: + # the deque has become empty; recenter instead of freeing block + self.rightndx = n//2 + self.leftndx = n//2+1 + else: + 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, "pop from an empty deque" + x = self.left[self.leftndx] + self.left[self.leftndx] = None + self.length -= 1 + self.leftndx += 1 + self.state += 1 + if self.leftndx == n: + prevblock = self.left[RGTLNK] + if prevblock is None: + # the deque has become empty; recenter instead of freeing block + self.rightndx = n//2 + self.leftndx = n//2+1 + else: + prevblock[LFTLNK] = None + self.left[RGTLNK] = None + self.left = prevblock + self.leftndx = 0 + return x + + def remove(self, value): + # Need to be defensive for mutating comparisons + for i in range(len(self)): + if self[i] == value: + del self[i] + return + raise ValueError("deque.remove(x): x not in deque") + + def rotate(self, n=1): + length = len(self) + if length == 0: + return + halflen = (length+1) >> 1 + if n > halflen or n < -halflen: + n %= length + if n > halflen: + n -= length + elif n < -halflen: + n += length + while n > 0: + self.appendleft(self.pop()) + n -= 1 + while n < 0: + self.append(self.popleft()) + n += 1 + + def __repr__(self): + threadlocalattr = '__repr' + str(_thread_ident()) + if threadlocalattr in self.__dict__: + return 'deque([...])' + else: + self.__dict__[threadlocalattr] = True + try: + return 'deque(%r)' % (list(self),) + finally: + del self.__dict__[threadlocalattr] + + def __iter__(self): + return deque_iterator(self, self._iter_impl) + + def _iter_impl(self, original_state, giveup): + if self.state != original_state: + giveup() + 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 + if self.state != original_state: + giveup() + block = block[RGTLNK] + + def __reversed__(self): + return deque_iterator(self, self._reversed_impl) + + def _reversed_impl(self, original_state, giveup): + if self.state != original_state: + giveup() + block = self.right + 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 reversed(block[l:r]): + yield elem + if self.state != original_state: + giveup() + block = block[LFTLNK] + + def __len__(self): + #sum = 0 + #block = self.left + #while block: + # sum += n + # block = block[RGTLNK] + #return sum + self.rightndx - self.leftndx + 1 - n + return self.length + + def __getref(self, index): + if index >= 0: + 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 + span = r-l + if index < span: + return block, l+index + index -= span + block = block[RGTLNK] + else: + block = self.right + while block: + l, r = 0, n + if block is self.left: + l = self.leftndx + if block is self.right: + r = self.rightndx + 1 + negative_span = l-r + if index >= negative_span: + return block, r+index + index -= negative_span + block = block[LFTLNK] + raise IndexError("deque index out of range") + + def __getitem__(self, index): + block, index = self.__getref(index) + return block[index] + + def __setitem__(self, index, value): + block, index = self.__getref(index) + block[index] = value + + def __delitem__(self, index): + length = len(self) + if index >= 0: + if index >= length: + raise IndexError("deque index out of range") + self.rotate(-index) + self.popleft() + self.rotate(index) + else: + index = ~index + if index >= length: + raise IndexError("deque index out of range") + self.rotate(index) + self.pop() + self.rotate(-index) + + def __reduce_ex__(self, proto): + return type(self), (), self.__dict__, iter(self), None + + def __hash__(self): + raise TypeError, "deque objects are unhashable" + + def __copy__(self): + return self.__class__(self) + + # XXX make comparison more efficient + def __eq__(self, other): + if isinstance(other, deque): + return list(self) == list(other) + else: + return NotImplemented + + def __ne__(self, other): + if isinstance(other, deque): + return list(self) != list(other) + else: + return NotImplemented + + def __lt__(self, other): + if isinstance(other, deque): + return list(self) < list(other) + else: + return NotImplemented + + def __le__(self, other): + if isinstance(other, deque): + return list(self) <= list(other) + else: + return NotImplemented + + def __gt__(self, other): + if isinstance(other, deque): + return list(self) > list(other) + else: + return NotImplemented + + def __ge__(self, other): + if isinstance(other, deque): + return list(self) >= list(other) + else: + return NotImplemented + +class deque_iterator(object): + + def __init__(self, deq, itergen): + self.counter = len(deq) + def giveup(): + self.counter = 0 + raise RuntimeError, "deque mutated during iteration" + self._gen = itergen(deq.state, giveup) + + def next(self): + res = self._gen.next() + self.counter -= 1 + return res + + def __iter__(self): + return self + +class defaultdict(dict): + + def __init__(self, *args, **kwds): + self.default_factory = None + if 'default_factory' in kwds: + self.default_factory = kwds.pop('default_factory') + elif len(args) > 0 and callable(args[0]): + self.default_factory = args[0] + args = args[1:] + super(defaultdict, self).__init__(*args, **kwds) + + def __missing__(self, key): + # from defaultdict docs + if self.default_factory is None: + raise KeyError(key) + self[key] = value = self.default_factory() + return value + + def __repr__(self, recurse=set()): + if id(self) in recurse: + return "defaultdict(...)" + try: + recurse.add(id(self)) + return "defaultdict(%s, %s)" % (repr(self.default_factory), super(defaultdict, self).__repr__()) + finally: + recurse.remove(id(self)) + + def copy(self): + return type(self)(self, default_factory=self.default_factory) + + def __copy__(self): + return self.copy() + + def __reduce__(self): + """ + __reduce__ must return a 5-tuple as follows: + + - factory function + - tuple of args for the factory function + - additional state (here None) + - sequence iterator (here None) + - dictionary iterator (yielding successive (key, value) pairs + + This API is used by pickle.py and copy.py. + """ + return (type(self), (self.default_factory,), None, None, self.iteritems()) + |