foldable_stack¶
ソースコード¶
from titan_pylib.data_structures.stack.foldable_stack import FoldableStack
展開済みコード¶
1# from titan_pylib.data_structures.stack.foldable_stack import FoldableStack
2from typing import Generic, Iterable, TypeVar, Callable, Union
3
4T = TypeVar("T")
5
6
7class FoldableStack(Generic[T]):
8
9 def __init__(
10 self, n_or_a: Union[int, Iterable[T]], op: Callable[[T, T], T], e: T
11 ) -> None:
12 self._op = op
13 self._e = e
14 if isinstance(n_or_a, int):
15 self._n = n_or_a
16 self._a = [e] * self._n
17 else:
18 n_or_a = list(n_or_a)
19 self._n = len(n_or_a)
20 self._a = list(n_or_a)
21 self._data = [e] * (self._n + 1)
22 for i in range(self._n):
23 self._data[i + 1] = op(self._data[i], self._a[i])
24
25 def append(self, key: T) -> None:
26 self._a.append(key)
27 self._data.append(self._op(self._data[-1], key))
28
29 def top(self) -> T:
30 return self._a[-1]
31
32 def pop(self) -> T:
33 self._data.pop()
34 return self._a.pop()
35
36 def all_prod(self) -> T:
37 return self._data[-1]
38
39 def prod(self, r: int) -> T:
40 return self._data[r]
41
42 def tolist(self) -> list[T]:
43 return list(self._a)
44
45 def __len__(self):
46 return len(self._a)