Struct nekolib::ds::FoldableDeque

source ·
pub struct FoldableDeque<M: Monoid> { /* private fields */ }
Expand description

fold 可能両端キュー。

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

Idea

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

Complexity

演算時間計算量
new$\Theta(1)$
push_back, push_front$\Theta(1)$
pop_back, pop_frontamortized $\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§

source§

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

source§

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

§

type Output = M

source§

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

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

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

§

type Output = <M as Magma>::Set

source§

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

source§

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

§

type Output = <M as Magma>::Set

source§

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

source§

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

§

type Input = <M as Magma>::Set

source§

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

source§

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

§

type Input = <M as Magma>::Set

source§

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

Auto Trait Implementations§

§

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

§

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

§

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

§

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

§

impl<M> UnwindSafe for FoldableDeque<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