Struct SbtNode 

pub struct SbtNode<T>
where
    T: Unsigned,
{
    pub l: URational<T>,
    pub r: URational<T>,
}

Fields

l: URational<T>

r: URational<T>

Implementations

impl<T> SbtNode<T>

where T: Unsigned,

pub fn to_path(&self) -> SbtPath<T>

pub fn lca<I, J>(path1: I, path2: J) -> Self

where I: IntoIterator<Item = T>, J: IntoIterator<Item = T>,

Examples found in repository

crates/library_checker/src/number_theory/stern_brocot_tree.rs (line 58)

pub fn stern_brocot_tree(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(t);
    for _ in 0..t {
        sc!(query: Query);
        match query {
            Query::EncodePath { a, b } => {
                let path = SbtPath::from(URational::new(a, b));
                let len = if path.path.first() == Some(&0) {
                    path.path.len() - 1
                } else {
                    path.path.len()
                };
                pp!(len, !);
                for (i, count) in path.into_iter().enumerate() {
                    if count == 0 {
                        continue;
                    }
                    if i % 2 == 0 {
                        pp!(@ns " R ", count, !);
                    } else {
                        pp!(@ns " L ", count, !);
                    }
                }
                pp!();
            }
            Query::DecodePath { path, .. } => {
                let node: SbtNode<u32> = if path.first().is_some_and(|t| t.0 == 'L') {
                    [0].into_iter()
                        .chain(path.into_iter().map(|(_, c)| c))
                        .collect()
                } else {
                    path.into_iter().map(|(_, c)| c).collect()
                };
                let val = node.eval();
                pp!(val.num, val.den);
            }
            Query::Lca { a, b, c, d } => {
                let path1 = SbtPath::from(URational::new(a, b));
                let path2 = SbtPath::from(URational::new(c, d));
                let val = SbtNode::lca(path1, path2).eval();
                pp!(val.num, val.den);
            }
            Query::Ancestor { k, a, b } => {
                let mut path = SbtPath::from(URational::new(a, b));
                let depth = path.depth();
                if k <= depth {
                    path.up(depth - k);
                    let val = path.eval();
                    pp!(val.num, val.den);
                } else {
                    pp!("-1");
                }
            }
            Query::Range { a, b } => {
                let node = SbtPath::from(URational::new(a, b)).to_node();
                pp!(node.l.num, node.l.den, node.r.num, node.r.den);
            }
        }
    }
}

Trait Implementations

impl<T> Clone for SbtNode<T>

where T: Unsigned + Clone,

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T> Copy for SbtNode<T>

where T: Unsigned + Copy,

impl<T> Debug for SbtNode<T>

where T: Unsigned + Debug,

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

Formats the value using the given formatter.

impl<T> Eq for SbtNode<T>

where T: Unsigned + Eq,

impl<T> From<URational<T>> for SbtNode<T>

where T: Unsigned,

fn from(r: URational<T>) -> Self

Converts to this type from the input type.

impl<T> FromIterator<T> for SbtNode<T>

where T: Unsigned,

fn from_iter<I>(iter: I) -> Self

where I: IntoIterator<Item = T>,

Creates a value from an iterator.

impl<T> PartialEq for SbtNode<T>

where T: Unsigned + PartialEq,

fn eq(&self, other: &Self) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

impl<T> SternBrocotTree for SbtNode<T>

where T: Unsigned,

type T = T

fn root() -> Self

fn is_root(&self) -> bool

fn eval(&self) -> URational<Self::T>

fn down_left(&mut self, count: Self::T)

fn down_right(&mut self, count: Self::T)

fn up(&mut self, count: Self::T) -> Self::T

Returns the remaining count after moving up.

impl<T> StructuralPartialEq for SbtNode<T>

where T: Unsigned + PartialEq,