malachite_nz/integer_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::integer::Integer;
10use crate::integer_vector::IntegerVector;
11use crate::integer_vector::arithmetic::max_bits::vec_max_bits;
12use crate::natural::Natural;
13use crate::natural_vector::ZERO;
14use malachite_base::num::arithmetic::traits::{Height, HeightRef, UnsignedAbs};
15use malachite_base::num::basic::traits::Zero;
16
17impl Height for IntegerVector {
18    type Output = Natural;
19
20    /// Returns the height of an [`IntegerVector`]: the largest of the absolute values of its
21    /// elements, taking the vector by reference and cloning.
22    ///
23    /// The 0-dimensional vector has no elements, and its height is 0.
24    ///
25    /// $$
26    /// f(v) = H(v) = \max_i |v_i|.
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, 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_nz::integer_vector::IntegerVector;
42    ///
43    /// assert_eq!(
44    ///     IntegerVector::from_str("(1, -3, 2)").unwrap().to_height(),
45    ///     3
46    /// );
47    /// assert_eq!(IntegerVector::from_str("()").unwrap().to_height(), 0);
48    /// ```
49    ///
50    /// This is equivalent to `_fmpz_vec_height` from `fmpz_vec/height.c`, FLINT 3.6.0.
51    #[inline]
52    fn to_height(&self) -> Natural {
53        self.height_ref().clone()
54    }
55
56    /// Returns the height of an [`IntegerVector`]: the largest of the absolute values of its
57    /// elements, taking the vector by value.
58    ///
59    /// The element of largest height, or the part of it that is the height, is moved out of the
60    /// vector rather than cloned.
61    ///
62    /// # Worst-case complexity
63    /// $T(n) = O(n)$
64    ///
65    /// $M(n) = O(1)$
66    ///
67    /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
68    /// elements.
69    ///
70    /// # Examples
71    /// ```
72    /// use core::str::FromStr;
73    /// use malachite_base::num::arithmetic::traits::Height;
74    /// use malachite_nz::integer_vector::IntegerVector;
75    ///
76    /// assert_eq!(
77    ///     IntegerVector::from_str("(1, -3, 2)").unwrap().into_height(),
78    ///     3
79    /// );
80    /// assert_eq!(IntegerVector::from_str("()").unwrap().into_height(), 0);
81    /// ```
82    #[inline]
83    fn into_height(self) -> Natural {
84        self.elements
85            .into_iter()
86            .map(Integer::unsigned_abs)
87            .max()
88            .unwrap_or(Natural::ZERO)
89    }
90
91    /// Returns the number of significant bits of the height of an [`IntegerVector`].
92    ///
93    /// Since bit length is monotone, this is the largest of the elements' heights' bit lengths, and
94    /// 0 for the 0-dimensional vector, without materializing the height.
95    ///
96    /// # Worst-case complexity
97    /// $T(n) = O(n)$
98    ///
99    /// $M(n) = O(1)$
100    ///
101    /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
102    /// elements.
103    ///
104    /// # Examples
105    /// ```
106    /// use core::str::FromStr;
107    /// use malachite_base::num::arithmetic::traits::Height;
108    /// use malachite_nz::integer_vector::IntegerVector;
109    ///
110    /// assert_eq!(
111    ///     IntegerVector::from_str("(1, -3, 2)")
112    ///         .unwrap()
113    ///         .height_significant_bits(),
114    ///     2
115    /// );
116    /// assert_eq!(
117    ///     IntegerVector::from_str("()")
118    ///         .unwrap()
119    ///         .height_significant_bits(),
120    ///     0
121    /// );
122    /// ```
123    ///
124    /// This is the absolute value of `_fmpz_vec_max_bits` from `fmpz_vec/max_bits.c`, FLINT 3.6.0.
125    #[inline]
126    fn height_significant_bits(&self) -> u64 {
127        vec_max_bits(&self.elements).0
128    }
129}
130
131impl HeightRef for IntegerVector {
132    /// Returns a reference to the height of an [`IntegerVector`]: the largest of the absolute
133    /// values of its elements.
134    ///
135    /// The height is one of the magnitudes the vector already holds, so it is lent rather than
136    /// built. For the 0-dimensional vector, a reference to 0 is returned.
137    ///
138    /// # Worst-case complexity
139    /// $T(n) = O(n)$
140    ///
141    /// $M(n) = O(1)$
142    ///
143    /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
144    /// elements.
145    ///
146    /// # Examples
147    /// ```
148    /// use core::str::FromStr;
149    /// use malachite_base::num::arithmetic::traits::HeightRef;
150    /// use malachite_nz::integer_vector::IntegerVector;
151    ///
152    /// assert_eq!(
153    ///     *IntegerVector::from_str("(1, -3, 2)").unwrap().height_ref(),
154    ///     3
155    /// );
156    /// assert_eq!(*IntegerVector::from_str("()").unwrap().height_ref(), 0);
157    /// ```
158    #[inline]
159    fn height_ref(&self) -> &Natural {
160        self.elements
161            .iter()
162            .map(Integer::unsigned_abs_ref)
163            .max()
164            .unwrap_or(&ZERO)
165    }
166}
malachite_nz/integer_vector/arithmetic/height.rs

malachite_nz/integer_vector/arithmetic/
height.rs
