deque¶
ソースコード¶
from titan_pylib.data_structures.deque.deque import Deque
展開済みコード¶
1# from titan_pylib.data_structures.deque.deque import Deque
2from typing import Iterable, Generic, TypeVar
3
4T = TypeVar("T")
5
6
7class Deque(Generic[T]):
8 """Deque です。
9 ランダムアクセスが :math:`O(1)` で可能です。
10 """
11
12 def __init__(self, a: Iterable[T] = []):
13 """
14 :math:`O(n)` です。
15
16 Args:
17 a (Iterable[T], optional): ``Deque`` を構築する配列です。
18 """
19 self.front: list[T] = []
20 self.back: list[T] = list(a)
21
22 def _rebuild(self) -> None:
23 new = self.front[::-1] + self.back
24 self.front = new[: len(new) // 2][::-1]
25 self.back = new[len(new) // 2 :]
26
27 def append(self, v: T) -> None:
28 """要素 ``v`` を末尾に追加します。
29 :math:`O(1)` です。
30
31 Args:
32 v (T): 追加する要素です。
33 """
34 self.back.append(v)
35
36 def appendleft(self, v: T) -> None:
37 """要素 ``v`` を先頭に追加します。
38 :math:`O(1)` です。
39
40 Args:
41 v (T): 追加する要素です。
42 """
43 self.front.append(v)
44
45 def pop(self) -> T:
46 """末尾の要素を削除し、その値を返します。
47 :math:`O(1)` です。
48 """
49 if not self.back:
50 self._rebuild()
51 return self.back.pop() if self.back else self.front.pop()
52
53 def popleft(self) -> T:
54 """先頭の要素を削除し、その値を返します。
55 :math:`O(1)` です。
56 """
57 if not self.front:
58 self._rebuild()
59 return self.front.pop() if self.front else self.back.pop()
60
61 def tolist(self) -> list[T]:
62 """``list`` に変換します。
63 :math:`O(n)` です。
64 """
65 return self.front[::-1] + self.back
66
67 def __getitem__(self, k: int) -> T:
68 """``k`` 番目の要素を取得します。
69 :math:`O(1)` です。
70 """
71 assert (
72 -len(self) <= k < len(self)
73 ), f"IndexError: {self.__class__.__name__}[{k}], len={len(self)}"
74 if k < 0:
75 k += len(self)
76 return (
77 self.front[len(self.front) - k - 1]
78 if k < len(self.front)
79 else self.back[k - len(self.front)]
80 )
81
82 def __setitem__(self, k: int, v: T):
83 """``k`` 番目の要素を ``v`` に更新します。
84 :math:`O(1)` です。
85 """
86 assert (
87 -len(self) <= k < len(self)
88 ), f"IndexError: {self.__class__.__name__}[{k} = {v}, len={len(self)}"
89 if k < 0:
90 k += len(self)
91 if k < len(self.front):
92 self.front[len(self.front) - k - 1] = v
93 else:
94 self.back[k - len(self.front)] = v
95
96 def __bool__(self):
97 return bool(self.front or self.back)
98
99 def __len__(self):
100 """要素数を取得します。
101 :math:`O(1)` です。
102 """
103 return len(self.front) + len(self.back)
104
105 def __contains__(self, v: T):
106 return (v in self.front) or (v in self.back)
107
108 def __str__(self):
109 return str(self.tolist())
110
111 def __repr__(self):
112 return f"{self.__class__.__name__}({self})"