English · 简体中文 · 繁體中文 · 日本語 · Español · Français · Русский
sparse-vector-rs
Rust implementation of sparse-vector: a mapping from integer index to arbitrary value that stores only the positions differing from a default value
Installation and the shared semantics live in the project README; this page covers the Rust API
Usage
use SparseVector;
let mut vector = with_default; // empty positions read back as ""
vector.set;
vector.set;
assert_eq!;
assert_eq!;
assert_eq!; // no entry there, so the default value
assert_eq!;
SparseVector::new() is the same thing for the default f64, starting from 0.0:
use SparseVector;
let vector = new;
assert_eq!;
assert_eq!;
The default value is replaceable, and replacing it prunes immediately:
use SparseVector;
let mut vector = with_default;
vector.set;
vector.set;
vector.set_default_value;
// Position 1 held 7, so it is dropped; position 2 keeps its value.
assert_eq!;
The type of the values is not restricted — anything with Clone can be read back, anything with PartialEq can be stored:
use ;
let mut vector: = with_default;
vector.set;
assert_eq!;
assert_eq!; // empty positions are None
API
SparseVector<T = f64>
| Member | Description |
|---|---|
new() -> SparseVector<f64> |
A vector whose default is 0.0. Defined on SparseVector<f64> only — for another T, use with_default |
with_default(default: T) -> SparseVector<T> |
A vector whose empty positions read back as default |
default_value(&self) -> &T |
The value reported for positions with no explicit entry |
set_default_value(&mut self, next: T) |
Replaces the default, immediately pruning every entry equal to it. Requires T: PartialEq |
len(&self) -> usize |
Number of explicitly stored entries |
is_empty(&self) -> bool |
Whether nothing is stored |
contains_key(&self, index: i64) -> bool |
Whether index holds an explicit entry |
get(&self, index: i64) -> T |
The value at index, or the default. Requires T: Clone |
set(&mut self, index: i64, value: T) -> &mut Self |
Inserts or updates; chainable. Requires T: PartialEq |
remove(&mut self, index: i64) -> Option<T> |
Removes the entry and returns it, if there was one. Requires T: PartialEq |
clear(&mut self) |
Removes every entry, keeping the default |
elements(&self) -> Vec<Element<T>> |
The stored entries, in ascending index order. Requires T: Clone |
keys(&self) -> Vec<i64> |
The stored indices, in ascending order |
values(&self) -> Vec<T> |
The stored values, in ascending index order. Requires T: Clone |
iter(&self) -> Iter<'_, T> |
Borrows the stored entries in ascending index order |
from_elements(elements, default) -> SparseVector<T> |
Builds from an IntoIterator<Item = Element<T>>. Requires T: PartialEq |
&SparseVector<T> is also IntoIterator, so for element in &vector works and yields Element<&T>. SparseVector<T> implements Default whenever T does, which is the T-generic spelling of with_default(T::default()).
SparseVector<T> implements Clone (an independent copy, default included) and Debug when T does. It deliberately has no PartialEq: this project has no equality semantics, and inventing some would be a decision the other implementations never made.
Element<T>
use Element;
let element = Element ;
assert_eq!;
assert_eq!;
The serialization shape described in the project README. A round trip carries the default alongside, since it is not part of the shape:
use SparseVector;
let mut original = with_default;
original.set;
original.set;
let restored = from_elements;
assert_eq!;
assert_eq!;
Differences from the TypeScript implementation
The semantics are shared, but not everything carries over. Stated here rather than papered over.
Indices are i64, so a non-integer index does not typecheck. The TypeScript version takes a number and throws a TypeError for 1.5, NaN or Infinity. Here those are compile errors, which is the better failure. The index domain is also strictly larger: TypeScript stops at Number.MAX_SAFE_INTEGER (2^53−1), this goes to the full i64 range.
Pruning compares with PartialEq. For f64 that is identical to the TypeScript behaviour, NaN caveat included: NaN != NaN, so a stored NaN survives even when the default is also NaN.
For your own types it can differ. TypeScript's === compares objects by reference; Rust's PartialEq is almost always structural. Two distinct objects with equal contents are one value there and two values here, so a position holding an equal-but-distinct object is pruned here and kept there. If you need reference identity, make it part of the type's equality — a newtype is the whole recipe:
use Rc;
;
Nothing is omitted by accident. SparseVector::new() uses T::default(), not a literal 0. For f64 that is 0.0, exactly the documented rule; for String it is "", which is the same rule generalised rather than a lie about the type.
There is no JSON encoder here, for the same reason there is none in the C++ implementation: elements() is the contract, and serialization is left to whatever crate you already use rather than taken on as a dependency.
Development
The library itself has no dependencies — not even for the tests
License
MIT