Struct URational

pub struct URational<T>
where
    T: Unsigned,
{
    pub num: T,
    pub den: T,
}

Fields

num: T

den: T

Implementations

impl<T> URational<T>

where T: Unsigned,

pub fn new(num: T, den: T) -> Self

Examples found in repository

crates/competitive/src/algorithm/stern_brocot_tree.rs (line 145)

    fn root() -> Self {
        Self {
            l: URational::new(T::zero(), T::one()),
            r: URational::new(T::one(), T::zero()),
        }
    }

crates/competitive/src/num/urational.rs (line 78)

    pub fn map<U>(self, mut f: impl FnMut(T) -> U) -> URational<U>
    where
        U: Unsigned,
    {
        URational::new(f(self.num), f(self.den))
    }
    pub fn map_unchecked<U>(self, mut f: impl FnMut(T) -> U) -> URational<U>
    where
        U: Unsigned,
    {
        URational::new_unchecked(f(self.num), f(self.den))
    }
    pub fn map_eval<U>(self, mut f: impl FnMut(T) -> U) -> <U as Div>::Output
    where
        U: Div,
    {
        f(self.num) / f(self.den)
    }
}

impl<T> Bounded for URational<T>
where
    T: Unsigned,
{
    fn maximum() -> Self {
        Self::new_unchecked(T::one(), T::zero())
    }
    fn minimum() -> Self {
        Self::zero()
    }
}

impl<T> Zero for URational<T>
where
    T: Unsigned,
{
    fn zero() -> Self {
        Self::new_unchecked(T::zero(), T::one())
    }
}
impl<T> One for URational<T>
where
    T: Unsigned,
{
    fn one() -> Self {
        Self::new_unchecked(T::one(), T::one())
    }
}

impl<T> Add for URational<T>
where
    T: Unsigned,
{
    type Output = Self;
    fn add(self, rhs: Self) -> Self::Output {
        Self::new(self.num * rhs.den + self.den * rhs.num, self.den * rhs.den)
    }
}
impl<T> Sub for URational<T>
where
    T: Unsigned,
{
    type Output = Self;
    fn sub(self, rhs: Self) -> Self::Output {
        Self::new(self.num * rhs.den - self.den * rhs.num, self.den * rhs.den)
    }
}
impl<T> Mul for URational<T>
where
    T: Unsigned,
{
    type Output = Self;
    fn mul(self, rhs: Self) -> Self::Output {
        Self::new(self.num * rhs.num, self.den * rhs.den)
    }
}
impl<T> Div for URational<T>
where
    T: Unsigned,
{
    type Output = Self;
    fn div(self, rhs: Self) -> Self::Output {
        Self::new(self.num * rhs.den, self.den * rhs.num)
    }

crates/library_checker/src/math/stern_brocot_tree.rs (line 18)

pub fn stern_brocot_tree(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, t);
    for _ in 0..t {
        scan!(scanner, type_: String);
        match type_.as_str() {
            "ENCODE_PATH" => {
                scan!(scanner, a: u32, b: u32);
                let path = SbtPath::from(URational::new(a, b));
                let len = if path.path.first() == Some(&0) {
                    path.path.len() - 1
                } else {
                    path.path.len()
                };
                write!(writer, "{}", len).ok();
                for (i, count) in path.into_iter().enumerate() {
                    if count == 0 {
                        continue;
                    }
                    if i % 2 == 0 {
                        write!(writer, " R {}", count).ok();
                    } else {
                        write!(writer, " L {}", count).ok();
                    }
                }
                writeln!(writer).ok();
            }
            "DECODE_PATH" => {
                scan!(scanner, k, path: [(char, u32); k]);
                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();
                writeln!(writer, "{} {}", val.num, val.den).ok();
            }
            "LCA" => {
                scan!(scanner, [a, b, c, d]: [u32; const 4]);
                let path1 = SbtPath::from(URational::new(a, b));
                let path2 = SbtPath::from(URational::new(c, d));
                let val = SbtNode::lca(path1, path2).eval();
                writeln!(writer, "{} {}", val.num, val.den).ok();
            }
            "ANCESTOR" => {
                scan!(scanner, [k, a, b]: [u32; const 3]);
                let mut path = SbtPath::from(URational::new(a, b));
                let depth = path.depth();
                if k <= depth {
                    path.up(depth - k);
                    let val = path.eval();
                    writeln!(writer, "{} {}", val.num, val.den).ok();
                } else {
                    writeln!(writer, "-1").ok();
                }
            }
            "RANGE" => {
                scan!(scanner, [a, b]: [u32; const 2]);
                let node = SbtPath::from(URational::new(a, b)).to_node();
                writeln!(
                    writer,
                    "{} {} {} {}",
                    node.l.num, node.l.den, node.r.num, node.r.den
                )
                .ok();
            }
            _ => unreachable!(),
        }
    }
}

pub fn new_unchecked(num: T, den: T) -> Self

Examples found in repository

crates/competitive/src/num/urational.rs (line 66)

    pub fn new(num: T, den: T) -> Self {
        let g = num.gcd(den);
        Self::new_unchecked(num / g, den / g)
    }
    pub fn new_unchecked(num: T, den: T) -> Self {
        Self { num, den }
    }
    pub fn eval(self) -> T {
        self.num / self.den
    }
    pub fn map<U>(self, mut f: impl FnMut(T) -> U) -> URational<U>
    where
        U: Unsigned,
    {
        URational::new(f(self.num), f(self.den))
    }
    pub fn map_unchecked<U>(self, mut f: impl FnMut(T) -> U) -> URational<U>
    where
        U: Unsigned,
    {
        URational::new_unchecked(f(self.num), f(self.den))
    }
    pub fn map_eval<U>(self, mut f: impl FnMut(T) -> U) -> <U as Div>::Output
    where
        U: Div,
    {
        f(self.num) / f(self.den)
    }
}

impl<T> Bounded for URational<T>
where
    T: Unsigned,
{
    fn maximum() -> Self {
        Self::new_unchecked(T::one(), T::zero())
    }
    fn minimum() -> Self {
        Self::zero()
    }
}

impl<T> Zero for URational<T>
where
    T: Unsigned,
{
    fn zero() -> Self {
        Self::new_unchecked(T::zero(), T::one())
    }
}
impl<T> One for URational<T>
where
    T: Unsigned,
{
    fn one() -> Self {
        Self::new_unchecked(T::one(), T::one())
    }

crates/competitive/src/algorithm/stern_brocot_tree.rs (line 155)

    fn eval(&self) -> URational<Self::T> {
        URational::new_unchecked(self.l.num + self.r.num, self.l.den + self.r.den)
    }

pub fn eval(self) -> T

pub fn map<U>(self, f: impl FnMut(T) -> U) -> URational<U>

where U: Unsigned,

pub fn map_unchecked<U>(self, f: impl FnMut(T) -> U) -> URational<U>

where U: Unsigned,

pub fn map_eval<U>(self, f: impl FnMut(T) -> U) -> <U as Div>::Output

where U: Div,

Trait Implementations

impl<T> Add for URational<T>

where T: Unsigned,

type Output = URational<T>

The resulting type after applying the + operator.

fn add(self, rhs: Self) -> Self::Output

Performs the + operation.

impl<T> AddAssign for URational<T>

where T: Unsigned,

fn add_assign(&mut self, rhs: Self)

Performs the += operation.

impl<T> Bounded for URational<T>

where T: Unsigned,

fn maximum() -> Self

fn minimum() -> Self

fn is_maximum(&self) -> bool

fn is_minimum(&self) -> bool

fn set_maximum(&mut self)

fn set_minimum(&mut self)

impl<T> Clone for URational<T>

where T: Unsigned + Clone,

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T> Debug for URational<T>

where T: Unsigned + Debug,

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

Formats the value using the given formatter.

impl<T> Div for URational<T>

where T: Unsigned,

type Output = URational<T>

The resulting type after applying the / operator.

fn div(self, rhs: Self) -> Self::Output

Performs the / operation.

impl<T> DivAssign for URational<T>

where T: Unsigned,

fn div_assign(&mut self, rhs: Self)

Performs the /= operation.

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> From<URational<T>> for SbtPath<T>

where T: Unsigned,

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

Converts to this type from the input type.

impl<T> Mul for URational<T>

where T: Unsigned,

type Output = URational<T>

The resulting type after applying the * operator.

fn mul(self, rhs: Self) -> Self::Output

Performs the * operation.

impl<T> MulAssign for URational<T>

where T: Unsigned,

fn mul_assign(&mut self, rhs: Self)

Performs the *= operation.

impl<T> One for URational<T>

where T: Unsigned,

fn one() -> Self

fn is_one(&self) -> bool

where Self: PartialEq,

fn set_one(&mut self)

impl<T> Ord for URational<T>

where T: Unsigned,

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl<T> PartialEq for URational<T>

where T: Unsigned,

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

Tests for self and other values to be equal, and is used by ==.

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

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T> PartialOrd for URational<T>

where T: Unsigned,

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

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

Tests less than (for self and other) and is used by the < operator.

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

Tests less than or equal to (for self and other) and is used by the <= operator.

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

Tests greater than (for self and other) and is used by the > operator.

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

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl<T> Sub for URational<T>

where T: Unsigned,

type Output = URational<T>

The resulting type after applying the - operator.

fn sub(self, rhs: Self) -> Self::Output

Performs the - operation.

impl<T> SubAssign for URational<T>

where T: Unsigned,

fn sub_assign(&mut self, rhs: Self)

Performs the -= operation.

impl<T> Zero for URational<T>

where T: Unsigned,

fn zero() -> Self

fn is_zero(&self) -> bool

where Self: PartialEq,

fn set_zero(&mut self)

impl<T> Copy for URational<T>

where T: Unsigned + Copy,

impl<T> Eq for URational<T>

where T: Unsigned,