Struct DequeAggregation 

pub struct DequeAggregation<M>
where
    M: Monoid,
{
    front_stack: Vec<(M::T, M::T)>,
    back_stack: Vec<(M::T, M::T)>,
}

Fields

front_stack: Vec<(M::T, M::T)>

back_stack: Vec<(M::T, M::T)>

Implementations

impl<M> DequeAggregation<M>

where M: Monoid,

pub fn new() -> Self

Examples found in repository

crates/library_checker/src/data_structure/deque_operate_all_composite.rs (line 20)

pub fn deque_operate_all_composite(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(q);
    let mut deq = DequeAggregation::<LinearOperation<_>>::new();
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::PushFront { ab } => {
                deq.push_front(ab);
            }
            Query::PushBack { ab } => {
                deq.push_back(ab);
            }
            Query::PopFront => {
                deq.pop_front();
            }
            Query::PopBack => {
                deq.pop_back();
            }
            Query::Apply { x } => {
                let (a, b) = deq.fold_all();
                pp!(a * x + b);
            }
        }
    }
}

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn fold_all(&self) -> M::T

Examples found in repository

crates/library_checker/src/data_structure/deque_operate_all_composite.rs (line 37)

pub fn deque_operate_all_composite(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(q);
    let mut deq = DequeAggregation::<LinearOperation<_>>::new();
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::PushFront { ab } => {
                deq.push_front(ab);
            }
            Query::PushBack { ab } => {
                deq.push_back(ab);
            }
            Query::PopFront => {
                deq.pop_front();
            }
            Query::PopBack => {
                deq.pop_back();
            }
            Query::Apply { x } => {
                let (a, b) = deq.fold_all();
                pp!(a * x + b);
            }
        }
    }
}

pub fn front(&self) -> Option<&M::T>

pub fn back(&self) -> Option<&M::T>

pub fn push_front(&mut self, value: M::T)

Examples found in repository

crates/competitive/src/data_structure/sliding_window_aggregation.rs (line 193)

    pub fn pop_front(&mut self) -> Option<M::T> {
        if self.front_stack.is_empty() {
            let n = self.back_stack.len();
            let mut back_stack = std::mem::take(&mut self.back_stack);
            for x in back_stack.drain(..n.div_ceil(2)).map(|t| t.1).rev() {
                self.push_front(x);
            }
            for x in back_stack.drain(..).map(|t| t.1) {
                self.push_back(x);
            }
        }
        self.front_stack.pop().map(|t| t.1)
    }
    pub fn pop_back(&mut self) -> Option<M::T> {
        if self.back_stack.is_empty() {
            let n = self.front_stack.len();
            let mut front_stack = std::mem::take(&mut self.front_stack);
            for x in front_stack.drain(..n.div_ceil(2)).map(|t| t.1).rev() {
                self.push_back(x);
            }
            for x in front_stack.drain(..).map(|t| t.1) {
                self.push_front(x);
            }
        }
        self.back_stack.pop().map(|t| t.1)
    }

crates/library_checker/src/data_structure/deque_operate_all_composite.rs (line 25)

pub fn deque_operate_all_composite(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(q);
    let mut deq = DequeAggregation::<LinearOperation<_>>::new();
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::PushFront { ab } => {
                deq.push_front(ab);
            }
            Query::PushBack { ab } => {
                deq.push_back(ab);
            }
            Query::PopFront => {
                deq.pop_front();
            }
            Query::PopBack => {
                deq.pop_back();
            }
            Query::Apply { x } => {
                let (a, b) = deq.fold_all();
                pp!(a * x + b);
            }
        }
    }
}

pub fn push_back(&mut self, value: M::T)

Examples found in repository

crates/competitive/src/data_structure/sliding_window_aggregation.rs (line 196)

    pub fn pop_front(&mut self) -> Option<M::T> {
        if self.front_stack.is_empty() {
            let n = self.back_stack.len();
            let mut back_stack = std::mem::take(&mut self.back_stack);
            for x in back_stack.drain(..n.div_ceil(2)).map(|t| t.1).rev() {
                self.push_front(x);
            }
            for x in back_stack.drain(..).map(|t| t.1) {
                self.push_back(x);
            }
        }
        self.front_stack.pop().map(|t| t.1)
    }
    pub fn pop_back(&mut self) -> Option<M::T> {
        if self.back_stack.is_empty() {
            let n = self.front_stack.len();
            let mut front_stack = std::mem::take(&mut self.front_stack);
            for x in front_stack.drain(..n.div_ceil(2)).map(|t| t.1).rev() {
                self.push_back(x);
            }
            for x in front_stack.drain(..).map(|t| t.1) {
                self.push_front(x);
            }
        }
        self.back_stack.pop().map(|t| t.1)
    }

crates/library_checker/src/data_structure/deque_operate_all_composite.rs (line 28)

pub fn deque_operate_all_composite(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(q);
    let mut deq = DequeAggregation::<LinearOperation<_>>::new();
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::PushFront { ab } => {
                deq.push_front(ab);
            }
            Query::PushBack { ab } => {
                deq.push_back(ab);
            }
            Query::PopFront => {
                deq.pop_front();
            }
            Query::PopBack => {
                deq.pop_back();
            }
            Query::Apply { x } => {
                let (a, b) = deq.fold_all();
                pp!(a * x + b);
            }
        }
    }
}

pub fn pop_front(&mut self) -> Option<M::T>

Examples found in repository

crates/library_checker/src/data_structure/deque_operate_all_composite.rs (line 31)

pub fn deque_operate_all_composite(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(q);
    let mut deq = DequeAggregation::<LinearOperation<_>>::new();
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::PushFront { ab } => {
                deq.push_front(ab);
            }
            Query::PushBack { ab } => {
                deq.push_back(ab);
            }
            Query::PopFront => {
                deq.pop_front();
            }
            Query::PopBack => {
                deq.pop_back();
            }
            Query::Apply { x } => {
                let (a, b) = deq.fold_all();
                pp!(a * x + b);
            }
        }
    }
}

pub fn pop_back(&mut self) -> Option<M::T>

Examples found in repository

crates/library_checker/src/data_structure/deque_operate_all_composite.rs (line 34)

pub fn deque_operate_all_composite(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(q);
    let mut deq = DequeAggregation::<LinearOperation<_>>::new();
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::PushFront { ab } => {
                deq.push_front(ab);
            }
            Query::PushBack { ab } => {
                deq.push_back(ab);
            }
            Query::PopFront => {
                deq.pop_front();
            }
            Query::PopBack => {
                deq.pop_back();
            }
            Query::Apply { x } => {
                let (a, b) = deq.fold_all();
                pp!(a * x + b);
            }
        }
    }
}

Trait Implementations

impl<M> Clone for DequeAggregation<M>

where M: Monoid,

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<M> Debug for DequeAggregation<M>

where M: Monoid<T: Debug>,

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

Formats the value using the given formatter.

impl<M> Default for DequeAggregation<M>

where M: Monoid,

fn default() -> Self

Returns the “default value” for a type.