"""Sorted array-backed set for small collections.

Ported from net.i2p.util.ArraySet.
"""

from __future__ import annotations

import bisect
from typing import Iterator


class ArraySet:
    """Sorted set backed by a list, efficient for small collections."""

    def __init__(self) -> None:
        self._data: list = []

    def add(self, item) -> None:
        idx = bisect.bisect_left(self._data, item)
        if idx < len(self._data) and self._data[idx] == item:
            return
        self._data.insert(idx, item)

    def remove(self, item) -> None:
        idx = bisect.bisect_left(self._data, item)
        if idx < len(self._data) and self._data[idx] == item:
            self._data.pop(idx)
        else:
            raise KeyError(item)

    def __contains__(self, item) -> bool:
        idx = bisect.bisect_left(self._data, item)
        return idx < len(self._data) and self._data[idx] == item

    def __len__(self) -> int:
        return len(self._data)

    def __iter__(self) -> Iterator:
        return iter(self._data)