use std::collections::btree_map;
use std::collections::BTreeMap;
use std::fmt;
use std::iter::FusedIterator;
use std::panic::RefUnwindSafe;
use std::sync::Arc;
use crate::Element;
pub type Equality<T> = Arc<dyn Fn(&T, &T) -> bool + Send + Sync + RefUnwindSafe>;
pub struct SparseVector<T = f64> {
elements: BTreeMap<i64, T>,
default: T,
equality: Option<Equality<T>>,
}
impl<T> SparseVector<T> {
pub fn new(default: T) -> Self {
Self {
elements: BTreeMap::new(),
default,
equality: None,
}
}
pub fn get_default_value(&self) -> &T {
&self.default
}
pub fn get_equality(&self) -> Option<&Equality<T>> {
self.equality.as_ref()
}
pub fn get_element_amount(&self) -> usize {
self.elements.len()
}
pub fn get_significant_dimension(&self) -> i64 {
match (self.elements.first_key_value(), self.elements.last_key_value()) {
(Some((&smallest, _)), Some((&largest, _))) => largest
.checked_sub(smallest)
.and_then(|span| span.checked_add(1))
.unwrap_or_else(|| panic!("SparseVector span {smallest}..={largest} overflows i64")),
_ => 0,
}
}
pub fn get_plus_dimension(&self) -> i64 {
match self.elements.last_key_value() {
Some((&leftmost, _)) if leftmost > 0 => leftmost,
_ => 0,
}
}
pub fn get_minus_dimension(&self) -> i64 {
match self.elements.first_key_value() {
Some((&rightmost, _)) if rightmost < 0 => rightmost
.checked_neg()
.unwrap_or_else(|| panic!("SparseVector index {rightmost} cannot be negated")),
_ => 0,
}
}
pub fn reset_vector(&mut self) -> bool {
if self.elements.is_empty() {
return false;
}
self.elements.clear();
true
}
pub fn indexes(&self) -> Vec<i64> {
self.elements.keys().rev().copied().collect()
}
pub fn inverted_indexes(&self) -> Vec<i64> {
self.elements.keys().copied().collect()
}
pub fn element_index(&self, n: usize) -> i64 {
*self.at_ordinal(n, false).0
}
pub fn inverted_element_index(&self, n: usize) -> i64 {
*self.at_ordinal(n, true).0
}
pub fn iter(&self) -> Iter<'_, T> {
Iter {
inner: self.elements.iter(),
}
}
fn at_ordinal(&self, n: usize, inverted: bool) -> (&i64, &T) {
let element = if inverted {
self.elements.iter().nth(n)
} else {
self.elements.iter().nth_back(n)
};
match element {
Some(element) => element,
None => {
let side = if inverted { "right" } else { "left" };
panic!(
"SparseVector holds {} elements, so there is no element {} from the {}",
self.elements.len(),
n,
side
)
}
}
}
fn anchor(&self, inverted: bool) -> i64 {
let index = if inverted {
self.elements.keys().next()
} else {
self.elements.keys().next_back()
};
match index {
Some(&index) => index,
None => panic!("SparseVector holds no elements, so there is nothing to measure from"),
}
}
fn stored_or_default(&self, index: i64) -> &T {
self.elements.get(&index).unwrap_or(&self.default)
}
}
impl<T: Default> SparseVector<T> {
pub fn default_new() -> Self {
Self::new(T::default())
}
}
impl<T: Clone> SparseVector<T> {
pub fn get(&self, index: i64) -> T {
match self.elements.get(&index) {
Some(value) => value.clone(),
None => self.default.clone(),
}
}
pub fn elements(&self) -> Vec<Element<T>> {
self.elements
.iter()
.rev()
.map(|(&index, value)| Element {
index,
value: value.clone(),
})
.collect()
}
pub fn inverted_elements(&self) -> Vec<Element<T>> {
self.elements
.iter()
.map(|(&index, value)| Element {
index,
value: value.clone(),
})
.collect()
}
pub fn values(&self) -> Vec<T> {
self.elements.values().rev().cloned().collect()
}
pub fn inverted_values(&self) -> Vec<T> {
self.elements.values().cloned().collect()
}
pub fn element(&self, n: usize) -> Element<T> {
let (&index, value) = self.at_ordinal(n, false);
Element {
index,
value: value.clone(),
}
}
pub fn element_value(&self, n: usize) -> T {
self.at_ordinal(n, false).1.clone()
}
pub fn inverted_element(&self, n: usize) -> Element<T> {
let (&index, value) = self.at_ordinal(n, true);
Element {
index,
value: value.clone(),
}
}
pub fn inverted_element_value(&self, n: usize) -> T {
self.at_ordinal(n, true).1.clone()
}
pub fn left_significant_value(&self, n: i64) -> T {
let anchor = self.anchor(false);
let index = anchor
.checked_sub(n)
.unwrap_or_else(|| panic!("SparseVector position {anchor} - {n} overflows i64"));
self.get(index)
}
pub fn right_significant_value(&self, n: i64) -> T {
let anchor = self.anchor(true);
let index = anchor
.checked_add(n)
.unwrap_or_else(|| panic!("SparseVector position {anchor} + {n} overflows i64"));
self.get(index)
}
}
impl<T: PartialEq> SparseVector<T> {
pub fn set(&mut self, index: i64, value: T) -> &mut Self {
if self.equals(&value) {
self.elements.remove(&index);
} else {
self.elements.insert(index, value);
}
self
}
pub fn set_default_value(&mut self, next: T) -> bool {
self.default = next;
self.prune()
}
pub fn set_equality(&mut self, equality: Option<Equality<T>>) -> bool {
self.equality = equality;
self.prune()
}
pub fn reset_value(&mut self, index: i64) -> bool {
self.elements.remove(&index).is_some()
}
pub fn is_equal_to(&self, other: &Self) -> bool {
let equality = self.equality.as_ref();
if !equals_with(equality, other.get_default_value(), self.get_default_value()) {
return false;
}
let mut mine = self.elements.iter().rev().peekable();
let mut theirs = other.elements.iter().rev().peekable();
loop {
let mine_index = mine.peek().map(|element| *element.0);
let their_index = theirs.peek().map(|element| *element.0);
let take_mine = match (mine_index, their_index) {
(None, None) => return true,
(Some(mine_index), Some(their_index)) => mine_index >= their_index,
(Some(_), None) => true,
(None, Some(_)) => false,
};
if take_mine {
let (index, value) = mine.next().expect("peeked above");
let other_value = if Some(*index) == their_index {
theirs.next().expect("peeked above").1
} else {
other.get_default_value()
};
if !equals_with(equality, other_value, value) {
return false;
}
} else {
let (_, value) = theirs.next().expect("peeked above");
if !equals_with(equality, value, self.get_default_value()) {
return false;
}
}
}
}
pub fn from_elements<I>(elements: I, default: T) -> Self
where
I: IntoIterator<Item = Element<T>>,
{
let mut vector = Self::new(default);
for element in elements {
vector.set(element.index, element.value);
}
vector
}
fn equals(&self, value: &T) -> bool {
equals_with(self.equality.as_ref(), value, &self.default)
}
fn prune(&mut self) -> bool {
let default = &self.default;
let equality = self.equality.as_ref();
let mut pruned = false;
self.elements.retain(|_, value| {
let equal = equals_with(equality, value, default);
pruned |= equal;
!equal
});
pruned
}
}
impl<T: Clone + PartialEq> SparseVector<T> {
pub fn differences(&self, other: &Self) -> Vec<Element<T>> {
let equality = self.equality.as_ref();
assert!(
equals_with(equality, other.get_default_value(), self.get_default_value()),
"SparseVector default values are not equal, so the two vectors cannot be compared"
);
let mut differing = Vec::new();
let mut mine = self.elements.iter().rev().peekable();
let mut theirs = other.elements.iter().rev().peekable();
loop {
let mine_index = mine.peek().map(|element| *element.0);
let their_index = theirs.peek().map(|element| *element.0);
let take_mine = match (mine_index, their_index) {
(None, None) => break,
(Some(mine_index), Some(their_index)) => mine_index >= their_index,
(Some(_), None) => true,
(None, Some(_)) => false,
};
if take_mine {
let index = *mine.next().expect("peeked above").0;
let other_value = if Some(index) == their_index {
theirs.next().expect("peeked above").1
} else {
other.get_default_value()
};
let value = self.stored_or_default(index);
if !equals_with(equality, other_value, value) {
differing.push(Element {
index,
value: value.clone(),
});
}
} else {
let (index, other_value) = theirs.next().expect("peeked above");
let value = self.stored_or_default(*index);
if !equals_with(equality, other_value, value) {
differing.push(Element {
index: *index,
value: value.clone(),
});
}
}
}
differing
}
}
fn equals_with<T: PartialEq>(equality: Option<&Equality<T>>, left: &T, right: &T) -> bool {
match equality {
Some(equality) => equality(left, right),
None => left == right,
}
}
impl<T: Clone> Clone for SparseVector<T> {
fn clone(&self) -> Self {
Self {
elements: self.elements.clone(),
default: self.default.clone(),
equality: self.equality.clone(),
}
}
}
impl<T: fmt::Debug> fmt::Debug for SparseVector<T> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("SparseVector")
.field("default", &self.default)
.field("elements", &self.elements)
.finish()
}
}
impl<'a, T> IntoIterator for &'a SparseVector<T> {
type Item = Element<&'a T>;
type IntoIter = Iter<'a, T>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
pub struct Iter<'a, T> {
inner: btree_map::Iter<'a, i64, T>,
}
impl<'a, T> Iterator for Iter<'a, T> {
type Item = Element<&'a T>;
fn next(&mut self) -> Option<Self::Item> {
self.inner
.next_back()
.map(|(&index, value)| Element { index, value })
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
}
impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
fn next_back(&mut self) -> Option<Self::Item> {
self.inner
.next()
.map(|(&index, value)| Element { index, value })
}
}
impl<T> ExactSizeIterator for Iter<'_, T> {
fn len(&self) -> usize {
self.inner.len()
}
}
impl<T> FusedIterator for Iter<'_, T> {}