Source code for titan_pylib.data_structures.deque.foldable_deque

 1from titan_pylib.data_structures.stack.foldable_stack import FoldableStack
 2from typing import Generic, Iterable, TypeVar, Callable, Union
 3
 4T = TypeVar("T")
 5
 6

[docs]
 7class FoldableDeque(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        self.front: FoldableStack[T] = FoldableStack(0, op, e)
15        self.back: FoldableStack[T] = FoldableStack(n_or_a, op, e)
16
17    def _rebuild(self) -> None:
18        new = self.front.tolist()[::-1] + self.back.tolist()
19        self.front = FoldableStack(new[: len(new) // 2][::-1], self._op, self._e)
20        self.back = FoldableStack(new[len(new) // 2 :], self._op, self._e)
21

[docs]
22    def tolist(self) -> list[T]:
23        return self.front.tolist()[::-1] + self.back.tolist()

24

[docs]
25    def append(self, v: T) -> None:
26        self.back.append(v)

27

[docs]
28    def appendleft(self, v: T) -> None:
29        self.front.append(v)

30

[docs]
31    def pop(self) -> T:
32        if not self.back:
33            self._rebuild()
34        return self.back.pop() if self.back else self.front.pop()

35

[docs]
36    def popleft(self) -> T:
37        if not self.front:
38            self._rebuild()
39        return self.front.pop() if self.front else self.back.pop()

40

[docs]
41    def all_prod(self) -> T:
42        return self._op(self.front.all_prod(), self.back.all_prod())

43
44    def __len__(self):
45        return len(self.front) + len(self.back)