1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
// Copyright © 2026 Mikhail Hogrefe
//
// This file is part of Malachite.
//
// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
use crate::num::conversion::traits::ExactFrom;
use alloc::vec;
use alloc::vec::Vec;
use core::mem::take;
/// What every vector type has in common: a vector of a fixed dimension, stored as its elements in
/// order.
///
/// The functions here are the ones whose meaning does not depend on what the elements are. Each
/// implementation documents its own complexity and gives its own examples.
pub trait Vector: Sized {
/// The type of an element.
type Element;
/// What [`pivot`](Self::pivot) returns.
///
/// This is a reference to an [`Element`](Self::Element) when the vector holds elements that are
/// expensive to copy, and an [`Element`](Self::Element) itself when one is cheap to copy.
type ElementOutput<'a>
where
Self: 'a;
/// Converts a slice to a vector, cloning the elements.
///
/// The vector's dimension is the length of the slice. Every slice is a valid vector, so this
/// cannot fail; the empty slice gives the 0-dimensional vector.
fn from_elements(xs: &[Self::Element]) -> Self
where
Self::Element: Clone;
/// Converts a [`Vec`] to a vector, taking ownership of it.
///
/// The vector's dimension is the length of the [`Vec`]. Every [`Vec`] is a valid vector, so
/// this cannot fail, and nothing is copied or allocated.
fn from_owned_elements(xs: Vec<Self::Element>) -> Self;
/// Returns the zero vector of a given dimension: a vector of `dimension` zeros.
fn zero(dimension: u64) -> Self;
/// Returns a standard basis vector: the vector of a given dimension whose element at `index` is
/// 1 and whose other elements are 0.
fn standard_basis_vector(dimension: u64, index: u64) -> Self;
/// Appends an element to the end of a vector, increasing its dimension by 1.
fn push(&mut self, x: Self::Element);
/// Sets the dimension of a vector, removing elements from the end if the new dimension is
/// smaller, and appending zeros if it is larger.
fn set_dimension(&mut self, dimension: u64);
/// Sets every element of a vector to zero, keeping its dimension.
fn set_zero(&mut self);
/// Sorts the elements of a vector in ascending order, keeping its dimension.
fn sort(&mut self);
/// Returns a vector's elements as a [`Vec`], cloning them.
fn to_elements(&self) -> Vec<Self::Element>
where
Self::Element: Clone;
/// Returns a vector's elements as a [`Vec`], taking ownership of the vector.
///
/// The [`Vec`] is what [`from_owned_elements`](Self::from_owned_elements) would take back.
fn into_elements(self) -> Vec<Self::Element>;
/// Returns a reference to a vector's elements, as a slice.
fn elements_ref(&self) -> &[Self::Element];
/// Returns the dimension of a vector: the number of its elements.
fn dimension(&self) -> u64;
/// Determines whether every element of a vector is zero. This includes the 0-dimensional
/// vector, which has no elements.
fn is_zero(&self) -> bool;
/// Returns the pivot of a vector: its first nonzero element.
///
/// This is the element that leads the vector when it is a row of a matrix in echelon form.
/// Returns `None` if every element is zero, which includes the 0-dimensional vector.
fn pivot(&self) -> Option<Self::ElementOutput<'_>>;
/// Returns the index of the pivot of a vector: the position of its first nonzero element.
///
/// Indices start at 0, as they do for [`Index`](core::ops::Index). Returns `None` if every
/// element is zero, which includes the 0-dimensional vector. When it returns `Some(i)`,
/// [`pivot`](Self::pivot) is the element at `i`.
fn pivot_index(&self) -> Option<u64>;
/// Returns the index of an element of largest height: the first one, when several share it.
///
/// The height of an integer is its absolute value, and the height of a rational number $p/q$ in
/// lowest terms is $\max(|p|, q)$. Returns `None` for the 0-dimensional vector.
fn height_index(&self) -> Option<u64>;
/// Determines whether a vector is a standard basis vector, returning the index of its 1 if it
/// is.
///
/// A standard basis vector has a single element equal to 1 and every other element 0, as
/// [`standard_basis_vector`](Self::standard_basis_vector) builds. Returns `None` for every
/// other vector, including the zero vectors and the 0-dimensional vector. When it returns
/// `Some(i)`, `i` is also the [`pivot_index`](Self::pivot_index), and the vector equals
/// `standard_basis_vector(self.dimension(), i)`.
fn standard_basis_index(&self) -> Option<u64>;
/// Returns the number of significant bits of a vector's height, together with whether any of
/// its elements is negative.
///
/// The bit count is the largest bit length of any element's height, or 0 for the 0-dimensional
/// vector; it is what `Height::height_significant_bits` returns.
fn max_bits(&self) -> (u64, bool);
/// Returns the number of significant bits of a vector's $\ell^1$ norm, the sum of the absolute
/// values of its elements, together with the number of significant bits of its height.
///
/// The counts are what `L1Norm::l1_norm_significant_bits` and `Height::height_significant_bits`
/// return, computed together in one pass where possible. The height of the 0-dimensional vector
/// is 0, and so, for integer elements, is its norm.
fn sum_max_bits(&self) -> (u64, u64);
}
/// Selects coordinates of a vector by index: the result's element $j$ is the original's element
/// `indices[j]`.
///
/// The indices may repeat and may appear in any order, so this covers projection onto some of the
/// coordinates (strictly increasing indices), permutation, and duplication of coordinates. The
/// result's dimension is the number of indices.
pub trait SelectCoordinates {
type Output;
fn select_coordinates(self, indices: &[u64]) -> Self::Output;
}
/// Selects coordinates of a vector by index, in place: afterwards, element $j$ of the vector is
/// what element `indices[j]` was before.
pub trait SelectCoordinatesAssign {
fn select_coordinates_assign(&mut self, indices: &[u64]);
}
fn check_index(index: u64, dimension: usize) -> usize {
let index = usize::exact_from(index);
assert!(
index < dimension,
"index {index} is out of range for a vector of dimension {dimension}"
);
index
}
// The elements of `xs` at `indices`, cloned. Panics if an index is out of range.
#[doc(hidden)]
#[inline]
pub fn select_elements<T: Clone>(xs: &[T], indices: &[u64]) -> Vec<T> {
indices
.iter()
.map(|&i| xs[check_index(i, xs.len())].clone())
.collect()
}
// Replaces `xs` with its elements at `indices`, cloning as few as possible. Panics if an index is
// out of range.
//
// When the indices are strictly increasing, the selected elements are swapped into place and the
// rest truncated away, so nothing is cloned or allocated. Otherwise each element is moved out at
// its last use and cloned at any earlier one, so an element is cloned once for each extra time it
// is selected, which is as few clones as any method needs.
#[doc(hidden)]
pub fn select_elements_in_place<T: Clone + Default>(xs: &mut Vec<T>, indices: &[u64]) {
let n = xs.len();
if indices.windows(2).all(|w| w[0] < w[1]) {
if let Some(&last) = indices.last() {
check_index(last, n);
}
for (j, &i) in indices.iter().enumerate() {
let i = usize::exact_from(i);
if i != j {
xs.swap(j, i);
}
}
xs.truncate(indices.len());
return;
}
let mut last_use = vec![usize::MAX; n];
for (j, &i) in indices.iter().enumerate() {
last_use[check_index(i, n)] = j;
}
let mut selected = Vec::with_capacity(indices.len());
for (j, &i) in indices.iter().enumerate() {
let i = usize::exact_from(i);
selected.push(if last_use[i] == j {
take(&mut xs[i])
} else {
xs[i].clone()
});
}
*xs = selected;
}