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
10pub type Equality<T> = Arc<dyn Fn(&T, &T) -> bool + Send + Sync + RefUnwindSafe>;
16
17pub struct SparseVector<T = f64> {
20 elements: BTreeMap<i64, T>,
22 default: T,
23 equality: Option<Equality<T>>,
25}
26
27impl<T> SparseVector<T> {
28 pub fn new(default: T) -> Self {
30 Self {
31 elements: BTreeMap::new(),
32 default,
33 equality: None,
34 }
35 }
36
37 pub fn get_default_value(&self) -> &T {
42 &self.default
43 }
44
45 pub fn get_equality(&self) -> Option<&Equality<T>> {
47 self.equality.as_ref()
48 }
49
50 pub fn get_element_amount(&self) -> usize {
52 self.elements.len()
53 }
54
55 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 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 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 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 pub fn indexes(&self) -> Vec<i64> {
103 self.elements.keys().rev().copied().collect()
104 }
105
106 pub fn inverted_indexes(&self) -> Vec<i64> {
108 self.elements.keys().copied().collect()
109 }
110
111 pub fn element_index(&self, n: usize) -> i64 {
118 *self.at_ordinal(n, false).0
119 }
120
121 pub fn inverted_element_index(&self, n: usize) -> i64 {
127 *self.at_ordinal(n, true).0
128 }
129
130 pub fn iter(&self) -> Iter<'_, T> {
132 Iter {
133 inner: self.elements.iter(),
134 }
135 }
136
137 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 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 pub fn default_new() -> Self {
181 Self::new(T::default())
182 }
183}
184
185impl<T: Clone> SparseVector<T> {
186 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 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 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 pub fn values(&self) -> Vec<T> {
221 self.elements.values().rev().cloned().collect()
222 }
223
224 pub fn inverted_values(&self) -> Vec<T> {
226 self.elements.values().cloned().collect()
227 }
228
229 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 pub fn element_value(&self, n: usize) -> T {
248 self.at_ordinal(n, false).1.clone()
249 }
250
251 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 pub fn inverted_element_value(&self, n: usize) -> T {
270 self.at_ordinal(n, true).1.clone()
271 }
272
273 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 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 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 pub fn set_default_value(&mut self, next: T) -> bool {
316 self.default = next;
317 self.prune()
318 }
319
320 pub fn set_equality(&mut self, equality: Option<Equality<T>>) -> bool {
323 self.equality = equality;
324 self.prune()
325 }
326
327 pub fn reset_value(&mut self, index: i64) -> bool {
330 self.elements.remove(&index).is_some()
331 }
332
333 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 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 fn equals(&self, value: &T) -> bool {
391 equals_with(self.equality.as_ref(), value, &self.default)
392 }
393
394 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
408impl<T: Clone + PartialEq> SparseVector<T> {
410 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
467fn 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 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
489impl<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
508pub 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 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> {}