Source code for titan_pylib.data_structures.deque.deque

  1from typing import Iterable, Generic, TypeVar
  2
  3T = TypeVar("T")
  4
  5

[docs]
  6class Deque(Generic[T]):
  7    """Deque です。
  8    ランダムアクセスが :math:`O(1)` で可能です。
  9    """
 10
 11    def __init__(self, a: Iterable[T] = []):
 12        """
 13        :math:`O(n)` です。
 14
 15        Args:
 16          a (Iterable[T], optional): ``Deque`` を構築する配列です。
 17        """
 18        self.front: list[T] = []
 19        self.back: list[T] = list(a)
 20
 21    def _rebuild(self) -> None:
 22        new = self.front[::-1] + self.back
 23        self.front = new[: len(new) // 2][::-1]
 24        self.back = new[len(new) // 2 :]
 25

[docs]
 26    def append(self, v: T) -> None:
 27        """要素 ``v`` を末尾に追加します。
 28        :math:`O(1)` です。
 29
 30        Args:
 31          v (T): 追加する要素です。
 32        """
 33        self.back.append(v)

 34

[docs]
 35    def appendleft(self, v: T) -> None:
 36        """要素 ``v`` を先頭に追加します。
 37        :math:`O(1)` です。
 38
 39        Args:
 40          v (T): 追加する要素です。
 41        """
 42        self.front.append(v)

 43

[docs]
 44    def pop(self) -> T:
 45        """末尾の要素を削除し、その値を返します。
 46        :math:`O(1)` です。
 47        """
 48        if not self.back:
 49            self._rebuild()
 50        return self.back.pop() if self.back else self.front.pop()

 51

[docs]
 52    def popleft(self) -> T:
 53        """先頭の要素を削除し、その値を返します。
 54        :math:`O(1)` です。
 55        """
 56        if not self.front:
 57            self._rebuild()
 58        return self.front.pop() if self.front else self.back.pop()

 59

[docs]
 60    def tolist(self) -> list[T]:
 61        """``list`` に変換します。
 62        :math:`O(n)` です。
 63        """
 64        return self.front[::-1] + self.back

 65

[docs]
 66    def __getitem__(self, k: int) -> T:
 67        """``k`` 番目の要素を取得します。
 68        :math:`O(1)` です。
 69        """
 70        assert (
 71            -len(self) <= k < len(self)
 72        ), f"IndexError: {self.__class__.__name__}[{k}], len={len(self)}"
 73        if k < 0:
 74            k += len(self)
 75        return (
 76            self.front[len(self.front) - k - 1]
 77            if k < len(self.front)
 78            else self.back[k - len(self.front)]
 79        )

 80

[docs]
 81    def __setitem__(self, k: int, v: T):
 82        """``k`` 番目の要素を ``v`` に更新します。
 83        :math:`O(1)` です。
 84        """
 85        assert (
 86            -len(self) <= k < len(self)
 87        ), f"IndexError: {self.__class__.__name__}[{k} = {v}, len={len(self)}"
 88        if k < 0:
 89            k += len(self)
 90        if k < len(self.front):
 91            self.front[len(self.front) - k - 1] = v
 92        else:
 93            self.back[k - len(self.front)] = v

 94
 95    def __bool__(self):
 96        return bool(self.front or self.back)
 97

[docs]
 98    def __len__(self):
 99        """要素数を取得します。
100        :math:`O(1)` です。
101        """
102        return len(self.front) + len(self.back)

103
104    def __contains__(self, v: T):
105        return (v in self.front) or (v in self.back)
106
107    def __str__(self):
108        return str(self.tolist())
109
110    def __repr__(self):
111        return f"{self.__class__.__name__}({self})"