competitive::algorithm::stern_brocot_tree

Struct SbtPath

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/number_theory/stern_brocot_tree.rs (line 75)

19pub fn stern_brocot_tree(reader: impl Read, mut writer: impl Write) {
20    let s = read_all_unchecked(reader);
21    let mut scanner = Scanner::new(&s);
22    scan!(scanner, t);
23    for _ in 0..t {
24        scan!(scanner, query: Query);
25        match query {
26            Query::EncodePath { a, b } => {
27                let path = SbtPath::from(URational::new(a, b));
28                let len = if path.path.first() == Some(&0) {
29                    path.path.len() - 1
30                } else {
31                    path.path.len()
32                };
33                write!(writer, "{}", len).ok();
34                for (i, count) in path.into_iter().enumerate() {
35                    if count == 0 {
36                        continue;
37                    }
38                    if i % 2 == 0 {
39                        write!(writer, " R {}", count).ok();
40                    } else {
41                        write!(writer, " L {}", count).ok();
42                    }
43                }
44                writeln!(writer).ok();
45            }
46            Query::DecodePath { path, .. } => {
47                let node: SbtNode<u32> = if path.first().is_some_and(|t| t.0 == 'L') {
48                    [0].into_iter()
49                        .chain(path.into_iter().map(|(_, c)| c))
50                        .collect()
51                } else {
52                    path.into_iter().map(|(_, c)| c).collect()
53                };
54                let val = node.eval();
55                writeln!(writer, "{} {}", val.num, val.den).ok();
56            }
57            Query::Lca { a, b, c, d } => {
58                let path1 = SbtPath::from(URational::new(a, b));
59                let path2 = SbtPath::from(URational::new(c, d));
60                let val = SbtNode::lca(path1, path2).eval();
61                writeln!(writer, "{} {}", val.num, val.den).ok();
62            }
63            Query::Ancestor { k, a, b } => {
64                let mut path = SbtPath::from(URational::new(a, b));
65                let depth = path.depth();
66                if k <= depth {
67                    path.up(depth - k);
68                    let val = path.eval();
69                    writeln!(writer, "{} {}", val.num, val.den).ok();
70                } else {
71                    writeln!(writer, "-1").ok();
72                }
73            }
74            Query::Range { a, b } => {
75                let node = SbtPath::from(URational::new(a, b)).to_node();
76                writeln!(
77                    writer,
78                    "{} {} {} {}",
79                    node.l.num, node.l.den, node.r.num, node.r.den
80                )
81                .ok();
82            }
83        }
84    }
85}

Source

pub fn depth(&self) -> T

Examples found in repository ?

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

19pub fn stern_brocot_tree(reader: impl Read, mut writer: impl Write) {
20    let s = read_all_unchecked(reader);
21    let mut scanner = Scanner::new(&s);
22    scan!(scanner, t);
23    for _ in 0..t {
24        scan!(scanner, query: Query);
25        match query {
26            Query::EncodePath { a, b } => {
27                let path = SbtPath::from(URational::new(a, b));
28                let len = if path.path.first() == Some(&0) {
29                    path.path.len() - 1
30                } else {
31                    path.path.len()
32                };
33                write!(writer, "{}", len).ok();
34                for (i, count) in path.into_iter().enumerate() {
35                    if count == 0 {
36                        continue;
37                    }
38                    if i % 2 == 0 {
39                        write!(writer, " R {}", count).ok();
40                    } else {
41                        write!(writer, " L {}", count).ok();
42                    }
43                }
44                writeln!(writer).ok();
45            }
46            Query::DecodePath { path, .. } => {
47                let node: SbtNode<u32> = if path.first().is_some_and(|t| t.0 == 'L') {
48                    [0].into_iter()
49                        .chain(path.into_iter().map(|(_, c)| c))
50                        .collect()
51                } else {
52                    path.into_iter().map(|(_, c)| c).collect()
53                };
54                let val = node.eval();
55                writeln!(writer, "{} {}", val.num, val.den).ok();
56            }
57            Query::Lca { a, b, c, d } => {
58                let path1 = SbtPath::from(URational::new(a, b));
59                let path2 = SbtPath::from(URational::new(c, d));
60                let val = SbtNode::lca(path1, path2).eval();
61                writeln!(writer, "{} {}", val.num, val.den).ok();
62            }
63            Query::Ancestor { k, a, b } => {
64                let mut path = SbtPath::from(URational::new(a, b));
65                let depth = path.depth();
66                if k <= depth {
67                    path.up(depth - k);
68                    let val = path.eval();
69                    writeln!(writer, "{} {}", val.num, val.den).ok();
70                } else {
71                    writeln!(writer, "-1").ok();
72                }
73            }
74            Query::Range { a, b } => {
75                let node = SbtPath::from(URational::new(a, b)).to_node();
76                writeln!(
77                    writer,
78                    "{} {} {} {}",
79                    node.l.num, node.l.den, node.r.num, node.r.den
80                )
81                .ok();
82            }
83        }
84    }
85}