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 73)

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

Source

pub fn depth(&self) -> T

Examples found in repository ?

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

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