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

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§

source§

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

source

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

source

pub fn with(monoid: M) -> Self

Trait Implementations§

source§

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

source§

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

Returns a copy of the value. Read more
1.0.0 · source§

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

Performs copy-assignment from source. Read more
source§

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

source§

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

Formats the value using the given formatter. Read more
source§

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

source§

fn default() -> Self

Returns the “default value” for a type. Read more
source§

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

§

type Output = M

source§

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

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

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

§

type Output = <M as Magma>::Set

source§

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

source§

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

§

type Output = <M as Magma>::Set

source§

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

source§

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

§

type Input = <M as Magma>::Set

source§

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

source§

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

§

type Input = <M as Magma>::Set

source§

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

Auto Trait Implementations§

§

impl<M> RefUnwindSafe for FoldableQueue<M>where M: RefUnwindSafe, <M as Magma>::Set: RefUnwindSafe,

§

impl<M> Send for FoldableQueue<M>where M: Send, <M as Magma>::Set: Send,

§

impl<M> Sync for FoldableQueue<M>where M: Sync, <M as Magma>::Set: Sync,

§

impl<M> Unpin for FoldableQueue<M>where M: Unpin, <M as Magma>::Set: Unpin,

§

impl<M> UnwindSafe for FoldableQueue<M>where M: UnwindSafe, <M as Magma>::Set: UnwindSafe,

Blanket Implementations§

source§

impl<T> Any for Twhere T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for Twhere T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for Twhere T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for Twhere U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> ToOwned for Twhere T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for Twhere U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for Twhere U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
§

impl<V, T> VZip<V> for Twhere V: MultiLane<T>,

§

fn vzip(self) -> V