Source code for titan_pylib.data_structures.set.min_max_set

 1from titan_pylib.my_class.supports_less_than import SupportsLessThan
 2from titan_pylib.data_structures.heap.double_ended_heap import DoubleEndedHeap
 3from typing import Generic, Iterable, TypeVar
 4
 5T = TypeVar("T", bound=SupportsLessThan)
 6
 7

[docs]
 8class MinMaxSet(Generic[T]):
 9
10    def __init__(self, a: Iterable[T] = []):
11        a = set(a)
12        self.data = a
13        self.heap = DoubleEndedHeap(a)
14

[docs]
15    def add(self, key: T) -> bool:
16        if key not in self.data:
17            self.heap.add(key)
18            self.data.add(key)
19            return True
20        return False

21

[docs]
22    def discard(self, key: T) -> bool:
23        if key in self.data:
24            self.data.discard(key)
25            return True
26        return False

27

[docs]
28    def pop_min(self) -> T:
29        while True:
30            v = self.heap.pop_min()
31            if v in self.data:
32                self.data.discard(v)
33                return v

34

[docs]
35    def pop_max(self) -> T:
36        while True:
37            v = self.heap.pop_max()
38            if v in self.data:
39                self.data.discard(v)
40                return v

41

[docs]
42    def get_min(self) -> T:
43        while True:
44            v = self.heap.get_min()
45            if v in self.data:
46                return v
47            else:
48                self.heap.pop_min()

49

[docs]
50    def get_max(self) -> T:
51        while True:
52            v = self.heap.get_max()
53            if v in self.data:
54                return v
55            else:
56                self.heap.pop_max()

57

[docs]
58    def tolist(self) -> list[T]:
59        return sorted(self.data)

60
61    def __contains__(self, key: T):
62        return key in self.data
63
64    def __getitem__(self, k: int):  # 末尾と先頭のみ
65        if k == -1 or k == len(self.data) - 1:
66            return self.get_max()
67        elif k == 0:
68            return self.get_min()
69        raise IndexError
70
71    def __len__(self):
72        return len(self.data)
73
74    def __str__(self):
75        return "{" + ", ".join(map(str, sorted(self.data))) + "}"
76
77    def __repr__(self):
78        return f"MinMaxSet({self})"