half_matrix/
lib.rs

1//! Half matrix storage, Row major
2//! ```ignore
3//!  ABCD
4//! A-
5//! B--
6//! C---
7//! D----
8//! ```
9//! 
10//! In memory representation:
11//! ```ignore
12//! -|--|---|----
13//! ```
14//! 
15//! Indexing starts at 0.
16//! ```ignore
17//! ABCD
18//! 0123
19//! ```
20//!
21//! Row Major means that the first parameter of the methods is the Y axis in the matrix, and the second is the X axis.
22//!
23//! As shown by the matrix, the row value is required to be bigger or equal to the column value.
24//! 
25//! ### Example
26//! Parameters: (3, 0) = (D, A)
27//!
28//! ```ignore
29//!  ABCD
30//! A-
31//! B--
32//! C---
33//! DX---
34//! ```
35//! 
36
37use hibitset::BitSet;
38
39/// A matrix where only half of it is stored. See the lib documentation for more details.
40#[derive(Debug, Clone)]
41pub struct HalfMatrix {
42    size: u32,
43    index_size: u32,
44    collision_matrix: BitSet,
45}
46
47impl HalfMatrix {
48    /// Creates a new half matrix of the given size.
49    /// This value represents the maximum number of indices you can have for both sides.
50    /// ABCD size = 4.
51    pub fn new(size: u32) -> Self {
52        if size > 5792 {
53            panic!("Size of HalfMatrix too big! Maximum size is 5792 and requested size is {}.", size);
54        }
55        let index_size = (size * (size + 1)) / 2;
56        HalfMatrix {
57            size,
58            index_size,
59            collision_matrix: BitSet::with_capacity(index_size),
60        }
61    }
62
63    /// Returns the size of one side of the matrix.
64    pub fn size(&self) -> u32 {
65        self.size
66    }
67
68    /// Enables the boolean for the position (row, column).
69    pub fn enable(&mut self, row: u32, column: u32) {
70        self.collision_matrix.add(self.index_of(row, column));
71    }
72
73    /// Disables the boolean for the position (row, column).
74    pub fn disable(&mut self, row: u32, column: u32) {
75        self.collision_matrix.remove(self.index_of(row, column));
76    }
77
78    /// Returns the boolean for the position (row, column).
79    pub fn contains(&self, row: u32, column: u32) -> bool {
80        self.collision_matrix.contains(self.index_of(row, column))
81    }
82
83    /// Gives the internal memory index of the bitset for the given (row, column) values.
84    /// The internal indexing starts at 0. This means that index_of(0,0) = 0. That is the position of (A, A).
85    /// Row is required to be bigger or equal to column.
86    pub(crate) fn index_of(&self, row: u32, column: u32) -> u32 {
87        // If you entered the indices in the wrong orther, I'll fix them for you. ;)
88        let (a, b) = if row >= column {
89            (row, column)
90        } else {
91            (column, row)
92        };
93
94        let row_sum = (a * (a + 1)) / 2;
95        let idx = row_sum + b;
96
97        assert!(idx < self.index_size);
98
99        idx
100    }
101}
102
103#[cfg(test)]
104mod tests {
105    use crate::*;
106
107    #[test]
108    fn index_calculation() {
109        // 4x4
110        // C,C (2,2)
111        // Expected: 5
112        let m = HalfMatrix::new(4);
113        assert_eq!(m.index_of(2,2), 5);
114    }
115
116    #[should_panic]
117    #[test]
118    fn index_of_fail() {
119        // 4x4
120        // C,C (2,2)
121        // Expected: 5
122        let m = HalfMatrix::new(1);
123        m.index_of(0, 1);
124    }
125
126    #[test]
127    fn index_calculation2() {
128        // 4x4
129        // D,C (3,2)
130        // Expected: 9
131        let m = HalfMatrix::new(4);
132        assert_eq!(m.index_of(3,2), 8);
133    }
134
135    #[test]
136    fn max_size_okay() {
137        let size = 5792;
138        HalfMatrix::new(size);
139    }
140
141    #[test]
142    #[should_panic]
143    fn max_size_too_big() {
144        let size = 5793;
145        HalfMatrix::new(size);
146    }
147
148    #[test]
149    fn enable() {
150        // 3x3
151        //
152        //   012
153        // 
154        // 2 oxo
155        // 1 xx
156        // 0 o
157
158        let mut m = HalfMatrix::new(3);
159        m.enable(2, 0);
160        m.enable(2, 2);
161        m.enable(0, 0);
162
163        assert!(m.contains(2,0));
164        assert!(m.contains(2,2));
165        assert!(m.contains(0,0));
166
167        assert!(!m.contains(1,0));
168        assert!(!m.contains(1,1));
169        assert!(!m.contains(2,1));
170    }
171
172    #[test]
173    fn out_of_range_swap() {
174        let m = HalfMatrix::new(3);
175        m.contains(0,1);
176    }
177}
half_matrix/lib.rs

half_matrix/
lib.rs
