sparse_rs/
sparse_vector.rs

1use std::collections::BTreeMap;
2use std::ops::{Index, Mul};
3use num::Zero;
4
5pub struct SparseVector<T> {
6    len: usize,
7    data: BTreeMap<usize, T>,
8    zero: T,
9}
10
11impl<T: Zero> SparseVector<T> {
12    pub fn insert(&mut self, index: usize, value: T) {
13        self.data.insert(index, value);
14    }
15}
16
17impl<T: Zero> SparseVector<T> {
18    pub fn zero(len: usize) -> SparseVector<T> {
19        SparseVector {
20            len: len,
21            data: BTreeMap::new(),
22            zero: T::zero(),
23        }
24    }
25}
26
27impl<T: Zero> Index<usize> for SparseVector<T> {
28    type Output = T;
29
30    fn index(&self, idx: usize) -> &T {
31        match self.data.get(&idx) {
32            Some(x) => x,
33            None => &self.zero,
34        }
35    }
36}
37
38impl<T: Mul<Output=T> + Clone + Zero> Mul<SparseVector<T>> for SparseVector<T> {
39    type Output = SparseVector<T>;
40
41    fn mul(self, rhs: SparseVector<T>) -> SparseVector<T> {
42        let data = self.data.into_iter().filter_map(|(key, value)| {
43            match rhs.data.get(&key) {
44                Some(r) => Some((key, r.clone() * value)),
45                None => None,
46            }
47        }).collect();
48        SparseVector {
49            len: self.len,
50            data: data,
51            zero: self.zero,
52        }
53    }
54}
55
56    #[test]
57    fn mul_test() {
58        let mut lhs = SparseVector::zero(3);
59        lhs.insert(1, 3);
60        lhs.insert(2, 3);
61
62        let mut rhs = SparseVector::zero(3);
63        rhs.insert(1,2);
64        rhs.insert(0,1);
65
66        let product = lhs * rhs;
67        assert_eq!(product[0], 0);
68        assert_eq!(product[1], 6);
69        assert_eq!(product[2], 0);
70    }
sparse_rs/sparse_vector.rs

sparse_rs/
sparse_vector.rs
