Source code for titan_pylib.data_structures.set.static_ordered_set

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

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

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

18

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

22

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

26

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

30

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

33

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

36
37    def __getitem__(self, k: int) -> T:
38        return self.l[k]
39
40    def __contains__(self, x: T):
41        return x in self.s
42
43    def __len__(self):
44        return self.n
45
46    def __str__(self):
47        return "{" + ", ".join(map(str, self.l)) + "}"
48
49    def __repr__(self):
50        return f"StaticOrderedSet({self})"