distributed.camp
A Python port of the Invisible Internet Project (I2P)
1"""Sorted array-backed set for small collections.
2
3Ported from net.i2p.util.ArraySet.
4"""
5
6from __future__ import annotations
7
8import bisect
9from typing import Iterator
10
11
12class ArraySet:
13 """Sorted set backed by a list, efficient for small collections."""
14
15 def __init__(self) -> None:
16 self._data: list = []
17
18 def add(self, item) -> None:
19 idx = bisect.bisect_left(self._data, item)
20 if idx < len(self._data) and self._data[idx] == item:
21 return
22 self._data.insert(idx, item)
23
24 def remove(self, item) -> None:
25 idx = bisect.bisect_left(self._data, item)
26 if idx < len(self._data) and self._data[idx] == item:
27 self._data.pop(idx)
28 else:
29 raise KeyError(item)
30
31 def __contains__(self, item) -> bool:
32 idx = bisect.bisect_left(self._data, item)
33 return idx < len(self._data) and self._data[idx] == item
34
35 def __len__(self) -> int:
36 return len(self._data)
37
38 def __iter__(self) -> Iterator:
39 return iter(self._data)