Struct PartiallyRetroactivePriorityQueue

pub struct PartiallyRetroactivePriorityQueue<T>
where
    T: Clone + Ord + Bounded,
{ /* private fields */ }

max-heap

Implementations

impl<T> PartiallyRetroactivePriorityQueue<T>

where T: Clone + Ord + Bounded,

pub fn new(n: usize) -> Self

pub unsafe fn set_push_unchecked(&mut self, i: usize, x: T) -> Option<T>

Examples found in repository

crates/competitive/src/data_structure/partially_retroactive_priority_queue.rs (line 217)

    pub fn set_push(&mut self, i: usize, x: T) -> Changed<T> {
        assert!(i < self.n);
        let mut changed = self.set_no_op(i);
        changed.inserted[1] = unsafe { self.set_push_unchecked(i, x) };
        changed
    }

pub unsafe fn unset_pop_unchecked(&mut self, i: usize) -> Option<T>

Examples found in repository

crates/competitive/src/data_structure/partially_retroactive_priority_queue.rs (line 208)

    pub fn set_no_op(&mut self, i: usize) -> Changed<T> {
        assert!(i < self.n);
        let mut changed = Changed::default();
        let (max, Reverse(k)) = self.in_edges.get(i);
        let (min, kk) = self.out_edges.get(i);
        if k != i && kk != i {
            return changed;
        }
        if i == k && max == T::minimum() || i == kk && min == T::minimum() {
            changed.inserted[0] = unsafe { self.unset_pop_unchecked(i) };
        } else {
            changed.removed[0] = unsafe { self.unset_push_unchecked(i) };
        }
        changed
    }

pub unsafe fn set_pop_unchecked(&mut self, i: usize) -> Option<T>

Examples found in repository

crates/competitive/src/data_structure/partially_retroactive_priority_queue.rs (line 223)

    pub fn set_pop(&mut self, i: usize) -> Changed<T> {
        assert!(i < self.n);
        let mut changed = self.set_no_op(i);
        changed.removed[1] = unsafe { self.set_pop_unchecked(i) };
        changed
    }

pub unsafe fn unset_push_unchecked(&mut self, i: usize) -> Option<T>

Examples found in repository

crates/competitive/src/data_structure/partially_retroactive_priority_queue.rs (line 210)

    pub fn set_no_op(&mut self, i: usize) -> Changed<T> {
        assert!(i < self.n);
        let mut changed = Changed::default();
        let (max, Reverse(k)) = self.in_edges.get(i);
        let (min, kk) = self.out_edges.get(i);
        if k != i && kk != i {
            return changed;
        }
        if i == k && max == T::minimum() || i == kk && min == T::minimum() {
            changed.inserted[0] = unsafe { self.unset_pop_unchecked(i) };
        } else {
            changed.removed[0] = unsafe { self.unset_push_unchecked(i) };
        }
        changed
    }

pub fn set_no_op(&mut self, i: usize) -> Changed<T>

Examples found in repository

crates/competitive/src/data_structure/partially_retroactive_priority_queue.rs (line 216)

    pub fn set_push(&mut self, i: usize, x: T) -> Changed<T> {
        assert!(i < self.n);
        let mut changed = self.set_no_op(i);
        changed.inserted[1] = unsafe { self.set_push_unchecked(i, x) };
        changed
    }
    pub fn set_pop(&mut self, i: usize) -> Changed<T> {
        assert!(i < self.n);
        let mut changed = self.set_no_op(i);
        changed.removed[1] = unsafe { self.set_pop_unchecked(i) };
        changed
    }

pub fn set_push(&mut self, i: usize, x: T) -> Changed<T>

pub fn set_pop(&mut self, i: usize) -> Changed<T>

Trait Implementations

impl<T> Clone for PartiallyRetroactivePriorityQueue<T>

where T: Clone + Ord + Bounded + Clone,

fn clone(&self) -> PartiallyRetroactivePriorityQueue<T>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T> Debug for PartiallyRetroactivePriorityQueue<T>

where T: Clone + Ord + Bounded + Debug,

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

Formats the value using the given formatter.