sparse_vector/vector.rs
1use std::collections::btree_map;
2use std::collections::BTreeMap;
3use std::fmt;
4use std::iter::FusedIterator;
5
6use crate::Element;
7
8/// A sparse vector: a mapping from integer index to arbitrary value, in which
9/// only the positions that differ from a default value are stored.
10///
11/// Because only non-default positions are kept, a vector occupies O(k) memory for
12/// k stored entries no matter how far apart the indices are, and whether they are
13/// large or negative. Indices need not be contiguous, and an index holding no
14/// explicit entry simply reports the default value.
15pub struct SparseVector<T = f64> {
16 // Ordered on purpose: `keys`, `values`, `elements` and `iter` all guarantee
17 // ascending index order, which this container gives for free.
18 entries: BTreeMap<i64, T>,
19 default: T,
20}
21
22impl<T> SparseVector<T> {
23 /// Creates a vector whose empty positions read back as `default`.
24 pub fn with_default(default: T) -> Self {
25 Self {
26 entries: BTreeMap::new(),
27 default,
28 }
29 }
30
31 /// The value reported for every position that has no explicit entry.
32 ///
33 /// There is deliberately no `&mut` counterpart: mutating the default has to
34 /// prune, which [`set_default_value`](Self::set_default_value) does.
35 pub fn default_value(&self) -> &T {
36 &self.default
37 }
38
39 /// The number of explicitly stored entries.
40 pub fn len(&self) -> usize {
41 self.entries.len()
42 }
43
44 /// Whether no entry is stored at all.
45 pub fn is_empty(&self) -> bool {
46 self.entries.is_empty()
47 }
48
49 /// Whether `index` has an explicitly stored entry.
50 pub fn contains_key(&self, index: i64) -> bool {
51 self.entries.contains_key(&index)
52 }
53
54 /// Removes every explicit entry, keeping the default value.
55 pub fn clear(&mut self) {
56 self.entries.clear();
57 }
58
59 /// The indices holding an explicit entry, in ascending order.
60 pub fn keys(&self) -> Vec<i64> {
61 self.entries.keys().copied().collect()
62 }
63
64 /// The index of the entry at 0-based ordinal `n` of [`elements`](Self::elements),
65 /// counting from the left.
66 ///
67 /// The ordinal numbers the entries, not the positions: ordinal `0` is the
68 /// leftmost stored entry however far out its index lies.
69 ///
70 /// # Panics
71 ///
72 /// Panics when fewer than n + 1 entries are stored.
73 pub fn element_index(&self, n: usize) -> i64 {
74 *self.at_ordinal(n, false).0
75 }
76
77 /// The index of the entry at 0-based ordinal `n` of [`elements`](Self::elements),
78 /// counting from the right.
79 ///
80 /// Ordinal `0` is the rightmost stored entry.
81 ///
82 /// # Panics
83 ///
84 /// Panics when fewer than n + 1 entries are stored.
85 pub fn last_element_index(&self, n: usize) -> i64 {
86 *self.at_ordinal(n, true).0
87 }
88
89 /// Iterates the explicit entries in ascending index order, borrowing them.
90 ///
91 /// Reach for this instead of [`elements`](Self::elements) when you do not
92 /// want to allocate.
93 pub fn iter(&self) -> Iter<'_, T> {
94 Iter {
95 inner: self.entries.iter(),
96 }
97 }
98
99 /// The entry at 0-based ordinal `n` from whichever end.
100 ///
101 /// Walks the map rather than going through [`elements`](Self::elements),
102 /// which would copy the whole array to read one element of it.
103 fn at_ordinal(&self, n: usize, from_right: bool) -> (&i64, &T) {
104 let entry = if from_right {
105 self.entries.iter().nth_back(n)
106 } else {
107 self.entries.iter().nth(n)
108 };
109 match entry {
110 Some(entry) => entry,
111 None => {
112 let side = if from_right { "right" } else { "left" };
113 panic!(
114 "SparseVector holds {} entries, so there is no entry {} from the {}",
115 self.entries.len(),
116 n,
117 side
118 )
119 }
120 }
121 }
122
123 /// The outermost stored index, the first one or the last one.
124 ///
125 /// # Panics
126 ///
127 /// Panics when nothing is stored, there being no position to measure from.
128 fn anchor(&self, from_left: bool) -> i64 {
129 let index = if from_left {
130 self.entries.keys().next()
131 } else {
132 self.entries.keys().next_back()
133 };
134 match index {
135 Some(&index) => index,
136 None => panic!("SparseVector holds no entries, so there is nothing to measure from"),
137 }
138 }
139}
140
141impl SparseVector<f64> {
142 /// Creates a vector whose empty positions read back as `0.0`.
143 ///
144 /// This exists only for `f64`, where the `0` the shared semantics name is a
145 /// value of the right type; for any other `T` use
146 /// [`with_default`](Self::with_default).
147 pub fn new() -> Self {
148 Self::with_default(0.0)
149 }
150}
151
152impl<T: Default> Default for SparseVector<T> {
153 fn default() -> Self {
154 Self::with_default(T::default())
155 }
156}
157
158impl<T: Clone> SparseVector<T> {
159 /// The value at `index`, or the default value when nothing is stored there.
160 ///
161 /// Reading is total: every `i64`, negative, huge or far outside anything ever
162 /// written, returns a value rather than failing, so this returns `T` and not
163 /// `Option<T>`.
164 pub fn get(&self, index: i64) -> T {
165 match self.entries.get(&index) {
166 Some(value) => value.clone(),
167 None => self.default.clone(),
168 }
169 }
170
171 /// The explicit entries, in ascending index order.
172 ///
173 /// This is the serialization shape described on [`Element`].
174 pub fn elements(&self) -> Vec<Element<T>> {
175 self.entries
176 .iter()
177 .map(|(&index, value)| Element {
178 index,
179 value: value.clone(),
180 })
181 .collect()
182 }
183
184 /// The stored values, in ascending index order.
185 pub fn values(&self) -> Vec<T> {
186 self.entries.values().cloned().collect()
187 }
188
189 /// The element at 0-based ordinal `n` of [`elements`](Self::elements),
190 /// counting from the left.
191 ///
192 /// The ordinal numbers the entries, not the positions: `element(0)` is the
193 /// leftmost stored entry however far out its index lies.
194 ///
195 /// # Panics
196 ///
197 /// Panics when fewer than n + 1 entries are stored.
198 pub fn element(&self, n: usize) -> Element<T> {
199 let (&index, value) = self.at_ordinal(n, false);
200 Element {
201 index,
202 value: value.clone(),
203 }
204 }
205
206 /// The value of the entry at 0-based ordinal `n`, counting from the left.
207 ///
208 /// # Panics
209 ///
210 /// Panics when fewer than n + 1 entries are stored.
211 pub fn element_value(&self, n: usize) -> T {
212 self.at_ordinal(n, false).1.clone()
213 }
214
215 /// The element at 0-based ordinal `n` of [`elements`](Self::elements),
216 /// counting from the right.
217 ///
218 /// `last_element(0)` is the rightmost stored entry.
219 ///
220 /// # Panics
221 ///
222 /// Panics when fewer than n + 1 entries are stored.
223 pub fn last_element(&self, n: usize) -> Element<T> {
224 let (&index, value) = self.at_ordinal(n, true);
225 Element {
226 index,
227 value: value.clone(),
228 }
229 }
230
231 /// The value of the entry at 0-based ordinal `n`, counting from the right.
232 ///
233 /// # Panics
234 ///
235 /// Panics when fewer than n + 1 entries are stored.
236 pub fn last_element_value(&self, n: usize) -> T {
237 self.at_ordinal(n, true).1.clone()
238 }
239
240 /// Treating the first stored entry as the first significant digit, the value
241 /// `n` positions to its right.
242 ///
243 /// Positions without an entry in between count, the way the zeros inside a
244 /// number count towards its sign. `n` may be negative, which walks left of
245 /// that first entry instead; the result is then the default value.
246 ///
247 /// # Panics
248 ///
249 /// Panics when nothing is stored, so there is no position to measure from, or
250 /// when the position leaves the `i64` range.
251 pub fn left_significant_value(&self, n: i64) -> T {
252 let anchor = self.anchor(true);
253 let index = anchor
254 .checked_add(n)
255 .unwrap_or_else(|| panic!("SparseVector position {anchor} + {n} overflows i64"));
256 self.get(index)
257 }
258
259 /// Treating the last stored entry as the first significant digit counting
260 /// from the right, the value `n` positions to its left.
261 ///
262 /// `n` may be negative, which walks right of that last entry instead.
263 ///
264 /// # Panics
265 ///
266 /// Panics when nothing is stored, so there is no position to measure from, or
267 /// when the position leaves the `i64` range.
268 pub fn right_significant_value(&self, n: i64) -> T {
269 let anchor = self.anchor(false);
270 let index = anchor
271 .checked_sub(n)
272 .unwrap_or_else(|| panic!("SparseVector position {anchor} - {n} overflows i64"));
273 self.get(index)
274 }
275}
276
277impl<T: PartialEq> SparseVector<T> {
278 /// Inserts or updates `value` at `index`, returning `&mut self` so calls chain.
279 ///
280 /// Writing a value equal to the default removes whatever was there instead of
281 /// storing it: that is what keeps the structure sparse.
282 pub fn set(&mut self, index: i64, value: T) -> &mut Self {
283 if value == self.default {
284 self.entries.remove(&index);
285 } else {
286 self.entries.insert(index, value);
287 }
288 self
289 }
290
291 /// Replaces the default value, immediately dropping every entry equal to it.
292 ///
293 /// Pruning is one-way: the previous default is not remembered, so positions
294 /// dropped here never come back.
295 pub fn set_default_value(&mut self, next: T) {
296 self.default = next;
297 self.prune();
298 }
299
300 /// Removes the explicit entry at `index` and returns it, if there was one.
301 ///
302 /// The position subsequently reads back as the default value. Returned as an
303 /// `Option` rather than a `bool` so the removed value is available;
304 /// `.is_some()` recovers the boolean.
305 pub fn remove(&mut self, index: i64) -> Option<T> {
306 self.entries.remove(&index)
307 }
308
309 /// Builds a vector from a sequence of elements.
310 ///
311 /// Entries equal to the default are dropped, and for a repeated index the
312 /// last element wins, both because this goes through [`set`](Self::set).
313 pub fn from_elements<I>(elements: I, default: T) -> Self
314 where
315 I: IntoIterator<Item = Element<T>>,
316 {
317 let mut vector = Self::with_default(default);
318 for element in elements {
319 vector.set(element.index, element.value);
320 }
321 vector
322 }
323
324 /// Drops every entry equal to the current default.
325 fn prune(&mut self) {
326 let default = &self.default;
327 self.entries.retain(|_, value| value != default);
328 }
329}
330
331impl<T: Clone> Clone for SparseVector<T> {
332 /// An independent copy, default value included.
333 fn clone(&self) -> Self {
334 Self {
335 entries: self.entries.clone(),
336 default: self.default.clone(),
337 }
338 }
339}
340
341impl<T: fmt::Debug> fmt::Debug for SparseVector<T> {
342 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
343 f.debug_struct("SparseVector")
344 .field("default", &self.default)
345 .field("entries", &self.entries)
346 .finish()
347 }
348}
349
350impl<'a, T> IntoIterator for &'a SparseVector<T> {
351 type Item = Element<&'a T>;
352 type IntoIter = Iter<'a, T>;
353
354 fn into_iter(self) -> Self::IntoIter {
355 self.iter()
356 }
357}
358
359/// An iterator over the entries of a [`SparseVector`], in ascending index order.
360///
361/// Yields [`Element<&T>`](Element), borrowing the stored values.
362pub struct Iter<'a, T> {
363 inner: btree_map::Iter<'a, i64, T>,
364}
365
366impl<'a, T> Iterator for Iter<'a, T> {
367 type Item = Element<&'a T>;
368
369 fn next(&mut self) -> Option<Self::Item> {
370 self.inner
371 .next()
372 .map(|(&index, value)| Element { index, value })
373 }
374
375 fn size_hint(&self) -> (usize, Option<usize>) {
376 self.inner.size_hint()
377 }
378}
379
380impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
381 fn next_back(&mut self) -> Option<Self::Item> {
382 self.inner
383 .next_back()
384 .map(|(&index, value)| Element { index, value })
385 }
386}
387
388impl<T> ExactSizeIterator for Iter<'_, T> {
389 fn len(&self) -> usize {
390 self.inner.len()
391 }
392}
393
394impl<T> FusedIterator for Iter<'_, T> {}