Source code for titan_pylib.data_structures.set.static_ordered_multiset

 1from titan_pylib.my_class.supports_less_than import SupportsLessThan
 2from typing import Iterable, Optional, TypeVar, Generic
 3from bisect import bisect_right, bisect_left
 4from collections import Counter
 5
 6T = TypeVar("T", bound=SupportsLessThan)
 7
 8

[docs]
 9class StaticOrderedMultiset(Generic[T]):
10
11    def __init__(self, a: Iterable = [T]):
12        self.l: list[T] = sorted(a)
13        self.s: Counter[T] = Counter(self.l)
14        self.n: int = len(self.l)
15

[docs]
16    def ge(self, x: T) -> Optional[T]:
17        i = bisect_left(self.l, x)
18        return self.l[i] if i < self.n else None

19

[docs]
20    def gt(self, x: T) -> Optional[T]:
21        i = bisect_right(self.l, x)
22        return self.l[i] if i < self.n else None

23

[docs]
24    def le(self, x: T) -> Optional[T]:
25        i = bisect_right(self.l, x) - 1
26        return self.l[i] if i >= 0 else None

27

[docs]
28    def lt(self, x: T) -> Optional[T]:
29        i = bisect_left(self.l, x) - 1
30        return self.l[i] if i >= 0 else None

31

[docs]
32    def index(self, x: T) -> int:
33        return bisect_left(self.l, x)

34

[docs]
35    def index_right(self, x: T) -> int:
36        return bisect_right(self.l, x)

37

[docs]
38    def count(self, x: T) -> int:
39        return self.s[x]

40

[docs]
41    def len_elm(self) -> int:
42        return len(self.s)

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 "StaticOrderedMultiset([" + ", ".join(map(str, self.l)) + "])"