sparse 0.1.2

//! Coordinate (COO) format sparse matrix.

use std::{cmp::max, iter::FromIterator};
/// Coordinate (COO) format sparse matrix.
///
/// # Format
///
/// The coordinate storage format stores tuples `(row, col, value)` for each non-zero element of the matrix.
///
/// ## Properties
///
/// - The coordinate format is intented for incremental matrix constructions.
/// - The coordinate format **allows** duplicates.
/// - When a COO matrix is converted to a compressed format (CSC or CSR), **duplicate entries are summed up**.
///
/// ## Storage
///
/// Let `A` a 3-by-4 (real) matrix with 6 non-zero entries:
///
/// ```text
///     | 0 1 0 2 |
/// A = | 0 0 3 0 |
///     | 4 5 6 0 |
/// ```
///
/// In arbitrary order, 'A' may be stored as follows:
///
/// ```text
/// (row, col, val) idx
/// (0, 1, 1.0)     [0]
/// (1, 2, 3.0)     [1]
/// (2, 1, 5.0)     [2]
/// (0, 3, 2.0)     [3]
/// (2, 0, 4.0)     [4]
/// (2, 2, 6.0)     [5]
/// ```
///
/// In row major order, `A` is stored as follows:
///
/// ```text
/// (row, col, val) idx
/// (0, 1, 1.0)     [0]
/// (0, 3, 2.0)     [1]
/// (1, 2, 3.0)     [2]
/// (2, 0, 4.0)     [3]
/// (2, 1, 5.0)     [4]
/// (2, 2, 6.0)     [5]
///  ^
///  | major
/// ```
///
/// In column major order, `A` is stored as follows:
///
/// ```text
/// (row, col, val) idx
/// (2, 0, 4.0)     [0]
/// (0, 1, 1.0)     [1]
/// (2, 1, 5.0)     [2]
/// (1, 2, 3.0)     [3]
/// (2, 2, 6.0)     [4]
/// (0, 3, 2.0)     [5]
///     ^
///     | major
/// ```
///
/// ## Constructors
///
/// `CooMat` provides multiple constructors:
///
/// ```rust
/// use sparse::CooMat;
///
/// // Create an empty COO matrix
/// let rows = 2;
/// let cols = 3;
/// let a = CooMat::<f64>::new(rows, cols);
///
/// // Create an empty COO matrix with initial capacity
/// let rows = 2;
/// let cols = 3;
/// let capacity = 6;
/// let b = CooMat::<f64>::with_capacity(rows, cols, capacity);
///
/// // Create a COO matrix with initial entries from entry vector
/// // Providing shape ...
/// let rows = 2;
/// let cols = 2;
/// let entries = vec![(0, 0, 1.0), (1, 1, 2.0)];
/// let c = CooMat::with_entries(rows, cols, entries);
/// // ... or not (rows = max(row), cols = max(col))
/// let entries = vec![(0, 0, 1.0), (1, 1, 2.0)];
/// let c: CooMat<f64> = entries.into_iter().collect();
///
/// // Create a COO matrix with initial entries from triplet vectors
/// let rows = 2;
/// let cols = 2;
/// let rowind = vec![0, 1];
/// let colind = vec![0, 1];
/// let values = vec![1.0, 2.0];
/// let e = CooMat::with_triplets(rows, cols, rowind, colind, values);
/// ```
///
/// ## Entry get/insertion/removal/clear
///
/// `CooMat` is intented for incremental matrix constructions and provides corresponding methods:
///
/// ```rust
/// use sparse::CooMat;
///
/// let mut matrix = CooMat::with_capacity(3, 3, 9);
/// // matrix:
/// // | 0 0 0 |
/// // | 0 0 0 |
/// // | 0 0 0 |
///
/// // Insert new entries one by one
/// matrix.push(0, 0, 1.0);
/// matrix.push(0, 1, 2.0);
/// matrix.push(1, 0, 3.0);
/// matrix.push(1, 1, 4.0);
/// // matrix:
/// // | 1 2 0 |
/// // | 3 4 0 |
/// // | 0 0 0 |
/// // entries:
/// // (0, 0, 1.0) [0]
/// // (0, 1, 2.0) [1]
/// // (1, 0, 3.0) [2]
/// // (1, 1, 4.0) [3]
/// assert_eq!(matrix.len(), 4);
///
/// // Get an immutable reference to an entry
/// let entry = matrix.get(0);
/// assert_eq!(entry, Some((&0, &0, &1.0)));
///
/// // Get a mutable reference to an entry and modify it
/// // (only the value is mutable)
/// if let Some((r, c, v)) = matrix.get_mut(0) {
///     *v *= -1.0;
/// }
/// // matrix:
/// // |-1 2 0 |
/// // | 3 4 0 |
/// // | 0 0 0 |
/// // entries:
/// // (0, 0,-1.0) [0]
/// // (0, 1, 2.0) [1]
/// // (1, 0, 3.0) [2]
/// // (1, 1, 4.0) [3]
/// let entry = matrix.get(0);
/// assert_eq!(entry, Some((&0, &0, &-1.0)));
///
/// // Extend the matrix with new entries
/// let entries = vec![
///     (0, 2, 5.0),
///     (1, 2, 6.0),
///     (2, 1, 8.0),
///     (2, 2, 9.0),
/// ];
/// matrix.extend(entries);
/// // matrix:
/// // |-1 2 5 |
/// // | 3 4 6 |
/// // | 0 8 9 |
/// // entries:
/// // (0, 0,-1.0) [0]
/// // (0, 1, 2.0) [1]
/// // (1, 0, 3.0) [2]
/// // (1, 1, 4.0) [3]
/// // (0, 2, 5.0) [4] <|
/// // (1, 2, 6.0) [5] <|
/// // (2, 1, 8.0) [6] <|
/// // (2, 2, 9.0) [7] <|- entries added
/// assert_eq!(matrix.len(), 8);
///
/// // Insert new entry at specified index
/// matrix.insert(6, 2, 0, 7.0);
/// // matrix:
/// // |-1 2 5 |
/// // | 3 4 6 |
/// // | 7 8 9 |
/// // entries:
/// // (0, 0,-1.0) [0]
/// // (0, 1, 2.0) [1]
/// // (1, 0, 3.0) [2]
/// // (1, 1, 4.0) [3]
/// // (0, 2, 5.0) [4]
/// // (1, 2, 6.0) [5]
/// // (2, 0, 7.0) [6] <- entry inserted
/// // (2, 1, 8.0) [7] <|
/// // (2, 2, 9.0) [8] <|- indices shifted
/// assert_eq!(matrix.len(), 9);
/// assert_eq!(matrix.get(6), Some((&2, &0, &7.0)));
///
/// // Remove last entry
/// assert_eq!(matrix.pop(), Some((2, 2, 9.0)));
/// // matrix:
/// // |-1 2 5 |
/// // | 3 4 6 |
/// // | 7 8 0 |
/// // entries:
/// // (0, 0,-1.0) [0]
/// // (0, 1, 2.0) [1]
/// // (1, 0, 3.0) [2]
/// // (1, 1, 4.0) [3]
/// // (0, 2, 5.0) [4]
/// // (1, 2, 6.0) [5]
/// // (2, 0, 7.0) [6]
/// // (2, 1, 8.0) [7]
/// // (2, 2, 9.0) [x] <- entry removed
/// assert_eq!(matrix.len(), 8);
///
/// // Remove a specific entry
/// let entry = matrix.remove(1);
/// assert_eq!(entry, (0, 1, 2.0));
/// // matrix:
/// // |-1 0 5 |
/// // | 3 4 6 |
/// // | 7 8 0 |
/// // entries:
/// // (0, 0,-1.0) [0]
/// // (0, 1, 2.0) [x] <- entry removed
/// // (1, 0, 3.0) [1] <|
/// // (1, 1, 4.0) [2] <|
/// // (0, 2, 5.0) [3] <|
/// // (1, 2, 6.0) [4] <|
/// // (2, 0, 7.0) [5] <|
/// // (2, 1, 8.0) [6] <|- indices shifted
/// assert_eq!(matrix.len(), 7);
///
/// // Swap entries
/// matrix.swap(3, 5);
/// // matrix:
/// // |-1 0 7 |
/// // | 3 4 6 |
/// // | 5 8 0 |
/// // entries:
/// // (0, 0,-1.0) [0]
/// // (1, 0, 3.0) [1]
/// // (1, 1, 4.0) [2]
/// // (2, 0, 7.0) [3] <- entry swapped [5] -> [3]
/// // (1, 2, 6.0) [4]
/// // (0, 2, 5.0) [5] <- entry swapped [3] -> [5]
/// // (2, 1, 8.0) [6]
/// assert_eq!(matrix.get(3), Some((&2, &0, &7.0)));
/// assert_eq!(matrix.get(5), Some((&0, &2, &5.0)));
///
/// // Swap remove a specific entry
/// let entry = matrix.swap_remove(1);
/// assert_eq!(entry, (1, 0, 3.0));
/// // matrix:
/// // |-1 0 5 |
/// // | 0 4 6 |
/// // | 7 8 0 |
/// // entries:
/// // (0, 0,-1.0) [0]
/// // (1, 0, 3.0) [x] <- entry removed
/// // (2, 1, 8.0) [1] <- entry swapped [6] -> [1]
/// // (1, 1, 4.0) [2]
/// // (2, 0, 7.0) [3]
/// // (1, 2, 6.0) [4]
/// // (0, 2, 5.0) [5]
/// assert_eq!(matrix.len(), 6);
/// assert_eq!(matrix.get(1), Some((&2, &1, &8.0)));
///
/// // Retain entries
/// matrix.retain(|(r, c, _)| *r > 0 && *c > 0);
/// // matrix:
/// // |-1 0 5 |
/// // | 0 4 6 |
/// // | 7 8 0 |
/// // entries:
/// // (0, 0,-1.0) [x] <- entry removed
/// // (2, 1, 8.0) [0]
/// // (1, 1, 4.0) [1]
/// // (2, 0, 7.0) [x] <- entry removed
/// // (1, 2, 6.0) [2]
/// // (0, 2, 5.0) [x] <- entry removed
/// assert_eq!(matrix.len(), 3);
/// assert_eq!(matrix.get(0), Some((&2, &1, &8.0)));
/// assert_eq!(matrix.get(1), Some((&1, &1, &4.0)));
/// assert_eq!(matrix.get(2), Some((&1, &2, &6.0)));
///
/// // Clear matrix
/// matrix.clear();
/// assert!(matrix.is_empty())
/// ```
///
/// ## Capacity and Length
///
/// The matrix *capacity* corresponds to the amount of space allocated for the matrix entries unlike the matrix *length* which corresponds to the number of entries in the matrix.
/// Initially for empty matrices, no memory is allocated.
/// If entries are inserted, matrix capacity will grow accordingly.
/// The growth strategy is *unspecified behavior* and no guarentees are made.
///
/// `CooMat` provides multiple methods to manage matrix capacity and length:
///
/// ```rust
/// use sparse::CooMat;
///
/// let mut matrix: CooMat<f64> = CooMat::new(2, 2);
/// // Initially capacity and length are 0
/// assert_eq!(matrix.capacity(), 0);
/// assert_eq!(matrix.len(), 0);
///
/// // Inserting an entry allocate space for at least one entry
/// matrix.push(0, 0, 1.0);
/// assert!(matrix.capacity() >= 1);
/// assert_eq!(matrix.len(), 1);
///
/// // Inserting other entries may reallocate
/// matrix.push(1, 1, 2.0);
/// assert!(matrix.capacity() >= 2);
/// assert_eq!(matrix.len(), 2);
///
/// // To prevent reallocation, capacity can be adjusted at construction time
/// let mut matrix: CooMat<f64> = CooMat::with_capacity(2, 2, 4);
/// assert_eq!(matrix.capacity(), 4);
/// assert!(matrix.is_empty());
///
/// // Pushing values will not reallocate
/// matrix.push(0, 0, 1.0);
/// assert_eq!(matrix.capacity(), 4);
/// assert_eq!(matrix.len(), 1);
///
/// // Additional capacity can be requested after construction
/// let mut matrix: CooMat<f64> = CooMat::with_capacity(2, 2, 1);
/// assert_eq!(matrix.capacity(), 1);
/// matrix.reserve(4);
/// assert!(matrix.capacity() >= 4);
///
/// // Capacity can be shrunk to fit (best effort) actual number of entries
/// let mut matrix: CooMat<f64> = CooMat::with_capacity(3, 3, 9);
/// assert_eq!(matrix.capacity(), 9);
/// matrix.push(1, 1, 1.0);
/// matrix.shrink();
/// assert!(matrix.capacity() < 9);
/// ```
///
/// ## Iterators
///
/// CooMat also provides convenient Iterators/IntoIterator:
///
/// ```rust
/// use sparse::CooMat;
/// let entries = vec![
///     (0, 0, 1.0),
///     (0, 1, 2.0),
///     (1, 0, 3.0),
///     (1, 1, 4.0),
/// ];
/// let mut matrix = CooMat::with_entries(2, 2, entries);
///
/// // Immutable iterator over entries
/// let mut iter = matrix.iter();
/// assert_eq!(iter.next(), Some((&0, &0, &1.0)));
/// assert_eq!(iter.next(), Some((&0, &1, &2.0)));
/// assert_eq!(iter.next(), Some((&1, &0, &3.0)));
/// assert_eq!(iter.next(), Some((&1, &1, &4.0)));
/// assert_eq!(iter.next(), None);
///
/// // Mutable iterator over entries
/// let mut iter = matrix.iter_mut();
/// for (r, c, v) in iter {
///     *v *= 2.0;
/// }
/// let mut iter = matrix.iter();
/// assert_eq!(iter.next(), Some((&0, &0, &2.0)));
/// assert_eq!(iter.next(), Some((&0, &1, &4.0)));
/// assert_eq!(iter.next(), Some((&1, &0, &6.0)));
/// assert_eq!(iter.next(), Some((&1, &1, &8.0)));
/// assert_eq!(iter.next(), None);
///
/// // Turn matrix into iterator
/// for (r, c, v) in matrix {
///     println!("row = {}, col = {}, value = {}", r, c, v);
/// }
/// ```
///
/// ## Sorting
///
/// Sorting entries before iterating over matrix entries can be convenient.
/// Coordinate matrix format can be sorted in row/column major order:
///
/// ```rust
/// use sparse::CooMat;
/// let rows = 2;
/// let cols = 2;
/// let rowind = vec![0, 0, 1, 1];
/// let colind = vec![0, 1, 0, 1];
/// let values = vec![1.0, 2.0, 3.0, 4.0];
/// let mut matrix = CooMat::with_triplets(rows, cols, rowind, colind, values);
/// // matrix:
/// // | 1 2 |
/// // | 3 4 |
///
/// // Sort row major order
/// matrix.sort_unstable_row_major();
/// // Row major order: 1 -> 2 -> 3 -> 4
/// let mut iter = matrix.iter();
/// assert_eq!(iter.next(), Some((&0, &0, &1.0)));
/// assert_eq!(iter.next(), Some((&0, &1, &2.0)));
/// assert_eq!(iter.next(), Some((&1, &0, &3.0)));
/// assert_eq!(iter.next(), Some((&1, &1, &4.0)));
/// assert_eq!(iter.next(), None);
///
/// // Sort column major order
/// matrix.sort_unstable_col_major();
/// // Col major order: 1 -> 3 -> 2 -> 4
/// let mut iter = matrix.iter();
/// assert_eq!(iter.next(), Some((&0, &0, &1.0)));
/// assert_eq!(iter.next(), Some((&1, &0, &3.0)));
/// assert_eq!(iter.next(), Some((&0, &1, &2.0)));
/// assert_eq!(iter.next(), Some((&1, &1, &4.0)));
/// assert_eq!(iter.next(), None);
/// ```
///
/// If sorting stability is not required, prefer `sort_unstable_*` variants for performance.
#[derive(Clone, Debug)]
pub struct CooMat<T> {
    rows: usize,
    cols: usize,
    entries: Vec<(usize, usize, T)>,
}

impl<T> CooMat<T> {
    /// Creates a coordinate format sparse matrix with specified shape `(rows, cols)`.
    ///
    /// The created matrix has following properties:
    /// - the matrix is empty
    /// - the matrix capacity is `0`
    /// - the matrix will **not** allocate memory before any insert/push operation
    ///
    /// If `rows` or `cols` is `0` the corresponding dimension is set to `1`.
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    ///
    /// // With type annotation ...
    /// let matrix: CooMat<f64> = CooMat::new(2, 2);
    /// assert_eq!(matrix.shape(), (2, 2));
    /// assert!(matrix.is_empty());
    /// assert_eq!(matrix.capacity(), 0);
    ///
    /// // ... or with turbofish operator
    /// let matrix = CooMat::<f64>::new(3, 4);
    /// assert_eq!(matrix.shape(), (3, 4));
    /// assert!(matrix.is_empty());
    /// assert_eq!(matrix.capacity(), 0);
    /// ```
    pub fn new(rows: usize, cols: usize) -> Self {
        let rows = max(rows, 1);
        let cols = max(cols, 1);
        let entries = Vec::new();
        CooMat {
            rows,
            cols,
            entries,
        }
    }

    /// Creates a coordinate format sparse matrix with specified shape `(rows, cols)` and capacity.
    ///
    /// The created matrix has following properties:
    /// - the matrix is empty
    /// - the matrix capacity is `capacity`
    /// - the matrix will allocate memory for at least `capacity` entries
    ///
    /// If `rows` or `cols` is `0` the corresponding dimension is set to `1`.
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let matrix = CooMat::<f64>::with_capacity(2, 2, 4);
    /// assert_eq!(matrix.shape(), (2, 2));
    /// assert!(matrix.is_empty());
    /// assert_eq!(matrix.capacity(), 4);
    /// ```
    pub fn with_capacity(rows: usize, cols: usize, capacity: usize) -> Self {
        let rows = max(rows, 1);
        let cols = max(cols, 1);
        let entries = Vec::with_capacity(capacity);
        CooMat {
            rows,
            cols,
            entries,
        }
    }

    /// Creates a coordinate format sparse matrix with specified shape `(rows, cols)` and entries.
    ///
    /// The created matrix has following properties:
    /// - the matrix is filled with `entries`
    /// - the matrix capacity is at least `entries.len()`
    ///
    /// If `rows` or `cols` is `0` the corresponding dimension is set to `1`.
    ///
    /// # Panics
    ///
    /// Panics if any entry's row or column index exceeds number of rows or columns respectively.
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let entries = vec![
    ///     (0, 0, 1.0),
    ///     (0, 1, 2.0),
    ///     (1, 0, 3.0),
    ///     (1, 1, 4.0),
    /// ];
    /// let matrix = CooMat::with_entries(2, 2, entries);
    /// assert_eq!(matrix.shape(), (2, 2));
    /// assert_eq!(matrix.len(), 4);
    /// assert!(matrix.capacity() >= 4);
    /// ```
    pub fn with_entries<I>(rows: usize, cols: usize, entries: I) -> Self
    where
        I: IntoIterator<Item = (usize, usize, T)>,
    {
        let rows = max(rows, 1);
        let cols = max(cols, 1);
        let entries: Vec<_> = entries.into_iter().collect();
        for (row, col, _) in entries.iter() {
            if *row >= rows {
                panic!("invalid row index ({}) should be < rows ({})", row, rows);
            }
            if *col >= cols {
                panic!("invalid column index ({}) should be < cols ({})", col, cols);
            }
        }
        CooMat {
            rows,
            cols,
            entries,
        }
    }

    /// Creates a coordinate format sparse matrix with specified shape `(rows, cols)` and triplets.
    ///
    /// The created matrix has following properties:
    /// - the matrix is filled with `values.len()` entries
    /// - the matrix capacity is at least `values.len()`
    ///
    /// # Panics
    ///
    /// Panics if
    /// - any row or column index exceeds number of rows or columns respectively.
    /// - `rowind`, `colind` and `values` length differ.
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let rowind = vec![0, 0, 1, 1];
    /// let colind = vec![0, 1, 0, 1];
    /// let values = vec![1.0, 2.0, 3.0, 4.0];
    /// let matrix = CooMat::with_triplets(2, 2, rowind, colind, values);
    /// assert_eq!(matrix.shape(), (2, 2));
    /// assert_eq!(matrix.len(), 4);
    /// assert!(matrix.capacity() >= 4);
    /// ```
    pub fn with_triplets<R, C, V>(rows: usize, cols: usize, rowind: R, colind: C, values: V) -> Self
    where
        R: IntoIterator<Item = usize>,
        C: IntoIterator<Item = usize>,
        V: IntoIterator<Item = T>,
    {
        let rows = max(rows, 1);
        let cols = max(cols, 1);
        let rowind: Vec<_> = rowind.into_iter().collect();
        let colind: Vec<_> = colind.into_iter().collect();
        let values: Vec<_> = values.into_iter().collect();
        let len = values.len();
        if rowind.len() != len || colind.len() != len {
            panic!(
                "invalid triplets: rowind ({}), colind ({}) and values ({}) lengths differ",
                rowind.len(),
                colind.len(),
                values.len()
            );
        }
        for (row, col) in rowind.iter().zip(colind.iter()) {
            if *row >= rows {
                panic!("invalid row index ({}) should be < rows ({})", row, rows);
            }
            if *col >= cols {
                panic!("invalid column index ({}) should be < cols ({})", col, cols);
            }
        }
        let mut entries = Vec::with_capacity(len);
        for (idx, value) in values.into_iter().enumerate() {
            entries.push((rowind[idx], colind[idx], value));
        }
        CooMat {
            rows,
            cols,
            entries,
        }
    }

    /// Returns the number of rows of the matrix.
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let matrix = CooMat::<f64>::new(1, 2);
    /// assert_eq!(matrix.rows(), 1);
    /// ```
    pub fn rows(&self) -> usize {
        self.rows
    }

    /// Returns the number of cols of the matrix.
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let matrix = CooMat::<f64>::new(1, 2);
    /// assert_eq!(matrix.cols(), 2);
    /// ```
    pub fn cols(&self) -> usize {
        self.cols
    }

    /// Returns the shape of the matrix.
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let matrix = CooMat::<f64>::new(1, 2);
    /// assert_eq!(matrix.shape(), (1, 2));
    /// ```
    pub fn shape(&self) -> (usize, usize) {
        (self.rows, self.cols)
    }

    /// Returns the capacity of the matrix.
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let matrix = CooMat::<f64>::with_capacity(1, 1, 42);
    /// assert_eq!(matrix.capacity(), 42);
    /// ```
    pub fn capacity(&self) -> usize {
        self.entries.capacity()
    }

    /// Reserve additional capacity for the matrix.
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let mut matrix = CooMat::<f64>::new(1, 1);
    /// assert_eq!(matrix.capacity(), 0);
    /// matrix.reserve(10);
    /// assert!(matrix.capacity() >= 10);
    /// ```
    pub fn reserve(&mut self, additional: usize) {
        self.entries.reserve(additional);
    }

    /// Shrink the capacity of the matrix.
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let mut matrix = CooMat::<f64>::with_capacity(1, 1, 42);
    /// assert_eq!(matrix.capacity(), 42);
    /// matrix.shrink();
    /// assert!(matrix.capacity() <= 42);
    /// ```
    pub fn shrink(&mut self) {
        self.entries.shrink_to_fit();
    }

    /// Returns the number of entries in the matrix.
    ///
    /// This number is **not** the number of non zeros element in the matrix because duplicates are
    /// allowed.
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let entries = vec![
    ///     (0, 0, 1.0),
    ///     (0, 1, 2.0),
    ///     (1, 0, 3.0),
    ///     (1, 1, 4.0),
    /// ];
    /// let matrix = CooMat::with_entries(2, 2, entries);
    /// assert_eq!(matrix.len(), 4);
    /// ```
    pub fn len(&self) -> usize {
        self.entries.len()
    }

    /// Returns `true` if the matrix contains no entry.
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let entries = vec![
    ///     (0, 0, 1.0),
    ///     (0, 1, 2.0),
    ///     (1, 0, 3.0),
    ///     (1, 1, 4.0),
    /// ];
    /// let matrix = CooMat::with_entries(2, 2, entries);
    /// let empty = CooMat::<f64>::new(2, 2);
    /// assert!(!matrix.is_empty());
    /// assert!(empty.is_empty());
    /// ```
    pub fn is_empty(&self) -> bool {
        self.entries.is_empty()
    }

    /// Shortens the matrix to `len`.
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let entries = vec![
    ///     (0, 0, 1.0),
    ///     (0, 1, 2.0),
    ///     (1, 0, 3.0),
    ///     (1, 1, 4.0),
    /// ];
    /// let mut matrix = CooMat::with_entries(2, 2, entries);
    /// assert_eq!(matrix.len(), 4);
    /// matrix.truncate(4);
    /// assert_eq!(matrix.len(), 4);
    /// matrix.truncate(2);
    /// assert_eq!(matrix.len(), 2);
    /// ```
    pub fn truncate(&mut self, len: usize) {
        self.entries.truncate(len);
    }

    /// Returns an immutable reference to the entry at specified index.
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let entries = vec![(0, 0, 1.0)];
    /// let matrix = CooMat::with_entries(1, 1, entries);
    /// assert_eq!(matrix.get(0), Some((&0, &0, &1.0)));
    /// ```
    pub fn get(&self, index: usize) -> Option<(&usize, &usize, &T)> {
        self.entries.get(index).map(|(r, c, v)| (r, c, v))
    }

    /// Returns a mutable reference to the entry at specified index.
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let entries = vec![(0, 0, 1.0)];
    /// let mut matrix = CooMat::with_entries(1, 1, entries);
    /// if let Some((_, _, v)) = matrix.get_mut(0) {
    ///     *v *= 2.0;
    /// }
    /// assert_eq!(matrix.get(0), Some((&0, &0, &2.0)));
    /// ```
    pub fn get_mut(&mut self, index: usize) -> Option<(&usize, &usize, &mut T)> {
        self.entries.get_mut(index).map(|(r, c, v)| (&*r, &*c, v))
    }

    /// Swaps two matrix entries.
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let entries = vec![
    ///     (0, 0, 1.0),
    ///     (0, 1, 2.0),
    /// ];
    /// let mut matrix = CooMat::with_entries(1, 2, entries);
    /// assert_eq!(matrix.get(0), Some((&0, &0, &1.0)));
    /// assert_eq!(matrix.get(1), Some((&0, &1, &2.0)));
    /// matrix.swap(0, 1);
    /// assert_eq!(matrix.get(0), Some((&0, &1, &2.0)));
    /// assert_eq!(matrix.get(1), Some((&0, &0, &1.0)));
    /// ```
    pub fn swap(&mut self, a: usize, b: usize) {
        if a > self.len() {
            panic!("invalid index: index = {} | length = {}", a, self.len());
        }
        if b > self.len() {
            panic!("invalid index: index = {} | length = {}", b, self.len());
        }
        self.entries.swap(a, b);
    }

    /// Inserts an entry to the matrix.
    ///
    /// # Panics
    ///
    /// Panics if:
    /// - `row >= self.rows()`
    /// - `col >= self.cols()`
    /// - `index > self.len()`
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let entries = vec![
    ///     (0, 0, 1.0),
    ///     (0, 1, 2.0),
    ///     (1, 1, 4.0),
    /// ];
    /// let mut matrix = CooMat::with_entries(2, 2, entries);
    /// assert_eq!(matrix.get(2), Some((&1, &1, &4.0)));
    /// matrix.insert(2, 1, 0, 3.0);
    /// assert_eq!(matrix.len(), 4);
    /// assert_eq!(matrix.get(2), Some((&1, &0, &3.0)));
    /// assert_eq!(matrix.get(3), Some((&1, &1, &4.0)));
    /// ```
    pub fn insert(&mut self, index: usize, row: usize, col: usize, val: T) {
        if index > self.len() {
            panic!("invalid index: index = {} | length = {}", index, self.len());
        }
        if row >= self.rows {
            panic!("invalid row index: row = {} | rows = {}", row, self.rows);
        }
        if col >= self.cols {
            panic!("invalid column index: col = {} | cols = {}", col, self.cols);
        }
        self.entries.insert(index, (row, col, val));
    }

    /// Remove an entry from the matrix.
    ///
    /// # Panics
    ///
    /// Panics if `index > self.len()`
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let entries = vec![
    ///     (0, 0, 1.0),
    ///     (0, 1, 2.0),
    ///     (1, 0, 3.0),
    ///     (1, 1, 4.0),
    /// ];
    /// let mut matrix = CooMat::with_entries(2, 2, entries);
    /// assert_eq!(matrix.remove(2), (1, 0, 3.0));
    /// assert_eq!(matrix.len(), 3);
    /// ```
    pub fn remove(&mut self, index: usize) -> (usize, usize, T) {
        if index > self.len() {
            panic!("invalid index: index = {} | length = {}", index, self.len());
        }
        self.entries.remove(index)
    }

    /// Remove an entry from the matrix and swap with last entry.
    ///
    /// # Panics
    ///
    /// Panics if `index > self.len()`
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let entries = vec![
    ///     (0, 0, 1.0),
    ///     (0, 1, 2.0),
    ///     (1, 0, 3.0),
    ///     (1, 1, 4.0),
    /// ];
    /// let mut matrix = CooMat::with_entries(2, 2, entries);
    /// assert_eq!(matrix.swap_remove(1), (0, 1, 2.0));
    /// assert_eq!(matrix.len(), 3);
    /// assert_eq!(matrix.get(1), Some((&1, &1, &4.0)));
    /// ```
    pub fn swap_remove(&mut self, index: usize) -> (usize, usize, T) {
        if index > self.len() {
            panic!("invalid index: index = {} | length = {}", index, self.len());
        }
        self.entries.swap_remove(index)
    }

    /// Appends an entry to the matrix.
    ///
    /// # Panics
    ///
    /// Panics if:
    /// - `row >= self.rows()`
    /// - `col >= self.cols()`
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let mut matrix = CooMat::with_capacity(1, 1, 1);
    /// matrix.push(0, 0, 1.0);
    /// assert_eq!(matrix.len(), 1);
    /// assert_eq!(matrix.get(0), Some((&0, &0, &1.0)));
    /// ```
    pub fn push(&mut self, row: usize, col: usize, val: T) {
        if row >= self.rows {
            panic!("invalid row index: row = {} | rows = {}", row, self.rows);
        }
        if col >= self.cols {
            panic!("invalid column index: col = {} | cols = {}", col, self.cols);
        }
        self.entries.push((row, col, val));
    }

    /// Remove last entry from the matrix.
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let entries = vec![(0, 0, 1.0), (1, 1, 2.0)];
    /// let mut matrix = CooMat::with_entries(2, 2, entries);
    /// assert_eq!(matrix.get(matrix.len() - 1), Some((&1, &1, &2.0)));
    /// assert_eq!(matrix.pop(), Some((1, 1, 2.0)));
    /// assert_eq!(matrix.get(matrix.len() - 1), Some((&0, &0, &1.0)));
    /// assert_eq!(matrix.pop(), Some((0, 0, 1.0)));
    /// assert!(matrix.is_empty());
    /// ```
    pub fn pop(&mut self) -> Option<(usize, usize, T)> {
        self.entries.pop()
    }

    /// Retains only the entries specified by the predicate.
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let entries = vec![
    ///     (0, 0, 1.0),
    ///     (0, 1, 2.0),
    ///     (1, 0, 3.0),
    ///     (1, 1, 4.0),
    /// ];
    /// let mut matrix = CooMat::with_entries(2, 2, entries);
    /// matrix.retain(|(r, c, _)| *r + *c != 1);
    /// assert_eq!(matrix.len(), 2);
    /// assert_eq!(matrix.get(0), Some((&0, &0, &1.0)));
    /// assert_eq!(matrix.get(1), Some((&1, &1, &4.0)));
    /// ```
    pub fn retain<F>(&mut self, pred: F)
    where
        F: FnMut(&(usize, usize, T)) -> bool,
    {
        self.entries.retain(pred);
    }

    /// Clears the matrix.
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let entries = vec![
    ///     (0, 0, 1.0),
    ///     (0, 1, 2.0),
    ///     (1, 0, 3.0),
    ///     (1, 1, 4.0),
    /// ];
    /// let mut matrix = CooMat::with_entries(2, 2, entries);
    /// matrix.clear();
    /// assert!(matrix.is_empty());
    /// ```
    pub fn clear(&mut self) {
        self.entries.clear();
    }

    /// Sort (stable) the matrix entries with row major order.
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let entries = vec![
    ///     (1, 1, 4.0),
    ///     (0, 0, 1.0),
    ///     (1, 0, 3.0),
    ///     (0, 1, 2.0),
    /// ];
    /// let mut matrix = CooMat::with_entries(2, 2, entries);
    /// matrix.sort_stable_row_major();
    ///
    /// let mut iter = matrix.iter();
    /// assert_eq!(iter.next(), Some((&0, &0, &1.0)));
    /// assert_eq!(iter.next(), Some((&0, &1, &2.0)));
    /// assert_eq!(iter.next(), Some((&1, &0, &3.0)));
    /// assert_eq!(iter.next(), Some((&1, &1, &4.0)));
    /// assert_eq!(iter.next(), None);
    /// ```
    pub fn sort_stable_row_major(&mut self) {
        self.entries
            .sort_by(|(r1, c1, _), (r2, c2, _)| r1.cmp(r2).then(c1.cmp(c2)));
    }

    /// Sort (stable) the matrix entries with column major order.
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let entries = vec![
    ///     (1, 1, 4.0),
    ///     (0, 0, 1.0),
    ///     (1, 0, 3.0),
    ///     (0, 1, 2.0),
    /// ];
    /// let mut matrix = CooMat::with_entries(2, 2, entries);
    /// matrix.sort_stable_col_major();
    ///
    /// let mut iter = matrix.iter();
    /// assert_eq!(iter.next(), Some((&0, &0, &1.0)));
    /// assert_eq!(iter.next(), Some((&1, &0, &3.0)));
    /// assert_eq!(iter.next(), Some((&0, &1, &2.0)));
    /// assert_eq!(iter.next(), Some((&1, &1, &4.0)));
    /// assert_eq!(iter.next(), None);
    /// ```
    pub fn sort_stable_col_major(&mut self) {
        self.entries
            .sort_by(|(r1, c1, _), (r2, c2, _)| c1.cmp(c2).then(r1.cmp(r2)));
    }

    /// Sort (unstable) the matrix entries with row major order.
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let entries = vec![
    ///     (1, 1, 4.0),
    ///     (0, 0, 1.0),
    ///     (1, 0, 3.0),
    ///     (0, 1, 2.0),
    /// ];
    /// let mut matrix = CooMat::with_entries(2, 2, entries);
    /// matrix.sort_unstable_row_major();
    ///
    /// let mut iter = matrix.iter();
    /// assert_eq!(iter.next(), Some((&0, &0, &1.0)));
    /// assert_eq!(iter.next(), Some((&0, &1, &2.0)));
    /// assert_eq!(iter.next(), Some((&1, &0, &3.0)));
    /// assert_eq!(iter.next(), Some((&1, &1, &4.0)));
    /// assert_eq!(iter.next(), None);
    /// ```
    pub fn sort_unstable_row_major(&mut self) {
        self.entries
            .sort_unstable_by(|(r1, c1, _), (r2, c2, _)| r1.cmp(r2).then(c1.cmp(c2)));
    }

    /// Sort (unstable) the matrix entries with column major order.
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let entries = vec![
    ///     (1, 1, 4.0),
    ///     (0, 0, 1.0),
    ///     (1, 0, 3.0),
    ///     (0, 1, 2.0),
    /// ];
    /// let mut matrix = CooMat::with_entries(2, 2, entries);
    /// matrix.sort_unstable_col_major();
    ///
    /// let mut iter = matrix.iter();
    /// assert_eq!(iter.next(), Some((&0, &0, &1.0)));
    /// assert_eq!(iter.next(), Some((&1, &0, &3.0)));
    /// assert_eq!(iter.next(), Some((&0, &1, &2.0)));
    /// assert_eq!(iter.next(), Some((&1, &1, &4.0)));
    /// assert_eq!(iter.next(), None);
    /// ```
    pub fn sort_unstable_col_major(&mut self) {
        self.entries
            .sort_unstable_by(|(r1, c1, _), (r2, c2, _)| c1.cmp(c2).then(r1.cmp(r2)));
    }

    /// Reverse matrix entries order.
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let entries = vec![
    ///     (1, 1, 4.0),
    ///     (0, 0, 1.0),
    ///     (1, 0, 3.0),
    ///     (0, 1, 2.0),
    /// ];
    /// let mut matrix = CooMat::with_entries(2, 2, entries);
    /// matrix.sort_stable_row_major();
    ///
    /// let mut iter = matrix.iter();
    /// assert_eq!(iter.next(), Some((&0, &0, &1.0)));
    /// assert_eq!(iter.next(), Some((&0, &1, &2.0)));
    /// assert_eq!(iter.next(), Some((&1, &0, &3.0)));
    /// assert_eq!(iter.next(), Some((&1, &1, &4.0)));
    /// assert_eq!(iter.next(), None);
    ///
    /// matrix.reverse();
    /// let mut iter = matrix.iter();
    /// assert_eq!(iter.next(), Some((&1, &1, &4.0)));
    /// assert_eq!(iter.next(), Some((&1, &0, &3.0)));
    /// assert_eq!(iter.next(), Some((&0, &1, &2.0)));
    /// assert_eq!(iter.next(), Some((&0, &0, &1.0)));
    /// assert_eq!(iter.next(), None);
    /// ```
    pub fn reverse(&mut self) {
        self.entries.reverse();
    }

    /// An iterator visiting all entries of the matrix.
    /// The iterator element type is `(&'a usize, &'a usize, &'a T)`.
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let entries = vec![
    ///     (0, 0, 1.0),
    ///     (0, 1, 2.0),
    ///     (1, 0, 3.0),
    ///     (1, 1, 4.0),
    /// ];
    /// let matrix = CooMat::with_entries(2, 2, entries);
    ///
    /// let mut iter = matrix.iter();
    /// assert_eq!(iter.next(), Some((&0, &0, &1.0)));
    /// assert_eq!(iter.next(), Some((&0, &1, &2.0)));
    /// assert_eq!(iter.next(), Some((&1, &0, &3.0)));
    /// assert_eq!(iter.next(), Some((&1, &1, &4.0)));
    /// assert_eq!(iter.next(), None);
    /// ```
    pub fn iter(&self) -> Iter<T> {
        Iter {
            inner: self.entries.iter(),
        }
    }

    /// An iterator visiting all mutable entries of the matrix.
    /// The iterator element type is `(&'a usize, &'a usize, &'a mut T)`.
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let entries = vec![
    ///     (0, 0, 1.0),
    ///     (0, 1, 2.0),
    ///     (1, 0, 3.0),
    ///     (1, 1, 4.0),
    /// ];
    /// let mut matrix = CooMat::with_entries(2, 2, entries);
    ///
    /// let mut iter = matrix.iter_mut();
    /// for (_, _, v) in iter {
    ///     *v *= 2.0;
    /// }
    ///
    /// let mut iter = matrix.iter_mut();
    /// assert_eq!(iter.next(), Some((&0, &0, &mut 2.0)));
    /// assert_eq!(iter.next(), Some((&0, &1, &mut 4.0)));
    /// assert_eq!(iter.next(), Some((&1, &0, &mut 6.0)));
    /// assert_eq!(iter.next(), Some((&1, &1, &mut 8.0)));
    /// assert_eq!(iter.next(), None);
    /// ```
    pub fn iter_mut(&mut self) -> IterMut<T> {
        IterMut {
            inner: self.entries.iter_mut(),
        }
    }
}

impl<T> Extend<(usize, usize, T)> for CooMat<T> {
    /// Extend matrix entries.
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let entries = vec![
    ///     (0, 0, 1.0),
    ///     (0, 1, 2.0),
    ///     (1, 0, 3.0),
    ///     (1, 1, 4.0),
    /// ];
    /// let mut matrix: CooMat<f64> = CooMat::new(2, 2);
    /// assert_eq!(matrix.len(), 0);
    /// matrix.extend(entries);
    /// assert_eq!(matrix.len(), 4);
    /// ```
    fn extend<I: IntoIterator<Item = (usize, usize, T)>>(&mut self, iter: I) {
        for (row, col, val) in iter {
            self.push(row, col, val);
        }
    }
}

impl<T> FromIterator<(usize, usize, T)> for CooMat<T> {
    /// Collect entries into matrix.
    ///
    /// # Example
    ///
    /// ```rust
    /// use sparse::CooMat;
    /// let entries = vec![
    ///     (0, 0, 1.0),
    ///     (0, 1, 2.0),
    ///     (1, 0, 3.0),
    ///     (1, 1, 4.0),
    /// ];
    /// let matrix: CooMat<f64> = entries.into_iter().collect();
    /// ```
    fn from_iter<I: IntoIterator<Item = (usize, usize, T)>>(iter: I) -> Self {
        let entries: Vec<_> = iter.into_iter().collect();
        if entries.is_empty() {
            CooMat::new(1, 1)
        } else {
            let rows = entries.iter().map(|&(r, _, _)| r).max().unwrap() + 1;
            let cols = entries.iter().map(|&(_, c, _)| c).max().unwrap() + 1;
            CooMat::with_entries(rows, cols, entries)
        }
    }
}

impl<T> IntoIterator for CooMat<T> {
    type Item = (usize, usize, T);

    type IntoIter = IntoIter<T>;

    fn into_iter(self) -> Self::IntoIter {
        IntoIter {
            inner: self.entries.into_iter(),
        }
    }
}

/// Immutable coordinate sparse matrix iterator.
///
/// This iterator is created by the [iter()](CooMat::iter()) method on
/// coordinate sparse matrix.
#[derive(Clone, Debug)]
pub struct Iter<'iter, T: 'iter> {
    inner: std::slice::Iter<'iter, (usize, usize, T)>,
}

impl<'iter, T: 'iter> Iterator for Iter<'iter, T> {
    type Item = (&'iter usize, &'iter usize, &'iter T);

    fn next(&mut self) -> Option<Self::Item> {
        self.inner.next().map(|(r, c, v)| (r, c, v))
    }
}

impl<T> DoubleEndedIterator for Iter<'_, T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.inner.next_back().map(|(r, c, v)| (r, c, v))
    }
}

impl<T> ExactSizeIterator for Iter<'_, T> {}

/// Mutable coordinate sparse matrix iterator.
///
/// This iterator is created by the [iter_mut()](CooMat::iter_mut()) method on
/// coordinate sparse matrix.
#[derive(Debug)]
pub struct IterMut<'iter, T: 'iter> {
    inner: std::slice::IterMut<'iter, (usize, usize, T)>,
}

impl<'iter, T: 'iter> Iterator for IterMut<'iter, T> {
    type Item = (&'iter usize, &'iter usize, &'iter mut T);

    fn next(&mut self) -> Option<Self::Item> {
        self.inner.next().map(|(r, c, v)| (&*r, &*c, v))
    }
}

impl<T> DoubleEndedIterator for IterMut<'_, T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.inner.next_back().map(|(r, c, v)| (&*r, &*c, v))
    }
}

impl<T> ExactSizeIterator for IterMut<'_, T> {}

/// An iterator that moves out of a matrix.
///
/// # Example
///
/// ```rust
/// use sparse::CooMat;
/// let start = vec![
///     (0, 0, 1.0),
///     (0, 1, 2.0),
///     (1, 0, 3.0),
///     (1, 1, 4.0),
/// ];
/// let matrix = CooMat::with_entries(2, 2, start.clone());
/// let end: Vec<_> = matrix.into_iter().collect();
/// assert_eq!(start, end);
/// ```
#[derive(Debug)]
pub struct IntoIter<T> {
    inner: std::vec::IntoIter<(usize, usize, T)>,
}

impl<T> Iterator for IntoIter<T> {
    type Item = (usize, usize, T);

    fn next(&mut self) -> Option<Self::Item> {
        self.inner.next()
    }
}

impl<T> DoubleEndedIterator for IntoIter<T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.inner.next_back()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn new_annotation() {
        let _: CooMat<f64> = CooMat::new(1, 2);
    }

    #[test]
    fn new_fish() {
        CooMat::<f64>::new(2, 1);
    }

    #[test]
    fn new_shape() {
        let matrix = CooMat::<f64>::new(1, 2);
        assert_eq!(matrix.shape(), (1, 2));
    }

    #[test]
    fn new_length() {
        let matrix = CooMat::<f64>::new(1, 1);
        assert_eq!(matrix.entries.len(), 0)
    }

    #[test]
    fn new_capacity() {
        let matrix = CooMat::<f64>::new(1, 1);
        assert_eq!(matrix.entries.capacity(), 0);
    }

    #[test]
    fn new_null_rows_cols() {
        let matrix = CooMat::<f64>::new(0, 0);
        assert_eq!(matrix.shape(), (1, 1));
    }

    #[test]
    fn with_capacity_annotation() {
        let _: CooMat<f64> = CooMat::with_capacity(1, 2, 3);
    }

    #[test]
    fn with_capacity_fish() {
        CooMat::<f64>::with_capacity(2, 1, 3);
    }

    #[test]
    fn with_capacity_shape() {
        let matrix = CooMat::<f64>::with_capacity(1, 2, 3);
        assert_eq!(matrix.shape(), (1, 2));
    }

    #[test]
    fn with_capacity_length() {
        let matrix = CooMat::<f64>::with_capacity(1, 1, 1);
        assert_eq!(matrix.entries.len(), 0)
    }

    #[test]
    fn with_capacity_capacity() {
        let matrix = CooMat::<f64>::with_capacity(1, 1, 1);
        assert_eq!(matrix.entries.capacity(), 1);
    }

    #[test]
    fn with_capacity_null_rows_cols() {
        let matrix = CooMat::<f64>::with_capacity(0, 0, 1);
        assert_eq!(matrix.shape(), (1, 1));
    }

    #[test]
    fn with_entries() {
        let entries = vec![(0, 0, 1.0)];
        let matrix = CooMat::with_entries(1, 1, entries);
        assert_eq!(matrix.get(0), Some((&0, &0, &1.0)));
        assert_eq!(matrix.get(1), None);
    }

    #[test]
    fn with_entries_order() {
        let entries = vec![(0, 0, 1.0), (0, 1, 2.0), (1, 0, 3.0), (1, 1, 4.0)];
        let matrix = CooMat::with_entries(2, 2, entries);
        let mut iter = matrix.iter();
        assert_eq!(iter.next(), Some((&0, &0, &1.0)));
        assert_eq!(iter.next(), Some((&0, &1, &2.0)));
        assert_eq!(iter.next(), Some((&1, &0, &3.0)));
        assert_eq!(iter.next(), Some((&1, &1, &4.0)));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn with_entries_length() {
        let entries = vec![(0, 0, 1.0)];
        let matrix = CooMat::with_entries(1, 1, entries);
        assert_eq!(matrix.entries.len(), 1)
    }

    #[test]
    fn with_entries_capacity() {
        let entries = vec![(0, 0, 1.0)];
        let matrix = CooMat::with_entries(1, 1, entries);
        assert_eq!(matrix.entries.capacity(), 1)
    }

    #[test]
    fn with_entries_null_rows_cols() {
        let matrix: CooMat<f64> = CooMat::with_entries(0, 0, vec![]);
        assert_eq!(matrix.shape(), (1, 1));
    }

    #[test]
    #[should_panic]
    fn with_entries_invalid_row() {
        let entries = vec![(1, 0, 1.0)];
        CooMat::with_entries(1, 1, entries);
    }

    #[test]
    #[should_panic]
    fn with_entries_invalid_col() {
        let entries = vec![(0, 1, 1.0)];
        CooMat::with_entries(1, 1, entries);
    }

    #[test]
    fn with_triplets() {
        let rowind = vec![0];
        let colind = vec![0];
        let values = vec![1.0];
        let matrix = CooMat::with_triplets(1, 1, rowind, colind, values);
        assert_eq!(matrix.get(0), Some((&0, &0, &1.0)));
        assert_eq!(matrix.get(1), None);
    }

    #[test]
    fn with_triplets_order() {
        let rowind = vec![0, 0, 1, 1];
        let colind = vec![0, 1, 0, 1];
        let values = vec![1.0, 2.0, 3.0, 4.0];
        let matrix = CooMat::with_triplets(2, 2, rowind, colind, values);
        let mut iter = matrix.iter();
        assert_eq!(iter.next(), Some((&0, &0, &1.0)));
        assert_eq!(iter.next(), Some((&0, &1, &2.0)));
        assert_eq!(iter.next(), Some((&1, &0, &3.0)));
        assert_eq!(iter.next(), Some((&1, &1, &4.0)));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn with_triplets_length() {
        let rowind = vec![0];
        let colind = vec![0];
        let values = vec![1.0];
        let matrix = CooMat::with_triplets(1, 1, rowind, colind, values);
        assert_eq!(matrix.entries.len(), 1);
    }

    #[test]
    fn with_triplets_capacity() {
        let rowind = vec![0];
        let colind = vec![0];
        let values = vec![1.0];
        let matrix = CooMat::with_triplets(1, 1, rowind, colind, values);
        assert_eq!(matrix.entries.capacity(), 1);
    }

    #[test]
    #[should_panic]
    fn with_triplets_invalid_row() {
        let rowind = vec![1];
        let colind = vec![0];
        let values = vec![1.0];
        CooMat::with_triplets(1, 1, rowind, colind, values);
    }

    #[test]
    #[should_panic]
    fn with_triplets_invalid_col() {
        let rowind = vec![0];
        let colind = vec![1];
        let values = vec![1.0];
        CooMat::with_triplets(1, 1, rowind, colind, values);
    }

    #[test]
    #[should_panic]
    fn with_triplets_invalid_length() {
        let rowind = vec![0; 2];
        let colind = vec![1; 1];
        let values = vec![1.0; 3];
        CooMat::with_triplets(1, 1, rowind, colind, values);
    }

    #[test]
    fn rows() {
        let matrix: CooMat<f64> = CooMat::new(0, 1);
        assert_eq!(matrix.rows(), 1);
        let matrix: CooMat<f64> = CooMat::new(1, 1);
        assert_eq!(matrix.rows(), 1);
        let matrix: CooMat<f64> = CooMat::new(123, 1);
        assert_eq!(matrix.rows(), 123);
    }

    #[test]
    fn cols() {
        let matrix: CooMat<f64> = CooMat::new(1, 0);
        assert_eq!(matrix.cols(), 1);
        let matrix: CooMat<f64> = CooMat::new(1, 1);
        assert_eq!(matrix.cols(), 1);
        let matrix: CooMat<f64> = CooMat::new(1, 123);
        assert_eq!(matrix.cols(), 123);
    }

    #[test]
    fn shape() {
        let matrix: CooMat<f64> = CooMat::new(0, 0);
        assert_eq!(matrix.shape(), (1, 1));
        let matrix: CooMat<f64> = CooMat::new(1, 1);
        assert_eq!(matrix.shape(), (1, 1));
        let matrix: CooMat<f64> = CooMat::new(123, 123);
        assert_eq!(matrix.shape(), (123, 123));
    }

    #[test]
    fn capacity_new() {
        let matrix: CooMat<f64> = CooMat::new(1, 1);
        assert_eq!(matrix.capacity(), 0);
    }

    #[test]
    fn capacity_with_capacity() {
        let matrix: CooMat<f64> = CooMat::with_capacity(1, 1, 0);
        assert_eq!(matrix.capacity(), 0);
        let matrix: CooMat<f64> = CooMat::with_capacity(1, 1, 1);
        assert_eq!(matrix.capacity(), 1);
        let matrix: CooMat<f64> = CooMat::with_capacity(1, 1, 123);
        assert_eq!(matrix.capacity(), 123);
    }

    #[test]
    fn capacity_with_entries() {
        let entries = vec![];
        let matrix: CooMat<f64> = CooMat::with_entries(1, 1, entries);
        assert_eq!(matrix.capacity(), 0);
        let entries = vec![(0, 0, 1.0)];
        let matrix = CooMat::with_entries(1, 1, entries);
        assert_eq!(matrix.capacity(), 1);
        let entries = vec![(0, 0, 1.0); 123];
        let matrix = CooMat::with_entries(1, 1, entries);
        assert_eq!(matrix.capacity(), 123);
    }

    #[test]
    fn capacity_with_triplets() {
        let rowind = vec![];
        let colind = vec![];
        let values: Vec<f64> = vec![];
        let matrix = CooMat::with_triplets(1, 1, rowind, colind, values);
        assert_eq!(matrix.capacity(), 0);
        let rowind = vec![0];
        let colind = vec![0];
        let values = vec![1.0];
        let matrix = CooMat::with_triplets(1, 1, rowind, colind, values);
        assert_eq!(matrix.capacity(), 1);
        let rowind = vec![0; 123];
        let colind = vec![0; 123];
        let values = vec![1.0; 123];
        let matrix = CooMat::with_triplets(1, 1, rowind, colind, values);
        assert_eq!(matrix.capacity(), 123);
    }

    #[test]
    fn reserve() {
        let mut matrix: CooMat<f64> = CooMat {
            rows: 1,
            cols: 1,
            entries: Vec::new(),
        };
        assert_eq!(matrix.capacity(), 0);
        matrix.reserve(10);
        assert!(matrix.entries.capacity() >= 10);
    }

    #[test]
    fn shrink() {
        let mut matrix: CooMat<f64> = CooMat {
            rows: 1,
            cols: 1,
            entries: Vec::with_capacity(10),
        };
        assert_eq!(matrix.capacity(), 10);
        matrix.shrink();
        assert_eq!(matrix.capacity(), 0);
    }

    #[test]
    fn length_new() {
        let matrix: CooMat<f64> = CooMat::new(1, 1);
        assert_eq!(matrix.len(), 0);
    }

    #[test]
    fn length_with_capacity() {
        let matrix: CooMat<f64> = CooMat::with_capacity(1, 1, 1);
        assert_eq!(matrix.len(), 0);
    }

    #[test]
    fn length_with_entries() {
        let entries = vec![];
        let matrix: CooMat<f64> = CooMat::with_entries(1, 1, entries);
        assert_eq!(matrix.len(), 0);
        let entries = vec![(0, 0, 1.0)];
        let matrix = CooMat::with_entries(1, 1, entries);
        assert_eq!(matrix.len(), 1);
        let entries = vec![(0, 0, 1.0); 123];
        let matrix = CooMat::with_entries(1, 1, entries);
        assert_eq!(matrix.len(), 123);
    }

    #[test]
    fn length_with_triplets() {
        let rowind = vec![];
        let colind = vec![];
        let values: Vec<f64> = vec![];
        let matrix = CooMat::with_triplets(1, 1, rowind, colind, values);
        assert_eq!(matrix.len(), 0);
        let rowind = vec![0];
        let colind = vec![0];
        let values = vec![1.0];
        let matrix = CooMat::with_triplets(1, 1, rowind, colind, values);
        assert_eq!(matrix.len(), 1);
        let rowind = vec![0; 123];
        let colind = vec![0; 123];
        let values = vec![1.0; 123];
        let matrix = CooMat::with_triplets(1, 1, rowind, colind, values);
        assert_eq!(matrix.len(), 123);
    }

    #[test]
    fn is_empty() {
        let mut matrix: CooMat<f64> = CooMat {
            rows: 2,
            cols: 2,
            entries: Vec::new(),
        };
        assert!(matrix.is_empty());
        matrix.push(0, 0, 1.0);
        assert!(!matrix.is_empty());
    }

    #[test]
    fn truncate() {
        let mut matrix: CooMat<f64> = CooMat {
            rows: 2,
            cols: 2,
            entries: vec![(0, 0, 1.0), (0, 1, 2.0), (1, 0, 3.0), (1, 1, 4.0)],
        };
        assert_eq!(matrix.len(), 4);
        matrix.truncate(2);
        assert_eq!(matrix.len(), 2);
    }

    #[test]
    fn truncate_clear() {
        let mut matrix: CooMat<f64> = CooMat {
            rows: 2,
            cols: 2,
            entries: vec![(0, 0, 1.0), (0, 1, 2.0), (1, 0, 3.0), (1, 1, 4.0)],
        };
        assert_eq!(matrix.len(), 4);
        matrix.truncate(0);
        assert!(matrix.is_empty());
    }

    #[test]
    fn truncate_noop() {
        let mut matrix: CooMat<f64> = CooMat {
            rows: 2,
            cols: 2,
            entries: vec![(0, 0, 1.0), (0, 1, 2.0), (1, 0, 3.0), (1, 1, 4.0)],
        };
        assert_eq!(matrix.len(), 4);
        matrix.truncate(4);
        assert_eq!(matrix.len(), 4);
    }

    #[test]
    fn truncate_outofbounds() {
        let mut matrix: CooMat<f64> = CooMat {
            rows: 2,
            cols: 2,
            entries: vec![(0, 0, 1.0), (0, 1, 2.0), (1, 0, 3.0), (1, 1, 4.0)],
        };
        assert_eq!(matrix.len(), 4);
        matrix.truncate(5);
        assert_eq!(matrix.len(), 4);
    }

    #[test]
    fn get() {
        let matrix: CooMat<f64> = CooMat {
            rows: 1,
            cols: 1,
            entries: vec![(0, 0, 1.0)],
        };
        assert_eq!(matrix.get(0), Some((&0, &0, &1.0)));
        assert_eq!(matrix.get(1), None);
    }

    #[test]
    fn get_mut() {
        let mut matrix: CooMat<f64> = CooMat {
            rows: 1,
            cols: 1,
            entries: vec![(0, 0, 1.0)],
        };
        assert_eq!(matrix.get_mut(0), Some((&0, &0, &mut 1.0)));
        assert_eq!(matrix.get_mut(1), None);
    }

    #[test]
    fn swap() {
        let mut matrix: CooMat<f64> = CooMat {
            rows: 1,
            cols: 2,
            entries: vec![(0, 0, 1.0), (0, 1, 2.0)],
        };
        assert_eq!(matrix.entries.get(0), Some(&(0, 0, 1.0)));
        assert_eq!(matrix.entries.get(1), Some(&(0, 1, 2.0)));
        matrix.swap(0, 1);
        assert_eq!(matrix.entries.get(0), Some(&(0, 1, 2.0)));
        assert_eq!(matrix.entries.get(1), Some(&(0, 0, 1.0)));
    }

    #[test]
    #[should_panic]
    fn swap_outofbounds() {
        let mut matrix: CooMat<f64> = CooMat {
            rows: 1,
            cols: 1,
            entries: vec![],
        };
        matrix.swap(0, 1);
    }

    #[test]
    fn insert() {
        let mut matrix: CooMat<f64> = CooMat {
            rows: 2,
            cols: 2,
            entries: vec![(0, 0, 1.0), (1, 1, 4.0)],
        };
        matrix.insert(1, 0, 1, 2.0);
        matrix.insert(2, 1, 0, 3.0);
        assert_eq!(matrix.entries.len(), 4);
        assert_eq!(matrix.entries.get(0), Some(&(0, 0, 1.0)));
        assert_eq!(matrix.entries.get(1), Some(&(0, 1, 2.0)));
        assert_eq!(matrix.entries.get(2), Some(&(1, 0, 3.0)));
        assert_eq!(matrix.entries.get(3), Some(&(1, 1, 4.0)));
    }

    #[test]
    #[should_panic]
    fn insert_outofbounds() {
        let mut matrix: CooMat<f64> = CooMat {
            rows: 1,
            cols: 1,
            entries: vec![],
        };
        matrix.insert(1, 0, 0, 1.0);
    }

    #[test]
    fn remove() {
        let mut matrix: CooMat<f64> = CooMat {
            rows: 1,
            cols: 1,
            entries: vec![(0, 0, 1.0)],
        };
        assert_eq!(matrix.entries.len(), 1);
        assert_eq!(matrix.remove(0), (0, 0, 1.0));
        assert!(matrix.entries.is_empty());
    }

    #[test]
    #[should_panic]
    fn remove_outofbounds() {
        let mut matrix: CooMat<f64> = CooMat {
            rows: 1,
            cols: 1,
            entries: vec![],
        };
        matrix.remove(0);
    }

    #[test]
    fn swap_remove() {
        let mut matrix: CooMat<f64> = CooMat {
            rows: 2,
            cols: 2,
            entries: vec![(0, 0, 1.0), (0, 1, 2.0), (1, 0, 3.0), (1, 1, 4.0)],
        };
        assert_eq!(matrix.entries.len(), 4);
        assert_eq!(matrix.swap_remove(1), (0, 1, 2.0));
        assert_eq!(matrix.entries.len(), 3);
        assert_eq!(matrix.entries.get(0), Some(&(0, 0, 1.0)));
        assert_eq!(matrix.entries.get(1), Some(&(1, 1, 4.0)));
        assert_eq!(matrix.entries.get(2), Some(&(1, 0, 3.0)));
    }

    #[test]
    #[should_panic]
    fn swap_remove_outofbounds() {
        let mut matrix: CooMat<f64> = CooMat {
            rows: 1,
            cols: 1,
            entries: vec![],
        };
        matrix.swap_remove(0);
    }

    #[test]
    fn push() {
        let mut matrix: CooMat<f64> = CooMat {
            rows: 1,
            cols: 1,
            entries: vec![],
        };
        matrix.push(0, 0, 1.0);
        assert_eq!(matrix.entries.len(), 1);
        assert_eq!(matrix.entries.get(0), Some(&(0, 0, 1.0)));
    }

    #[test]
    fn pop() {
        let mut matrix: CooMat<f64> = CooMat {
            rows: 1,
            cols: 1,
            entries: vec![(0, 0, 1.0)],
        };
        assert_eq!(matrix.pop(), Some((0, 0, 1.0)));
        assert!(matrix.entries.is_empty())
    }

    #[test]
    fn retain() {
        let mut matrix: CooMat<f64> = CooMat {
            rows: 2,
            cols: 2,
            entries: vec![(0, 0, 1.0), (0, 1, 2.0), (1, 0, 3.0), (1, 1, 4.0)],
        };
        matrix.retain(|(r, c, v)| *v <= 3.0 && r != c);
        assert_eq!(matrix.entries.len(), 2);
    }

    #[test]
    fn clear() {
        let mut matrix: CooMat<f64> = CooMat {
            rows: 1,
            cols: 1,
            entries: vec![(0, 0, 1.0)],
        };
        matrix.clear();
        assert!(matrix.entries.is_empty())
    }

    #[test]
    fn sort_stable_row_major() {
        let mut matrix: CooMat<f64> = CooMat {
            rows: 2,
            cols: 2,
            entries: vec![(0, 0, 1.0), (1, 1, 4.0), (1, 0, 3.0), (0, 1, 2.0)],
        };
        matrix.sort_stable_row_major();
        assert_eq!(matrix.entries.get(0), Some(&(0, 0, 1.0)));
        assert_eq!(matrix.entries.get(1), Some(&(0, 1, 2.0)));
        assert_eq!(matrix.entries.get(2), Some(&(1, 0, 3.0)));
        assert_eq!(matrix.entries.get(3), Some(&(1, 1, 4.0)));
    }

    #[test]
    fn sort_unstable_row_major() {
        let mut matrix: CooMat<f64> = CooMat {
            rows: 2,
            cols: 2,
            entries: vec![(0, 0, 1.0), (1, 1, 4.0), (1, 0, 3.0), (0, 1, 2.0)],
        };
        matrix.sort_unstable_row_major();
        assert_eq!(matrix.entries.get(0), Some(&(0, 0, 1.0)));
        assert_eq!(matrix.entries.get(1), Some(&(0, 1, 2.0)));
        assert_eq!(matrix.entries.get(2), Some(&(1, 0, 3.0)));
        assert_eq!(matrix.entries.get(3), Some(&(1, 1, 4.0)));
    }

    #[test]
    fn sort_stable_col_major() {
        let mut matrix: CooMat<f64> = CooMat {
            rows: 2,
            cols: 2,
            entries: vec![(0, 0, 1.0), (1, 1, 4.0), (1, 0, 2.0), (0, 1, 3.0)],
        };
        matrix.sort_stable_col_major();
        assert_eq!(matrix.entries.get(0), Some(&(0, 0, 1.0)));
        assert_eq!(matrix.entries.get(1), Some(&(1, 0, 2.0)));
        assert_eq!(matrix.entries.get(2), Some(&(0, 1, 3.0)));
        assert_eq!(matrix.entries.get(3), Some(&(1, 1, 4.0)));
    }

    #[test]
    fn sort_unstable_col_major() {
        let mut matrix: CooMat<f64> = CooMat {
            rows: 2,
            cols: 2,
            entries: vec![(0, 0, 1.0), (1, 1, 4.0), (1, 0, 2.0), (0, 1, 3.0)],
        };
        matrix.sort_unstable_col_major();
        assert_eq!(matrix.entries.get(0), Some(&(0, 0, 1.0)));
        assert_eq!(matrix.entries.get(1), Some(&(1, 0, 2.0)));
        assert_eq!(matrix.entries.get(2), Some(&(0, 1, 3.0)));
        assert_eq!(matrix.entries.get(3), Some(&(1, 1, 4.0)));
    }

    #[test]
    fn reverse() {
        let mut matrix: CooMat<f64> = CooMat {
            rows: 2,
            cols: 2,
            entries: vec![(0, 0, 1.0), (0, 1, 2.0), (1, 0, 3.0), (1, 1, 4.0)],
        };
        matrix.reverse();
        assert_eq!(matrix.entries.get(0), Some(&(1, 1, 4.0)));
        assert_eq!(matrix.entries.get(1), Some(&(1, 0, 3.0)));
        assert_eq!(matrix.entries.get(2), Some(&(0, 1, 2.0)));
        assert_eq!(matrix.entries.get(3), Some(&(0, 0, 1.0)));
    }

    #[test]
    fn iter() {
        let matrix: CooMat<f64> = CooMat {
            rows: 2,
            cols: 2,
            entries: vec![(0, 0, 1.0), (0, 1, 2.0), (1, 0, 3.0), (1, 1, 4.0)],
        };
        let mut iter = matrix.iter();
        assert_eq!(iter.next(), Some((&0, &0, &1.0)));
        assert_eq!(iter.next(), Some((&0, &1, &2.0)));
        assert_eq!(iter.next(), Some((&1, &0, &3.0)));
        assert_eq!(iter.next(), Some((&1, &1, &4.0)));
        assert!(iter.next().is_none());
    }

    #[test]
    fn iter_mut() {
        let mut matrix: CooMat<f64> = CooMat {
            rows: 2,
            cols: 2,
            entries: vec![(0, 0, 1.0), (0, 1, 2.0), (1, 0, 3.0), (1, 1, 4.0)],
        };
        let mut iter = matrix.iter_mut();
        assert_eq!(iter.next(), Some((&0, &0, &mut 1.0)));
        assert_eq!(iter.next(), Some((&0, &1, &mut 2.0)));
        assert_eq!(iter.next(), Some((&1, &0, &mut 3.0)));
        assert_eq!(iter.next(), Some((&1, &1, &mut 4.0)));
        assert!(iter.next().is_none());
    }

    #[test]
    fn extend() {
        let mut matrix: CooMat<f64> = CooMat {
            rows: 2,
            cols: 2,
            entries: vec![],
        };
        assert!(matrix.entries.is_empty());
        matrix.extend(vec![(0, 0, 1.0), (0, 1, 2.0), (1, 0, 3.0), (1, 1, 4.0)]);
        assert_eq!(matrix.entries.len(), 4);
        assert_eq!(matrix.entries.get(0), Some(&(0, 0, 1.0)));
        assert_eq!(matrix.entries.get(1), Some(&(0, 1, 2.0)));
        assert_eq!(matrix.entries.get(2), Some(&(1, 0, 3.0)));
        assert_eq!(matrix.entries.get(3), Some(&(1, 1, 4.0)));
    }

    #[test]
    fn from_iter() {
        let entries = vec![(0, 0, 1.0), (0, 1, 2.0), (1, 0, 3.0), (1, 1, 4.0)];
        let matrix = CooMat::from_iter(entries);
        assert_eq!(matrix.entries.len(), 4);
        assert_eq!(matrix.entries.get(0), Some(&(0, 0, 1.0)));
        assert_eq!(matrix.entries.get(1), Some(&(0, 1, 2.0)));
        assert_eq!(matrix.entries.get(2), Some(&(1, 0, 3.0)));
        assert_eq!(matrix.entries.get(3), Some(&(1, 1, 4.0)));
    }

    #[test]
    fn into_iter() {
        let matrix: CooMat<f64> = CooMat {
            rows: 2,
            cols: 2,
            entries: vec![(0, 0, 1.0), (0, 1, 2.0), (1, 0, 3.0), (1, 1, 4.0)],
        };
        let mut iter = matrix.into_iter();
        assert_eq!(iter.next(), Some((0, 0, 1.0)));
        assert_eq!(iter.next(), Some((0, 1, 2.0)));
        assert_eq!(iter.next(), Some((1, 0, 3.0)));
        assert_eq!(iter.next(), Some((1, 1, 4.0)));
        assert!(iter.next().is_none());
    }

    #[test]
    fn collect() {
        let matrix: CooMat<_> = vec![(0, 0, 1.0), (0, 1, 2.0), (1, 0, 3.0), (1, 1, 4.0)]
            .into_iter()
            .collect();
        assert_eq!(matrix.entries.len(), 4);
        assert_eq!(matrix.entries.get(0), Some(&(0, 0, 1.0)));
        assert_eq!(matrix.entries.get(1), Some(&(0, 1, 2.0)));
        assert_eq!(matrix.entries.get(2), Some(&(1, 0, 3.0)));
        assert_eq!(matrix.entries.get(3), Some(&(1, 1, 4.0)));
    }
}