OA: Snapshot Set Iterator

A metadata service keeps a set of integer file ids. Readers want to walk the set while writers keep changing it, and a reader must see the set exactly as it was when the walk started.

Implement class SnapshotSet:

• add(x: int) -> bool: add x; True if it was new, False if it was already there (the set is unchanged).
• remove(x: int) -> bool: remove x; True if it was there, False otherwise.
• contains(x: int) -> bool
• size() -> int: how many elements the set holds now.
• iterator() -> SnapshotIterator: an iterator over the elements present at this moment.

A SnapshotIterator has:

• has_next() -> bool
• next() -> int: the next element; raises StopIteration when there are none left.

Rules:

• Elements come out in insertion order: the order of the add calls that put them in. Adding an element that is already present doesn't move it. An element that is removed and later added again counts as newly inserted, so it goes to the end.
• Later add/remove calls must not change what an existing iterator produces, whether it has started or not. Several iterators can be in use at once, each with its own snapshot.
• add, remove, contains and size must be O(1) on average.

s = SnapshotSet()
s.add(5); s.add(2); s.add(9)
it = s.iterator()
s.remove(2); s.add(4); s.add(2)
it.next()            # 5
it.next()            # 2   still in its snapshot
it.next()            # 9
it.has_next()        # False
it2 = s.iterator()   # produces 5, 9, 4, 2
s.add(5)             # False, already present, stays first

For this level, iterator() may copy the current elements.