competitive::algorithm

Struct SbtPath

Source 
pub struct SbtPath<T>
where
    T: Unsigned,
{
    pub path: Vec<T>,
}

Fields§

§path: Vec<T>

Implementations§

Source§

impl<T> SbtPath<T>
where T: Unsigned,

Source

pub fn to_node(&self) -> SbtNode<T>

Examples found in repository?
crates/competitive/src/algorithm/stern_brocot_tree.rs (line 43)
42    fn from(r: URational<T>) -> Self {
43        SbtPath::from(r).to_node()
44    }
45}
46
47impl<T> FromIterator<T> for SbtNode<T>
48where
49    T: Unsigned,
50{
51    fn from_iter<I>(iter: I) -> Self
52    where
53        I: IntoIterator<Item = T>,
54    {
55        let mut node = SbtNode::root();
56        for (i, count) in iter.into_iter().enumerate() {
57            if i % 2 == 0 {
58                node.down_right(count);
59            } else {
60                node.down_left(count);
61            }
62        }
63        node
64    }
65}
66
67impl<T> From<URational<T>> for SbtPath<T>
68where
69    T: Unsigned,
70{
71    fn from(r: URational<T>) -> Self {
72        assert!(!r.num.is_zero(), "rational must be positive");
73        assert!(!r.den.is_zero(), "rational must be positive");
74
75        let (mut a, mut b) = (r.num, r.den);
76        let mut path = vec![];
77        loop {
78            let x = a / b;
79            a %= b;
80            if a.is_zero() {
81                if !x.is_one() {
82                    path.push(x - T::one());
83                }
84                break;
85            }
86            path.push(x);
87            swap(&mut a, &mut b);
88        }
89        Self { path }
90    }
91}
92
93impl<T> FromIterator<T> for SbtPath<T>
94where
95    T: Unsigned,
96{
97    fn from_iter<I>(iter: I) -> Self
98    where
99        I: IntoIterator<Item = T>,
100    {
101        let mut path = SbtPath::root();
102        for (i, count) in iter.into_iter().enumerate() {
103            if i % 2 == 0 {
104                path.down_right(count);
105            } else {
106                path.down_left(count);
107            }
108        }
109        path
110    }
111}
112
113impl<T> IntoIterator for SbtPath<T>
114where
115    T: Unsigned,
116{
117    type Item = T;
118    type IntoIter = std::vec::IntoIter<T>;
119
120    fn into_iter(self) -> Self::IntoIter {
121        self.path.into_iter()
122    }
123}
124
125impl<'a, T> IntoIterator for &'a SbtPath<T>
126where
127    T: Unsigned,
128{
129    type Item = T;
130    type IntoIter = std::iter::Cloned<std::slice::Iter<'a, T>>;
131
132    fn into_iter(self) -> Self::IntoIter {
133        self.path.iter().cloned()
134    }
135}
136
137impl<T> SternBrocotTree for SbtNode<T>
138where
139    T: Unsigned,
140{
141    type T = T;
142
143    fn root() -> Self {
144        Self {
145            l: URational::new(T::zero(), T::one()),
146            r: URational::new(T::one(), T::zero()),
147        }
148    }
149
150    fn is_root(&self) -> bool {
151        self.l.num.is_zero() && self.r.den.is_zero()
152    }
153
154    fn eval(&self) -> URational<Self::T> {
155        URational::new_unchecked(self.l.num + self.r.num, self.l.den + self.r.den)
156    }
157
158    fn down_left(&mut self, count: Self::T) {
159        self.r.num += self.l.num * count;
160        self.r.den += self.l.den * count;
161    }
162
163    fn down_right(&mut self, count: Self::T) {
164        self.l.num += self.r.num * count;
165        self.l.den += self.r.den * count;
166    }
167
168    fn up(&mut self, mut count: Self::T) -> Self::T {
169        while count > T::zero() && !self.is_root() {
170            if self.l.den > self.r.den {
171                let x = count.min(self.l.num / self.r.num);
172                count -= x;
173                self.l.num -= self.r.num * x;
174                self.l.den -= self.r.den * x;
175            } else {
176                let x = count.min(self.r.den / self.l.den);
177                count -= x;
178                self.r.num -= self.l.num * x;
179                self.r.den -= self.l.den * x;
180            }
181        }
182        count
183    }
184}
185
186impl<T> SternBrocotTree for SbtPath<T>
187where
188    T: Unsigned,
189{
190    type T = T;
191
192    fn root() -> Self {
193        Self::default()
194    }
195
196    fn is_root(&self) -> bool {
197        self.path.is_empty()
198    }
199
200    fn eval(&self) -> URational<Self::T> {
201        self.to_node().eval()
202    }
More examples
Hide additional examples
crates/library_checker/src/math/stern_brocot_tree.rs (line 70)
9pub fn stern_brocot_tree(reader: impl Read, mut writer: impl Write) {
10    let s = read_all_unchecked(reader);
11    let mut scanner = Scanner::new(&s);
12    scan!(scanner, t);
13    for _ in 0..t {
14        scan!(scanner, type_: String);
15        match type_.as_str() {
16            "ENCODE_PATH" => {
17                scan!(scanner, a: u32, b: u32);
18                let path = SbtPath::from(URational::new(a, b));
19                let len = if path.path.first() == Some(&0) {
20                    path.path.len() - 1
21                } else {
22                    path.path.len()
23                };
24                write!(writer, "{}", len).ok();
25                for (i, count) in path.into_iter().enumerate() {
26                    if count == 0 {
27                        continue;
28                    }
29                    if i % 2 == 0 {
30                        write!(writer, " R {}", count).ok();
31                    } else {
32                        write!(writer, " L {}", count).ok();
33                    }
34                }
35                writeln!(writer).ok();
36            }
37            "DECODE_PATH" => {
38                scan!(scanner, k, path: [(char, u32); k]);
39                let node: SbtNode<u32> = if path.first().is_some_and(|t| t.0 == 'L') {
40                    [0].into_iter()
41                        .chain(path.into_iter().map(|(_, c)| c))
42                        .collect()
43                } else {
44                    path.into_iter().map(|(_, c)| c).collect()
45                };
46                let val = node.eval();
47                writeln!(writer, "{} {}", val.num, val.den).ok();
48            }
49            "LCA" => {
50                scan!(scanner, [a, b, c, d]: [u32; const 4]);
51                let path1 = SbtPath::from(URational::new(a, b));
52                let path2 = SbtPath::from(URational::new(c, d));
53                let val = SbtNode::lca(path1, path2).eval();
54                writeln!(writer, "{} {}", val.num, val.den).ok();
55            }
56            "ANCESTOR" => {
57                scan!(scanner, [k, a, b]: [u32; const 3]);
58                let mut path = SbtPath::from(URational::new(a, b));
59                let depth = path.depth();
60                if k <= depth {
61                    path.up(depth - k);
62                    let val = path.eval();
63                    writeln!(writer, "{} {}", val.num, val.den).ok();
64                } else {
65                    writeln!(writer, "-1").ok();
66                }
67            }
68            "RANGE" => {
69                scan!(scanner, [a, b]: [u32; const 2]);
70                let node = SbtPath::from(URational::new(a, b)).to_node();
71                writeln!(
72                    writer,
73                    "{} {} {} {}",
74                    node.l.num, node.l.den, node.r.num, node.r.den
75                )
76                .ok();
77            }
78            _ => unreachable!(),
79        }
80    }
81}
Source

pub fn depth(&self) -> T

Examples found in repository?
crates/library_checker/src/math/stern_brocot_tree.rs (line 59)
9pub fn stern_brocot_tree(reader: impl Read, mut writer: impl Write) {
10    let s = read_all_unchecked(reader);
11    let mut scanner = Scanner::new(&s);
12    scan!(scanner, t);
13    for _ in 0..t {
14        scan!(scanner, type_: String);
15        match type_.as_str() {
16            "ENCODE_PATH" => {
17                scan!(scanner, a: u32, b: u32);
18                let path = SbtPath::from(URational::new(a, b));
19                let len = if path.path.first() == Some(&0) {
20                    path.path.len() - 1
21                } else {
22                    path.path.len()
23                };
24                write!(writer, "{}", len).ok();
25                for (i, count) in path.into_iter().enumerate() {
26                    if count == 0 {
27                        continue;
28                    }
29                    if i % 2 == 0 {
30                        write!(writer, " R {}", count).ok();
31                    } else {
32                        write!(writer, " L {}", count).ok();
33                    }
34                }
35                writeln!(writer).ok();
36            }
37            "DECODE_PATH" => {
38                scan!(scanner, k, path: [(char, u32); k]);
39                let node: SbtNode<u32> = if path.first().is_some_and(|t| t.0 == 'L') {
40                    [0].into_iter()
41                        .chain(path.into_iter().map(|(_, c)| c))
42                        .collect()
43                } else {
44                    path.into_iter().map(|(_, c)| c).collect()
45                };
46                let val = node.eval();
47                writeln!(writer, "{} {}", val.num, val.den).ok();
48            }
49            "LCA" => {
50                scan!(scanner, [a, b, c, d]: [u32; const 4]);
51                let path1 = SbtPath::from(URational::new(a, b));
52                let path2 = SbtPath::from(URational::new(c, d));
53                let val = SbtNode::lca(path1, path2).eval();
54                writeln!(writer, "{} {}", val.num, val.den).ok();
55            }
56            "ANCESTOR" => {
57                scan!(scanner, [k, a, b]: [u32; const 3]);
58                let mut path = SbtPath::from(URational::new(a, b));
59                let depth = path.depth();
60                if k <= depth {
61                    path.up(depth - k);
62                    let val = path.eval();
63                    writeln!(writer, "{} {}", val.num, val.den).ok();
64                } else {
65                    writeln!(writer, "-1").ok();
66                }
67            }
68            "RANGE" => {
69                scan!(scanner, [a, b]: [u32; const 2]);
70                let node = SbtPath::from(URational::new(a, b)).to_node();
71                writeln!(
72                    writer,
73                    "{} {} {} {}",
74                    node.l.num, node.l.den, node.r.num, node.r.den
75                )
76                .ok();
77            }
78            _ => unreachable!(),
79        }
80    }
81}

Trait Implementations§

Source§

impl<T> Clone for SbtPath<T>
where T: Unsigned + Clone,

Source§

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

Returns a duplicate of the value. Read more
1.0.0 · Source§

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

Performs copy-assignment from source. Read more
Source§

impl<T> Debug for SbtPath<T>
where T: Unsigned + Debug,

Source§

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

Formats the value using the given formatter. Read more
Source§

impl<T> Default for SbtPath<T>
where T: Unsigned + Default,

Source§

fn default() -> SbtPath<T>

Returns the “default value” for a type. Read more
Source§

impl<T> From<URational<T>> for SbtPath<T>
where T: Unsigned,

Source§

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

Converts to this type from the input type.
Source§

impl<T> FromIterator<T> for SbtPath<T>
where T: Unsigned,

Source§

fn from_iter<I>(iter: I) -> Self
where I: IntoIterator<Item = T>,

Creates a value from an iterator. Read more
Source§

impl<'a, T> IntoIterator for &'a SbtPath<T>
where T: Unsigned,

Source§

type Item = T

The type of the elements being iterated over.
Source§

type IntoIter = Cloned<Iter<'a, T>>

Which kind of iterator are we turning this into?
Source§

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value. Read more
Source§

impl<T> IntoIterator for SbtPath<T>
where T: Unsigned,

Source§

type Item = T

The type of the elements being iterated over.
Source§

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?
Source§

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value. Read more
Source§

impl<T> PartialEq for SbtPath<T>
where T: Unsigned + PartialEq,

Source§

fn eq(&self, other: &SbtPath<T>) -> bool

Tests for self and other values to be equal, and is used by ==.
1.0.0 · Source§

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

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

impl<T> SternBrocotTree for SbtPath<T>
where T: Unsigned,

Source§

type T = T

Source§

fn root() -> Self

Source§

fn is_root(&self) -> bool

Source§

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

Source§

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

Source§

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

Source§

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

Returns the remaining count after moving up.
Source§

impl<T> Eq for SbtPath<T>
where T: Unsigned + Eq,

Source§

impl<T> StructuralPartialEq for SbtPath<T>
where T: Unsigned,

Auto Trait Implementations§

§

impl<T> Freeze for SbtPath<T>

§

impl<T> RefUnwindSafe for SbtPath<T>
where T: RefUnwindSafe,

§

impl<T> Send for SbtPath<T>
where T: Send,

§

impl<T> Sync for SbtPath<T>
where T: Sync,

§

impl<T> Unpin for SbtPath<T>
where T: Unpin,

§

impl<T> UnwindSafe for SbtPath<T>
where T: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.