Skip to main content

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 that stores only the
9/// positions differing from the default value. Entries are ordered largest index leftmost.
10pub struct SparseVector<T = f64> {
11    // Kept ascending, the order every ordered view reverses.
12    entries: BTreeMap<i64, T>,
13    default: T,
14}
15
16impl<T> SparseVector<T> {
17    /// Creates a vector whose empty positions read back as `default`.
18    pub fn with_default(default: T) -> Self {
19        Self {
20            entries: BTreeMap::new(),
21            default,
22        }
23    }
24
25    /// The value reported for every position with no explicit entry.
26    ///
27    /// There is deliberately no `&mut` counterpart; use
28    /// [`set_default_value`](Self::set_default_value), which prunes.
29    pub fn get_default_value(&self) -> &T {
30        &self.default
31    }
32
33    /// The number of explicitly stored entries.
34    pub fn get_element_amount(&self) -> usize {
35        self.entries.len()
36    }
37
38    /// The distance between the leftmost and rightmost entries, both included; zero when empty.
39    ///
40    /// # Panics
41    ///
42    /// Panics when the span leaves the `i64` range.
43    pub fn get_significant_dimension(&self) -> i64 {
44        match (self.entries.first_key_value(), self.entries.last_key_value()) {
45            (Some((&smallest, _)), Some((&largest, _))) => largest
46                .checked_sub(smallest)
47                .and_then(|span| span.checked_add(1))
48                .unwrap_or_else(|| panic!("SparseVector span {smallest}..={largest} overflows i64")),
49            _ => 0,
50        }
51    }
52
53    /// How far the vector reaches above zero: the leftmost index itself, or zero.
54    pub fn get_plus_dimension(&self) -> i64 {
55        match self.entries.last_key_value() {
56            Some((&leftmost, _)) if leftmost > 0 => leftmost,
57            _ => 0,
58        }
59    }
60
61    /// How far the vector reaches below zero: the rightmost index negated, or zero.
62    ///
63    /// # Panics
64    ///
65    /// Panics when the negation leaves the `i64` range.
66    pub fn get_minus_dimension(&self) -> i64 {
67        match self.entries.first_key_value() {
68            Some((&rightmost, _)) if rightmost < 0 => rightmost
69                .checked_neg()
70                .unwrap_or_else(|| panic!("SparseVector index {rightmost} cannot be negated")),
71            _ => 0,
72        }
73    }
74
75    /// Resets every explicit entry, keeping the default value.
76    pub fn reset_vector(&mut self) {
77        self.entries.clear();
78    }
79
80    /// The stored indices, descending.
81    pub fn indexes(&self) -> Vec<i64> {
82        self.entries.keys().rev().copied().collect()
83    }
84
85    /// The stored indices, ascending.
86    pub fn inverted_indexes(&self) -> Vec<i64> {
87        self.entries.keys().copied().collect()
88    }
89
90    /// The index of the (n+1)-th entry from the left; the ordinal numbers the entries, not
91    /// the positions.
92    ///
93    /// # Panics
94    ///
95    /// Panics when fewer than n + 1 entries are stored.
96    pub fn element_index(&self, n: usize) -> i64 {
97        *self.at_ordinal(n, false).0
98    }
99
100    /// The index of the (n+1)-th entry from the right.
101    ///
102    /// # Panics
103    ///
104    /// Panics when fewer than n + 1 entries are stored.
105    pub fn inverted_element_index(&self, n: usize) -> i64 {
106        *self.at_ordinal(n, true).0
107    }
108
109    /// Iterates the entries descending by index, borrowing them, without allocating.
110    pub fn iter(&self) -> Iter<'_, T> {
111        Iter {
112            inner: self.entries.iter(),
113        }
114    }
115
116    /// The entry at 0-based ordinal `n` from whichever end.
117    fn at_ordinal(&self, n: usize, inverted: bool) -> (&i64, &T) {
118        let entry = if inverted {
119            self.entries.iter().nth(n)
120        } else {
121            self.entries.iter().nth_back(n)
122        };
123        match entry {
124            Some(entry) => entry,
125            None => {
126                let side = if inverted { "right" } else { "left" };
127                panic!(
128                    "SparseVector holds {} entries, so there is no entry {} from the {}",
129                    self.entries.len(),
130                    n,
131                    side
132                )
133            }
134        }
135    }
136
137    fn anchor(&self, inverted: bool) -> i64 {
138        let index = if inverted {
139            self.entries.keys().next()
140        } else {
141            self.entries.keys().next_back()
142        };
143        match index {
144            Some(&index) => index,
145            None => panic!("SparseVector holds no entries, so there is nothing to measure from"),
146        }
147    }
148}
149
150impl SparseVector<f64> {
151    /// Creates a vector whose empty positions read back as `0.0`; for any other `T` use
152    /// [`with_default`](Self::with_default).
153    pub fn new() -> Self {
154        Self::with_default(0.0)
155    }
156}
157
158impl<T: Default> Default for SparseVector<T> {
159    fn default() -> Self {
160        Self::with_default(T::default())
161    }
162}
163
164impl<T: Clone> SparseVector<T> {
165    /// The value at `index`, or the default value when nothing is stored there. Reading is
166    /// total, so it returns `T` and not `Option<T>`.
167    pub fn get(&self, index: i64) -> T {
168        match self.entries.get(&index) {
169            Some(value) => value.clone(),
170            None => self.default.clone(),
171        }
172    }
173
174    /// The explicit entries, descending by index: the serialization shape described on
175    /// [`Element`].
176    pub fn elements(&self) -> Vec<Element<T>> {
177        self.entries
178            .iter()
179            .rev()
180            .map(|(&index, value)| Element {
181                index,
182                value: value.clone(),
183            })
184            .collect()
185    }
186
187    /// The explicit entries, ascending by index.
188    pub fn inverted_elements(&self) -> Vec<Element<T>> {
189        self.entries
190            .iter()
191            .map(|(&index, value)| Element {
192                index,
193                value: value.clone(),
194            })
195            .collect()
196    }
197
198    /// The stored values, descending by index.
199    pub fn values(&self) -> Vec<T> {
200        self.entries.values().rev().cloned().collect()
201    }
202
203    /// The stored values, ascending by index.
204    pub fn inverted_values(&self) -> Vec<T> {
205        self.entries.values().cloned().collect()
206    }
207
208    /// The (n+1)-th entry from the left; the ordinal numbers the entries, not the positions.
209    ///
210    /// # Panics
211    ///
212    /// Panics when fewer than n + 1 entries are stored.
213    pub fn element(&self, n: usize) -> Element<T> {
214        let (&index, value) = self.at_ordinal(n, false);
215        Element {
216            index,
217            value: value.clone(),
218        }
219    }
220
221    /// The value of the (n+1)-th entry from the left.
222    ///
223    /// # Panics
224    ///
225    /// Panics when fewer than n + 1 entries are stored.
226    pub fn element_value(&self, n: usize) -> T {
227        self.at_ordinal(n, false).1.clone()
228    }
229
230    /// The (n+1)-th entry from the right, `inverted_element(0)` being the rightmost.
231    ///
232    /// # Panics
233    ///
234    /// Panics when fewer than n + 1 entries are stored.
235    pub fn inverted_element(&self, n: usize) -> Element<T> {
236        let (&index, value) = self.at_ordinal(n, true);
237        Element {
238            index,
239            value: value.clone(),
240        }
241    }
242
243    /// The value of the (n+1)-th entry from the right.
244    ///
245    /// # Panics
246    ///
247    /// Panics when fewer than n + 1 entries are stored.
248    pub fn inverted_element_value(&self, n: usize) -> T {
249        self.at_ordinal(n, true).1.clone()
250    }
251
252    /// The value `n` positions right of the leftmost entry, empty positions counting; a
253    /// negative `n` walks left of it, into the default value.
254    ///
255    /// # Panics
256    ///
257    /// Panics when nothing is stored, or the position leaves the `i64` range.
258    pub fn left_significant_value(&self, n: i64) -> T {
259        let anchor = self.anchor(false);
260        let index = anchor
261            .checked_sub(n)
262            .unwrap_or_else(|| panic!("SparseVector position {anchor} - {n} overflows i64"));
263        self.get(index)
264    }
265
266    /// The value `n` positions left of the rightmost entry; a negative `n` walks right of it.
267    ///
268    /// # Panics
269    ///
270    /// Panics when nothing is stored, or the position leaves the `i64` range.
271    pub fn right_significant_value(&self, n: i64) -> T {
272        let anchor = self.anchor(true);
273        let index = anchor
274            .checked_add(n)
275            .unwrap_or_else(|| panic!("SparseVector position {anchor} + {n} overflows i64"));
276        self.get(index)
277    }
278}
279
280impl<T: PartialEq> SparseVector<T> {
281    /// Inserts or updates the entry at `index`, returning `&mut self` so calls chain;
282    /// writing the default removes instead.
283    pub fn set(&mut self, index: i64, value: T) -> &mut Self {
284        if value == self.default {
285            self.entries.remove(&index);
286        } else {
287            self.entries.insert(index, value);
288        }
289        self
290    }
291
292    /// Replaces the default value, immediately dropping every entry equal to it. Pruning is
293    /// one-way: dropped positions never come back.
294    pub fn set_default_value(&mut self, next: T) {
295        self.default = next;
296        self.prune();
297    }
298
299    /// Resets the entry at `index` and returns it if there was one. Returned as an `Option`
300    /// rather than a `bool`, so `.is_some()` recovers the boolean.
301    pub fn reset_value(&mut self, index: i64) -> Option<T> {
302        self.entries.remove(&index)
303    }
304
305    /// Builds from any iterator of elements, dropping those equal to the default and keeping
306    /// the last of a repeated index.
307    pub fn from_elements<I>(elements: I, default: T) -> Self
308    where
309        I: IntoIterator<Item = Element<T>>,
310    {
311        let mut vector = Self::with_default(default);
312        for element in elements {
313            vector.set(element.index, element.value);
314        }
315        vector
316    }
317
318    fn prune(&mut self) {
319        let default = &self.default;
320        self.entries.retain(|_, value| value != default);
321    }
322}
323
324impl<T: Clone> Clone for SparseVector<T> {
325    /// An independent copy, default value included.
326    fn clone(&self) -> Self {
327        Self {
328            entries: self.entries.clone(),
329            default: self.default.clone(),
330        }
331    }
332}
333
334// The storage as it is, ascending, not one of the ordered views.
335impl<T: fmt::Debug> fmt::Debug for SparseVector<T> {
336    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
337        f.debug_struct("SparseVector")
338            .field("default", &self.default)
339            .field("entries", &self.entries)
340            .finish()
341    }
342}
343
344impl<'a, T> IntoIterator for &'a SparseVector<T> {
345    type Item = Element<&'a T>;
346    type IntoIter = Iter<'a, T>;
347
348    fn into_iter(self) -> Self::IntoIter {
349        self.iter()
350    }
351}
352
353/// An iterator over the entries of a [`SparseVector`], descending by index and borrowing the
354/// stored values as [`Element<&T>`](Element).
355pub struct Iter<'a, T> {
356    inner: btree_map::Iter<'a, i64, T>,
357}
358
359impl<'a, T> Iterator for Iter<'a, T> {
360    type Item = Element<&'a T>;
361
362    /// The inner map is ascending while this iterator is descending, so the ends swap here.
363    fn next(&mut self) -> Option<Self::Item> {
364        self.inner
365            .next_back()
366            .map(|(&index, value)| Element { index, value })
367    }
368
369    fn size_hint(&self) -> (usize, Option<usize>) {
370        self.inner.size_hint()
371    }
372}
373
374impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
375    fn next_back(&mut self) -> Option<Self::Item> {
376        self.inner
377            .next()
378            .map(|(&index, value)| Element { index, value })
379    }
380}
381
382impl<T> ExactSizeIterator for Iter<'_, T> {
383    fn len(&self) -> usize {
384        self.inner.len()
385    }
386}
387
388impl<T> FusedIterator for Iter<'_, T> {}