/*
 * 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)
            }
        }
    }
}
