Struct nekolib::ds::FoldableQueue

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

fold 可能キュー。

いわゆる SWAG (Sliding Window Aggregation)。 モノイドを要素とするキューであって、全体のモノイド積を計算できる。 逆元がある演算であれば、単に要素を一つ持って計算すればよい。

Idea

スタックを二つ使ってキューを実現できることを応用する。 モノイド積を管理するスタックも二つ用意する。 後者のスタックそれぞれの top が、対応する前者のスタック中の要素の総積となるように管理する。 これにより、キュー全体としての積は、二つの要素の積として計算できる。

Implementation notes

fold() だけを考えると front stack には元の値を入れる必要はないが、 pop() の際の挙動を標準の VecDeque などと合わせたかったので、含めることにした。 fold した値を返すということにすれば含めなくて済むが、あまりそうしたくなかったので。

Complexity

演算	時間計算量
new	$\Theta(1)$
push (push_back)	$\Theta(1)$
pop (pop_front)	amortized $\Theta(1)$
fold	$\Theta(1)$

pop の計算量は、two-stack queue のならし解析から従う。 わかりやすい資料として CS166 を挙げておく。

Examples

use nekolib::ds::FoldableQueue;
use nekolib::traits::{Fold, Pop, Push};
use nekolib::utils::OpMin;

let mut fq = FoldableQueue::<OpMin<i32>>::new();
assert_eq!(fq.fold(..), std::i32::MAX);
fq.push(6);
assert_eq!(fq.fold(..), 6);
fq.push(3);
assert_eq!(fq.fold(..), 3);
fq.push(4);
assert_eq!(fq.fold(..), 3);
fq.pop();
assert_eq!(fq.fold(..), 3);
fq.pop();
assert_eq!(fq.fold(..), 4);

Implementations

impl<M: Monoid> FoldableQueue<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 FoldableQueue<M>where M::Set: Clone,

fn clone(&self) -> FoldableQueue<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 FoldableQueue<M>where M::Set: Debug,

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

Formats the value using the given formatter.

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

fn default() -> Self

Returns the “default value” for a type.

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

type Output = M

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

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

impl<M: Monoid> Pop for FoldableQueue<M>where M::Set: Clone,

type Output = <M as Magma>::Set

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

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

type Output = <M as Magma>::Set

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

impl<M: Monoid> Push for FoldableQueue<M>where M::Set: Clone,

type Input = <M as Magma>::Set

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

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

type Input = <M as Magma>::Set

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