1# from titan_pylib.data_structures.set.static_ordered_set import StaticOrderedSet
2# from titan_pylib.my_class.supports_less_than import SupportsLessThan
3from typing import Protocol
4
5
6class SupportsLessThan(Protocol):
7
8 def __lt__(self, other) -> bool: ...
9from typing import Iterable, TypeVar, Generic, Optional
10from bisect import bisect_right, bisect_left
11
12T = TypeVar("T", bound=SupportsLessThan)
13
14
15class StaticOrderedSet(Generic[T]):
16
17 def __init__(self, a: Iterable = [T]):
18 self.s: set[T] = set(a)
19 self.l: list[T] = sorted(self.s)
20 self.n: int = len(self.l)
21
22 def ge(self, x: T) -> Optional[T]:
23 i = bisect_left(self.l, x)
24 return self.l[i] if i < self.n else None
25
26 def gt(self, x: T) -> Optional[T]:
27 i = bisect_right(self.l, x)
28 return self.l[i] if i < self.n else None
29
30 def le(self, x: T) -> Optional[T]:
31 i = bisect_right(self.l, x) - 1
32 return self.l[i] if i >= 0 else None
33
34 def lt(self, x: T) -> Optional[T]:
35 i = bisect_left(self.l, x) - 1
36 return self.l[i] if i >= 0 else None
37
38 def index(self, x: T) -> int:
39 return bisect_left(self.l, x)
40
41 def index_right(self, x: T) -> int:
42 return bisect_right(self.l, x)
43
44 def __getitem__(self, k: int) -> T:
45 return self.l[k]
46
47 def __contains__(self, x: T):
48 return x in self.s
49
50 def __len__(self):
51 return self.n
52
53 def __str__(self):
54 return "{" + ", ".join(map(str, self.l)) + "}"
55
56 def __repr__(self):
57 return f"StaticOrderedSet({self})"