Indexed sequence with checkpoints

Build a growable array that can take cheap snapshots. The spec arrives in three parts; finish and test each part before the next.

Part 1. append(value) -> index, pop() -> value, get(index), set(index, value) and len(). Indexes run from 0 to len - 1; anything else raises IndexError (no negative indexing).

Part 2. checkpoint() -> id returns ids 0, 1, 2, …. get_at(id, index) returns the value index had when that checkpoint was taken, and len_at(id) the length then. Writes made after checkpoint() returns are not part of it. An index that did not exist at the checkpoint raises IndexError; an unknown checkpoint raises KeyError. A checkpoint must not copy the array: assume 10^5 items and 10^4 checkpoints.

Part 3. rollback(id) makes the live array equal checkpoint id again. Checkpoint id stays valid; every later checkpoint is forgotten, and the next checkpoint() returns id + 1. Rollback must not scan the whole array.

class IndexedSequence:
    def __len__(self) -> int: ...
    def append(self, value) -> int: ...
    def pop(self): ...
    def get(self, index: int): ...
    def set(self, index: int, value) -> None: ...
    def checkpoint(self) -> int: ...
    def get_at(self, checkpoint: int, index: int): ...
    def len_at(self, checkpoint: int) -> int: ...
    def rollback(self, checkpoint: int) -> None: ...

Example

s.append(10); s.append(20)
c0 = s.checkpoint()        # 0
s.set(0, 11); s.append(30)
s.get_at(c0, 0)  -> 10
s.get_at(c0, 2)  -> IndexError   (index 2 did not exist at c0)
s.rollback(c0)
len(s) -> 2, s.get(0) -> 10
s.checkpoint()   -> 1