Foldable Deque
(DataStructure/misc/FoldableDeque.py)

• View this file on GitHub
• Last update: 2022-09-12 01:37:24+09:00

概要

両端キューの操作をサポートし、両端キュー全体の畳み込みを $O(1)$ で行えるデータ構造。畳み込みは半群を要請する。

使い方

FoldableDeque(op: Callable[[Any, Any], Any])
空の両端キューを構築する。op は畳み込みの二項演算。計算量 $O(1)$

• __len__() -> int
  両端キューの大きさを返す。計算量 $O(1)$

• all_fold() -> Any
  両端キュー全体の畳み込み結果を返す。計算量 $O(1)$

• append(val: Any) -> None
  キューの末尾に要素 val を追加する。計算量 $O(1)$

• append(val: Any) -> None
  キューの先頭に要素 val を追加する。計算量 $O(1)$

• pop() -> Any
  キューの末尾要素を削除し、その要素を返す。計算量 $\mathrm{amortized}\ O(1)$

• popleft() -> Any
  キューの先頭要素を削除し、その要素を返す。計算量 $\mathrm{amortized}\ O(1)$

Verified with

• TestCase/LibraryChecker/deque_operate_all_composite.test.py

Code

class FoldableDeque:
    def __init__(self, op):
        self.op = op
        self.front = []
        self.back = []

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

    def _trans(self):
        half = len(self) // 2
        if len(self.front) == 0:
            stack = []
            while self:
                stack.append(self.back.pop()[0])
            for i in range(half, len(stack)):
                self.append(stack[i])
            for i in reversed(range(0, half)):
                self.appendleft(stack[i])
        else:
            stack = []
            while self:
                stack.append(self.front.pop()[0])
            for i in range(half, len(stack)):
                self.appendleft(stack[i])
            for i in reversed(range(0, half)):
                self.append(stack[i])

    def fold_all(self):
        if not self.front:
            return self.back[-1][1]
        if not self.back:
            return self.front[-1][1]
        return self.op(self.back[-1][1], self.front[-1][1])

    def append(self, val):
        if self.front:
            self.front.append((val, self.op(self.front[-1][1], val)))
        else:
            self.front.append((val, val))

    def appendleft(self, val):
        if self.back:
            self.back.append((val, self.op(val, self.back[-1][1])))
        else:
            self.back.append((val, val))

    def pop(self):
        if not self.front:
            self._trans()
        val = self.front.pop()
        return val[0]

    def popleft(self):
        if not self.back:
            self._trans()
        val = self.back.pop()
        return val[0]

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page