use std::collections::btree_map;
use std::collections::BTreeMap;
use std::fmt;
use std::iter::FusedIterator;
use crate::Element;
pub struct SparseVector<T = f64> {
entries: BTreeMap<i64, T>,
default: T,
}
impl<T> SparseVector<T> {
pub fn with_default(default: T) -> Self {
Self {
entries: BTreeMap::new(),
default,
}
}
pub fn get_default_value(&self) -> &T {
&self.default
}
pub fn get_element_amount(&self) -> usize {
self.entries.len()
}
pub fn get_significant_dimension(&self) -> i64 {
match (self.entries.first_key_value(), self.entries.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.entries.last_key_value() {
Some((&leftmost, _)) if leftmost > 0 => leftmost,
_ => 0,
}
}
pub fn get_minus_dimension(&self) -> i64 {
match self.entries.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) {
self.entries.clear();
}
pub fn indexes(&self) -> Vec<i64> {
self.entries.keys().rev().copied().collect()
}
pub fn inverted_indexes(&self) -> Vec<i64> {
self.entries.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.entries.iter(),
}
}
fn at_ordinal(&self, n: usize, inverted: bool) -> (&i64, &T) {
let entry = if inverted {
self.entries.iter().nth(n)
} else {
self.entries.iter().nth_back(n)
};
match entry {
Some(entry) => entry,
None => {
let side = if inverted { "right" } else { "left" };
panic!(
"SparseVector holds {} entries, so there is no entry {} from the {}",
self.entries.len(),
n,
side
)
}
}
}
fn anchor(&self, inverted: bool) -> i64 {
let index = if inverted {
self.entries.keys().next()
} else {
self.entries.keys().next_back()
};
match index {
Some(&index) => index,
None => panic!("SparseVector holds no entries, so there is nothing to measure from"),
}
}
}
impl SparseVector<f64> {
pub fn new() -> Self {
Self::with_default(0.0)
}
}
impl<T: Default> Default for SparseVector<T> {
fn default() -> Self {
Self::with_default(T::default())
}
}
impl<T: Clone> SparseVector<T> {
pub fn get(&self, index: i64) -> T {
match self.entries.get(&index) {
Some(value) => value.clone(),
None => self.default.clone(),
}
}
pub fn elements(&self) -> Vec<Element<T>> {
self.entries
.iter()
.rev()
.map(|(&index, value)| Element {
index,
value: value.clone(),
})
.collect()
}
pub fn inverted_elements(&self) -> Vec<Element<T>> {
self.entries
.iter()
.map(|(&index, value)| Element {
index,
value: value.clone(),
})
.collect()
}
pub fn values(&self) -> Vec<T> {
self.entries.values().rev().cloned().collect()
}
pub fn inverted_values(&self) -> Vec<T> {
self.entries.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 value == self.default {
self.entries.remove(&index);
} else {
self.entries.insert(index, value);
}
self
}
pub fn set_default_value(&mut self, next: T) {
self.default = next;
self.prune();
}
pub fn reset_value(&mut self, index: i64) -> Option<T> {
self.entries.remove(&index)
}
pub fn from_elements<I>(elements: I, default: T) -> Self
where
I: IntoIterator<Item = Element<T>>,
{
let mut vector = Self::with_default(default);
for element in elements {
vector.set(element.index, element.value);
}
vector
}
fn prune(&mut self) {
let default = &self.default;
self.entries.retain(|_, value| value != default);
}
}
impl<T: Clone> Clone for SparseVector<T> {
fn clone(&self) -> Self {
Self {
entries: self.entries.clone(),
default: self.default.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("entries", &self.entries)
.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> {}