bst_multiset_node_base¶
ソースコード¶
from titan_pylib.data_structures.bst_base.bst_multiset_node_base import BSTMultisetNodeBase
展開済みコード¶
1# from titan_pylib.data_structures.bst_base.bst_multiset_node_base import BSTMultisetNodeBase
2from typing import TypeVar, Generic, Optional
3
4T = TypeVar("T")
5Node = TypeVar("Node")
6# protcolで、key,val,left,right を規定
7
8
9class BSTMultisetNodeBase(Generic[T, Node]):
10
11 @staticmethod
12 def count(node, key: T) -> int:
13 while node is not None:
14 if node.key == key:
15 return node.val
16 node = node.left if key < node.key else node.right
17 return 0
18
19 @staticmethod
20 def get_min(node: Node) -> Optional[T]:
21 if not node:
22 return None
23 while node.left:
24 node = node.left
25 return node.key
26
27 @staticmethod
28 def get_max(node: Node) -> Optional[T]:
29 if not node:
30 return None
31 while node.right:
32 node = node.right
33 return node.key
34
35 @staticmethod
36 def contains(node: Node, key: T) -> bool:
37 while node:
38 if key == node.key:
39 return True
40 node = node.left if key < node.key else node.right
41 return False
42
43 @staticmethod
44 def tolist(node: Node) -> list[T]:
45 stack = []
46 a = []
47 while stack or node:
48 if node:
49 stack.append(node)
50 node = node.left
51 else:
52 node = stack.pop()
53 for _ in range(node.val):
54 a.append(node.key)
55 node = node.right
56 return a
57
58 @staticmethod
59 def tolist_items(node: Node) -> list[tuple[T, int]]:
60 stack = []
61 a = []
62 while stack or node:
63 if node:
64 stack.append(node)
65 node = node.left
66 else:
67 node = stack.pop()
68 a.append((node.key, node.val))
69 node = node.right
70 return a
71
72 @staticmethod
73 def _rle(a: list[T]) -> tuple[list[T], list[int]]:
74 keys, vals = [], []
75 keys.append(a[0])
76 vals.append(1)
77 for i, elm in enumerate(a):
78 if i == 0:
79 continue
80 if elm == keys[-1]:
81 vals[-1] += 1
82 continue
83 keys.append(elm)
84 vals.append(1)
85 return keys, vals
86
87 @staticmethod
88 def le(node: Node, key: T) -> Optional[T]:
89 res = None
90 while node is not None:
91 if key == node.key:
92 res = key
93 break
94 if key < node.key:
95 node = node.left
96 else:
97 res = node.key
98 node = node.right
99 return res
100
101 @staticmethod
102 def lt(node: Node, key: T) -> Optional[T]:
103 res = None
104 while node is not None:
105 if key <= node.key:
106 node = node.left
107 else:
108 res = node.key
109 node = node.right
110 return res
111
112 @staticmethod
113 def ge(node: Node, key: T) -> Optional[T]:
114 res = None
115 while node is not None:
116 if key == node.key:
117 res = key
118 break
119 if key < node.key:
120 res = node.key
121 node = node.left
122 else:
123 node = node.right
124 return res
125
126 @staticmethod
127 def gt(node: Node, key: T) -> Optional[T]:
128 res = None
129 while node is not None:
130 if key < node.key:
131 res = node.key
132 node = node.left
133 else:
134 node = node.right
135 return res
136
137 @staticmethod
138 def index(node: Node, key: T) -> int:
139 k = 0
140 while node:
141 if key == node.key:
142 if node.left:
143 k += node.left.valsize
144 break
145 if key < node.key:
146 node = node.left
147 else:
148 k += node.val if node.left is None else node.left.valsize + node.val
149 node = node.right
150 return k
151
152 @staticmethod
153 def index_right(node: Node, key: T) -> int:
154 k = 0
155 while node:
156 if key == node.key:
157 k += node.val if node.left is None else node.left.valsize + node.val
158 break
159 if key < node.key:
160 node = node.left
161 else:
162 k += node.val if node.left is None else node.left.valsize + node.val
163 node = node.right
164 return k