The cost of data-structure choices

from collections.abc import Hashable


def find_duplicates(items: list[Hashable]) -> list[Hashable]:
    """Items that occur more than once, each listed once, in order of their second occurrence."""
    seen = []
    reported = []
    duplicates = []
    for item in items:
        if item in seen:
            if item not in reported:
                reported.append(item)
                duplicates.append(item)
        else:
            seen.append(item)
    return duplicates

from main import find_duplicates


class Key:
    """An int wrapper that counts how often Python compares it."""

    comparisons = 0

    def __init__(self, n):
        self.n = n

    def __eq__(self, other):
        Key.comparisons += 1
        return isinstance(other, Key) and self.n == other.n

    def __hash__(self):
        return hash(self.n)

    def __repr__(self):
        return f"Key({self.n})"


def test_duplicates():
    """3 and 1 repeat: [3, 1], each once"""
    got = find_duplicates([3, 1, 3, 2, 1, 3])
    assert got == [3, 1], f"got {got!r}, expected [3, 1]"


def test_no_duplicates():
    """Distinct items give an empty list"""
    got = find_duplicates(["a", "b", "c"])
    assert got == [], f"got {got!r}, expected []"


def test_comparisons():
    """400 distinct keys need almost no == comparisons"""
    items = [Key(i) for i in range(400)] + [Key(7)]
    Key.comparisons = 0
    got = find_duplicates(items)
    assert [k.n for k in got] == [7], f"got {got!r}, expected [Key(7)]"
    assert Key.comparisons < 50, f"find_duplicates made {Key.comparisons} == comparisons; a list is scanned item by item, a set is not"

class History:
    """The last `size` events, oldest first."""

    def __init__(self, size: int) -> None:
        self.size = size
        self.events: list[str] = []

    def add(self, event: str) -> None:
        self.events.append(event)
        if len(self.events) > self.size:
            self.events.pop(0)  # shifts every other event

    def oldest(self) -> str:
        return self.events[0]

    def recent(self) -> list[str]:
        return list(self.events)

from collections import deque

from main import History


def test_keeps_last_three():
    """With size 3, adding a to e keeps c, d and e"""
    h = History(3)
    for event in "abcde":
        h.add(event)
    assert h.recent() == ["c", "d", "e"], f"recent() returned {h.recent()!r}, expected ['c', 'd', 'e']"


def test_oldest():
    """oldest() is the first event still kept"""
    h = History(2)
    for event in ["login", "view", "logout"]:
        h.add(event)
    assert h.oldest() == "view", f"oldest() returned {h.oldest()!r}, expected 'view'"


def test_uses_bounded_deque():
    """events is a deque with maxlen equal to size"""
    h = History(4)
    ok = isinstance(h.events, deque) and h.events.maxlen == 4
    assert ok, f"events is {h.events!r}; expected deque(maxlen=4), which drops the oldest item in constant time"


def test_recent_is_a_copy():
    """recent() returns a new list, not the internal store"""
    h = History(2)
    h.add("a")
    h.recent().append("x")
    assert h.recent() == ["a"], f"changing the list from recent() changed the history: {h.recent()!r}"