csr_matrix 0.1.0

use super::CsrMatrix;
use super::CsrMatrixBuilder;

impl<T> CsrMatrixBuilder<T> {
    /// Creates and returns a new builder.
    pub fn new(m: usize, n: usize) -> Self {
        Self {
            m,
            n,
            entries: vec![],
        }
    }

    /// Informs the builder that position (i, j) is populated with the given value.
    pub fn add_entry(&mut self, i: usize, j: usize, value: T) {
        self.entries.push((i, j, value));
    }

    /// Consumes the builder, and builds a CsrMatrix from the builder and returns it.
    pub fn build(mut self) -> CsrMatrix<T> {
        let offsets = self.get_offsets();

        self.sort_entries_by_row(&offsets);

        CsrMatrix {
            m: self.m,
            n: self.n,
            offsets,
            entries: self
                .entries
                .into_iter()
                .map(|(_, j, value)| (j, value))
                .collect(),
        }
    }

    fn get_offsets(&self) -> Vec<usize> {
        let mut offsets = vec![0usize; self.m + 1];
        for (i, _, _) in self.entries.iter() {
            offsets[*i] += 1;
        }

        let mut sum = 0;
        for row in 0..=self.m {
            let offset = offsets[row];
            offsets[row] = sum;
            sum += offset;
        }

        offsets
    }

    fn sort_entries_by_row(&mut self, offsets: &Vec<usize>) {
        let mut next = vec![0usize; self.m];

        for index in 0..self.entries.len() {
            loop {
                let (i, _, _) = self.entries[index];
                if offsets[i] <= index && index < offsets[i + 1] {
                    break;
                } else {
                    self.entries.swap(index, offsets[i] + next[i]);
                    next[i] += 1;
                }
            }
        }
    }
}