Insert, delete and getRandom in O(1)

"""Two obvious raffle boxes, each with one slow call, and the work each call does counted.

ListBox keeps the tickets in a list: a draw reads one position, but insert and remove search the list, and a removal
shifts every ticket after the hole. SetBox keeps them in a set: insert and remove are O(1) on average, but a set has
no positions, so pick(r) walks through r of its tickets."""
import json


class ListBox:
    def __init__(self):
        self.tickets, self.work = [], 0

    def insert(self, t):
        self.work += len(self.tickets)  # the search for t
        if t in self.tickets:
            return False
        self.tickets.append(t)
        return True

    def remove(self, t):
        self.work += len(self.tickets)  # the search, then the shift of everything after the hole
        if t not in self.tickets:
            return False
        self.tickets.remove(t)
        return True

    def size(self):
        return len(self.tickets)

    def pick(self, r):
        self.work += 1
        return self.tickets[r]


class SetBox:
    def __init__(self):
        self.tickets, self.work = set(), 0

    def insert(self, t):
        self.work += 1
        if t in self.tickets:
            return False
        self.tickets.add(t)
        return True

    def remove(self, t):
        self.work += 1
        if t not in self.tickets:
            return False
        self.tickets.remove(t)
        return True

    def size(self):
        return len(self.tickets)

    def pick(self, r):
        for i, t in enumerate(self.tickets):  # no positions: walk to the r-th ticket of the iteration
            self.work += 1
            if i == r:
                return t


def replay(box, ops, args):
    return [None] + [getattr(box, op)(*a) for op, a in zip(ops[1:], args[1:])]


def fair_day(box_class, n):
    """n tickets sold, then 2n calls: a refund and a new sale (the refunds hit the oldest tickets), and a draw."""
    box = box_class()
    for t in range(1, n + 1):
        box.insert(t)
    start = box.work
    for i in range(n // 2):
        box.remove(i + 1)
        box.insert(n + 1 + i)
        box.pick(box.size() - 1 - i % box.size())
        box.pick(i % box.size())
    return box.work - start


if __name__ == "__main__":
    ops = ["RaffleBox", "insert", "insert", "insert", "remove", "insert", "remove", "size"]
    args = [[], [501], [502], [501], [503], [503], [501], []]
    for box_class in (ListBox, SetBox):
        box = box_class()
        answers = replay(box, ops, args)
        print(f"{box_class.__name__}: {json.dumps(answers)}, tickets {sorted(box.pick(r) for r in range(box.size()))}")
    print()
    print(f"{'tickets':>8} {'calls':>7} {'ListBox work':>13} {'per call':>9} {'SetBox work':>12} {'per call':>9}")
    for n in (500, 1_000, 2_000, 4_000):
        lw, sw = fair_day(ListBox, n), fair_day(SetBox, n)
        print(f"{n:>8,} {2 * n:>7,} {lw:>13,} {lw / (2 * n):>9,.0f} {sw:>12,} {sw / (2 * n):>9,.0f}")

ListBox: [null, true, true, false, false, true, true, 2], tickets [502, 503]
SetBox: [null, true, true, false, false, true, true, 2], tickets [502, 503]

 tickets   calls  ListBox work  per call  SetBox work  per call
     500   1,000       250,250       250      125,750       126
   1,000   2,000     1,000,500       500      501,500       251
   2,000   4,000     4,001,000     1,000    2,003,000       501
   4,000   8,000    16,002,000     2,000    8,006,000     1,001