Enum UfCell 

pub enum UfCell<U, M, P>
where
    U: UnionStrategy,
    M: UfMergeSpec,
    P: Monoid,
{
    Root((U::Info, M::Data)),
    Child((usize, P::T)),
}

Variants

Root((U::Info, M::Data))

Child((usize, P::T))

Implementations

impl<U, M, P> UfCell<U, M, P>

where U: UnionStrategy, M: UfMergeSpec, P: Monoid,

fn root_mut(&mut self) -> Option<&mut (U::Info, M::Data)>

Examples found in repository

crates/competitive/src/data_structure/union_find.rs (line 417)

    pub fn unite_noninv(&mut self, x: usize, y: usize, potential: P::T) -> bool {
        let (rx, potx) = self.find(x);
        let ry = self.find_root(y);
        if rx == ry || y != ry {
            return false;
        }
        H::unite(&mut self.history, rx, ry, &self.cells);
        {
            let ptr = self.cells.as_mut_ptr();
            let (cx, cy) = unsafe { (&mut *ptr.add(rx), &mut *ptr.add(ry)) };
            self.merger
                .merge(&mut cx.root_mut().unwrap().1, &mut cy.root_mut().unwrap().1);
        }
        *self.root_info_mut(rx).unwrap() =
            U::unite(&self.root_info(rx).unwrap(), &self.root_info(ry).unwrap());
        self.cells[ry] = UfCell::Child((rx, P::operate(&potx, &potential)));
        true
    }
}

impl<U, F, M, P, H> UnionFindBase<U, F, M, P, H>
where
    U: UnionStrategy,
    F: FindStrategy,
    M: UfMergeSpec,
    P: Group,
    H: UndoStrategy<UfCell<U, M, P>>,
{
    pub fn difference(&mut self, x: usize, y: usize) -> Option<P::T> {
        let (rx, potx) = self.find(x);
        let (ry, poty) = self.find(y);
        if rx == ry {
            Some(P::operate(&P::inverse(&potx), &poty))
        } else {
            None
        }
    }

    pub fn unite_with(&mut self, x: usize, y: usize, potential: P::T) -> bool {
        let (mut rx, potx) = self.find(x);
        let (mut ry, poty) = self.find(y);
        if rx == ry {
            return false;
        }
        let mut xinfo = self.root_info(rx).unwrap();
        let mut yinfo = self.root_info(ry).unwrap();
        let inverse = !U::check_directoin(&xinfo, &yinfo);
        let potential = if inverse {
            P::rinv_operate(&poty, &P::operate(&potx, &potential))
        } else {
            P::operate(&potx, &P::rinv_operate(&potential, &poty))
        };
        if inverse {
            swap(&mut rx, &mut ry);
            swap(&mut xinfo, &mut yinfo);
        }
        H::unite(&mut self.history, rx, ry, &self.cells);
        {
            let ptr = self.cells.as_mut_ptr();
            let (cx, cy) = unsafe { (&mut *ptr.add(rx), &mut *ptr.add(ry)) };
            self.merger
                .merge(&mut cx.root_mut().unwrap().1, &mut cy.root_mut().unwrap().1);
        }
        *self.root_info_mut(rx).unwrap() = U::unite(&xinfo, &yinfo);
        self.cells[ry] = UfCell::Child((rx, potential));
        true
    }

fn child_mut(&mut self) -> Option<&mut (usize, P::T)>

Examples found in repository

crates/competitive/src/data_structure/union_find.rs (line 376)

    pub fn find(&mut self, x: usize) -> (usize, P::T) {
        let (parent_parent, parent_potential) = match &self.cells[x] {
            UfCell::Child((parent, _)) => self.find(*parent),
            UfCell::Root(_) => return (x, P::unit()),
        };
        let (parent, potential) = self.cells[x].child_mut().unwrap();
        let potential = if F::CHENGE_ROOT {
            *parent = parent_parent;
            *potential = P::operate(&parent_potential, potential);
            potential.clone()
        } else {
            P::operate(&parent_potential, potential)
        };
        (parent_parent, potential)
    }

    pub fn find_root(&mut self, x: usize) -> usize {
        let (parent, parent_parent) = match &self.cells[x] {
            UfCell::Child((parent, _)) => (*parent, self.find_root(*parent)),
            UfCell::Root(_) => return x,
        };
        if F::CHENGE_ROOT {
            let (cx, cp) = {
                let ptr = self.cells.as_mut_ptr();
                unsafe { (&mut *ptr.add(x), &*ptr.add(parent)) }
            };
            let (parent, potential) = cx.child_mut().unwrap();
            *parent = parent_parent;
            if let UfCell::Child((_, ppot)) = &cp {
                *potential = P::operate(ppot, potential);
            }
        }
        parent_parent
    }

Trait Implementations

impl<U, M, P> Clone for UfCell<U, M, P>

where U: UnionStrategy<Info: Clone>, M: UfMergeSpec<Data: Clone>, P: Monoid,

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<U, M, P> Debug for UfCell<U, M, P>

where U: UnionStrategy<Info: Debug>, M: UfMergeSpec<Data: Debug>, P: Monoid<T: Debug>,

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

Formats the value using the given formatter.