malachite_q/rational_vector/
mod.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 alloc::vec;
11use alloc::vec::Vec;
12use core::ops::Deref;
13use malachite_base::named::Named;
14use malachite_base::num::arithmetic::traits::{Height, HeightRef, L1Norm};
15use malachite_base::num::basic::traits::{One, Zero};
16use malachite_base::num::conversion::traits::ExactFrom;
17use malachite_base::vector::Vector;
18use malachite_nz::natural::Natural;
19
20/// Implementations of [`Index`](core::ops::Index) and [`IndexMut`](core::ops::IndexMut) for
21/// [`RationalVector`].
22pub mod access;
23/// Traits for arithmetic on [`RationalVector`]s.
24pub mod arithmetic;
25/// Implementations of [`Ord`] and [`PartialOrd`] for [`ShortlexRationalVector`] and
26/// [`ShortlexRationalVectorRef`], comparing two vectors by dimension and then lexicographically.
27pub mod comparison;
28/// Functions for converting a [`RationalVector`] to and from other types.
29pub mod conversion;
30/// Iterators that generate [`RationalVector`]s without repetition.
31pub mod exhaustive;
32/// An implementation of [`Extend`], for appending the elements produced by an iterator to a
33/// [`RationalVector`].
34pub mod extend;
35/// Traits for logic and bit manipulation on [`RationalVector`]s.
36pub mod logic;
37/// Iterators that generate [`RationalVector`]s randomly.
38#[cfg(feature = "random")]
39pub mod random;
40/// Implementations of [`SelectCoordinates`](malachite_base::vector::SelectCoordinates) and
41/// [`SelectCoordinatesAssign`](malachite_base::vector::SelectCoordinatesAssign), for selecting
42/// coordinates of a [`RationalVector`] by index.
43pub mod select_coordinates;
44
45// The height of the 0-dimensional vector, which `height_ref` lends. A `Natural` owns a `Vec` when
46// it is large, so it has a destructor, and a reference to a constant with a destructor cannot be
47// promoted to `'static`; a `static` can be borrowed for as long as needed.
48pub(crate) static ZERO: Natural = Natural::ZERO;
49
50/// A vector whose elements are [`Rational`]s.
51///
52/// Its dimension is the number of elements, and the 0-dimensional vector has none. The field is
53/// public, since every [`Vec`] of [`Rational`]s is a valid vector: unlike a polynomial, a vector
54/// has no normal form to maintain, and two vectors are equal exactly when their elements are.
55///
56/// The elements are held entrywise, each as a [`Rational`] of its own. This is the representation
57/// FLINT uses for its `fmpq_vec` and `fmpq_mat`, rather than the single common denominator of a
58/// [`RationalPolynomial`](crate::rational_polynomial::RationalPolynomial): a vector's elements are
59/// read and written one at a time, and a common denominator would make every element as large as
60/// the least common multiple of all their denominators.
61/// [`to_numerators_and_denominator`](RationalVector::to_numerators_and_denominator) gives the
62/// common-denominator form when it is wanted.
63///
64/// A `RationalVector` is serialized as the list of its elements, each serialized the way a
65/// [`Rational`] is.
66///
67/// # Examples
68/// ```
69/// use malachite_base::num::basic::traits::{One, Two};
70/// use malachite_base::vector::Vector;
71/// use malachite_q::Rational;
72/// use malachite_q::rational_vector::RationalVector;
73///
74/// let v = RationalVector {
75///     elements: vec![Rational::ONE, Rational::TWO, Rational::from(3u32)],
76/// };
77/// assert_eq!(v.dimension(), 3);
78/// ```
79#[derive(Clone, Eq, Hash, PartialEq)]
80#[cfg_attr(feature = "serde", derive(Deserialize, Serialize))]
81#[cfg_attr(feature = "serde", serde(transparent))]
82pub struct RationalVector {
83    pub elements: Vec<Rational>,
84}
85
86impl Vector for RationalVector {
87    type Element = Rational;
88    type ElementOutput<'a>
89        = &'a Rational
90    where
91        Self: 'a;
92
93    /// Converts a slice of [`Rational`]s to a [`RationalVector`], cloning them.
94    ///
95    /// The vector's dimension is the length of the slice. Every slice is a valid vector, so this
96    /// cannot fail; the empty slice gives the 0-dimensional vector.
97    ///
98    /// # Worst-case complexity
99    /// $T(n) = O(n)$
100    ///
101    /// $M(n) = O(n)$
102    ///
103    /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
104    /// elements.
105    ///
106    /// # Examples
107    /// ```
108    /// use malachite_base::num::basic::traits::{One, Two};
109    /// use malachite_base::vector::Vector;
110    /// use malachite_q::Rational;
111    /// use malachite_q::rational_vector::RationalVector;
112    ///
113    /// assert_eq!(
114    ///     RationalVector::from_elements(&[Rational::ONE, Rational::TWO]).to_string(),
115    ///     "(1, 2)"
116    /// );
117    /// assert_eq!(RationalVector::from_elements(&[]).to_string(), "()");
118    /// ```
119    #[inline]
120    fn from_elements(xs: &[Rational]) -> Self {
121        Self {
122            elements: xs.to_vec(),
123        }
124    }
125
126    /// Converts a [`Vec`] of [`Rational`]s to a [`RationalVector`], taking ownership of it.
127    ///
128    /// The vector's dimension is the length of the [`Vec`]. Every [`Vec`] is a valid vector, so
129    /// this cannot fail, and nothing is copied or allocated.
130    ///
131    /// # Worst-case complexity
132    /// Constant time and additional memory.
133    ///
134    /// # Examples
135    /// ```
136    /// use malachite_base::num::basic::traits::{One, Two};
137    /// use malachite_base::vector::Vector;
138    /// use malachite_q::Rational;
139    /// use malachite_q::rational_vector::RationalVector;
140    ///
141    /// assert_eq!(
142    ///     RationalVector::from_owned_elements(vec![Rational::ONE, Rational::TWO]).to_string(),
143    ///     "(1, 2)"
144    /// );
145    /// assert_eq!(
146    ///     RationalVector::from_owned_elements(Vec::new()).to_string(),
147    ///     "()"
148    /// );
149    /// ```
150    #[inline]
151    fn from_owned_elements(xs: Vec<Rational>) -> Self {
152        Self { elements: xs }
153    }
154
155    /// Returns the zero vector of a given dimension: a vector of `dimension` zeros.
156    ///
157    /// # Worst-case complexity
158    /// $T(n) = O(n)$
159    ///
160    /// $M(n) = O(n)$
161    ///
162    /// where $T$ is time, $M$ is additional memory, and $n$ is `dimension`.
163    ///
164    /// # Panics
165    /// Panics if `dimension` is greater than [`usize::MAX`].
166    ///
167    /// # Examples
168    /// ```
169    /// use malachite_base::vector::Vector;
170    /// use malachite_q::rational_vector::RationalVector;
171    ///
172    /// assert_eq!(RationalVector::zero(3).to_string(), "(0, 0, 0)");
173    /// assert_eq!(RationalVector::zero(0).to_string(), "()");
174    /// ```
175    ///
176    /// This is equivalent to `_fmpq_vec_init` from `fmpq_vec/init.c`, FLINT 3.6.0.
177    #[inline]
178    fn zero(dimension: u64) -> Self {
179        Self {
180            elements: vec![Rational::ZERO; usize::exact_from(dimension)],
181        }
182    }
183
184    /// Returns the standard basis vector $e_i$ of a given dimension: the vector whose element at
185    /// `index` is 1 and whose other elements are 0.
186    ///
187    /// Indices start at 0, as they do for [`Index`](core::ops::Index).
188    ///
189    /// # Worst-case complexity
190    /// $T(n) = O(n)$
191    ///
192    /// $M(n) = O(n)$
193    ///
194    /// where $T$ is time, $M$ is additional memory, and $n$ is `dimension`.
195    ///
196    /// # Panics
197    /// Panics if `index` is greater than or equal to `dimension`, or if `dimension` is greater than
198    /// [`usize::MAX`].
199    ///
200    /// # Examples
201    /// ```
202    /// use malachite_base::vector::Vector;
203    /// use malachite_q::rational_vector::RationalVector;
204    ///
205    /// assert_eq!(
206    ///     RationalVector::standard_basis_vector(3, 1).to_string(),
207    ///     "(0, 1, 0)"
208    /// );
209    /// assert_eq!(
210    ///     RationalVector::standard_basis_vector(1, 0).to_string(),
211    ///     "(1)"
212    /// );
213    /// ```
214    fn standard_basis_vector(dimension: u64, index: u64) -> Self {
215        assert!(
216            index < dimension,
217            "the index {index} is not less than the dimension {dimension}"
218        );
219        let mut v = Self::zero(dimension);
220        v.elements[usize::exact_from(index)] = Rational::ONE;
221        v
222    }
223
224    /// Appends an element to the end of a [`RationalVector`], increasing its dimension by 1.
225    ///
226    /// # Worst-case complexity
227    /// $T(n) = O(n)$
228    ///
229    /// $M(n) = O(n)$
230    ///
231    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.dimension()`. The capacity
232    /// grows geometrically, so pushing $n$ elements onto an empty vector takes $O(n)$ time in
233    /// total.
234    ///
235    /// # Examples
236    /// ```
237    /// use core::str::FromStr;
238    /// use malachite_base::vector::Vector;
239    /// use malachite_q::Rational;
240    /// use malachite_q::rational_vector::RationalVector;
241    ///
242    /// let mut v = RationalVector::from_str("(1, 2)").unwrap();
243    /// v.push(Rational::from_unsigneds(1u32, 3));
244    /// assert_eq!(v.to_string(), "(1, 2, 1/3)");
245    ///
246    /// let mut v = RationalVector::zero(0);
247    /// v.push(Rational::from(5));
248    /// assert_eq!(v.to_string(), "(5)");
249    /// ```
250    #[inline]
251    fn push(&mut self, x: Rational) {
252        self.elements.push(x);
253    }
254
255    /// Sets the dimension of a [`RationalVector`], removing elements from the end if the new
256    /// dimension is smaller, and appending zeros if it is larger.
257    ///
258    /// Reducing the dimension keeps the first `dimension` coordinates: it is the projection onto
259    /// them.
260    ///
261    /// # Worst-case complexity
262    /// $T(n) = O(n)$
263    ///
264    /// $M(n) = O(n)$
265    ///
266    /// where $T$ is time, $M$ is additional memory, and $n$ is the larger of `self.dimension()` and
267    /// `dimension`.
268    ///
269    /// # Panics
270    /// Panics if `dimension` is greater than [`usize::MAX`].
271    ///
272    /// # Examples
273    /// ```
274    /// use core::str::FromStr;
275    /// use malachite_base::vector::Vector;
276    /// use malachite_q::rational_vector::RationalVector;
277    ///
278    /// let mut v = RationalVector::from_str("(1, 2, 3)").unwrap();
279    /// v.set_dimension(5);
280    /// assert_eq!(v.to_string(), "(1, 2, 3, 0, 0)");
281    /// v.set_dimension(2);
282    /// assert_eq!(v.to_string(), "(1, 2)");
283    /// v.set_dimension(0);
284    /// assert_eq!(v.to_string(), "()");
285    /// ```
286    #[inline]
287    fn set_dimension(&mut self, dimension: u64) {
288        self.elements
289            .resize(usize::exact_from(dimension), Rational::ZERO);
290    }
291
292    /// Sets every element of a [`RationalVector`] to zero, keeping its dimension.
293    ///
294    /// Afterwards the vector equals [`zero`](Vector::zero) of the same dimension.
295    ///
296    /// # Worst-case complexity
297    /// $T(n) = O(n)$
298    ///
299    /// $M(n) = O(1)$
300    ///
301    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.dimension()`.
302    ///
303    /// # Examples
304    /// ```
305    /// use core::str::FromStr;
306    /// use malachite_base::vector::Vector;
307    /// use malachite_q::rational_vector::RationalVector;
308    ///
309    /// let mut v = RationalVector::from_str("(1/2, -2, 3)").unwrap();
310    /// v.set_zero();
311    /// assert_eq!(v.to_string(), "(0, 0, 0)");
312    ///
313    /// let mut v = RationalVector::from_str("()").unwrap();
314    /// v.set_zero();
315    /// assert_eq!(v.to_string(), "()");
316    /// ```
317    #[inline]
318    fn set_zero(&mut self) {
319        self.elements.fill(Rational::ZERO);
320    }
321
322    /// Sorts the elements of a [`RationalVector`] in ascending order, keeping its dimension.
323    ///
324    /// Equal elements are indistinguishable, so the sort does not need to be stable, and an
325    /// unstable sort is used.
326    ///
327    /// # Worst-case complexity
328    /// $T(n) = O(n \log n)$
329    ///
330    /// $M(n) = O(1)$
331    ///
332    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.dimension()`, assuming that
333    /// comparing two elements takes constant time; comparing large elements takes time proportional
334    /// to their sizes.
335    ///
336    /// # Examples
337    /// ```
338    /// use core::str::FromStr;
339    /// use malachite_base::vector::Vector;
340    /// use malachite_q::rational_vector::RationalVector;
341    ///
342    /// let mut v = RationalVector::from_str("(1/2, -1, 1/3, 0)").unwrap();
343    /// v.sort();
344    /// assert_eq!(v.to_string(), "(-1, 0, 1/3, 1/2)");
345    /// ```
346    ///
347    /// This is equivalent to `_fmpq_vec_sort` from `fmpq_vec/sort.c`, FLINT 3.6.0.
348    #[inline]
349    fn sort(&mut self) {
350        self.elements.sort_unstable();
351    }
352
353    /// Returns a [`RationalVector`]'s elements as a [`Vec`], cloning them.
354    ///
355    /// # Worst-case complexity
356    /// $T(n) = O(n)$
357    ///
358    /// $M(n) = O(n)$
359    ///
360    /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
361    /// elements.
362    ///
363    /// # Examples
364    /// ```
365    /// use core::str::FromStr;
366    /// use malachite_base::strings::ToDebugString;
367    /// use malachite_base::vector::Vector;
368    /// use malachite_q::rational_vector::RationalVector;
369    ///
370    /// let v = RationalVector::from_str("(1, 2, 3)").unwrap();
371    /// assert_eq!(v.to_elements().to_debug_string(), "[1, 2, 3]");
372    /// assert_eq!(
373    ///     RationalVector::from_str("()")
374    ///         .unwrap()
375    ///         .to_elements()
376    ///         .to_debug_string(),
377    ///     "[]"
378    /// );
379    /// ```
380    #[inline]
381    fn to_elements(&self) -> Vec<Rational> {
382        self.elements.clone()
383    }
384
385    /// Returns a [`RationalVector`]'s elements as a [`Vec`], taking ownership of the
386    /// [`RationalVector`].
387    ///
388    /// Nothing is copied or allocated.
389    ///
390    /// # Worst-case complexity
391    /// Constant time and additional memory.
392    ///
393    /// # Examples
394    /// ```
395    /// use core::str::FromStr;
396    /// use malachite_base::strings::ToDebugString;
397    /// use malachite_base::vector::Vector;
398    /// use malachite_q::rational_vector::RationalVector;
399    ///
400    /// let v = RationalVector::from_str("(1, 2, 3)").unwrap();
401    /// assert_eq!(v.into_elements().to_debug_string(), "[1, 2, 3]");
402    /// assert_eq!(
403    ///     RationalVector::from_str("()")
404    ///         .unwrap()
405    ///         .into_elements()
406    ///         .to_debug_string(),
407    ///     "[]"
408    /// );
409    /// ```
410    #[inline]
411    fn into_elements(self) -> Vec<Rational> {
412        self.elements
413    }
414
415    /// Returns a reference to a [`RationalVector`]'s elements, as a slice.
416    ///
417    /// # Worst-case complexity
418    /// Constant time and additional memory.
419    ///
420    /// # Examples
421    /// ```
422    /// use core::str::FromStr;
423    /// use malachite_base::strings::ToDebugString;
424    /// use malachite_base::vector::Vector;
425    /// use malachite_q::rational_vector::RationalVector;
426    ///
427    /// let v = RationalVector::from_str("(1, 2, 3)").unwrap();
428    /// assert_eq!(v.elements_ref().to_debug_string(), "[1, 2, 3]");
429    ///
430    /// // A slice of the elements can be taken directly.
431    /// let tail = &v.elements_ref()[1..];
432    /// assert_eq!(tail.to_debug_string(), "[2, 3]");
433    /// assert_eq!(
434    ///     RationalVector::from_str("()")
435    ///         .unwrap()
436    ///         .elements_ref()
437    ///         .to_debug_string(),
438    ///     "[]"
439    /// );
440    /// ```
441    #[inline]
442    fn elements_ref(&self) -> &[Rational] {
443        &self.elements
444    }
445
446    /// Returns the dimension of a [`RationalVector`]: the number of its elements.
447    ///
448    /// # Worst-case complexity
449    /// Constant time and additional memory.
450    ///
451    /// # Examples
452    /// ```
453    /// use malachite_base::vector::Vector;
454    /// use malachite_q::Rational;
455    /// use malachite_q::rational_vector::RationalVector;
456    ///
457    /// let v = RationalVector {
458    ///     elements: vec![Rational::from(4u32), Rational::from(5u32)],
459    /// };
460    /// assert_eq!(v.dimension(), 2);
461    /// assert_eq!(
462    ///     RationalVector {
463    ///         elements: Vec::new()
464    ///     }
465    ///     .dimension(),
466    ///     0
467    /// );
468    /// ```
469    #[inline]
470    fn dimension(&self) -> u64 {
471        u64::exact_from(self.elements.len())
472    }
473
474    /// Returns the pivot of a [`RationalVector`]: its first nonzero element.
475    ///
476    /// This is the element that leads the vector when it is a row of a matrix in echelon form. It
477    /// returns a reference to it, or `None` if every element is zero, which includes the
478    /// 0-dimensional vector.
479    ///
480    /// # Worst-case complexity
481    /// $T(n) = O(n)$
482    ///
483    /// $M(n) = O(1)$
484    ///
485    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.dimension()`.
486    ///
487    /// # Examples
488    /// ```
489    /// use core::str::FromStr;
490    /// use malachite_base::vector::Vector;
491    /// use malachite_q::Rational;
492    /// use malachite_q::rational_vector::RationalVector;
493    ///
494    /// assert_eq!(
495    ///     RationalVector::from_str("(0, 0, -3/4, 0, 5)")
496    ///         .unwrap()
497    ///         .pivot(),
498    ///     Some(&Rational::from_signeds(-3, 4))
499    /// );
500    /// assert_eq!(RationalVector::from_str("(0, 0)").unwrap().pivot(), None);
501    /// assert_eq!(RationalVector::from_str("()").unwrap().pivot(), None);
502    /// ```
503    #[inline]
504    fn pivot(&self) -> Option<&Rational> {
505        self.elements.iter().find(|x| **x != 0u32)
506    }
507
508    /// Returns the index of the pivot of a [`RationalVector`]: the position of its first nonzero
509    /// element.
510    ///
511    /// Indices start at 0, as they do for [`Index`](core::ops::Index). Returns `None` if every
512    /// element is zero, which includes the 0-dimensional vector. When it returns `Some(i)`,
513    /// [`pivot`](Self::pivot) is the element at `i`.
514    ///
515    /// # Worst-case complexity
516    /// $T(n) = O(n)$
517    ///
518    /// $M(n) = O(1)$
519    ///
520    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.dimension()`.
521    ///
522    /// # Examples
523    /// ```
524    /// use core::str::FromStr;
525    /// use malachite_base::vector::Vector;
526    /// use malachite_q::rational_vector::RationalVector;
527    ///
528    /// assert_eq!(
529    ///     RationalVector::from_str("(0, 0, -3/4, 0, 5)")
530    ///         .unwrap()
531    ///         .pivot_index(),
532    ///     Some(2)
533    /// );
534    /// assert_eq!(
535    ///     RationalVector::from_str("(0, 0)").unwrap().pivot_index(),
536    ///     None
537    /// );
538    /// assert_eq!(RationalVector::from_str("()").unwrap().pivot_index(), None);
539    /// ```
540    #[inline]
541    fn pivot_index(&self) -> Option<u64> {
542        self.elements
543            .iter()
544            .position(|x| *x != 0u32)
545            .map(u64::exact_from)
546    }
547
548    /// Returns the index of an element of largest height of a [`RationalVector`]: the first one,
549    /// when several are tied.
550    ///
551    /// Indices start at 0, as they do for [`Index`](core::ops::Index). Returns `None` for the
552    /// 0-dimensional vector.
553    ///
554    /// # Worst-case complexity
555    /// $T(n) = O(n)$
556    ///
557    /// $M(n) = O(1)$
558    ///
559    /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
560    /// elements.
561    ///
562    /// # Examples
563    /// ```
564    /// use core::str::FromStr;
565    /// use malachite_base::vector::Vector;
566    /// use malachite_q::rational_vector::RationalVector;
567    ///
568    /// assert_eq!(
569    ///     RationalVector::from_str("(1/2, -3, 1/4)")
570    ///         .unwrap()
571    ///         .height_index(),
572    ///     Some(2)
573    /// );
574    /// assert_eq!(
575    ///     RationalVector::from_str("(3, -1/3)")
576    ///         .unwrap()
577    ///         .height_index(),
578    ///     Some(0)
579    /// );
580    /// assert_eq!(RationalVector::from_str("()").unwrap().height_index(), None);
581    /// ```
582    #[inline]
583    fn height_index(&self) -> Option<u64> {
584        // `max_by` returns the last of several equal maxima, so iterating in reverse gives the
585        // first.
586        self.elements
587            .iter()
588            .enumerate()
589            .rev()
590            .max_by(|(_, x), (_, y)| x.height_ref().cmp(y.height_ref()))
591            .map(|(i, _)| u64::exact_from(i))
592    }
593
594    /// Determines whether every element of a [`RationalVector`] is zero.
595    ///
596    /// The 0-dimensional vector, which has no elements, counts as zero.
597    ///
598    /// # Worst-case complexity
599    /// $T(n) = O(n)$
600    ///
601    /// $M(n) = O(1)$
602    ///
603    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.dimension()`.
604    ///
605    /// # Examples
606    /// ```
607    /// use core::str::FromStr;
608    /// use malachite_base::vector::Vector;
609    /// use malachite_q::rational_vector::RationalVector;
610    ///
611    /// assert!(RationalVector::from_str("(0, 0)").unwrap().is_zero());
612    /// assert!(RationalVector::from_str("()").unwrap().is_zero());
613    /// assert!(!RationalVector::from_str("(0, 1, 0)").unwrap().is_zero());
614    /// ```
615    #[inline]
616    fn is_zero(&self) -> bool {
617        self.elements.iter().all(|x| *x == 0u32)
618    }
619
620    /// Determines whether a [`RationalVector`] is a standard basis vector, returning the index of
621    /// its 1 if it is.
622    ///
623    /// A standard basis vector has a single element equal to 1 and every other element 0. Returns
624    /// `None` for every other vector, including the zero vectors and the 0-dimensional vector.
625    ///
626    /// # Worst-case complexity
627    /// $T(n) = O(n)$
628    ///
629    /// $M(n) = O(1)$
630    ///
631    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.dimension()`.
632    ///
633    /// # Examples
634    /// ```
635    /// use core::str::FromStr;
636    /// use malachite_base::vector::Vector;
637    /// use malachite_q::rational_vector::RationalVector;
638    ///
639    /// assert_eq!(
640    ///     RationalVector::from_str("(0, 1, 0)")
641    ///         .unwrap()
642    ///         .standard_basis_index(),
643    ///     Some(1)
644    /// );
645    /// assert_eq!(
646    ///     RationalVector::from_str("(0, 1/2, 0)")
647    ///         .unwrap()
648    ///         .standard_basis_index(),
649    ///     None
650    /// );
651    /// assert_eq!(
652    ///     RationalVector::from_str("(1, 0, 1)")
653    ///         .unwrap()
654    ///         .standard_basis_index(),
655    ///     None
656    /// );
657    /// assert_eq!(
658    ///     RationalVector::from_str("(0, 0)")
659    ///         .unwrap()
660    ///         .standard_basis_index(),
661    ///     None
662    /// );
663    /// ```
664    fn standard_basis_index(&self) -> Option<u64> {
665        let index = self.pivot_index()?;
666        let i = usize::exact_from(index);
667        if self.elements[i] == 1u32 && self.elements[i + 1..].iter().all(|x| *x == 0u32) {
668            Some(index)
669        } else {
670            None
671        }
672    }
673
674    /// Returns the number of significant bits of the height of a [`RationalVector`], together with
675    /// whether any of its elements is negative.
676    ///
677    /// The bit count is that of the largest of the elements' heights, $\max(|p|, q)$ for $p/q$ in
678    /// lowest terms.
679    ///
680    /// # Worst-case complexity
681    /// $T(n) = O(n)$
682    ///
683    /// $M(n) = O(1)$
684    ///
685    /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
686    /// elements' numerators and denominators.
687    ///
688    /// # Examples
689    /// ```
690    /// use core::str::FromStr;
691    /// use malachite_base::vector::Vector;
692    /// use malachite_q::rational_vector::RationalVector;
693    ///
694    /// assert_eq!(
695    ///     RationalVector::from_str("(1/4, -2)").unwrap().max_bits(),
696    ///     (3, true)
697    /// );
698    /// assert_eq!(
699    ///     RationalVector::from_str("()").unwrap().max_bits(),
700    ///     (0, false)
701    /// );
702    /// ```
703    #[inline]
704    fn max_bits(&self) -> (u64, bool) {
705        (
706            self.height_significant_bits(),
707            self.elements.iter().any(|x| *x < 0u32),
708        )
709    }
710
711    /// Returns the number of significant bits of the sum of the absolute values of the elements of
712    /// a [`RationalVector`] (its $\ell^1$ norm), together with the number of significant bits of
713    /// its height.
714    ///
715    /// The $\ell^1$ norm is a rational number, and, as for a single [`Rational`], its number of
716    /// significant bits is the sum of those of its numerator and denominator. So a norm of 0, which
717    /// is $0/1$, has 1 significant bit, even for the 0-dimensional vector.
718    ///
719    /// # Worst-case complexity
720    /// $T(n) = O(n)$
721    ///
722    /// $M(n) = O(n)$
723    ///
724    /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
725    /// elements' numerators and denominators.
726    ///
727    /// # Examples
728    /// ```
729    /// use core::str::FromStr;
730    /// use malachite_base::vector::Vector;
731    /// use malachite_q::rational_vector::RationalVector;
732    ///
733    /// assert_eq!(
734    ///     RationalVector::from_str("(1/2, -1/3)")
735    ///         .unwrap()
736    ///         .sum_max_bits(),
737    ///     (6, 2)
738    /// );
739    /// assert_eq!(
740    ///     RationalVector::from_str("()").unwrap().sum_max_bits(),
741    ///     (1, 0)
742    /// );
743    /// ```
744    fn sum_max_bits(&self) -> (u64, u64) {
745        (
746            self.l1_norm_significant_bits(),
747            self.height_significant_bits(),
748        )
749    }
750}
751
752// Implements `Named` for `RationalVector`.
753impl_named!(RationalVector);
754
755/// `ShortlexRationalVector` is a wrapper around a [`RationalVector`], taking the [`RationalVector`]
756/// by value.
757///
758/// [`RationalVector`] does not implement [`Ord`], because no order on vectors is canonical: lex,
759/// graded lex, and the others all have their uses, and the order most natural mathematically,
760/// comparing vectors of the same dimension element by element, is only partial. Wrapping a
761/// [`RationalVector`] in a `ShortlexRationalVector` provides one total order: vectors are compared
762/// first by dimension and then, in case of a tie, lexicographically, by their elements from first
763/// to last. Its equality agrees with [`RationalVector`] equality.
764///
765/// Unlike lexicographic order on [`Vec`]s, this order puts every vector of a smaller dimension
766/// before every vector of a larger one, so that $(5) < (0, 0)$. It is not a well-order, since the
767/// [`Rational`]s are not: $(0) > (-1) > (-2) > \ldots$ descends forever.
768///
769/// `ShortlexRationalVector` owns its value. This is useful in many cases, for example if you want
770/// to use [`RationalVector`]s as keys in a [`BTreeMap`](alloc::collections::BTreeMap). In other
771/// situations, it is better to use [`ShortlexRationalVectorRef`], which only has a reference to its
772/// value.
773// Serialized as its inner `RationalVector`, since the wrapper adds no data of its own.
774#[derive(Clone, Debug, Eq, Hash, PartialEq)]
775#[cfg_attr(feature = "serde", derive(Deserialize, Serialize))]
776#[cfg_attr(feature = "serde", serde(transparent))]
777pub struct ShortlexRationalVector(pub RationalVector);
778
779/// `ShortlexRationalVectorRef` is a wrapper around a [`RationalVector`], taking the
780/// [`RationalVector`] by reference.
781///
782/// See the [`ShortlexRationalVector`] documentation for details.
783#[derive(Clone, Debug, Eq, Hash, PartialEq)]
784pub struct ShortlexRationalVectorRef<'a>(pub &'a RationalVector);
785
786impl ShortlexRationalVector {
787    /// Borrows a [`ShortlexRationalVector`] as a [`ShortlexRationalVectorRef`].
788    ///
789    /// # Worst-case complexity
790    /// Constant time and additional memory.
791    ///
792    /// # Examples
793    /// ```
794    /// use core::str::FromStr;
795    /// use malachite_q::rational_vector::{
796    ///     RationalVector, ShortlexRationalVector, ShortlexRationalVectorRef,
797    /// };
798    ///
799    /// let v = RationalVector::from_str("(1, 2, 3)").unwrap();
800    /// let x = ShortlexRationalVector(v.clone());
801    /// assert_eq!(x.as_ref(), ShortlexRationalVectorRef(&v));
802    /// ```
803    pub const fn as_ref(&self) -> ShortlexRationalVectorRef<'_> {
804        ShortlexRationalVectorRef(&self.0)
805    }
806}
807
808impl Deref for ShortlexRationalVector {
809    type Target = RationalVector;
810
811    /// Allows a [`ShortlexRationalVector`] to dereference to a [`RationalVector`].
812    ///
813    /// ```
814    /// use core::str::FromStr;
815    /// use malachite_q::rational_vector::{RationalVector, ShortlexRationalVector};
816    ///
817    /// let v = RationalVector::from_str("(1, 2, 3)").unwrap();
818    /// let x = ShortlexRationalVector(v.clone());
819    /// assert_eq!(*x, v);
820    /// ```
821    fn deref(&self) -> &RationalVector {
822        &self.0
823    }
824}
825
826impl Deref for ShortlexRationalVectorRef<'_> {
827    type Target = RationalVector;
828
829    /// Allows a [`ShortlexRationalVectorRef`] to dereference to a [`RationalVector`].
830    ///
831    /// ```
832    /// use core::str::FromStr;
833    /// use malachite_q::rational_vector::{RationalVector, ShortlexRationalVectorRef};
834    ///
835    /// let v = RationalVector::from_str("(1, 2, 3)").unwrap();
836    /// let x = ShortlexRationalVectorRef(&v);
837    /// assert_eq!(*x, v);
838    /// ```
839    fn deref(&self) -> &RationalVector {
840        self.0
841    }
842}
malachite_q/rational_vector/mod.rs

malachite_q/rational_vector/
mod.rs
