malachite_base/unsigned_vector/arithmetic/
content_chained.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::ContentChained;
10use crate::num::basic::unsigneds::PrimitiveUnsigned;
11use crate::unsigned_vector::UnsignedVector;
12
13// Returns the GCD of `gcd` and the elements of `xs`. Zeros at either end are skipped, an element of
14// 1 at either end gives 1 at once, and the rest are taken in pairs from both ends, stopping as soon
15// as the GCD reaches 1.
16//
17// This is equivalent to `_fmpz_vec_content_chained` from `fmpz_vec/content_chained.c`, FLINT 3.6.0.
18pub(crate) fn content_chained<T: PrimitiveUnsigned>(xs: &[T], mut gcd: T) -> T {
19    let Some(start) = xs.iter().position(|&c| c != T::ZERO) else {
20        return gcd;
21    };
22    let end = xs.iter().rposition(|&c| c != T::ZERO).unwrap();
23    let mut xs = &xs[start..=end];
24    if let [first, .., last] = xs
25        && (*first == T::ONE || *last == T::ONE)
26    {
27        return T::ONE;
28    }
29    while gcd != T::ONE
30        && let [first, middle @ .., last] = xs
31    {
32        gcd.gcd_assign(first.gcd(*last));
33        xs = middle;
34    }
35    if gcd != T::ONE
36        && let [middle] = xs
37    {
38        gcd.gcd_assign(*middle);
39    }
40    gcd
41}
42
43impl<T: PrimitiveUnsigned> ContentChained<T> for UnsignedVector<T> {
44    type Output = T;
45
46    /// Computes the GCD of `x` and the elements of an [`UnsignedVector`], taking the vector by
47    /// value.
48    ///
49    /// The GCD of `x` and the elements of the 0-dimensional vector, or of a vector of zeros, is
50    /// `x`. The computation stops as soon as the GCD reaches 1.
51    ///
52    /// $$
53    /// f(v, x) = \gcd(x, v_0, v_1, \ldots, v_{n-1}),
54    /// $$
55    ///
56    /// where $n$ is the dimension of $v$.
57    ///
58    /// # Worst-case complexity
59    /// $T(n) = O(n)$
60    ///
61    /// $M(n) = O(1)$
62    ///
63    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.dimension()`.
64    ///
65    /// # Examples
66    /// ```
67    /// use core::str::FromStr;
68    /// use malachite_base::num::arithmetic::traits::ContentChained;
69    /// use malachite_base::unsigned_vector::UnsignedVector;
70    ///
71    /// let v = UnsignedVector::<u8>::from_str("(6, 4, 10)").unwrap();
72    /// assert_eq!(v.clone().content_chained(4), 2);
73    /// assert_eq!(v.content_chained(0), 2);
74    /// let v = UnsignedVector::<u8>::from_str("()").unwrap();
75    /// assert_eq!(v.content_chained(6), 6);
76    /// ```
77    ///
78    /// This is equivalent to `_fmpz_vec_content_chained` from `fmpz_vec/content_chained.c`, FLINT
79    /// 3.6.0.
80    #[inline]
81    fn content_chained(self, x: T) -> T {
82        content_chained(&self.elements, x)
83    }
84}
85
86impl<T: PrimitiveUnsigned> ContentChained<T> for &UnsignedVector<T> {
87    type Output = T;
88
89    /// Computes the GCD of `x` and the elements of an [`UnsignedVector`], taking the vector by
90    /// reference.
91    ///
92    /// The GCD of `x` and the elements of the 0-dimensional vector, or of a vector of zeros, is
93    /// `x`. The computation stops as soon as the GCD reaches 1.
94    ///
95    /// $$
96    /// f(v, x) = \gcd(x, v_0, v_1, \ldots, v_{n-1}),
97    /// $$
98    ///
99    /// where $n$ is the dimension of $v$.
100    ///
101    /// # Worst-case complexity
102    /// $T(n) = O(n)$
103    ///
104    /// $M(n) = O(1)$
105    ///
106    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.dimension()`.
107    ///
108    /// # Examples
109    /// ```
110    /// use core::str::FromStr;
111    /// use malachite_base::num::arithmetic::traits::ContentChained;
112    /// use malachite_base::unsigned_vector::UnsignedVector;
113    ///
114    /// let v = UnsignedVector::<u8>::from_str("(6, 4, 10)").unwrap();
115    /// assert_eq!((&v).content_chained(4), 2);
116    /// assert_eq!((&v).content_chained(0), 2);
117    /// let v = UnsignedVector::<u8>::from_str("()").unwrap();
118    /// assert_eq!((&v).content_chained(6), 6);
119    /// ```
120    ///
121    /// This is equivalent to `_fmpz_vec_content_chained` from `fmpz_vec/content_chained.c`, FLINT
122    /// 3.6.0.
123    #[inline]
124    fn content_chained(self, x: T) -> T {
125        content_chained(&self.elements, x)
126    }
127}
malachite_base/unsigned_vector/arithmetic/content_chained.rs

malachite_base/unsigned_vector/arithmetic/
content_chained.rs
