Struct XorBasis

pub struct XorBasis { /* private fields */ }

Basis of xor operation.

Implementations

impl XorBasis

pub fn new() -> Self

Create a empty space.

pub fn reduce(&self, x: u64) -> (u64, u64)

Return (reduced basis, coordinate). Coordinate means if i-th bit is 1, x was reduced by i-th inserted basis.

Examples found in repository

crates/competitive/src/algorithm/xorbasis.rs (line 27)

    pub fn insert(&mut self, x: u64) -> bool {
        let (y, coord) = self.reduce(x);
        if y != 0 {
            self.bases.push((y, coord, x));
        }
        y != 0
    }
    /// Return coordinate if element can be consisted by current basis.
    pub fn find(&self, x: u64) -> Option<u64> {
        let (y, coord) = self.reduce(x);
        if y == 0 { Some(coord) } else { None }
    }
    /// Return coordinate if element can be consisted by current basis.
    pub fn basis(&self, x: u64) -> Option<Vec<u64>> {
        let (y, coord) = self.reduce(x);
        if y == 0 {
            Some(
                self.bases
                    .iter()
                    .enumerate()
                    .filter_map(|(i, (_, _, b))| {
                        if coord & (1 << i) != 0 {
                            Some(*b)
                        } else {
                            None
                        }
                    })
                    .collect(),
            )
        } else {
            None
        }
    }

pub fn insert(&mut self, x: u64) -> bool

Return true if inserted element cannot be consisted by current basis and be added as a new basis. Return false if inserted element can be consisted by current basis.

Examples found in repository

crates/competitive/src/algorithm/xorbasis.rs (line 64)

    fn from_iter<T: IntoIterator<Item = u64>>(iter: T) -> Self {
        let mut basis = XorBasis::default();
        for x in iter {
            basis.insert(x);
        }
        basis
    }

pub fn find(&self, x: u64) -> Option<u64>

Return coordinate if element can be consisted by current basis.

pub fn basis(&self, x: u64) -> Option<Vec<u64>>

Return coordinate if element can be consisted by current basis.

Trait Implementations

impl Clone for XorBasis

fn clone(&self) -> XorBasis

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for XorBasis

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

Formats the value using the given formatter.

impl Default for XorBasis

fn default() -> XorBasis

Returns the “default value” for a type.

impl FromIterator<u64> for XorBasis

fn from_iter<T: IntoIterator<Item = u64>>(iter: T) -> Self

Creates a value from an iterator.