alg_ds/ds/
matrix.rs

1use std::ops::{Index, IndexMut};
2use std::slice::{Iter, IterMut};
3use std::{alloc, fmt, mem, ops, ptr};
4
5/// Rectangular table of elements (two-dimensional array).
6///
7pub struct Matrix<'a, T>
8where
9    T: Default + Clone,
10{
11    cols: usize,
12    buffer: &'a mut [T],
13}
14
15impl<'a, T> Matrix<'a, T>
16where
17    T: Default + Clone,
18{
19    /// Creates new Matrix and fills it with default values.
20    ///
21    /// `rows` - rows number.
22    /// `cols` - columns number.
23    /// Panic, if memory allocation is not succesfully.
24    pub fn new(rows: usize, cols: usize) -> Self {
25        Self {
26            cols,
27            buffer: Self::alloc(rows, cols),
28        }
29    }
30
31    /// Fills matrix with a default values.
32    ///
33    pub fn clear(&mut self) {
34        Self::fill_with(self.buffer, T::default());
35    }
36
37    /// Fills matrix with a `value`.
38    ///
39    pub fn fill(&mut self, value: T) {
40        Self::fill_with(self.buffer, value);
41    }
42
43    /// Returns rows number.
44    ///
45    pub fn rows(&self) -> usize {
46        self.buffer.len() / self.cols
47    }
48
49    /// Returns columns number.
50    ///
51    pub fn cols(&self) -> usize {
52        self.cols
53    }
54
55    /// Returns number of elements in matrix.
56    ///
57    pub fn elements_number(&self) -> usize {
58        self.buffer.len()
59    }
60
61    /// Returns the n-th element of the table in line traversal order.
62    ///
63    pub fn nth(&self, index: usize) -> &T {
64        &self.buffer[index]
65    }
66
67    /// Returns value at [row][col] position.
68    ///
69    /// There are bounds checking.
70    /// If index out of range, then panic.
71    pub fn get(&self, row: usize, col: usize) -> &T {
72        &self.buffer[self.linear_index(row, col)]
73    }
74
75    /// Sets the `value` of element at [row][col] position.
76    ///
77    /// There are bounds checking.
78    /// If index out of range, then panic.
79    pub fn set(&mut self, row: usize, col: usize, value: T) {
80        self.buffer[self.linear_index(row, col)] = value;
81    }
82
83    /// Iterator over matrix in line traversal order.
84    ///
85    pub fn iter(&self) -> Iter<'_, T> {
86        self.buffer.iter()
87    }
88
89    /// Mutable iterator over matrix in line traversal order.
90    ///
91    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
92        self.buffer.iter_mut()
93    }
94
95    /// Memory allocation for data buffer.
96    ///
97    fn alloc(rows: usize, cols: usize) -> &'a mut [T] {
98        unsafe {
99            let buf = alloc::alloc(layout::<T>(rows * cols).unwrap()) as *mut T;
100            let slice = std::slice::from_raw_parts_mut(buf, rows * cols);
101            Self::fill_with(slice, T::default());
102            slice
103        }
104    }
105
106    /// Fills data buffer with a `value`.
107    ///
108    fn fill_with(buf: &mut [T], value: T) {
109        let mut ptr = buf.as_mut_ptr();
110        for _ in 0..buf.len() {
111            unsafe {
112                ptr::write(ptr, value.clone());
113                ptr = ptr.offset(1);
114            }
115        }
116    }
117
118    fn linear_index(&self, row: usize, col: usize) -> usize {
119        if row >= self.rows() || col >= self.cols {
120            panic!("index out of bounds");
121        }
122        row * self.cols + col
123    }
124
125    fn is_same_size(&self, other: &Self) -> bool {
126        self.cols == other.cols && self.buffer.len() == other.buffer.len()
127    }
128}
129
130impl<'a, T> Drop for Matrix<'a, T>
131where
132    T: Default + Clone,
133{
134    fn drop(&mut self) {
135        unsafe {
136            alloc::dealloc(
137                self.buffer.as_mut_ptr() as *mut u8,
138                layout::<T>(self.buffer.len()).unwrap(),
139            );
140        }
141    }
142}
143
144fn layout<T>(size: usize) -> Result<alloc::Layout, alloc::LayoutError> {
145    alloc::Layout::from_size_align(size * mem::size_of::<T>(), mem::align_of::<T>())
146}
147
148impl<'a, T> PartialEq for Matrix<'a, T>
149where
150    T: Default + Clone + PartialEq,
151{
152    fn eq(&self, other: &Self) -> bool {
153        if self.cols == other.cols && self.buffer == other.buffer {
154            true
155        } else {
156            false
157        }
158    }
159}
160
161impl<'a, T> Index<usize> for Matrix<'a, T>
162where
163    T: Default + Clone,
164{
165    type Output = [T];
166
167    fn index(&self, row: usize) -> &Self::Output {
168        if row >= self.rows() {
169            panic!("index out of bounds")
170        }
171        &self.buffer[row * self.cols..(row + 1) * self.cols]
172    }
173}
174
175impl<'a, T> IndexMut<usize> for Matrix<'a, T>
176where
177    T: Default + Clone,
178{
179    fn index_mut(&mut self, row: usize) -> &mut Self::Output {
180        if row >= self.rows() {
181            panic!("index out of bounds")
182        }
183        &mut self.buffer[row * self.cols..(row + 1) * self.cols]
184    }
185}
186
187impl<'a, T> Clone for Matrix<'a, T>
188where
189    T: Default + Clone,
190{
191    fn clone(&self) -> Self {
192        let new_buf = Self::alloc(self.rows(), self.cols());
193        for idx in 0..self.buffer.len() {
194            new_buf[idx] = self.buffer[idx].clone();
195        }
196        Matrix {
197            cols: self.cols,
198            buffer: new_buf,
199        }
200    }
201}
202
203impl<'a, T> fmt::Debug for Matrix<'a, T>
204where
205    T: Default + Clone + fmt::Display,
206{
207    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
208        write!(f, "{{")?;
209        for i in 0..self.rows() {
210            if i > 0 {
211                write!(f, " ")?;
212            }
213            write!(f, "{{")?;
214            for j in 0..self.cols() {
215                write!(f, "{}", self[i][j])?;
216                if j + 1 < self.cols() {
217                    write!(f, ",")?;
218                }
219            }
220            write!(f, "}}")?;
221            if i + 1 < self.rows() {
222                writeln!(f)?;
223            }
224        }
225        write!(f, "}}")
226    }
227}
228
229impl<'a, T> ops::Add for Matrix<'a, T>
230where
231    T: Default + Clone + ops::Add<Output = T>,
232{
233    type Output = Self;
234
235    /// Performs addition of two matrices.
236    /// Panics, if the sizes of the operands do not match.
237    fn add(self, other: Self) -> Self {
238        if !self.is_same_size(&other) {
239            panic!("operands vary in size");
240        }
241        let result = Self::new(self.rows(), self.cols());
242        for idx in 0..self.elements_number() {
243            result.buffer[idx] = self.buffer[idx].clone() + other.buffer[idx].clone();
244        }
245        result
246    }
247}
248
249impl<'a, T> ops::Sub for Matrix<'a, T>
250where
251    T: Default + Clone + ops::Sub<Output = T>,
252{
253    type Output = Self;
254
255    /// Performs subtraction of two matrices.
256    /// Panics, if the sizes of the operands do not match.
257    fn sub(self, other: Self) -> Self {
258        if !self.is_same_size(&other) {
259            panic!("operands vary in size");
260        }
261        let result = Self::new(self.rows(), self.cols());
262        for idx in 0..self.elements_number() {
263            result.buffer[idx] = self.buffer[idx].clone() - other.buffer[idx].clone();
264        }
265        result
266    }
267}
268
269impl<'a, T> ops::Mul<T> for Matrix<'a, T>
270where
271    T: Default + Clone + ops::Mul<Output = T>,
272{
273    type Output = Self;
274
275    /// Performs multiplication the matrix by a number.
276    fn mul(self, value: T) -> Self {
277        let result = Self::new(self.rows(), self.cols());
278        for idx in 0..self.elements_number() {
279            result.buffer[idx] = self.buffer[idx].clone() * value.clone();
280        }
281        result
282    }
283}
284
285impl<'a, T> ops::Deref for Matrix<'a, T>
286where
287    T: Default + Clone,
288{
289    type Target = [T];
290
291    fn deref(&self) -> &Self::Target {
292        self.buffer
293    }
294}
295
296impl<'a, T> ops::DerefMut for Matrix<'a, T>
297where
298    T: Default + Clone,
299{
300    fn deref_mut(&mut self) -> &mut Self::Target {
301        self.buffer
302    }
303}
304
305#[cfg(test)]
306mod tests {
307    use super::Matrix;
308    use std::fmt::Debug;
309
310    #[test]
311    fn new_ok() {
312        let m = Matrix::<i32>::new(100, 100);
313        assert_eq_all::<i32>(&m, 0);
314    }
315
316    #[test]
317    fn fill_ok() {
318        let mut m = Matrix::<i32>::new(100, 100);
319        m.fill(1);
320        assert_eq_all::<i32>(&m, 1);
321    }
322
323    #[test]
324    fn clear_ok() {
325        let mut m = Matrix::<i32>::new(100, 100);
326        m.fill(1);
327        assert_eq_all::<i32>(&m, 1);
328        m.clear();
329        assert_eq_all::<i32>(&m, 0);
330    }
331
332    #[test]
333    fn get_set_ok() {
334        let mut m = Matrix::<i32>::new(2, 3);
335        m.set(1, 1, 777);
336        assert_eq!(m.get(1, 1), &777);
337    }
338
339    #[test]
340    fn index_ok() {
341        let mut m = Matrix::<i32>::new(2, 3);
342        m.set(1, 1, 777);
343        assert_eq!(m[0][2], 0);
344        assert_eq!(m[1][1], 777);
345    }
346
347    #[test]
348    fn index_mut_ok() {
349        let mut m = Matrix::<i32>::new(2, 3);
350        m[1][1] = 777;
351        assert_eq!(m.get(1, 1), &777);
352        m[0][0] = m[1][1] - 111;
353        assert_eq!(m.get(0, 0), &666);
354    }
355
356    #[test]
357    fn clone_ok() {
358        // numbers
359        let mut a = Matrix::<i32>::new(2, 3);
360        a.fill(100);
361        let b = a.clone();
362        a.fill(200);
363        assert_eq_all(&b, 100);
364        assert_eq_all(&a, 200);
365
366        // Strings
367        let mut s1 = Matrix::<String>::new(2, 3);
368        s1.fill(String::from("first"));
369        let s2 = s1.clone();
370        s1.fill(String::from("second"));
371        assert_eq_all(&s2, String::from("first"));
372        assert_eq_all(&s1, String::from("second"));
373    }
374
375    #[test]
376    fn debug_ok() {
377        let mut a = Matrix::<i32>::new(3, 3);
378        a.fill(2);
379        println!("{:?}", a);
380    }
381
382    #[test]
383    fn iter_ok() {
384        let mut m = Matrix::<i32>::new(2, 3);
385        m.fill(7);
386        let mut count = 0;
387        for e in m.iter() {
388            assert_eq!(e, &7);
389            count += 1;
390        }
391        assert_eq!(count, m.elements_number());
392    }
393
394    #[test]
395    fn iter_mut_ok() {
396        let mut m1 = Matrix::<i32>::new(2, 3);
397        for e in m1.iter_mut() {
398            *e = 7;
399        }
400        let mut m2 = Matrix::<i32>::new(2, 3);
401        m2.fill(7);
402        assert_eq!(m1, m2);
403    }
404
405    #[test]
406    fn add_ok() {
407        let mut a = Matrix::<i32>::new(2, 3);
408        a.fill(7);
409        let mut b = Matrix::<i32>::new(2, 3);
410        b.fill(5);
411        let c = a + b;
412        assert_eq_all(&c, 12);
413    }
414
415    #[test]
416    fn sub_ok() {
417        let mut a = Matrix::<i32>::new(2, 3);
418        a.fill(7);
419        let mut b = Matrix::<i32>::new(2, 3);
420        b.fill(5);
421        let c = a - b;
422        assert_eq_all(&c, 2);
423    }
424
425    #[test]
426    fn mul_ok() {
427        let mut a = Matrix::<i32>::new(2, 3);
428        a.fill(7);
429        let b = a * 10;
430        assert_eq_all(&b, 70);
431    }
432
433    #[test]
434    fn deref_ok() {
435        let mut m = Matrix::<i32>::new(2, 3);
436        m[0][0] = 7;
437        m[0][1] = 12;
438        m[0][2] = 17;
439        m[1][0] = 25;
440        m[1][1] = 31;
441        m[1][2] = 100;
442        assert_eq!(m.binary_search(&31), Ok(4));
443    }
444
445    #[test]
446    fn deref_mut_ok() {
447        let mut m = Matrix::<i32>::new(2, 3);
448        m.fill(7);
449        if let Some(first) = m.first_mut() {
450            *first = 70;
451        }
452        assert_eq!(m[0][0], 70);
453    }
454
455    fn assert_eq_all<T: Default + Clone + PartialEq + Debug>(m: &Matrix<T>, value: T) {
456        for i in 0..m.rows() {
457            for j in 0..m.cols() {
458                assert_eq!(m.get(i, j), &value);
459            }
460        }
461    }
462}
alg_ds/ds/matrix.rs

alg_ds/ds/
matrix.rs
