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 /// Iterates the explicit entries in ascending index order, borrowing them.
65 ///
66 /// Reach for this instead of [`elements`](Self::elements) when you do not
67 /// want to allocate.
68 pub fn iter(&self) -> Iter<'_, T> {
69 Iter {
70 inner: self.entries.iter(),
71 }
72 }
73}
74
75impl SparseVector<f64> {
76 /// Creates a vector whose empty positions read back as `0.0`.
77 ///
78 /// This exists only for `f64`, where the `0` the shared semantics name is a
79 /// value of the right type; for any other `T` use
80 /// [`with_default`](Self::with_default).
81 pub fn new() -> Self {
82 Self::with_default(0.0)
83 }
84}
85
86impl<T: Default> Default for SparseVector<T> {
87 fn default() -> Self {
88 Self::with_default(T::default())
89 }
90}
91
92impl<T: Clone> SparseVector<T> {
93 /// The value at `index`, or the default value when nothing is stored there.
94 ///
95 /// Reading is total: every `i64`, negative, huge or far outside anything ever
96 /// written, returns a value rather than failing, so this returns `T` and not
97 /// `Option<T>`.
98 pub fn get(&self, index: i64) -> T {
99 match self.entries.get(&index) {
100 Some(value) => value.clone(),
101 None => self.default.clone(),
102 }
103 }
104
105 /// The explicit entries, in ascending index order.
106 ///
107 /// This is the serialization shape described on [`Element`].
108 pub fn elements(&self) -> Vec<Element<T>> {
109 self.entries
110 .iter()
111 .map(|(&index, value)| Element {
112 index,
113 value: value.clone(),
114 })
115 .collect()
116 }
117
118 /// The stored values, in ascending index order.
119 pub fn values(&self) -> Vec<T> {
120 self.entries.values().cloned().collect()
121 }
122}
123
124impl<T: PartialEq> SparseVector<T> {
125 /// Inserts or updates `value` at `index`, returning `&mut self` so calls chain.
126 ///
127 /// Writing a value equal to the default removes whatever was there instead of
128 /// storing it: that is what keeps the structure sparse.
129 pub fn set(&mut self, index: i64, value: T) -> &mut Self {
130 if value == self.default {
131 self.entries.remove(&index);
132 } else {
133 self.entries.insert(index, value);
134 }
135 self
136 }
137
138 /// Replaces the default value, immediately dropping every entry equal to it.
139 ///
140 /// Pruning is one-way: the previous default is not remembered, so positions
141 /// dropped here never come back.
142 pub fn set_default_value(&mut self, next: T) {
143 self.default = next;
144 self.prune();
145 }
146
147 /// Removes the explicit entry at `index` and returns it, if there was one.
148 ///
149 /// The position subsequently reads back as the default value. Returned as an
150 /// `Option` rather than a `bool` so the removed value is available;
151 /// `.is_some()` recovers the boolean.
152 pub fn remove(&mut self, index: i64) -> Option<T> {
153 self.entries.remove(&index)
154 }
155
156 /// Builds a vector from a sequence of elements.
157 ///
158 /// Entries equal to the default are dropped, and for a repeated index the
159 /// last element wins, both because this goes through [`set`](Self::set).
160 pub fn from_elements<I>(elements: I, default: T) -> Self
161 where
162 I: IntoIterator<Item = Element<T>>,
163 {
164 let mut vector = Self::with_default(default);
165 for element in elements {
166 vector.set(element.index, element.value);
167 }
168 vector
169 }
170
171 /// Drops every entry equal to the current default.
172 fn prune(&mut self) {
173 let default = &self.default;
174 self.entries.retain(|_, value| value != default);
175 }
176}
177
178impl<T: Clone> Clone for SparseVector<T> {
179 /// An independent copy, default value included.
180 fn clone(&self) -> Self {
181 Self {
182 entries: self.entries.clone(),
183 default: self.default.clone(),
184 }
185 }
186}
187
188impl<T: fmt::Debug> fmt::Debug for SparseVector<T> {
189 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
190 f.debug_struct("SparseVector")
191 .field("default", &self.default)
192 .field("entries", &self.entries)
193 .finish()
194 }
195}
196
197impl<'a, T> IntoIterator for &'a SparseVector<T> {
198 type Item = Element<&'a T>;
199 type IntoIter = Iter<'a, T>;
200
201 fn into_iter(self) -> Self::IntoIter {
202 self.iter()
203 }
204}
205
206/// An iterator over the entries of a [`SparseVector`], in ascending index order.
207///
208/// Yields [`Element<&T>`](Element), borrowing the stored values.
209pub struct Iter<'a, T> {
210 inner: btree_map::Iter<'a, i64, T>,
211}
212
213impl<'a, T> Iterator for Iter<'a, T> {
214 type Item = Element<&'a T>;
215
216 fn next(&mut self) -> Option<Self::Item> {
217 self.inner
218 .next()
219 .map(|(&index, value)| Element { index, value })
220 }
221
222 fn size_hint(&self) -> (usize, Option<usize>) {
223 self.inner.size_hint()
224 }
225}
226
227impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
228 fn next_back(&mut self) -> Option<Self::Item> {
229 self.inner
230 .next_back()
231 .map(|(&index, value)| Element { index, value })
232 }
233}
234
235impl<T> ExactSizeIterator for Iter<'_, T> {
236 fn len(&self) -> usize {
237 self.inner.len()
238 }
239}
240
241impl<T> FusedIterator for Iter<'_, T> {}