use std::{
fmt,
ops::{Index, IndexMut},
};
// Layout of our data in this structure.
// The values will be stored from "left to right", from "up" to "down".
//
// j --->
// 0 1 2 3
// i 0 x x x
// | 1 x x
// v 2 x
// 3
/// Square triangular matrix.
#[derive(Clone, Default)]
pub struct Triangular<T>
where
T: Copy + Sized,
{
/// Width and height of the matrix
pub(crate) dimension: usize,
/// Actual data, see comment above for how indices are stored.
pub(crate) data: Vec<T>,
}
impl<T> Triangular<T>
where
T: Copy + Sized,
{
/// Creates a triangular with the given dimension.
pub fn with_dimension(dimension: usize, default: T) -> Self {
let len = match dimension {
0 => 0,
_ => (dimension * (dimension - 1)) / 2,
};
Self {
dimension,
data: vec![default; len],
}
}
/// Computes the offset for a given i,j position.
#[inline]
pub fn offset(&self, i: usize, j: usize) -> usize {
debug_assert!(i < j);
debug_assert!(i < self.dimension);
debug_assert!(j < self.dimension);
// j --->
// 0 1 2 3 4 // n = 5
// i 0 x x x x
// | 1 x x x
// v 2 x x
// 3 x
//
// 0,0 -> invalid
// 0,1 -> 0
// 0,3 -> 2
// 2,3 -> 5
// base i:2 == (n-1) + (n-2) + ... + (n - i)
// == i*n + (-1 + -2 + ... + -i)
// == i*n - 1/2i (i+1)
// i*2
// for i = 2 ... 1 2 == 3
// for i = 3 ... 1 2 3 == 6
// for i = 4 ... 1 2 3 4 == 10
// for i = 5 ... 1 2 3 4 5 == 15
// x = (i * i + i) / 2
// i:1, j:4
// (n - 1)
// The vast majority of calculations we do will be i == 0. Fast pass.
if i == 0 {
return j - 1;
}
// We're doing (i*i+i)/2 instead of i/2*(i+1) to prevent math errors.
// Pro tip: don't write a function like this in the middle of the night ...
let last_index = (i * self.dimension) - (i * i + i) / 2;
last_index + (j - i - 1)
}
}
impl<'a, T> From<&'a Vec<T>> for Triangular<T>
where
T: Copy + Sized,
{
#[allow(clippy::cast_sign_loss)]
fn from(vec: &Vec<T>) -> Self {
// len 1: dim: 2
// len 3: dim: 3
// len 6: dim: 4
// len 10: dim: 5
// dim = round_down(sqrt(2 * len)) + 1
//
let dimension = (((2 * vec.len()) as f32).sqrt() as usize) + 1;
Self { dimension, data: vec.clone() }
}
}
impl<T> Index<(usize, usize)> for Triangular<T>
where
T: Copy + Sized,
{
type Output = T;
fn index(&self, index: (usize, usize)) -> &T {
let offset = self.offset(index.0, index.1);
&self.data[offset]
}
}
impl<T> Index<usize> for Triangular<T>
where
T: Copy + Sized,
{
type Output = T;
fn index(&self, index: usize) -> &T { &self.data[index] }
}
impl<T> IndexMut<(usize, usize)> for Triangular<T>
where
T: Copy + Sized,
{
fn index_mut(&mut self, index: (usize, usize)) -> &mut T {
let offset = self.offset(index.0, index.1);
&mut self.data[offset]
}
}
impl<T> fmt::Debug for Triangular<T>
where
T: Copy + Sized,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { write!(f, "(Triangular {}, [data])", self.dimension) }
}
#[cfg(test)]
mod tests {
use super::Triangular;
#[test]
fn test_offset() {
let matrix = Triangular::with_dimension(4, 0);
assert_eq!(matrix.offset(0, 1), 0);
assert_eq!(matrix.offset(0, 3), 2);
assert_eq!(matrix.offset(2, 3), 5);
let matrix = Triangular::with_dimension(5, 0);
assert_eq!(matrix.offset(0, 1), 0);
assert_eq!(matrix.offset(1, 4), 6);
assert_eq!(matrix.offset(2, 3), 7);
assert_eq!(matrix.offset(3, 4), 9);
}
#[test]
fn test_index() {
let mut matrix = Triangular::with_dimension(5, 0);
matrix[(2, 3)] = 667;
assert_eq!(matrix.data[7], 667);
}
}