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