Author: Armin Rigo <ar...@tunes.org> Branch: Changeset: r55000:083a5889c293 Date: 2012-05-10 08:10 +0200 http://bitbucket.org/pypy/pypy/changeset/083a5889c293/
Log: Add a generally useful auto-shrinking list type. diff --git a/pypy/rlib/rshrinklist.py b/pypy/rlib/rshrinklist.py new file mode 100644 --- /dev/null +++ b/pypy/rlib/rshrinklist.py @@ -0,0 +1,27 @@ + +class AbstractShrinkList(object): + _mixin_ = True + + def __init__(self): + self._list = [] + self._next_shrink = 16 + + def append(self, x): + self._do_shrink() + self._list.append(x) + + def items(self): + return self._list + + def _do_shrink(self): + if len(self._list) >= self._next_shrink: + rest = 0 + for x in self._list: + if self.must_keep(x): + self._list[rest] = x + rest += 1 + del self._list[rest:] + self._next_shrink = 16 + 2 * rest + + def must_keep(self, x): + raise NotImplementedError diff --git a/pypy/rlib/test/test_rshrinklist.py b/pypy/rlib/test/test_rshrinklist.py new file mode 100644 --- /dev/null +++ b/pypy/rlib/test/test_rshrinklist.py @@ -0,0 +1,30 @@ +from pypy.rlib.rshrinklist import AbstractShrinkList + +class Item: + alive = True + +class ItemList(AbstractShrinkList): + def must_keep(self, x): + return x.alive + +def test_simple(): + l = ItemList() + l2 = [Item() for i in range(150)] + for x in l2: + l.append(x) + assert l.items() == l2 + # + for x in l2[::2]: + x.alive = False + l3 = [Item() for i in range(150 + 16)] + for x in l3: + l.append(x) + assert l.items() == l2[1::2] + l3 + +def test_append_dead_items(): + l = ItemList() + for i in range(150): + x = Item() + l.append(x) + x.alive = False + assert len(l.items()) <= 16 _______________________________________________ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
