1# from titan_pylib.data_structures.set.static_ordered_multiset import StaticOrderedMultiset
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, Optional, TypeVar, Generic
10from bisect import bisect_right, bisect_left
11from collections import Counter
12
13T = TypeVar("T", bound=SupportsLessThan)
14
15
16class StaticOrderedMultiset(Generic[T]):
17
18 def __init__(self, a: Iterable = [T]):
19 self.l: list[T] = sorted(a)
20 self.s: Counter[T] = Counter(self.l)
21 self.n: int = len(self.l)
22
23 def ge(self, x: T) -> Optional[T]:
24 i = bisect_left(self.l, x)
25 return self.l[i] if i < self.n else None
26
27 def gt(self, x: T) -> Optional[T]:
28 i = bisect_right(self.l, x)
29 return self.l[i] if i < self.n else None
30
31 def le(self, x: T) -> Optional[T]:
32 i = bisect_right(self.l, x) - 1
33 return self.l[i] if i >= 0 else None
34
35 def lt(self, x: T) -> Optional[T]:
36 i = bisect_left(self.l, x) - 1
37 return self.l[i] if i >= 0 else None
38
39 def index(self, x: T) -> int:
40 return bisect_left(self.l, x)
41
42 def index_right(self, x: T) -> int:
43 return bisect_right(self.l, x)
44
45 def count(self, x: T) -> int:
46 return self.s[x]
47
48 def len_elm(self) -> int:
49 return len(self.s)
50
51 def __getitem__(self, k: int) -> T:
52 return self.l[k]
53
54 def __contains__(self, x: T):
55 return x in self.s
56
57 def __len__(self):
58 return self.n
59
60 def __str__(self):
61 return "{" + ", ".join(map(str, self.l)) + "}"
62
63 def __repr__(self):
64 return "StaticOrderedMultiset([" + ", ".join(map(str, self.l)) + "])"