malachite_q/rational_vector/arithmetic/height.rs
1// Copyright © 2026 Mikhail Hogrefe
2//
3// This file is part of Malachite.
4//
5// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
6// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
7// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
8
9use crate::Rational;
10use crate::rational_vector::{RationalVector, ZERO};
11use malachite_base::num::arithmetic::traits::{Height, HeightRef};
12use malachite_base::num::basic::traits::Zero;
13use malachite_nz::natural::Natural;
14
15impl Height for RationalVector {
16 type Output = Natural;
17
18 /// Returns the height of a [`RationalVector`]: the largest of the heights of its elements,
19 /// taking the vector by reference and cloning.
20 ///
21 /// The 0-dimensional vector has no elements, and its height is 0. Every other vector has height
22 /// at least 1, since every denominator is at least 1; in particular, a nonzero-dimensional
23 /// vector of zeros has height 1, the height of $0 = 0/1$.
24 ///
25 /// $$
26 /// f(v) = H(v) = \max_i H(v_i), \quad H(p/q) = \max(|p|, q).
27 /// $$
28 ///
29 /// # Worst-case complexity
30 /// $T(n) = O(n)$
31 ///
32 /// $M(n) = O(m)$
33 ///
34 /// where $T$ is time, $M$ is additional memory, $n$ is the total number of bits of the
35 /// elements' numerators and denominators, and $m$ is the number of bits of the height.
36 ///
37 /// # Examples
38 /// ```
39 /// use core::str::FromStr;
40 /// use malachite_base::num::arithmetic::traits::Height;
41 /// use malachite_q::rational_vector::RationalVector;
42 ///
43 /// assert_eq!(
44 /// RationalVector::from_str("(1/2, -3, 1/4)")
45 /// .unwrap()
46 /// .to_height(),
47 /// 4
48 /// );
49 /// assert_eq!(RationalVector::from_str("()").unwrap().to_height(), 0);
50 /// ```
51 ///
52 /// This is equivalent to `_fmpq_vec_max_height` from `fmpq_vec/max_height.c`, FLINT 3.6.0.
53 #[inline]
54 fn to_height(&self) -> Natural {
55 self.height_ref().clone()
56 }
57
58 /// Returns the height of a [`RationalVector`]: the largest of the heights of its elements,
59 /// taking the vector by value.
60 ///
61 /// The element of largest height, or the part of it that is the height, is moved out of the
62 /// vector rather than cloned.
63 ///
64 /// # Worst-case complexity
65 /// $T(n) = O(n)$
66 ///
67 /// $M(n) = O(1)$
68 ///
69 /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
70 /// elements' numerators and denominators.
71 ///
72 /// # Examples
73 /// ```
74 /// use core::str::FromStr;
75 /// use malachite_base::num::arithmetic::traits::Height;
76 /// use malachite_q::rational_vector::RationalVector;
77 ///
78 /// assert_eq!(
79 /// RationalVector::from_str("(1/2, -3, 1/4)")
80 /// .unwrap()
81 /// .into_height(),
82 /// 4
83 /// );
84 /// assert_eq!(RationalVector::from_str("()").unwrap().into_height(), 0);
85 /// ```
86 #[inline]
87 fn into_height(self) -> Natural {
88 self.elements
89 .into_iter()
90 .map(Rational::into_height)
91 .max()
92 .unwrap_or(Natural::ZERO)
93 }
94
95 /// Returns the number of significant bits of the height of a [`RationalVector`].
96 ///
97 /// Since bit length is monotone, this is the largest of the elements' heights' bit lengths, and
98 /// 0 for the 0-dimensional vector, without materializing the height.
99 ///
100 /// # Worst-case complexity
101 /// $T(n) = O(n)$
102 ///
103 /// $M(n) = O(1)$
104 ///
105 /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
106 /// elements' numerators and denominators.
107 ///
108 /// # Examples
109 /// ```
110 /// use core::str::FromStr;
111 /// use malachite_base::num::arithmetic::traits::Height;
112 /// use malachite_q::rational_vector::RationalVector;
113 ///
114 /// assert_eq!(
115 /// RationalVector::from_str("(1/2, -3, 1/4)")
116 /// .unwrap()
117 /// .height_significant_bits(),
118 /// 3
119 /// );
120 /// assert_eq!(
121 /// RationalVector::from_str("()")
122 /// .unwrap()
123 /// .height_significant_bits(),
124 /// 0
125 /// );
126 /// ```
127 ///
128 /// This is equivalent to `_fmpq_vec_max_height_bits` from `fmpq_vec/max_height_bits.c`, FLINT
129 /// 3.6.0.
130 #[inline]
131 fn height_significant_bits(&self) -> u64 {
132 self.elements
133 .iter()
134 .map(Rational::height_significant_bits)
135 .max()
136 .unwrap_or(0)
137 }
138}
139
140impl HeightRef for RationalVector {
141 /// Returns a reference to the height of a [`RationalVector`]: the largest of the heights of its
142 /// elements.
143 ///
144 /// The height is one of the magnitudes the vector already holds, so it is lent rather than
145 /// built. For the 0-dimensional vector, a reference to 0 is returned.
146 ///
147 /// # Worst-case complexity
148 /// $T(n) = O(n)$
149 ///
150 /// $M(n) = O(1)$
151 ///
152 /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
153 /// elements' numerators and denominators.
154 ///
155 /// # Examples
156 /// ```
157 /// use core::str::FromStr;
158 /// use malachite_base::num::arithmetic::traits::HeightRef;
159 /// use malachite_q::rational_vector::RationalVector;
160 ///
161 /// assert_eq!(
162 /// *RationalVector::from_str("(1/2, -3, 1/4)")
163 /// .unwrap()
164 /// .height_ref(),
165 /// 4
166 /// );
167 /// assert_eq!(*RationalVector::from_str("()").unwrap().height_ref(), 0);
168 /// ```
169 #[inline]
170 fn height_ref(&self) -> &Natural {
171 self.elements
172 .iter()
173 .map(Rational::height_ref)
174 .max()
175 .unwrap_or(&ZERO)
176 }
177}