1use std::collections::btree_map;
2use std::collections::BTreeMap;
3use std::fmt;
4use std::iter::FusedIterator;
5
6use crate::Element;
7
8pub struct SparseVector<T = f64> {
11 entries: BTreeMap<i64, T>,
13 default: T,
14}
15
16impl<T> SparseVector<T> {
17 pub fn with_default(default: T) -> Self {
19 Self {
20 entries: BTreeMap::new(),
21 default,
22 }
23 }
24
25 pub fn get_default_value(&self) -> &T {
30 &self.default
31 }
32
33 pub fn get_element_amount(&self) -> usize {
35 self.entries.len()
36 }
37
38 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 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 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 pub fn reset_vector(&mut self) {
77 self.entries.clear();
78 }
79
80 pub fn indexes(&self) -> Vec<i64> {
82 self.entries.keys().rev().copied().collect()
83 }
84
85 pub fn inverted_indexes(&self) -> Vec<i64> {
87 self.entries.keys().copied().collect()
88 }
89
90 pub fn element_index(&self, n: usize) -> i64 {
97 *self.at_ordinal(n, false).0
98 }
99
100 pub fn inverted_element_index(&self, n: usize) -> i64 {
106 *self.at_ordinal(n, true).0
107 }
108
109 pub fn iter(&self) -> Iter<'_, T> {
111 Iter {
112 inner: self.entries.iter(),
113 }
114 }
115
116 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 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 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 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 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 pub fn values(&self) -> Vec<T> {
200 self.entries.values().rev().cloned().collect()
201 }
202
203 pub fn inverted_values(&self) -> Vec<T> {
205 self.entries.values().cloned().collect()
206 }
207
208 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 pub fn element_value(&self, n: usize) -> T {
227 self.at_ordinal(n, false).1.clone()
228 }
229
230 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 pub fn inverted_element_value(&self, n: usize) -> T {
249 self.at_ordinal(n, true).1.clone()
250 }
251
252 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 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 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 pub fn set_default_value(&mut self, next: T) {
295 self.default = next;
296 self.prune();
297 }
298
299 pub fn reset_value(&mut self, index: i64) -> Option<T> {
302 self.entries.remove(&index)
303 }
304
305 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 fn clone(&self) -> Self {
327 Self {
328 entries: self.entries.clone(),
329 default: self.default.clone(),
330 }
331 }
332}
333
334impl<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
353pub 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 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> {}