Struct nekolib::ds::FoldableDeque

pub struct FoldableDeque<M: Monoid> { /* private fields */ }

fold 可能両端キュー。

モノイドを要素とする両端キューであって、全体のモノイド積を計算できる。 逆元がある演算であれば、単に要素を一つ持って計算すればよい。

Idea

スタックを二つ使って両端キューを実現できることを応用する¹。 モノイド積に関する方針は FoldableQueue と同じ。

Complexity

演算	時間計算量
new	$\Theta(1)$
push_back, push_front	$\Theta(1)$
pop_back, pop_front	amortized $\Theta(1)$
fold	$\Theta(1)$

キューを実現する場合と異なり、pop したい側の stack が空の際は、 他方の stack から半分（奇数なら切り上げ）だけ要素をもらってくるようにする。 各スタックの要素数の差の絶対値をポテンシャルとすることで、ならし定数時間が示せる。

Examples

use nekolib::ds::FoldableDeque;
use nekolib::traits::{Fold, PopBack, PopFront, PushBack, PushFront};
use nekolib::utils::OpMin;

let mut fq = FoldableDeque::<OpMin<i32>>::new();
assert_eq!(fq.fold(..), std::i32::MAX);
fq.push_back(6);
assert_eq!(fq.fold(..), 6);
fq.push_back(3);
assert_eq!(fq.fold(..), 3);
fq.push_front(4);
assert_eq!(fq.fold(..), 3);
fq.pop_back();
assert_eq!(fq.fold(..), 4);
fq.pop_front();
assert_eq!(fq.fold(..), 6);
fq.pop_back();
assert_eq!(fq.fold(..), std::i32::MAX);

---

1. 内部的には std::VecDeque を使ってスタックを実現しているため、 両端キュー二つで両端キューを実現していることになっている。ギャグ？ ↩

Implementations

impl<M: Monoid> FoldableDeque<M>where M::Set: Clone,

pub fn new() -> Selfwhere M: Default,

pub fn with(monoid: M) -> Self

Trait Implementations

impl<M: Clone + Monoid> Clone for FoldableDeque<M>where M::Set: Clone,

fn clone(&self) -> FoldableDeque<M>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<M: Debug + Monoid> Debug for FoldableDeque<M>where M::Set: Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<M> Default for FoldableDeque<M>where M: Default + Monoid, M::Set: Clone,

fn default() -> Self

Returns the “default value” for a type.

impl<M: Monoid> Fold<RangeFull> for FoldableDeque<M>where M::Set: Clone,

type Output = M

fn fold(&self, _: RangeFull) -> M::Set

r で指定される区間の和を返す。

impl<M: Monoid> PopBack for FoldableDeque<M>where M::Set: Clone,

type Output = <M as Magma>::Set

fn pop_back(&mut self) -> Option<Self::Output>

impl<M: Monoid> PopFront for FoldableDeque<M>where M::Set: Clone,

type Output = <M as Magma>::Set

fn pop_front(&mut self) -> Option<Self::Output>

impl<M: Monoid> PushBack for FoldableDeque<M>where M::Set: Clone,

type Input = <M as Magma>::Set

fn push_back(&mut self, x: Self::Input)

impl<M: Monoid> PushFront for FoldableDeque<M>where M::Set: Clone,

type Input = <M as Magma>::Set

fn push_front(&mut self, x: Self::Input)