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, 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> {}