malachite_base/unsigned_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::num::arithmetic::traits::Height;
10use crate::num::basic::unsigneds::PrimitiveUnsigned;
11use crate::unsigned_vector::UnsignedVector;
12
13impl<T: PrimitiveUnsigned> Height for UnsignedVector<T> {
14    type Output = T;
15
16    /// Returns the height of an [`UnsignedVector`]: the largest of its elements, taking the vector
17    /// by reference.
18    ///
19    /// The 0-dimensional vector has no elements, and its height is 0.
20    ///
21    /// $$
22    /// f(v) = H(v) = \max_i v_i.
23    /// $$
24    ///
25    /// # Worst-case complexity
26    /// $T(n) = O(n)$
27    ///
28    /// $M(n) = O(1)$
29    ///
30    /// where $T$ is time, $M$ is additional memory, $n$ is the number of elements.
31    ///
32    /// # Examples
33    /// ```
34    /// use core::str::FromStr;
35    /// use malachite_base::num::arithmetic::traits::Height;
36    /// use malachite_base::unsigned_vector::UnsignedVector;
37    ///
38    /// assert_eq!(
39    ///     UnsignedVector::<u8>::from_str("(1, 3, 2)")
40    ///         .unwrap()
41    ///         .to_height(),
42    ///     3
43    /// );
44    /// assert_eq!(UnsignedVector::<u8>::from_str("()").unwrap().to_height(), 0);
45    /// ```
46    #[inline]
47    fn to_height(&self) -> T {
48        self.elements.iter().copied().max().unwrap_or(T::ZERO)
49    }
50
51    /// Returns the height of an [`UnsignedVector`]: the largest of its elements, taking the vector
52    /// by value.
53    ///
54    /// # Worst-case complexity
55    /// $T(n) = O(n)$
56    ///
57    /// $M(n) = O(1)$
58    ///
59    /// where $T$ is time, $M$ is additional memory, and $n$ is the number of elements.
60    ///
61    /// # Examples
62    /// ```
63    /// use core::str::FromStr;
64    /// use malachite_base::num::arithmetic::traits::Height;
65    /// use malachite_base::unsigned_vector::UnsignedVector;
66    ///
67    /// assert_eq!(
68    ///     UnsignedVector::<u8>::from_str("(1, 3, 2)")
69    ///         .unwrap()
70    ///         .into_height(),
71    ///     3
72    /// );
73    /// assert_eq!(
74    ///     UnsignedVector::<u8>::from_str("()").unwrap().into_height(),
75    ///     0
76    /// );
77    /// ```
78    #[inline]
79    fn into_height(self) -> T {
80        self.to_height()
81    }
82
83    /// Returns the number of significant bits of the height of an [`UnsignedVector`].
84    ///
85    /// Since bit length is monotone, this is the largest of the elements' heights' bit lengths, and
86    /// 0 for the 0-dimensional vector, without materializing the height.
87    ///
88    /// # Worst-case complexity
89    /// $T(n) = O(n)$
90    ///
91    /// $M(n) = O(1)$
92    ///
93    /// where $T$ is time, $M$ is additional memory, and $n$ is the number of elements.
94    ///
95    /// # Examples
96    /// ```
97    /// use core::str::FromStr;
98    /// use malachite_base::num::arithmetic::traits::Height;
99    /// use malachite_base::unsigned_vector::UnsignedVector;
100    ///
101    /// assert_eq!(
102    ///     UnsignedVector::<u8>::from_str("(1, 3, 2)")
103    ///         .unwrap()
104    ///         .height_significant_bits(),
105    ///     2
106    /// );
107    /// assert_eq!(
108    ///     UnsignedVector::<u8>::from_str("()")
109    ///         .unwrap()
110    ///         .height_significant_bits(),
111    ///     0
112    /// );
113    /// ```
114    ///
115    /// This is equivalent to `_nmod_vec_max_bits` from `nmod_vec/max_bits.c`, FLINT 3.6.0.
116    #[inline]
117    fn height_significant_bits(&self) -> u64 {
118        self.to_height().significant_bits()
119    }
120}
malachite_base/unsigned_vector/arithmetic/height.rs

malachite_base/unsigned_vector/arithmetic/
height.rs
