Commits

rkruppe committed c837f7b

import entity component system

Comments (0)

Files changed (4)

+import base64
+from types import SimpleNamespace
+from collections import OrderedDict
+import logging; logging.basicConfig(level=logging.DEBUG)
+import jinja2
+import ttgx.rawbuf
+
+
+class _Type:
+    def __init__(self, name):
+        self._name = name
+
+    def _make_array(self):
+        buf_type = _dtype_to_buf[self]
+        return ttgx.rawbuf.Array(buf_type)
+
+    def __repr__(self):
+        return __name__ + '.dtype.' + self._name
+
+
+dtype = SimpleNamespace()
+
+for typename in ('I32', 'U32'):
+    setattr(dtype, typename, _Type(typename))
+del typename
+
+_dtype_to_buf = {
+    dtype.I32: ttgx.rawbuf.I32,
+    dtype.U32: ttgx.rawbuf.U32
+}
+
+log = logging.getLogger(__name__)
+_jinja_env = jinja2.Environment(
+    undefined=jinja2.StrictUndefined, # error on undefined variables
+)
+_jinja_env.filters['repr'] = repr
+_jinja_env.filters['enumerate'] = enumerate
+_component_template = _jinja_env.from_string('''
+{#-
+We could supply the imports from _make_component_class() but this way the
+generated code is self-contained and can be stored in an on-disk module,
+which we may want to do later on.
+-#}
+import ttgx.dodecs
+
+{# Is actually completely independent and could live in dodecs.
+    Including it here only to permit better error messages. #}
+class _{{clsname}}AttributeView:
+    def __init__(self, comp, indices, values):
+        self._comp = comp
+        self._indices = indices
+        self._values = values
+
+    def __setitem__(self, e, val):
+        self._comp.universe.check_entity(e)
+        self._values[self._indices[e]] = val
+
+    def __getitem__(self, e):
+        self._comp.universe.check_entity(e)
+        return self._values[self._indices[e]]
+
+
+class {{clsname}}:
+    identifier = {{identifier|repr}}
+
+    def __init__(self):
+        self.__indices = {}
+        self.__entities = []
+{%- for name, t in attrs.items() %}
+        self._{{name}} = {{t}}._make_array()
+        self.{{name}} = _{{clsname}}AttributeView(
+            self, self.__indices, self._{{name}})
+{%- endfor %}
+
+    def __setitem__(self, e, vals):
+    {%- if attrs|length == 1 %}
+        vals = [vals]
+    {%- endif %}
+        self.universe.check_entity(e)
+        if e in self.__indices:
+        {%- for i, name in attrs|enumerate %}
+            j = self.__indices[e]
+            self._{{name}}[j] = vals[{{i}}]
+        {%- endfor %}
+        else:
+        {%- for i, name in attrs|enumerate %}
+            self._{{name}}.append(vals[{{i}}])
+        {%- endfor %}
+            self.__indices[e] = len(self.__indices)
+            self.__entities.append(e)
+    {% for name in attrs %}
+        assert len(self._{{name}}) == len(self.__indices)
+    {%- endfor %}
+
+    def __delitem__(self, e):
+        self.universe.check_entity(e)
+        i = self.__indices.pop(e)
+        assert e is self.__entities[i]
+    {%- for name in attrs %}
+        self._{{name}}.pop_by_swap(i)
+        assert len(self._{{name}}) == len(self.__indices)
+    {%- endfor %}
+        if i != len(self.__entities) - 1:
+            self.__entities[i] = self.__entities.pop()
+            self.__indices[self.__entities[i]] = i
+
+{% if attrs|length == 1 %}
+    def __getitem__(self, e):
+        return self.{{attrs|first}}[e]
+{% else %}
+    def __getitem__(self, e):
+        self.universe.check_entity(e)
+        i = self.__indices[e]
+        return (
+        {%- for name in attrs %}
+            self._{{name}}[i],
+        {%- endfor %}
+        )
+{% endif -%}
+''')
+
+
+def _make_component_class(clsname, **kwds):
+    src = _component_template.render(clsname=clsname, **kwds)
+    log.debug('Code for component %s:%s', clsname, src)
+    code = compile(src, '<dodecs component>', 'exec')
+    namespace = {}
+    exec(code, namespace, namespace)
+    return namespace[clsname]
+
+
+def _b64id(o):
+    """A base64 variation on id() for humans.
+
+    A dirty trick is used to make the ids more distinguishable:
+    The id() is interpreted LSByte-first, because the higher-valued bytes
+    the same for most objects with typical memory management.
+    This is only useful if id() is indeed a memory address and the memory
+    management is somewhat typical. That detail is true for CPython and the
+    best/default PyPy GC.
+    In addition, it doesn't do harm if the assumptions are wrong.
+
+    A much more implementation-dependent, even dirtier trick, which we don't
+    implement (yet) for that reason:
+    We *could*, if we knew the alignment of the  PyObjects, divide the memory
+    address by that alignment. But we don't know it, can't know it reliably,
+    and don't need the extra distinguishability that badly.
+    If we get this wrong, distinct entities would be displayed the same,
+    which is of course quite harmful.
+    """
+    id_bytes = id(o).to_bytes(64, byteorder='big').lstrip(b'\x00')
+    reverse_id_bytes = id_bytes[::-1]
+    full_addr = base64.b64encode(reverse_id_bytes).decode('ascii')
+    addr = full_addr.rstrip('=')
+    return addr
+
+
+class InvalidEntityError(BaseException):
+    pass
+
+
+class _Entity:
+    __slots__ = ()
+
+    def __repr__(self):
+        return '<Entity ' + _b64id(self) + '>'
+
+
+
+class Universe:
+    def __init__(self):
+        self._entities = set()
+        self._component_identifiers = set()
+        self._system_identifiers = set()
+        self.comp = SimpleNamespace()
+        self.sys = SimpleNamespace()
+
+    def _components(self):
+        return (getattr(self.comp, ident)
+                for ident in self._component_identifiers)
+
+    def _systems(self):
+        return (getattr(self.sys, ident)
+                for ident in self._system_identifiers)
+
+    def new(self):
+        e = _Entity()
+        self._entities.add(e)
+        return e
+
+    def delete(self, e):
+        self._entities.remove(e)
+        for c in self._components():
+            c.discard(e)
+
+    def check_entity(self, e):
+        if type(e) is not _Entity or e not in self._entities:
+            raise InvalidEntityError
+
+    def register_component(self, c):
+        ident = c.identifier
+        if hasattr(self.comp, ident):
+            if getattr(self.comp, ident) is c:
+                raise RuntimeError("Component already registered")
+            raise KeyError("Component name already reserved")
+        self._component_identifiers.add(ident)
+        setattr(self.comp, ident, c)
+        c.universe = self
+
+    def register_system(self, s):
+        ident = s.identifier
+        if hasattr(self.sys, ident):
+            if getattr(self.sys, ident) is s:
+                raise RuntimeError("System already registered")
+            raise KeyError("System name already reserved")
+        self._system_identifiers.add(ident)
+        setattr(self.sys, ident, s)
+
+    def step(self):
+        for s in self._systems():
+            args = (getattr(self.comp, ident) for ident in s.components)
+            s.step(*args)
+
+
+def component(clsname, identifier, attr_order, **attr_types):
+    attrs = OrderedDict()
+    for attr in attr_order:
+        attrs[attr] = attr_types[attr]
+    return _make_component_class(clsname, identifier=identifier, attrs=attrs)
+
+import cffi
+
+
+_ffi = cffi.FFI()
+
+_ffi.cdef('''
+    void *memcpy(void *dest, const void *src, size_t count);
+''')
+_libc = _ffi.dlopen(None)
+
+
+class _Buffer:
+    def __init__(self, size):
+        self._data = _ffi.new(self._ctype, size)
+
+    def __len__(self):
+        return len(self._data)
+
+    def __getitem__(self, i):
+        return self._data[i]
+
+    def __setitem__(self, i, val):
+        self._data[i] = val
+
+    def _memcpy_into(self, dest):
+        #TODO find a cleaner way (that doesn't involve several copies)
+        assert _ffi.sizeof(dest._data) >= _ffi.sizeof(self._data)
+        _libc.memcpy(dest._data, self._data, _ffi.sizeof(self._data))
+
+    def swap(self, i, j):
+        self._data[i], self._data[j] = self._data[j], self._data[i]
+
+
+class I32(_Buffer):
+    _ctype = 'int32_t[]'
+    maxval = 2**31 - 1
+    minval = -(2**31)
+
+
+class U32(_Buffer):
+    _ctype = 'uint32_t[]'
+    maxval = 2**32 - 1
+    minval = 0
+
+
+class F32(_Buffer):
+    _ctype = 'double[]'
+
+
+class F64(_Buffer):
+    _ctype = 'double[]'
+
+
+class Bool(_Buffer):
+    #TODO pack multiple "bits"/bools into a char for 8x space 
+    _ctype = '_Bool[]'
+    maxval = True
+    minval = False
+
+    # needed because a cffi _Bool[] only stores 0/1
+    def __getitem__(self, i):
+        return bool(self._data[i])
+
+#TODO composites: 2xInt, 2xFloat, 3xFloat, possibly more
+
+
+class Array:
+    """An over-allocating dynamic array with primitive elements.
+
+    Backed by a buffer whose size may exceed the size of the array
+    dramatically, to perform some operations more efficiently.
+    """
+    def __init__(self, t, size=0):
+        self.dtype = t
+        capacity = 0
+        if size > 0:
+            capacity = 2**size.bit_length()
+        self._buf = t(capacity)
+        self._used = size
+
+    @property
+    def capacity(self):
+        """Size of the backing buffer."""
+        return len(self._buf)
+
+    def append(self, x):
+        """Append the value to the array.
+        
+        Occasionally has to grow the backing buffer.
+        Amortized constant time complexity.
+        """
+        if self._used == self.capacity:
+            new_capacity = max(self.capacity * 2, 1)
+            self._buf, old_buf = self.dtype(new_capacity), self._buf
+            old_buf._memcpy_into(self._buf)
+        self._buf[self._used] = x
+        self._used += 1
+
+    def pop_by_swap(self, i):
+        """Remove and return the value at index i, scrambling element order.
+        
+        Specifically, swap the last value with the value to be removed,
+        then pop() the last element.
+        Worst-case constant time and space complexity.
+        """
+        self._buf.swap(i, self._used - 1)
+        self._used -= 1
+        return self._buf[self._used]
+
+    def __len__(self):
+        # Used length, not capacity!
+        return self._used
+
+    def __getitem__(self, i):
+        if not (0 <= i < self._used):
+            raise IndexError("{} out of range(0, {})".format(i, self._used))
+        return self._buf[i]
+
+    def __setitem__(self, i, x):
+        if not (0 <= i < self._used):
+            raise IndexError("{} out of range(0, {})".format(i, self._used))
+        self._buf[i] = x
+
+    def __repr__(self):
+        def parts():
+            yield 'rawbuf.Array['
+            yield from map(str, self._buf)
+            yield ']'
+        return ' '.join(parts())
+

ttgx/tests/test_dodecs.py

+import sys
+import base64
+from operator import getitem, setitem
+from unittest.mock import Mock, call
+from pytest import fixture, raises
+import pretend
+from ttgx.dodecs import Universe, InvalidEntityError, component, dtype
+
+
+@fixture
+def u():
+    return Universe()
+
+
+@fixture
+def e():
+    return Universe().new()
+
+
+@fixture
+def x():
+    u = Universe()
+    u.register_component(ScalarC())
+    return u.comp.scalar
+
+
+@fixture
+def pos():
+    u = Universe()
+    u.register_component(PositionC())
+    return u.comp.position
+
+ScalarC = component('ScalarC', 'scalar', ['x'], x=dtype.I32)
+PositionC = component('PositionC', 'position', ['x', 'y'],
+                      x=dtype.U32, y=dtype.U32)
+
+def component_stub(ident):
+    return pretend.stub(identifier=ident)
+
+
+def system_stub(ident, *cs, step=NotImplemented):
+    return pretend.stub(identifier=ident, components=cs, step=step)
+
+
+def system_mock(ident, *cs):
+    s = Mock()
+    s.identifier = ident
+    s.components = cs
+    return s
+
+##
+
+
+def test_check_entity(u):
+    e = u.new()
+    u.check_entity(e)
+
+
+def test_distinct_entities(u):
+    assert u.new() is not u.new() is not u.new()
+
+
+def test_check_nonentity(u):
+    raises(InvalidEntityError, u.check_entity, None)
+    raises(InvalidEntityError, u.check_entity, 123)
+    raises(InvalidEntityError, u.check_entity, memoryview(bytearray()))
+    raises(InvalidEntityError, u.check_entity, test_check_nonentity)
+
+
+def test_check_foreign_entity(u, e):
+    raises(InvalidEntityError, u.check_entity, e)
+
+
+def test_entity_is_flyweight(e):
+    # This is rather implementation-dependent, but it seems like an easy way
+    # to prevent attributes (WHICH ARE BAD!) and spot missed space
+    # optimizations. The exact equality may break later though.
+    assert sys.getsizeof(e) == sys.getsizeof(object())
+
+
+def test_entity_repr(e):
+    id_bytes = id(e).to_bytes(64, byteorder='big').lstrip(b'\x00')
+    reverse_id_bytes = id_bytes[::-1]
+    full_addr = base64.b64encode(reverse_id_bytes).decode('ascii')
+    assert base64.b64decode(b'AA==') == b'\x00'
+    addr = full_addr.rstrip('=')
+    print(id(e), hex(id(e)), addr)
+    assert repr(e) == '<Entity ' + addr + '>'
+
+
+def test_entity_has_no_behavior(e):
+    e_names = set(dir(e))
+    allowed_names = set(dir(object()))
+    allowed_names |= {'__slots__', '__module__', '__qualname__', '__locals__'}
+    # __locals__ pop up if run with coverage, which I assume is a weird
+    # artifact of the implementation of trace functions, but whatever.
+    assert e_names.issubset(allowed_names), e_names - allowed_names
+
+def test_delete(u):
+    e = u.new()
+    u.delete(e)
+    raises(InvalidEntityError, u.check_entity, e)
+
+
+def test_entity_error_not_easily_swallowed(u, e):
+    assert not issubclass(InvalidEntityError, Exception)
+    assert issubclass(InvalidEntityError, BaseException)
+
+
+def test_register_component(u):
+    c = component_stub('foo')
+    u.register_component(c)
+    assert u.comp.foo is c
+    assert c.universe is u
+
+
+def test_unique_component_names(u):
+    c1 = component_stub('same')
+    c2 = component_stub('same')
+    u.register_component(c1)
+    raises(KeyError, u.register_component, c2)
+    assert u.comp.same is c1
+
+
+def test_prevent_component_reregister(u):
+    c = component_stub('foo')
+    u.register_component(c)
+    raises(RuntimeError, u.register_component, c)
+
+
+def test_nonstring_component_identifier(u):
+    class C:
+        pass
+    c = component_stub(ident=C)
+    raises(TypeError, u.register_component, c)
+
+
+def test_entity_delete_notifies_all_components(u):
+    e = u.new()
+    c = Mock()
+    c.identifier = 'quux'
+    u.register_component(c)
+    u.delete(e)
+    assert c.mock_calls == [call.discard(e)]
+
+
+def test_register_system(u):
+    s = system_stub('frobnication')
+    u.register_system(s)
+    assert u.sys.frobnication is s
+
+
+def test_prevent_system_reregister(u):
+    s = system_stub('foo')
+    u.register_system(s)
+    raises(RuntimeError, u.register_system, s)
+
+
+def test_unique_system_names(u):
+    s1 = system_stub('foo')
+    s2 = system_stub('foo')
+    u.register_system(s1)
+    raises(KeyError, u.register_system, s2)
+
+
+def test_system_step(u):
+    s = system_mock('a')
+    u.register_system(s)
+    u.step()
+    assert s.mock_calls == [call.step()]
+
+
+def test_system_uses_component(u):
+    s = system_mock('foo', 'c1', 'c2')
+    u.register_component(component_stub('c1'))
+    u.register_component(component_stub('c2'))
+    u.register_system(s)
+    u.step()
+    assert s.mock_calls == [call.step(u.comp.c1, u.comp.c2)]
+
+
+class TestScalarComponent:
+    def test_set_and_get(self, x):
+        e = x.universe.new()
+        x[e] = 1
+        assert x[e] == 1
+
+    def test_keyerror(self, x):
+        e = x.universe.new()
+        raises(KeyError, getitem, x, e)
+
+    def test_checks_entity(self, x, e):
+        # e is from a different Universe()
+        with raises(InvalidEntityError):
+            x[e]
+        with raises(InvalidEntityError):
+            x[e] = 0
+
+    def test_del_entity(self, x):
+        e = x.universe.new()
+        x[e] = -42
+        del x[e]
+        with raises(KeyError):
+            x[e]
+
+    def test_del_invalid(self, x, e):
+        with raises(InvalidEntityError):
+            del x[e]
+
+    def test_typechecks(self, x):
+        e = x.universe.new()
+        with raises(TypeError):
+            x[e] = 'hello'
+        with raises(TypeError):
+            x[e] = x
+
+class TestComplexComponent:
+    def test_set_and_get_row(self, pos):
+        e = pos.universe.new()
+        pos[e] = (3, 0)
+        assert pos[e] == (3, 0)
+
+    def test_keyerror(self, pos):
+        e = pos.universe.new()
+        raises(KeyError, getitem, pos, e)
+
+    def test_checks_entity(self, pos, e):
+        # e is from a different Universe()
+        with raises(InvalidEntityError):
+            pos[e]
+        with raises(InvalidEntityError):
+            pos[e] = (0, 0)
+
+    def test_del_entity(self, pos):
+        e = pos.universe.new()
+        pos[e] = (1024, 768)
+        del pos[e]
+        with raises(KeyError):
+            pos[e]
+
+    def test_del_invalid(self, pos, e):
+        with raises(InvalidEntityError):
+            del pos[e]
+
+    def test_typechecks(self, pos):
+        e = pos.universe.new()
+        with raises(TypeError):
+            pos[e] = 5
+        with raises(TypeError):
+            pos[e] = (2, 'top')
+
+    def test_retrieve_attrs(self, pos):
+        e = pos.universe.new()
+        pos[e] = (1, 1)
+        pos.x[e] = 2
+        pos.y[e] = 3
+        assert pos[e] == (2, 3)
+
+    def test_cannot_add_by_view(self, pos):
+        e = pos.universe.new()
+        with raises(KeyError):
+            pos.x[e] = 4
+
+    def test_cannot_del_from_view(self, pos):
+        e = pos.universe.new()
+        with raises(AttributeError) as excinfo:
+            del pos.y[e]
+        assert '__delitem__' in excinfo.value.args[0]
+
+    def test_overwriting_works(self, pos):
+        e = pos.universe.new()
+        pos[e] = (0, 0)
+        pos[e] = (1, 1)
+        assert pos[e] == (1, 1)
+        assert len(pos._x) == len(pos._y) == 1 # ugly, but to be sure...
+
+    def test_indices_are_reused_properly(self, pos):
+        e1 = pos.universe.new()
+        e2 = pos.universe.new()
+        pos[e1] = (42, 127)
+        pos[e2] = (0, 9)
+        del pos[e1]
+        pos[e1] = (42, 127)
+        assert pos[e1] == (42, 127)
+        assert pos[e2] == (0, 9)

ttgx/tests/test_rawbuf.py

+from operator import getitem, setitem
+from functools import partial
+import pytest
+from pytest import raises
+import ttgx.rawbuf as rawbuf
+
+
+_INT_TYPES = [rawbuf.I32, rawbuf.U32, rawbuf.Bool]
+_TYPES = _INT_TYPES + [rawbuf.F64, rawbuf.F32]
+_X = {rawbuf.Bool: True, rawbuf.F32: 2.3, rawbuf.F64: -4.01}
+_Y = {rawbuf.Bool: False, rawbuf.F32: -99.9, rawbuf.F64: 47.1}
+
+
+def pytest_generate_tests(metafunc):
+    if 'empty_buf' in metafunc.fixturenames:
+        param, vals = 'empty_buf', [t(0) for t in _TYPES]
+    elif 'empty_arr' in metafunc.fixturenames:
+        param, vals = 'empty_arr', [rawbuf.Array(t) for t in _TYPES]
+    elif 'buf' in metafunc.fixturenames:
+        param, vals = 'buf', [t(5) for t in _TYPES]
+    elif 'arr' in metafunc.fixturenames:
+        param, vals = 'arr', [rawbuf.Array(t, 5) for t in _TYPES]
+    elif 'intbuf' in metafunc.fixturenames:
+        param, vals = 'intbuf', [t(5) for t in _INT_TYPES]
+    else:
+        return
+    metafunc.parametrize(param, vals, ids=[t.__name__ for t in _TYPES])
+
+
+def _roundtrip(buf, val):
+    buf[0] = val
+    return buf[0]
+
+
+def _val(o, values, default, offset=None):
+    if isinstance(o, rawbuf.Array):
+        t = o.dtype
+    else:
+        t = type(o)
+    val = values.get(t, default)
+    if hasattr(t, 'maxval') and offset is not None:
+        val %= t.maxval + offset
+    return val
+
+_x = partial(_val, values=_X, default=2)
+_y = partial(_val, values=_Y, default=3)
+
+
+def test_xy_distinct(buf):
+    assert _x(buf) != _y(buf)
+
+class TestEmptyBuffer:
+    def test_length(self, empty_buf):
+        assert len(empty_buf) == 0
+
+    def test_get(self, empty_buf):
+        raises(IndexError, getitem, empty_buf, 0)
+        raises(IndexError, getitem, empty_buf, 5)
+        raises(IndexError, getitem, empty_buf, -2)
+
+    def test_set(self, empty_buf):
+        raises(IndexError, setitem, empty_buf, 0, 0)
+        raises(IndexError, setitem, empty_buf, 2, 0)
+        raises(IndexError, setitem, empty_buf, -3, 0)
+
+    def test_swap(self, empty_buf):
+        raises(IndexError, empty_buf.swap, 1, 2)
+        raises(IndexError, empty_buf.swap, -4, 7)
+        raises(IndexError, empty_buf.swap, 0, 0)
+
+
+class Test5ElementBuffer:
+    def test_length(self, buf):
+        assert len(buf) == 5
+
+    def test_zeros(self, buf):
+        for i in range(len(buf)):
+            assert buf[i] == 0
+
+    def test_swap(self, buf):
+        x = _x(buf)
+        y = _y(buf)
+        buf[0] = x
+        buf[1] = y
+        buf.swap(0, 1)
+        assert buf[0] == y
+        assert buf[1] == x
+
+    def test_set_and_get(self, buf):
+        x = _x(buf)
+        y = _y(buf)
+        buf[0] = x
+        assert buf[0] == x
+        buf[3] = y
+        assert buf[3] == y
+
+    def test_can_store_maxval(self, intbuf):
+        roundtrip = partial(_roundtrip, intbuf)
+        maxval = type(intbuf).maxval
+        assert roundtrip(maxval) == maxval
+
+    def test_ovf_raises(self, intbuf):
+        store = partial(setitem, intbuf, 0)
+        maxval = type(intbuf).maxval
+        raises(OverflowError, store, maxval + 1)
+        raises(OverflowError, store, maxval * 3)
+
+    def test_can_store_minval(self, intbuf):
+        roundtrip = partial(_roundtrip, intbuf)
+        minval = type(intbuf).minval
+        assert roundtrip(minval) == minval
+
+    def test_underflow_raises(self, intbuf):
+        store = partial(setitem, intbuf, 0)
+        minval = type(intbuf).minval
+        raises(OverflowError, store, minval - 1)
+        raises(OverflowError, store, minval * 3 - 6)
+
+## special cases for specific types
+
+def test_boolbuf_yields_booleans():
+    buf = rawbuf.Bool(2)
+    buf[0] = True
+    assert buf[0] is True
+    assert buf[1] is False
+
+## array tests
+
+def test_array_dtype(empty_arr):
+    assert empty_arr.dtype in _TYPES
+
+class TestEmptyArray:
+    def test_length(self, empty_arr):
+        assert len(empty_arr) == 0
+
+    def test_get_raises(self, empty_arr):
+        raises(IndexError, getitem, empty_arr, 0)
+        raises(IndexError, getitem, empty_arr, 4)
+        raises(IndexError, getitem, empty_arr, -2)
+
+    def test_add_increases_length(self, empty_arr):
+        empty_arr.append(_x(empty_arr))
+        assert len(empty_arr) == 1
+
+    def test_add_enables_get(self, empty_arr):
+        empty_arr.append(_x(empty_arr))
+        assert empty_arr[0] == _x(empty_arr)
+        raises(IndexError, getitem, empty_arr, 1)
+
+    def test_append_preserves_previous_values(self, empty_arr):
+        for i in range(10):
+            empty_arr.append(_x(empty_arr, offset=i))
+        # Intentionally split in two loops!
+        # We want 'add, add, ..., check, check ...' not 'add, check, add, ...'
+        for i in range(10):
+            assert empty_arr[i] == _x(empty_arr, offset=i)
+
+    def test_capacity_grows_exponentially(self, empty_arr):
+        capacities = set()
+        for i in range(18):
+            empty_arr.append(_x(empty_arr))
+            capacities.add(empty_arr.capacity)
+        assert capacities == {2**i for i in range(6)} # ceil(log2(18))
+
+class TestFiveElementArray:
+    def test_set_and_get(self, arr):
+        arr[0], arr[4] = _x(arr), _y(arr)
+        assert arr[0] == _x(arr)
+        assert arr[4] == _y(arr)
+
+    def test_length(self, arr):
+        assert len(arr) == 5
+
+    def test_capacity_rounded_up(self, arr):
+        assert arr.capacity == 8
+
+    def test_get_between_length_and_capacity_raises(self, arr):
+        raises(IndexError, getitem, arr, 6)
+
+    def test_get_between_length_and_capacity_raises(self, arr):
+        raises(IndexError, setitem, arr, 6, _x(arr))
+
+    def test_remove(self, arr):
+        arr[2], arr[4] = _x(arr), _y(arr)
+        removed = arr.pop_by_swap(2)
+        assert arr[2] == _y(arr)
+        assert removed == _x(arr)
+        raises(IndexError, getitem, arr, 4)
+