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