persistent_stack¶
ソースコード¶
from titan_pylib.data_structures.stack.persistent_stack import PersistentStack
展開済みコード¶
1# from titan_pylib.data_structures.stack.persistent_stack import PersistentStack
2from typing import Iterable, Optional, TypeVar, Generic
3
4T = TypeVar("T")
5
6
7class PersistentStack(Generic[T]):
8
9 class Node:
10
11 def __init__(self, key: Optional[T], prev=None):
12 self.key: Optional[T] = key
13 self.prev: Optional[PersistentStack.Node] = prev
14
15 def __init__(
16 self,
17 a: Iterable[T] = [],
18 init_t: int = -1,
19 _prev: Optional["PersistentStack"] = None,
20 ):
21 self.prev: Optional[PersistentStack] = _prev
22 stack = PersistentStack.Node(None, None)
23 for e in a:
24 stack = PersistentStack.Node(e, prev=stack)
25 self.a: dict[int, PersistentStack.Node] = {init_t: stack}
26
27 def top(self, t: int) -> T:
28 res = self.a[t].key
29 assert (
30 res is not None
31 ), f"IndexError: top() from empty {self.__class__.__name__}."
32 return res
33
34 def append(self, key: T, pre_t: int, new_t: int) -> None:
35 s = self.a[pre_t]
36 new_stack = PersistentStack.Node(key, s)
37 self.a[new_t] = new_stack
38
39 def pop(self, pre_t: int, new_t: int) -> T:
40 s = self.a[pre_t]
41 assert (
42 s.key is not None
43 ), f"IndexError: pop() from empty {self.__class__.__name__}."
44 self.a[new_t] = PersistentStack.Node(None) if s.prev is None else s.prev
45 return s.key
46
47 def tolist(self, t: int) -> list[T]:
48 a = []
49 stack = self.a[t]
50 while stack.prev is not None:
51 a.append(stack.key)
52 stack = stack.prev
53 return a[::-1]
仕様¶
- class PersistentStack(a: Iterable[T] = [], init_t: int = -1, _prev: PersistentStack | None = None)[source]¶
Bases:
Generic[T]