Skip to main content

sparse_vector/
vector.rs

1use std::collections::btree_map;
2use std::collections::BTreeMap;
3use std::fmt;
4use std::iter::FusedIterator;
5use std::panic::RefUnwindSafe;
6use std::sync::Arc;
7
8use crate::Element;
9
10/// The custom equality predicate, called with the value under test first and the current
11/// default second. It replaces `PartialEq`, in pruning as everywhere else.
12///
13/// `RefUnwindSafe` is required so that holding a predicate does not cost a
14/// `SparseVector` its own `UnwindSafe`.
15pub type Equality<T> = Arc<dyn Fn(&T, &T) -> bool + Send + Sync + RefUnwindSafe>;
16
17/// A sparse vector: a mapping from integer index to arbitrary value that stores only the
18/// positions differing from the default value. Entries are ordered largest index leftmost.
19pub struct SparseVector<T = f64> {
20    // Kept ascending, the order every ordered view reverses.
21    elements: BTreeMap<i64, T>,
22    default: T,
23    // `None` compares with `PartialEq`.
24    equality: Option<Equality<T>>,
25}
26
27impl<T> SparseVector<T> {
28    /// Creates a vector whose empty positions read back as `default`.
29    pub fn new(default: T) -> Self {
30        Self {
31            elements: BTreeMap::new(),
32            default,
33            equality: None,
34        }
35    }
36
37    /// The value reported for every position with no explicit element.
38    ///
39    /// There is deliberately no `&mut` counterpart; use
40    /// [`set_default_value`](Self::set_default_value), which prunes.
41    pub fn get_default_value(&self) -> &T {
42        &self.default
43    }
44
45    /// The predicate replacing `PartialEq`, or `None` when `PartialEq` decides.
46    pub fn get_equality(&self) -> Option<&Equality<T>> {
47        self.equality.as_ref()
48    }
49
50    /// The number of explicitly stored elements.
51    pub fn get_element_amount(&self) -> usize {
52        self.elements.len()
53    }
54
55    /// The distance between the leftmost and rightmost elements, both included; zero when empty.
56    ///
57    /// # Panics
58    ///
59    /// Panics when the span leaves the `i64` range.
60    pub fn get_significant_dimension(&self) -> i64 {
61        match (self.elements.first_key_value(), self.elements.last_key_value()) {
62            (Some((&smallest, _)), Some((&largest, _))) => largest
63                .checked_sub(smallest)
64                .and_then(|span| span.checked_add(1))
65                .unwrap_or_else(|| panic!("SparseVector span {smallest}..={largest} overflows i64")),
66            _ => 0,
67        }
68    }
69
70    /// How far the vector reaches above zero: the leftmost index itself, or zero.
71    pub fn get_plus_dimension(&self) -> i64 {
72        match self.elements.last_key_value() {
73            Some((&leftmost, _)) if leftmost > 0 => leftmost,
74            _ => 0,
75        }
76    }
77
78    /// How far the vector reaches below zero: the rightmost index negated, or zero.
79    ///
80    /// # Panics
81    ///
82    /// Panics when the negation leaves the `i64` range.
83    pub fn get_minus_dimension(&self) -> i64 {
84        match self.elements.first_key_value() {
85            Some((&rightmost, _)) if rightmost < 0 => rightmost
86                .checked_neg()
87                .unwrap_or_else(|| panic!("SparseVector index {rightmost} cannot be negated")),
88            _ => 0,
89        }
90    }
91
92    /// Resets every explicit element, keeping the default value, and returns whether there was any.
93    pub fn reset_vector(&mut self) -> bool {
94        if self.elements.is_empty() {
95            return false;
96        }
97        self.elements.clear();
98        true
99    }
100
101    /// The stored indices, descending.
102    pub fn indexes(&self) -> Vec<i64> {
103        self.elements.keys().rev().copied().collect()
104    }
105
106    /// The stored indices, ascending.
107    pub fn inverted_indexes(&self) -> Vec<i64> {
108        self.elements.keys().copied().collect()
109    }
110
111    /// The index of the (n+1)-th element from the left; the ordinal numbers the elements, not
112    /// the positions.
113    ///
114    /// # Panics
115    ///
116    /// Panics when fewer than n + 1 elements are stored.
117    pub fn element_index(&self, n: usize) -> i64 {
118        *self.at_ordinal(n, false).0
119    }
120
121    /// The index of the (n+1)-th element from the right.
122    ///
123    /// # Panics
124    ///
125    /// Panics when fewer than n + 1 elements are stored.
126    pub fn inverted_element_index(&self, n: usize) -> i64 {
127        *self.at_ordinal(n, true).0
128    }
129
130    /// Iterates the elements descending by index, borrowing them, without allocating.
131    pub fn iter(&self) -> Iter<'_, T> {
132        Iter {
133            inner: self.elements.iter(),
134        }
135    }
136
137    /// The element at 0-based ordinal `n` from whichever end.
138    fn at_ordinal(&self, n: usize, inverted: bool) -> (&i64, &T) {
139        let element = if inverted {
140            self.elements.iter().nth(n)
141        } else {
142            self.elements.iter().nth_back(n)
143        };
144        match element {
145            Some(element) => element,
146            None => {
147                let side = if inverted { "right" } else { "left" };
148                panic!(
149                    "SparseVector holds {} elements, so there is no element {} from the {}",
150                    self.elements.len(),
151                    n,
152                    side
153                )
154            }
155        }
156    }
157
158    fn anchor(&self, inverted: bool) -> i64 {
159        let index = if inverted {
160            self.elements.keys().next()
161        } else {
162            self.elements.keys().next_back()
163        };
164        match index {
165            Some(&index) => index,
166            None => panic!("SparseVector holds no elements, so there is nothing to measure from"),
167        }
168    }
169
170    /// The value at `index`, or the default when nothing is stored there, borrowing rather than
171    /// copying and panicking on nothing.
172    fn stored_or_default(&self, index: i64) -> &T {
173        self.elements.get(&index).unwrap_or(&self.default)
174    }
175}
176
177impl<T: Default> SparseVector<T> {
178    /// Creates a vector whose empty positions read back as `T::default()`, the default left
179    /// out. For `f64` that is `0.0`.
180    pub fn default_new() -> Self {
181        Self::new(T::default())
182    }
183}
184
185impl<T: Clone> SparseVector<T> {
186    /// The value at `index`, or the default value when nothing is stored there. Reading is
187    /// total, so it returns `T` and not `Option<T>`.
188    pub fn get(&self, index: i64) -> T {
189        match self.elements.get(&index) {
190            Some(value) => value.clone(),
191            None => self.default.clone(),
192        }
193    }
194
195    /// The explicit elements, descending by index: the serialization shape described on
196    /// [`Element`].
197    pub fn elements(&self) -> Vec<Element<T>> {
198        self.elements
199            .iter()
200            .rev()
201            .map(|(&index, value)| Element {
202                index,
203                value: value.clone(),
204            })
205            .collect()
206    }
207
208    /// The explicit elements, ascending by index.
209    pub fn inverted_elements(&self) -> Vec<Element<T>> {
210        self.elements
211            .iter()
212            .map(|(&index, value)| Element {
213                index,
214                value: value.clone(),
215            })
216            .collect()
217    }
218
219    /// The stored values, descending by index.
220    pub fn values(&self) -> Vec<T> {
221        self.elements.values().rev().cloned().collect()
222    }
223
224    /// The stored values, ascending by index.
225    pub fn inverted_values(&self) -> Vec<T> {
226        self.elements.values().cloned().collect()
227    }
228
229    /// The (n+1)-th element from the left; the ordinal numbers the elements, not the positions.
230    ///
231    /// # Panics
232    ///
233    /// Panics when fewer than n + 1 elements are stored.
234    pub fn element(&self, n: usize) -> Element<T> {
235        let (&index, value) = self.at_ordinal(n, false);
236        Element {
237            index,
238            value: value.clone(),
239        }
240    }
241
242    /// The value of the (n+1)-th element from the left.
243    ///
244    /// # Panics
245    ///
246    /// Panics when fewer than n + 1 elements are stored.
247    pub fn element_value(&self, n: usize) -> T {
248        self.at_ordinal(n, false).1.clone()
249    }
250
251    /// The (n+1)-th element from the right, `inverted_element(0)` being the rightmost.
252    ///
253    /// # Panics
254    ///
255    /// Panics when fewer than n + 1 elements are stored.
256    pub fn inverted_element(&self, n: usize) -> Element<T> {
257        let (&index, value) = self.at_ordinal(n, true);
258        Element {
259            index,
260            value: value.clone(),
261        }
262    }
263
264    /// The value of the (n+1)-th element from the right.
265    ///
266    /// # Panics
267    ///
268    /// Panics when fewer than n + 1 elements are stored.
269    pub fn inverted_element_value(&self, n: usize) -> T {
270        self.at_ordinal(n, true).1.clone()
271    }
272
273    /// The value `n` positions right of the leftmost element, empty positions counting; a
274    /// negative `n` walks left of it, into the default value.
275    ///
276    /// # Panics
277    ///
278    /// Panics when nothing is stored, or the position leaves the `i64` range.
279    pub fn left_significant_value(&self, n: i64) -> T {
280        let anchor = self.anchor(false);
281        let index = anchor
282            .checked_sub(n)
283            .unwrap_or_else(|| panic!("SparseVector position {anchor} - {n} overflows i64"));
284        self.get(index)
285    }
286
287    /// The value `n` positions left of the rightmost element; a negative `n` walks right of it.
288    ///
289    /// # Panics
290    ///
291    /// Panics when nothing is stored, or the position leaves the `i64` range.
292    pub fn right_significant_value(&self, n: i64) -> T {
293        let anchor = self.anchor(true);
294        let index = anchor
295            .checked_add(n)
296            .unwrap_or_else(|| panic!("SparseVector position {anchor} + {n} overflows i64"));
297        self.get(index)
298    }
299}
300
301impl<T: PartialEq> SparseVector<T> {
302    /// Inserts or updates the element at `index`, returning `&mut self` so calls chain;
303    /// writing the default removes instead.
304    pub fn set(&mut self, index: i64, value: T) -> &mut Self {
305        if self.equals(&value) {
306            self.elements.remove(&index);
307        } else {
308            self.elements.insert(index, value);
309        }
310        self
311    }
312
313    /// Replaces the default value, immediately dropping every element equal to it and returning
314    /// whether anything was dropped. Pruning is one-way: dropped positions never come back.
315    pub fn set_default_value(&mut self, next: T) -> bool {
316        self.default = next;
317        self.prune()
318    }
319
320    /// Replaces the predicate, immediately dropping every element it calls equal to the default
321    /// and returning whether anything was dropped. `None` restores `PartialEq`.
322    pub fn set_equality(&mut self, equality: Option<Equality<T>>) -> bool {
323        self.equality = equality;
324        self.prune()
325    }
326
327    /// Resets the element at `index`, returning whether there was one. It then reads as the
328    /// default.
329    pub fn reset_value(&mut self, index: i64) -> bool {
330        self.elements.remove(&index).is_some()
331    }
332
333    /// Whether `other` holds the same values as `self`, every comparison made by this vector's
334    /// predicate: the two default values first, then each index either vector stores an element
335    /// at, a position holding nothing contributing its own vector's default.
336    ///
337    /// Never panics. Two `NaN` defaults compare unequal, so a vector holding one is not equal to
338    /// itself. The three properties of equality hold only as far as the predicate does — an
339    /// asymmetric or non-reflexive predicate gives an asymmetric or non-reflexive answer, the
340    /// library never correcting it.
341    pub fn is_equal_to(&self, other: &Self) -> bool {
342        let equality = self.equality.as_ref();
343        if !equals_with(equality, other.get_default_value(), self.get_default_value()) {
344            return false;
345        }
346        let mut mine = self.elements.iter().rev().peekable();
347        let mut theirs = other.elements.iter().rev().peekable();
348        loop {
349            let mine_index = mine.peek().map(|element| *element.0);
350            let their_index = theirs.peek().map(|element| *element.0);
351            let take_mine = match (mine_index, their_index) {
352                (None, None) => return true,
353                (Some(mine_index), Some(their_index)) => mine_index >= their_index,
354                (Some(_), None) => true,
355                (None, Some(_)) => false,
356            };
357            if take_mine {
358                let (index, value) = mine.next().expect("peeked above");
359                let other_value = if Some(*index) == their_index {
360                    theirs.next().expect("peeked above").1
361                } else {
362                    other.get_default_value()
363                };
364                if !equals_with(equality, other_value, value) {
365                    return false;
366                }
367            } else {
368                let (_, value) = theirs.next().expect("peeked above");
369                if !equals_with(equality, value, self.get_default_value()) {
370                    return false;
371                }
372            }
373        }
374    }
375
376    /// Builds from any iterator of elements, dropping those equal to the default and keeping
377    /// the last of a repeated index.
378    pub fn from_elements<I>(elements: I, default: T) -> Self
379    where
380        I: IntoIterator<Item = Element<T>>,
381    {
382        let mut vector = Self::new(default);
383        for element in elements {
384            vector.set(element.index, element.value);
385        }
386        vector
387    }
388
389    /// Whether `value` equals the default, by `self.equality` when set and `PartialEq` otherwise.
390    fn equals(&self, value: &T) -> bool {
391        equals_with(self.equality.as_ref(), value, &self.default)
392    }
393
394    /// Drops every element equal to the default, returning whether anything was dropped.
395    fn prune(&mut self) -> bool {
396        let default = &self.default;
397        let equality = self.equality.as_ref();
398        let mut pruned = false;
399        self.elements.retain(|_, value| {
400            let equal = equals_with(equality, value, default);
401            pruned |= equal;
402            !equal
403        });
404        pruned
405    }
406}
407
408// Whole-vector comparison: the one method that reads another vector's elements as well.
409impl<T: Clone + PartialEq> SparseVector<T> {
410    /// The elements of `self` that differ from `other`, descending by index, each carrying this
411    /// vector's value at that index — the default value itself wherever nothing is stored there.
412    ///
413    /// Not a symmetric difference, and not guaranteed to be empty for `a.differences(a)`: a stored
414    /// `NaN` differs from itself, since `NaN != NaN`.
415    ///
416    /// # Panics
417    ///
418    /// Panics when the two default values do not compare equal under this vector's predicate, so
419    /// there is no sense in which the vectors can be compared.
420    pub fn differences(&self, other: &Self) -> Vec<Element<T>> {
421        let equality = self.equality.as_ref();
422        assert!(
423            equals_with(equality, other.get_default_value(), self.get_default_value()),
424            "SparseVector default values are not equal, so the two vectors cannot be compared"
425        );
426        let mut differing = Vec::new();
427        let mut mine = self.elements.iter().rev().peekable();
428        let mut theirs = other.elements.iter().rev().peekable();
429        loop {
430            let mine_index = mine.peek().map(|element| *element.0);
431            let their_index = theirs.peek().map(|element| *element.0);
432            let take_mine = match (mine_index, their_index) {
433                (None, None) => break,
434                (Some(mine_index), Some(their_index)) => mine_index >= their_index,
435                (Some(_), None) => true,
436                (None, Some(_)) => false,
437            };
438            if take_mine {
439                let index = *mine.next().expect("peeked above").0;
440                let other_value = if Some(index) == their_index {
441                    theirs.next().expect("peeked above").1
442                } else {
443                    other.get_default_value()
444                };
445                let value = self.stored_or_default(index);
446                if !equals_with(equality, other_value, value) {
447                    differing.push(Element {
448                        index,
449                        value: value.clone(),
450                    });
451                }
452            } else {
453                let (index, other_value) = theirs.next().expect("peeked above");
454                let value = self.stored_or_default(*index);
455                if !equals_with(equality, other_value, value) {
456                    differing.push(Element {
457                        index: *index,
458                        value: value.clone(),
459                    });
460                }
461            }
462        }
463        differing
464    }
465}
466
467/// Whether `left` equals `right`, by `equality` when set and `PartialEq` otherwise.
468///
469/// The predicate decides every comparison in this module. Which value goes in the first slot is
470/// the caller's choice, and a comparison against another vector always puts its value first.
471fn equals_with<T: PartialEq>(equality: Option<&Equality<T>>, left: &T, right: &T) -> bool {
472    match equality {
473        Some(equality) => equality(left, right),
474        None => left == right,
475    }
476}
477
478impl<T: Clone> Clone for SparseVector<T> {
479    /// An independent copy, default value and equality predicate included.
480    fn clone(&self) -> Self {
481        Self {
482            elements: self.elements.clone(),
483            default: self.default.clone(),
484            equality: self.equality.clone(),
485        }
486    }
487}
488
489// The storage as it is, ascending, not one of the ordered views.
490impl<T: fmt::Debug> fmt::Debug for SparseVector<T> {
491    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
492        f.debug_struct("SparseVector")
493            .field("default", &self.default)
494            .field("elements", &self.elements)
495            .finish()
496    }
497}
498
499impl<'a, T> IntoIterator for &'a SparseVector<T> {
500    type Item = Element<&'a T>;
501    type IntoIter = Iter<'a, T>;
502
503    fn into_iter(self) -> Self::IntoIter {
504        self.iter()
505    }
506}
507
508/// An iterator over the elements of a [`SparseVector`], descending by index and borrowing the
509/// stored values as [`Element<&T>`](Element).
510pub struct Iter<'a, T> {
511    inner: btree_map::Iter<'a, i64, T>,
512}
513
514impl<'a, T> Iterator for Iter<'a, T> {
515    type Item = Element<&'a T>;
516
517    /// The inner map is ascending while this iterator is descending, so the ends swap here.
518    fn next(&mut self) -> Option<Self::Item> {
519        self.inner
520            .next_back()
521            .map(|(&index, value)| Element { index, value })
522    }
523
524    fn size_hint(&self) -> (usize, Option<usize>) {
525        self.inner.size_hint()
526    }
527}
528
529impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
530    fn next_back(&mut self) -> Option<Self::Item> {
531        self.inner
532            .next()
533            .map(|(&index, value)| Element { index, value })
534    }
535}
536
537impl<T> ExactSizeIterator for Iter<'_, T> {
538    fn len(&self) -> usize {
539        self.inner.len()
540    }
541}
542
543impl<T> FusedIterator for Iter<'_, T> {}