containers.tngl.sh
A Vec of Bits
blackson.tngl.sh
1//! Submatrix of bits.
2
3use core::cmp;
4use core::fmt;
5use core::mem;
6use core::ops::RangeBounds;
7use core::ops::{Index, IndexMut};
8use core::slice;
9
10use crate::local_prelude::*;
11use crate::util::{div_rem, round_up_to_next};
12
13/// Immutable access to a range of matrix's rows.
14pub struct BitSubMatrix<'a> {
15 pub(crate) slice: &'a [Block],
16 pub(crate) row_bits: usize,
17}
18
19/// Mutable access to a range of matrix's rows.
20pub struct BitSubMatrixMut<'a> {
21 pub(crate) slice: &'a mut [Block],
22 pub(crate) row_bits: usize,
23}
24
25impl<'a> BitSubMatrix<'a> {
26 /// Returns a new BitSubMatrix.
27 pub fn new(slice: &[Block], row_bits: usize) -> BitSubMatrix<'_> {
28 BitSubMatrix { slice, row_bits }
29 }
30
31 /// Forms a BitSubMatrix from a pointer and dimensions.
32 ///
33 /// # Safety
34 ///
35 /// Can construct an ill-formed value, thus the function is marked as
36 /// unsafe.
37 #[inline]
38 pub unsafe fn from_raw_parts(ptr: *const Block, rows: usize, row_bits: usize) -> Self {
39 BitSubMatrix {
40 slice: slice::from_raw_parts(ptr, round_up_to_next(row_bits, BITS) / BITS * rows),
41 row_bits,
42 }
43 }
44
45 /// Iterates over the matrix's rows in the form of immutable slices.
46 pub fn iter(&self) -> impl Iterator<Item = &BitSlice> {
47 fn f(arg: &[Block]) -> &BitSlice {
48 unsafe { mem::transmute(arg) }
49 }
50 let row_size = round_up_to_next(self.row_bits, BITS) / BITS;
51 self.slice.chunks(row_size).map(f)
52 }
53}
54
55impl<'a> BitSubMatrixMut<'a> {
56 /// Returns a new `BitSubMatrixMut`.
57 pub fn new(slice: &mut [Block], row_bits: usize) -> BitSubMatrixMut<'_> {
58 BitSubMatrixMut { slice, row_bits }
59 }
60
61 /// Forms a `BitSubMatrix` from a pointer and dimensions.
62 ///
63 /// # Safety
64 ///
65 /// Can construct an ill-formed value, thus the function is unsafe.
66 #[inline]
67 pub unsafe fn from_raw_parts(ptr: *mut Block, rows: usize, row_bits: usize) -> Self {
68 BitSubMatrixMut {
69 slice: slice::from_raw_parts_mut(ptr, round_up_to_next(row_bits, BITS) / BITS * rows),
70 row_bits,
71 }
72 }
73
74 /// Returns the number of rows.
75 #[inline]
76 fn num_rows(&self) -> usize {
77 let row_size = round_up_to_next(self.row_bits, BITS) / BITS;
78 self.slice.len().checked_div(row_size).unwrap_or(0)
79 }
80
81 /// Returns the number of columns.
82 #[inline]
83 pub fn num_cols(&self) -> usize {
84 self.row_bits
85 }
86
87 /// Sets the value of a bit. The first argument is the row number.
88 ///
89 /// # Panics
90 ///
91 /// Panics if `(row, col)` is out of bounds.
92 #[inline]
93 pub fn set(&mut self, row: usize, col: usize, enabled: bool) {
94 let row_size_in_bits = round_up_to_next(self.row_bits, BITS);
95 let bit = row * row_size_in_bits + col;
96 let (block, i) = div_rem(bit, BITS);
97 assert!(block < self.slice.len() && col < self.row_bits);
98 unsafe {
99 let elt = self.slice.get_unchecked_mut(block);
100 if enabled {
101 *elt |= 1 << i;
102 } else {
103 *elt &= !(1 << i);
104 }
105 }
106 }
107
108 /// Returns a slice of the matrix's rows.
109 pub fn sub_matrix<R: RangeBounds<usize>>(&self, range: R) -> BitSubMatrix<'_> {
110 let row_size = round_up_to_next(self.row_bits, BITS) / BITS;
111 BitSubMatrix {
112 slice: &self.slice[(
113 range.start_bound().map(|&s| s * row_size),
114 range.end_bound().map(|&e| e * row_size),
115 )],
116 row_bits: self.row_bits,
117 }
118 }
119
120 /// Given a row's index, returns a slice of all rows above that row, a reference to said row,
121 /// and a slice of all rows below.
122 ///
123 /// Functionally equivalent to `(self.sub_matrix(0..row), &self[row],
124 /// self.sub_matrix(row..self.num_rows()))`.
125 #[inline]
126 pub fn split_at(&self, row: usize) -> (BitSubMatrix<'_>, BitSubMatrix<'_>) {
127 (
128 self.sub_matrix(0..row),
129 self.sub_matrix(row..self.num_rows()),
130 )
131 }
132
133 /// Given a row's index, returns a slice of all rows above that row, a reference to said row,
134 /// and a slice of all rows below.
135 #[inline]
136 pub fn split_at_mut(&mut self, row: usize) -> (BitSubMatrixMut<'_>, BitSubMatrixMut<'_>) {
137 let row_size = round_up_to_next(self.row_bits, BITS) / BITS;
138 let (first, second) = self.slice.split_at_mut(row * row_size);
139 (
140 BitSubMatrixMut::new(first, self.row_bits),
141 BitSubMatrixMut::new(second, self.row_bits),
142 )
143 }
144
145 /// Computes the transitive closure of the binary relation
146 /// represented by this square bit matrix.
147 ///
148 /// Modifies this matrix in place using Warshall's algorithm.
149 ///
150 /// After this operation, the matrix will describe a transitive
151 /// relation. This means that, for any indices `a`, `b`, `c`,
152 /// if `M[(a, b)]` and `M[(b, c)]`, then `M[(a, c)]`.
153 ///
154 /// # Complexity
155 ///
156 /// The time complexity is **O(n^3)**, where `n` is the number
157 /// of columns and rows.
158 ///
159 /// # Panics
160 ///
161 /// The matrix must be square for this operation to succeed.
162 pub fn transitive_closure(&mut self) {
163 assert!(self.is_square());
164 for pos in 0..self.row_bits {
165 let (mut rows0, mut rows1a) = self.split_at_mut(pos);
166 let (mut row, mut rows1b) = rows1a.split_at_mut(1);
167 for mut dst_row in rows0.iter_mut().chain(rows1b.iter_mut()) {
168 if dst_row[pos] {
169 dst_row |= &mut row[0];
170 }
171 }
172 }
173 }
174
175 /// Determines whether the number of rows equals the number of columns.
176 ///
177 /// This means the matrix is square.
178 fn is_square(&self) -> bool {
179 self.num_rows() == self.row_bits
180 }
181
182 /// Computes the reflexive closure of the binary relation represented by
183 /// this bit matrix. The matrix can be rectangular.
184 ///
185 /// The reflexive closure means that for every `x`` that will be within bounds,
186 /// `M[(x, x)]` is true.
187 ///
188 /// In other words, modifies this matrix in-place by making all
189 /// bits on the diagonal set.
190 pub fn reflexive_closure(&mut self) {
191 for i in 0..cmp::min(self.row_bits, self.num_rows()) {
192 self.set(i, i, true);
193 }
194 }
195
196 /// Iterates over the matrix's rows in the form of mutable slices.
197 pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut BitSlice> {
198 fn f(arg: &mut [Block]) -> &mut BitSlice {
199 unsafe { mem::transmute(arg) }
200 }
201 let row_size = round_up_to_next(self.row_bits, BITS) / BITS;
202 self.slice.chunks_mut(row_size).map(f)
203 }
204}
205
206/// Returns the matrix's row in the form of a mutable slice.
207impl<'a> Index<usize> for BitSubMatrixMut<'a> {
208 type Output = BitSlice;
209
210 #[inline]
211 fn index(&self, row: usize) -> &BitSlice {
212 let row_size = round_up_to_next(self.row_bits, BITS) / BITS;
213 unsafe { mem::transmute(&self.slice[row * row_size..(row + 1) * row_size]) }
214 }
215}
216
217/// Returns the matrix's row in the form of a mutable slice.
218impl<'a> IndexMut<usize> for BitSubMatrixMut<'a> {
219 #[inline]
220 fn index_mut(&mut self, row: usize) -> &mut BitSlice {
221 let row_size = round_up_to_next(self.row_bits, BITS) / BITS;
222 unsafe { mem::transmute(&mut self.slice[row * row_size..(row + 1) * row_size]) }
223 }
224}
225
226/// Returns the matrix's row in the form of a mutable slice.
227impl<'a> Index<usize> for BitSubMatrix<'a> {
228 type Output = BitSlice;
229
230 #[inline]
231 fn index(&self, row: usize) -> &BitSlice {
232 let row_size = round_up_to_next(self.row_bits, BITS) / BITS;
233 unsafe { mem::transmute(&self.slice[row * row_size..(row + 1) * row_size]) }
234 }
235}
236
237impl<'a> fmt::Debug for BitSubMatrix<'a> {
238 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
239 for row in self.iter() {
240 for bit in row.iter_bits(self.row_bits) {
241 write!(fmt, "{}", if bit { 1 } else { 0 })?;
242 }
243 writeln!(fmt)?;
244 }
245 Ok(())
246 }
247}