/*
* Copyright (c) 2016 Frank Fischer <frank-fischer@shadow-soft.de>
*
* This program is free software: you can redistribute it and/or
* modify it under the terms of the GNU General Public License as
* published by the Free Software Foundation, either version 3 of the
* License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>
*/
//! Finite-dimensional sparse and dense vectors.
use Real;
use std::fmt;
use std::ops::{Deref, DerefMut};
use std::cmp::min;
/// Type of dense vectors.
#[derive(Debug, Clone, PartialEq, Default)]
pub struct DVector(pub Vec<Real>);
impl Deref for DVector {
type Target = Vec<Real>;
fn deref(&self) -> &Vec<Real> { &self.0 }
}
impl DerefMut for DVector {
fn deref_mut(&mut self) -> &mut Vec<Real> { &mut self.0 }
}
impl fmt::Display for DVector {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
try!(write!(f, "("));
for (i,x) in self.iter().enumerate() {
if i > 0 { try!(write!(f, ", ")); }
try!(write!(f, "{}", x))
}
try!(write!(f, ")"));
Ok(())
}
}
/// Type of dense or vectors.
#[derive(Debug, Clone)]
pub enum Vector {
/// A vector with dense storage.
Dense(DVector),
/**
* A vector with sparse storage.
*
* For each non-zero element this vector stores an index and the
* value of the element in addition to the size of the vector.
*/
Sparse { size: usize, elems: Vec<(usize, Real)> },
}
impl fmt::Display for Vector {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
match self {
&Vector::Dense(ref v) => write!(f, "{}", v),
&Vector::Sparse{ size, ref elems } => {
let mut it = elems.iter();
try!(write!(f, "{}:(", size));
if let Some(&(i,x)) = it.next() {
try!(write!(f, "{}:{}", i, x));
for &(i,x) in it {
try!(write!(f, ", {}:{}", i, x));
}
}
write!(f, ")")
}
}
}
}
impl DVector {
/// Set all elements to 0.
pub fn init0(&mut self, size: usize) {
let n = self.len();
self.resize(size, 0.0);
for i in 0..min(n, size) {
self[i] = 0.0;
}
}
/// Set self = factor * y.
pub fn scal(&mut self, factor: Real, y: &DVector) {
self.resize(y.len(), 0.0);
for (i,x) in y.iter().enumerate() {
self[i] = factor * x;
}
}
/// Return the inner product with another vector.
pub fn dot(&self, other: &DVector) -> Real {
let mut ip = 0.0;
for i in 0..self.len() {
ip += self[i] * other[i];
}
return ip;
}
/// Add two vectors and store result in this vector.
pub fn add(&mut self, x: &DVector, y: &DVector) {
assert!(x.len() == y.len());
self.resize(x.len(), 0.0);
for i in 0..x.len() {
self[i] = x[i] + y[i];
}
}
/// Add two vectors and store result in this vector.
pub fn add_scaled(&mut self, alpha : Real, y: &DVector) {
assert!(self.len() == y.len());
for i in 0..self.len() {
self[i] += alpha * y[i];
}
}
/// Combines this vector with another vector.
pub fn combine(&self, self_factor: Real, other_factor: Real, other: &DVector) -> DVector{
assert!(self.len() == other.len());
let mut result = DVector(Vec::with_capacity(self.len()));
for i in 0..self.len() {
result.push(self_factor * self[i] + other_factor * other[i]);
}
result
}
/// Return the 2-norm of this vector.
pub fn norm2(&self) -> Real {
let mut norm = 0.0;
for x in self.iter() { norm += x*x }
norm.sqrt()
}
}
impl Vector {
/**
* Return a sparse vector with the given non-zeros.
*/
pub fn new_sparse(n: usize, indices: &[usize], values: &[Real]) -> Vector {
assert!(indices.len() == values.len());
if indices.len() == 0 {
Vector::Sparse { size: n, elems: vec![] }
} else {
let mut ordered : Vec<_> = (0..n).collect();
ordered.sort_by_key(|&i| indices[i]);
assert!(*indices.last().unwrap() < n);
let mut elems = Vec::with_capacity(indices.len());
let mut last_idx = n;
for i in ordered {
if values[i] != 0.0 {
if indices[i] != last_idx {
elems.push((indices[i], values[i]));
last_idx = indices[i];
} else {
elems.last_mut().unwrap().1 += values[i];
if elems.last_mut().unwrap().1 == 0.0 {
elems.pop();
last_idx = n;
}
}
}
}
Vector::Sparse { size: n, elems: elems }
}
}
/**
* Convert vector to a dense vector.
*
* This function always returns a copy of the vector.
*/
pub fn to_dense(&self) -> DVector {
match self {
&Vector::Dense(ref x) => x.clone(),
&Vector::Sparse{size: n, elems: ref xs} => {
let mut v = vec![0.0; n];
for &(i,x) in xs { v[i] = x; }
DVector(v)
}
}
}
}