Struct TreeHasher 

pub struct TreeHasher {
    rv: Vec<u64>,
    rng: Xorshift,
}

Fields

rv: Vec<u64>

rng: Xorshift

Implementations

impl TreeHasher

const MASK30: u64

const MASK31: u64

const MASK61: u64

const MOD: u64 = Self::MASK61

fn mersenne_mod(a: u64) -> u64

Examples found in repository

crates/competitive/src/tree/tree_hash.rs (line 40)

    fn mersenne_mul_mod(a: u64, b: u64) -> u64 {
        Self::mersenne_mod(Self::mersenne_mul(a, b))
    }
    pub fn new() -> Self {
        Self {
            rv: Vec::new(),
            rng: Xorshift::new(),
        }
    }
    pub fn with_seed(seed: u64) -> Self {
        Self {
            rv: Vec::new(),
            rng: Xorshift::new_with_seed(seed),
        }
    }
    pub fn hash(&mut self, g: &UndirectedSparseGraph) -> u64 {
        match g.tree_center() {
            TreeCenter::One(u) => self.hash_rec(g, u, !0, 0),
            TreeCenter::Two(u, v) => {
                Self::mersenne_mul_mod(self.hash_rooted(g, u, v), self.hash_rooted(g, v, u))
            }
        }
    }
    pub fn hash_rooted(&mut self, g: &UndirectedSparseGraph, root: usize, parent: usize) -> u64 {
        self.hash_rec(g, root, parent, 0)
    }
    fn hash_rec(&mut self, g: &UndirectedSparseGraph, u: usize, p: usize, d: usize) -> u64 {
        let mut s = 1u64;
        if self.rv.len() <= d {
            self.rv.push(Self::mersenne_mod(self.rng.rand64()));
        }
        for a in g.neighbors(u) {
            if a.to != p {
                s = Self::mersenne_mul_mod(s, self.hash_rec(g, a.to, u, d + 1));
            }
        }
        s += self.rv[d];
        if s >= Self::MOD {
            s -= Self::MOD;
        }
        s
    }

fn mersenne_mul(a: u64, b: u64) -> u64

Examples found in repository

crates/competitive/src/tree/tree_hash.rs (line 40)

    fn mersenne_mul_mod(a: u64, b: u64) -> u64 {
        Self::mersenne_mod(Self::mersenne_mul(a, b))
    }

fn mersenne_mul_mod(a: u64, b: u64) -> u64

Examples found in repository

crates/competitive/src/tree/tree_hash.rs (line 58)

    pub fn hash(&mut self, g: &UndirectedSparseGraph) -> u64 {
        match g.tree_center() {
            TreeCenter::One(u) => self.hash_rec(g, u, !0, 0),
            TreeCenter::Two(u, v) => {
                Self::mersenne_mul_mod(self.hash_rooted(g, u, v), self.hash_rooted(g, v, u))
            }
        }
    }
    pub fn hash_rooted(&mut self, g: &UndirectedSparseGraph, root: usize, parent: usize) -> u64 {
        self.hash_rec(g, root, parent, 0)
    }
    fn hash_rec(&mut self, g: &UndirectedSparseGraph, u: usize, p: usize, d: usize) -> u64 {
        let mut s = 1u64;
        if self.rv.len() <= d {
            self.rv.push(Self::mersenne_mod(self.rng.rand64()));
        }
        for a in g.neighbors(u) {
            if a.to != p {
                s = Self::mersenne_mul_mod(s, self.hash_rec(g, a.to, u, d + 1));
            }
        }
        s += self.rv[d];
        if s >= Self::MOD {
            s -= Self::MOD;
        }
        s
    }

pub fn new() -> Self

pub fn with_seed(seed: u64) -> Self

pub fn hash(&mut self, g: &UndirectedSparseGraph) -> u64

pub fn hash_rooted( &mut self, g: &UndirectedSparseGraph, root: usize, parent: usize, ) -> u64

Examples found in repository

crates/competitive/src/tree/tree_hash.rs (line 58)

    pub fn hash(&mut self, g: &UndirectedSparseGraph) -> u64 {
        match g.tree_center() {
            TreeCenter::One(u) => self.hash_rec(g, u, !0, 0),
            TreeCenter::Two(u, v) => {
                Self::mersenne_mul_mod(self.hash_rooted(g, u, v), self.hash_rooted(g, v, u))
            }
        }
    }

fn hash_rec( &mut self, g: &UndirectedSparseGraph, u: usize, p: usize, d: usize, ) -> u64

Examples found in repository

crates/competitive/src/tree/tree_hash.rs (line 56)

    pub fn hash(&mut self, g: &UndirectedSparseGraph) -> u64 {
        match g.tree_center() {
            TreeCenter::One(u) => self.hash_rec(g, u, !0, 0),
            TreeCenter::Two(u, v) => {
                Self::mersenne_mul_mod(self.hash_rooted(g, u, v), self.hash_rooted(g, v, u))
            }
        }
    }
    pub fn hash_rooted(&mut self, g: &UndirectedSparseGraph, root: usize, parent: usize) -> u64 {
        self.hash_rec(g, root, parent, 0)
    }
    fn hash_rec(&mut self, g: &UndirectedSparseGraph, u: usize, p: usize, d: usize) -> u64 {
        let mut s = 1u64;
        if self.rv.len() <= d {
            self.rv.push(Self::mersenne_mod(self.rng.rand64()));
        }
        for a in g.neighbors(u) {
            if a.to != p {
                s = Self::mersenne_mul_mod(s, self.hash_rec(g, a.to, u, d + 1));
            }
        }
        s += self.rv[d];
        if s >= Self::MOD {
            s -= Self::MOD;
        }
        s
    }

Trait Implementations

impl Debug for TreeHasher

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

Formats the value using the given formatter.

impl Default for TreeHasher

fn default() -> Self

Returns the “default value” for a type.