GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

mirrored from https://github.com/microsoft/qdkAvailable

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
fc18cc36fceb28438976110616dfee7b8b01bd85

Branches

Tags

  • No tags available.
0Branches0Tags
Go to file
Add file
Code

Clone

HTTPS

Download ZIP

qdk/source/paulimer/src/bits

source/paulimer/src/bits/bitmatrix.rs

1135lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4use super::bitvec::WORD_COUNT_DEFAULT;
5use super::{BitwiseNeutralElement, OverlapWeight};
6use crate::bits::bitblock::{BitAccessor, BitBlock};
7use crate::bits::{
8 BitVec, BitView, Bitwise, BitwiseBinaryOps, Dot, IndexAssignable, MutableBitView,
9};
10use crate::NeutralElement;
11use sorted_iter::assume::AssumeSortedByItemExt;
12use sorted_iter::SortedIterator;
13use std::cmp::PartialEq;
14use std::hash::Hash;
15use std::iter::FromIterator;
16use std::mem::size_of;
17use std::ops::{Add, AddAssign, BitAnd, BitAndAssign, BitXor, BitXorAssign, Mul};
18use std::ops::{Index, Range};
19use std::str::FromStr;
20
21#[must_use]
22#[derive(Debug, Eq)]
23pub struct BitMatrix<const WORD_COUNT: usize = WORD_COUNT_DEFAULT> {
24 blocks: Vec<BitBlock<WORD_COUNT>>,
25 rows: Vec<*mut BitBlock<WORD_COUNT>>,
26 columncount: usize,
27}
28
29impl<const WORD_COUNT: usize> Hash for BitMatrix<WORD_COUNT> {
30 fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
31 self.blocks.hash(state);
32 }
33}
34
35unsafe impl Sync for BitMatrix {}
36
37pub type Row<'life, const WORD_COUNT: usize = WORD_COUNT_DEFAULT> = BitView<'life, WORD_COUNT>; // should we use View in the name to indicate that it is a view and not a copy of a row ?
38pub type MutableRow<'life, const WORD_COUNT: usize = WORD_COUNT_DEFAULT> =
39 MutableBitView<'life, WORD_COUNT>; // should we use View in the name to indicate that it is a view and not a copy of a row ?
40
41#[derive(Clone, Debug, Hash)]
42pub struct Column<'life, const WORD_COUNT: usize = WORD_COUNT_DEFAULT> {
43 // TODO(VK) should we use View in the name to indicate that it is a view and not a copy of a column ?
44 rows: &'life [*mut BitBlock<WORD_COUNT>],
45 accessor: BitAccessor<WORD_COUNT>,
46 block_index: usize,
47}
48
49impl<const WORD_COUNT: usize> BitMatrix<WORD_COUNT> {
50 pub fn with_shape(rows: usize, columns: usize) -> Self {
51 Self::zeros(rows, columns)
52 }
53
54 pub fn zeros(rows: usize, columns: usize) -> Self {
55 Self::with_value(false, (rows, columns))
56 }
57
58 pub fn ones(rows: usize, columns: usize) -> Self {
59 Self::with_value(true, (rows, columns))
60 }
61
62 pub fn identity(dimension: usize) -> Self {
63 let mut res = Self::zeros(dimension, dimension);
64 for index in 0..dimension {
65 res.set((index, index), true);
66 }
67 res
68 }
69
70 pub fn from_row_iter<'life>(
71 iter: impl ExactSizeIterator<Item = BitView<'life, WORD_COUNT>>,
72 columns: usize,
73 ) -> Self {
74 let rows = iter.len();
75 let mut matrix = Self::zeros(rows, columns);
76 for (row_from, mut row_to) in std::iter::zip(iter, matrix.row_iterator_mut(0..rows)) {
77 row_to.assign(&row_from);
78 }
79 matrix
80 }
81
82 pub fn from_iter<Row, Rows>(iter: Rows, columncount: usize) -> Self
83 where
84 Row: IntoIterator<Item = bool>,
85 Rows: IntoIterator<Item = Row>,
86 {
87 // TODO(AEP): Expanding first into Vec<bool> is
88 // inefficient. Instead, append to Vec<BitBlock::<WORD_COUNT_DEFAULT>> as necessary.
89 let mut rows = Vec::<Vec<bool>>::new();
90 let mut rowcount = 0;
91 for row in iter {
92 rows.push(row.into_iter().collect());
93 rowcount += 1;
94 }
95 let mut matrix = BitMatrix::with_shape(rowcount, columncount);
96 for (row_index, row) in rows.iter().enumerate() {
97 for (column_index, value) in row.iter().take(columncount).enumerate() {
98 matrix.set((row_index, column_index), *value);
99 }
100 }
101 matrix
102 }
103
104 fn with_value(value: bool, shape: (usize, usize)) -> Self {
105 let (rowcount, columncount) = shape;
106 let rowstride = Self::rowstride_of(columncount);
107 let buffer = vec![BitBlock::<WORD_COUNT>::all(value); rowcount * rowstride];
108 Self::from_blocks(buffer, shape)
109 }
110
111 fn from_blocks(mut buffer: Vec<BitBlock<WORD_COUNT>>, shape: (usize, usize)) -> Self {
112 let rows = Self::rows_of(buffer.as_mut_slice(), shape.0);
113 Self::from_blocks_and_rows(buffer, shape, rows)
114 }
115
116 fn from_blocks_and_rows(
117 buffer: Vec<BitBlock<WORD_COUNT>>,
118 shape: (usize, usize),
119 rows: Vec<*mut BitBlock<WORD_COUNT>>,
120 ) -> Self {
121 let matrix = Self {
122 blocks: buffer,
123 rows,
124 columncount: shape.1,
125 };
126 debug_assert!(matrix.is_aligned());
127 matrix
128 }
129
130 #[must_use]
131 pub fn is_zero(&self) -> bool {
132 let zero = BitBlock::<WORD_COUNT>::zeros();
133 for block in &self.blocks {
134 if *block != zero {
135 return false;
136 }
137 }
138 true
139 }
140
141 fn is_aligned(&self) -> bool {
142 let alignment = (self.blocks.as_ptr() as usize) % size_of::<BitBlock<WORD_COUNT>>();
143 if alignment != 0 {
144 return false;
145 }
146 for row in &self.rows {
147 let alignment = (*row as usize) % size_of::<BitBlock<WORD_COUNT>>();
148 if alignment != 0 {
149 return false;
150 }
151 }
152 true
153 }
154
155 fn rowstride(&self) -> usize {
156 Self::rowstride_of(self.columncount)
157 }
158
159 fn rowstride_of(columncount: usize) -> usize {
160 let rowstride = columncount / BitBlock::<WORD_COUNT>::BITS;
161 let adjustment = !columncount.is_multiple_of(BitBlock::<WORD_COUNT>::BITS);
162 rowstride + usize::from(adjustment)
163 }
164
165 fn rows_of(
166 blocks: &mut [BitBlock<WORD_COUNT>],
167 rowcount: usize,
168 ) -> Vec<*mut BitBlock<WORD_COUNT>> {
169 let mut rows = Vec::<*mut BitBlock<WORD_COUNT>>::new();
170 let rowstride = blocks.len().checked_div(rowcount).unwrap_or(0);
171 if rowstride == 0 {
172 rows = vec![blocks.as_mut_ptr(); rowcount];
173 } else {
174 for row in blocks.chunks_exact_mut(rowstride) {
175 rows.push(row.as_mut_ptr());
176 }
177 }
178 rows
179 }
180
181 #[must_use]
182 pub fn rowcount(&self) -> usize {
183 self.rows.len()
184 }
185
186 #[must_use]
187 pub fn columncount(&self) -> usize {
188 self.columncount
189 }
190
191 #[must_use]
192 pub fn shape(&self) -> (usize, usize) {
193 (self.rowcount(), self.columncount())
194 }
195
196 #[must_use]
197 pub fn row(&self, index: usize) -> Row<'_, WORD_COUNT> {
198 Row::<WORD_COUNT> {
199 blocks: unsafe {
200 std::slice::from_raw_parts((*self.rows[index]).array(), self.block_count())
201 },
202 }
203 }
204
205 #[must_use]
206 pub fn rows(&self) -> impl ExactSizeIterator<Item = Row<'_, WORD_COUNT>> {
207 self.row_iterator(0..self.rowcount())
208 }
209
210 pub fn row_iterator(
211 &self,
212 index_iterator: impl ExactSizeIterator<Item = usize>,
213 ) -> impl ExactSizeIterator<Item = Row<'_, WORD_COUNT>> {
214 index_iterator.map(|index| self.row(index))
215 }
216
217 pub fn row_iterator_mut(
218 &mut self,
219 index_iterator: impl ExactSizeIterator<Item = usize>,
220 ) -> impl ExactSizeIterator<Item = MutableRow<'_, WORD_COUNT>> {
221 index_iterator.map(|index| self.build_mutable_row(index))
222 }
223
224 pub fn row_mut(&mut self, index: usize) -> MutableRow<'_, WORD_COUNT> {
225 self.build_mutable_row(index)
226 }
227
228 #[inline]
229 fn block_count(&self) -> usize {
230 let mut block_count = self.columncount() / BitBlock::<WORD_COUNT_DEFAULT>::BITS;
231 if !self
232 .columncount()
233 .is_multiple_of(BitBlock::<WORD_COUNT_DEFAULT>::BITS)
234 {
235 block_count += 1;
236 }
237 block_count
238 }
239
240 fn build_mutable_row(&self, index: usize) -> MutableRow<'_, WORD_COUNT> {
241 let ptr = self.rows[index];
242 MutableRow::<WORD_COUNT> {
243 blocks: unsafe {
244 std::slice::from_raw_parts_mut((*ptr).array_mut(), self.block_count())
245 },
246 }
247 }
248
249 pub fn rows_mut(
250 &mut self,
251 index: usize,
252 index2: usize,
253 ) -> (MutableRow<'_, WORD_COUNT>, MutableRow<'_, WORD_COUNT>) {
254 (
255 self.build_mutable_row(index),
256 self.build_mutable_row(index2),
257 )
258 }
259
260 pub fn rows2_mut(
261 &mut self,
262 index: (usize, usize),
263 ) -> (MutableRow<'_, WORD_COUNT>, MutableRow<'_, WORD_COUNT>) {
264 (
265 self.build_mutable_row(index.0),
266 self.build_mutable_row(index.1),
267 )
268 }
269
270 #[must_use]
271 pub fn rows2(&self, index: (usize, usize)) -> (Row<'_, WORD_COUNT>, Row<'_, WORD_COUNT>) {
272 (self.row(index.0), self.row(index.1))
273 }
274
275 /// # Safety
276 /// Does not check if all indexes are distinct
277 pub unsafe fn rows4_mut(
278 &mut self,
279 index: (usize, usize, usize, usize),
280 ) -> (
281 MutableRow<'_, WORD_COUNT>,
282 MutableRow<'_, WORD_COUNT>,
283 MutableRow<'_, WORD_COUNT>,
284 MutableRow<'_, WORD_COUNT>,
285 ) {
286 (
287 self.build_mutable_row(index.0),
288 self.build_mutable_row(index.1),
289 self.build_mutable_row(index.2),
290 self.build_mutable_row(index.3),
291 )
292 }
293
294 /// TODO(VK): Maybe use <https://doc.rust-lang.org/std/primitive.slice.html#method.get_many_mut> when it becomes stable
295 /// # Safety
296 /// Does not check if all indexes are distinct
297 pub unsafe fn rows8_mut(
298 &mut self,
299 index: crate::Tuple8<usize>,
300 ) -> crate::Tuple8<MutableRow<'_, WORD_COUNT>> {
301 (
302 self.build_mutable_row(index.0),
303 self.build_mutable_row(index.1),
304 self.build_mutable_row(index.2),
305 self.build_mutable_row(index.3),
306 self.build_mutable_row(index.4),
307 self.build_mutable_row(index.5),
308 self.build_mutable_row(index.6),
309 self.build_mutable_row(index.7),
310 )
311 }
312
313 #[must_use]
314 pub fn column(&self, index: usize) -> Column<'_, WORD_COUNT> {
315 let block_index = index / BitBlock::<WORD_COUNT_DEFAULT>::BITS;
316 let bit_index = index % BitBlock::<WORD_COUNT_DEFAULT>::BITS;
317 Column::<WORD_COUNT> {
318 rows: &self.rows,
319 accessor: BitAccessor::for_index(bit_index),
320 block_index,
321 }
322 }
323
324 #[must_use]
325 pub fn columns(&self) -> impl ExactSizeIterator<Item = Column<'_, WORD_COUNT>> {
326 let indexes = 0..self.columncount();
327 indexes.map(|index| self.column(index))
328 }
329
330 /// # Panics
331 ///
332 /// Will panic if index out of range
333 pub fn set(&mut self, index: (usize, usize), to: bool) {
334 assert!(index.0 < self.rowcount() && index.1 < self.columncount());
335 unsafe { self.set_unchecked(index, to) };
336 }
337
338 /// # Safety
339 /// Dose not check if index is out of bounds
340 pub unsafe fn set_unchecked(&mut self, index: (usize, usize), to: bool) {
341 let (block, bit_index) = self.block_index_of_mut(index);
342 block.set(bit_index, to);
343 }
344
345 /// # Panics
346 ///
347 /// Will panic if index out of range
348 #[must_use]
349 pub fn get(&self, index: (usize, usize)) -> bool {
350 assert!(index.0 < self.rowcount() && index.1 < self.columncount());
351 unsafe { self.get_unchecked(index) }
352 }
353
354 /// # Safety
355 /// Does not check if index is out of bounds
356 #[must_use]
357 pub unsafe fn get_unchecked(&self, index: (usize, usize)) -> bool {
358 let (block, bit_index) = self.block_index_of(index);
359 block.get_unchecked(bit_index)
360 }
361
362 pub fn echelonize(&mut self) -> Vec<usize> {
363 let mut pivot = pivot_of(self, (0, 0));
364 let mut rank_profile = Vec::<usize>::with_capacity(self.columncount());
365
366 for row_index in 0..self.rowcount() {
367 if pivot.1 >= self.columncount() {
368 break;
369 }
370 self.swap_rows(pivot.0, row_index);
371 pivot.0 = row_index;
372 rank_profile.push(pivot.1);
373 reduce(self, pivot);
374 pivot = pivot_of(self, (pivot.0 + 1, pivot.1 + 1));
375 }
376 rank_profile
377 }
378
379 #[must_use]
380 pub fn rank(&self) -> usize {
381 self.clone().echelonize().len()
382 }
383
384 pub fn transposed(&self) -> Self {
385 let mut res = Self::with_shape(self.columncount(), self.rowcount());
386 for i in 0..self.rowcount() {
387 for j in 0..self.columncount() {
388 res.set((j, i), self[(i, j)]);
389 }
390 }
391 res
392 }
393
394 pub fn submatrix(&self, rows: &[usize], columns: &[usize]) -> Self {
395 let mut res = Self::with_shape(rows.len(), columns.len());
396 for (row_index, &row) in rows.iter().enumerate() {
397 for (column_index, &column) in columns.iter().enumerate() {
398 res.set((row_index, column_index), self[(row, column)]);
399 }
400 }
401 res
402 }
403
404 /// # Panics
405 ///
406 /// Will panic if matrix is not invertible
407 pub fn inverted(&self) -> BitMatrix<WORD_COUNT> {
408 assert!(self.columncount() == self.rowcount());
409 let (_, t, _, profile) = rref_with_transforms(self.clone());
410 assert!(profile.len() == self.rowcount());
411 debug_assert_eq!(
412 self * &t,
413 BitMatrix::<WORD_COUNT>::identity(self.rowcount())
414 );
415 t
416 }
417
418 pub fn swap_rows(&mut self, left_row_index: usize, right_row_index: usize) {
419 self.rows.swap(left_row_index, right_row_index);
420 }
421
422 pub fn swap_columns(&mut self, left_column_index: usize, right_column_index: usize) {
423 for row_index in 0..self.rowcount() {
424 let left_bit = self.get((row_index, left_column_index));
425 let right_bit = self.get((row_index, right_column_index));
426 self.set((row_index, left_column_index), right_bit);
427 self.set((row_index, right_column_index), left_bit);
428 }
429 }
430
431 pub fn permute_rows(&mut self, permutation: &[usize]) {
432 let old_rows = self.rows.clone();
433 for index in 0..permutation.len() {
434 self.rows[index] = old_rows[permutation[index]];
435 }
436 }
437
438 pub fn add_into_row(&mut self, to_index: usize, from_index: usize) {
439 let mut to_block = self.rows[to_index];
440 let mut from_block = self.rows[from_index];
441 for _ in 0..self.rowstride() {
442 unsafe {
443 BitwiseBinaryOps::bitxor_assign(&mut *to_block, &*from_block);
444 to_block = to_block.add(1);
445 from_block = from_block.add(1);
446 }
447 }
448 }
449
450 // TODO(VK): check if we also need dot_transposed
451 /// # Panics
452 ///
453 /// Will panic if matrix dimensions are incompatible
454 pub fn dot(&self, rhs: &BitMatrix<WORD_COUNT>) -> BitMatrix<WORD_COUNT> {
455 assert_eq!(self.columncount(), rhs.rowcount());
456 let mut rows = Vec::with_capacity(self.rowcount());
457 for output_row in 0..self.rowcount() {
458 let mut row = BitVec::<WORD_COUNT>::zeros(rhs.columncount());
459 for column_index in 0..self.columncount() {
460 if self[(output_row, column_index)] {
461 // TODO(AEP): This is needlessly slow. Make it fast.
462 for into_column_index in 0..rhs.columncount() {
463 row.assign_index(
464 into_column_index,
465 row.index(into_column_index)
466 ^ rhs.get((column_index, into_column_index)),
467 );
468 }
469 }
470 }
471 rows.push(row);
472 }
473 Self::from_iter(rows.iter(), rhs.columncount())
474 }
475
476 fn block_index_of_mut(&mut self, index: (usize, usize)) -> (&mut BitBlock<WORD_COUNT>, usize) {
477 let column_block = index.1 / BitBlock::<WORD_COUNT_DEFAULT>::BITS;
478 let column_remainder = index.1 % BitBlock::<WORD_COUNT_DEFAULT>::BITS;
479 let bit_index = column_remainder % BitBlock::<WORD_COUNT_DEFAULT>::BITS;
480 unsafe {
481 let block = self.rows[index.0].add(column_block);
482 (&mut *block, bit_index)
483 }
484 }
485
486 fn block_index_of(&self, index: (usize, usize)) -> (&BitBlock<WORD_COUNT>, usize) {
487 let column_block = index.1 / BitBlock::<WORD_COUNT_DEFAULT>::BITS;
488 let column_remainder = index.1 % BitBlock::<WORD_COUNT_DEFAULT>::BITS;
489 let bit_index = column_remainder % BitBlock::<WORD_COUNT_DEFAULT>::BITS;
490 unsafe {
491 let block = self.rows[index.0].add(column_block);
492 (&*block, bit_index)
493 }
494 }
495}
496
497unsafe impl<const WORD_COUNT: usize> Send for BitMatrix<WORD_COUNT> {}
498
499impl<const WORD_COUNT: usize> Clone for BitMatrix<WORD_COUNT> {
500 fn clone(&self) -> Self {
501 let mut blocks = self.blocks.clone();
502 let mut rows = Vec::<*mut BitBlock<WORD_COUNT>>::new();
503 let offset = unsafe { blocks.as_mut_ptr().offset_from(self.blocks.as_ptr()) };
504 for row in &self.rows {
505 rows.push(unsafe { row.offset(offset) });
506 }
507 BitMatrix::from_blocks_and_rows(blocks, self.shape(), rows)
508 }
509}
510
511impl<const WORD_COUNT: usize> Index<[usize; 2]> for BitMatrix<WORD_COUNT> {
512 type Output = bool;
513
514 fn index(&self, index: [usize; 2]) -> &Self::Output {
515 &self[(index[0], index[1])]
516 }
517}
518
519impl<const WORD_COUNT: usize> Index<(usize, usize)> for BitMatrix<WORD_COUNT> {
520 type Output = bool;
521
522 fn index(&self, index: (usize, usize)) -> &Self::Output {
523 if self.get(index) {
524 return &true;
525 }
526 &false
527 }
528}
529
530impl<const WORD_COUNT: usize> PartialEq for BitMatrix<WORD_COUNT> {
531 fn eq(&self, other: &Self) -> bool {
532 if self.shape() != other.shape() {
533 return false;
534 }
535 for irow in 0..self.rowcount() {
536 for icol in 0..self.columncount() {
537 if self[(irow, icol)] != other[(irow, icol)] {
538 return false;
539 }
540 }
541 }
542 true
543 }
544}
545
546impl<const WORD_COUNT: usize> AddAssign<&BitMatrix<WORD_COUNT>> for BitMatrix<WORD_COUNT> {
547 fn add_assign(&mut self, other: &BitMatrix<WORD_COUNT>) {
548 assert_eq!(self.shape(), other.shape());
549 for index in 0..self.rowcount() {
550 self.row_mut(index).bitxor_assign(&other.row(index));
551 }
552 }
553}
554
555impl<const WORD_COUNT: usize> Add for &BitMatrix<WORD_COUNT> {
556 type Output = BitMatrix<WORD_COUNT>;
557
558 fn add(self, other: Self) -> Self::Output {
559 let mut clone = (*self).clone();
560 clone += other;
561 clone
562 }
563}
564
565impl<const WORD_COUNT: usize> BitXor for &BitMatrix<WORD_COUNT> {
566 type Output = BitMatrix<WORD_COUNT>;
567
568 fn bitxor(self, other: Self) -> Self::Output {
569 self.add(other)
570 }
571}
572
573impl<const WORD_COUNT: usize> BitXorAssign<&BitMatrix<WORD_COUNT>> for BitMatrix<WORD_COUNT> {
574 fn bitxor_assign(&mut self, other: &BitMatrix<WORD_COUNT>) {
575 self.add_assign(other);
576 }
577}
578
579impl<const WORD_COUNT: usize> BitAndAssign<&BitMatrix<WORD_COUNT>> for BitMatrix<WORD_COUNT> {
580 fn bitand_assign(&mut self, other: &Self) {
581 assert_eq!(self.shape(), other.shape());
582 for index in 0..self.rowcount() {
583 self.row_mut(index).bitand_assign(&other.row(index));
584 }
585 }
586}
587
588impl<const WORD_COUNT: usize> BitAnd for &BitMatrix<WORD_COUNT> {
589 type Output = BitMatrix<WORD_COUNT>;
590
591 fn bitand(self, other: Self) -> Self::Output {
592 let mut clone = (*self).clone();
593 clone &= other;
594 clone
595 }
596}
597
598impl<const WORD_COUNT: usize> Mul for &BitMatrix<WORD_COUNT> {
599 type Output = BitMatrix<WORD_COUNT>;
600
601 fn mul(self, other: Self) -> Self::Output {
602 assert_eq!(self.columncount(), other.rowcount());
603
604 let mut result = BitMatrix::<WORD_COUNT>::with_shape(self.rowcount(), other.columncount());
605
606 for i in 0..self.rowcount() {
607 for j in 0..other.columncount() {
608 let mut val = false;
609 for k in 0..self.columncount() {
610 val ^= self[[i, k]] && other[[k, j]];
611 }
612 result.set((i, j), val);
613 }
614 }
615
616 result
617 }
618}
619
620impl<const WORD_COUNT: usize> std::fmt::Display for BitMatrix<WORD_COUNT> {
621 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
622 for row_index in 0..self.rowcount() {
623 for column_index in 0..self.columncount() {
624 let value = i32::from(self.get((row_index, column_index)));
625 write!(f, "{value:?}")?;
626 }
627 writeln!(f)?;
628 }
629 Ok(())
630 }
631}
632
633impl<const WORD_COUNT: usize> FromStr for BitMatrix<WORD_COUNT> {
634 type Err = usize;
635
636 fn from_str(s: &str) -> Result<Self, Self::Err> {
637 let mut rows = Vec::<BitVec>::new();
638 let mut column_count = 0;
639 for row_string in s.split(&['|', '[', ']', '(', ')', ';', '\n']) {
640 if !row_string.is_empty() {
641 let mut res = Vec::<bool>::new();
642 for char in row_string.chars() {
643 match char {
644 '0' | '.' | '▫' | '□' => res.push(false),
645 '1' | '▪' | '■' => res.push(true),
646 ' ' | '-' | ',' => {}
647 _ => return Err(0),
648 }
649 }
650 if !res.is_empty() {
651 column_count = column_count.max(res.len());
652 rows.push(res.into_iter().collect());
653 }
654 }
655 }
656 Ok(BitMatrix::from_iter(rows.iter(), column_count))
657 }
658}
659
660/// # Panics
661///
662/// Should not panic. TODO: refactor so clippy does not complain
663pub fn row_stacked<'t, Matrices, const WORD_COUNT: usize>(
664 matrices: Matrices,
665) -> BitMatrix<WORD_COUNT>
666where
667 Matrices: IntoIterator<Item = &'t BitMatrix<WORD_COUNT>>,
668{
669 let mut buffer = Vec::<BitBlock<WORD_COUNT>>::new();
670 let mut columncount: Option<usize> = None;
671 let mut rowcount = 0;
672 for matrix in matrices {
673 debug_assert!(columncount.is_none() || columncount.unwrap() == matrix.columncount());
674 buffer.append(&mut matrix.blocks.clone());
675 columncount = Some(matrix.columncount());
676 rowcount += matrix.rowcount();
677 }
678 BitMatrix::<WORD_COUNT>::from_blocks(buffer, (rowcount, *columncount.get_or_insert(0)))
679}
680
681pub fn directly_summed<'t, Matrices>(matrices: Matrices) -> BitMatrix
682where
683 Matrices: IntoIterator<Item = &'t BitMatrix>,
684{
685 let mut rowcount = 0;
686 let mut columncount = 0;
687 let vec_matrices = Vec::from_iter(matrices);
688 for matrix in &vec_matrices {
689 rowcount += matrix.rowcount();
690 columncount += matrix.columncount();
691 }
692 let mut sum = BitMatrix::zeros(rowcount, columncount);
693 let mut sum_row_offset = 0;
694 let mut sum_column_offset = 0;
695 for matrix in &vec_matrices {
696 for row_index in 0..matrix.rowcount() {
697 for column_index in 0..matrix.columncount() {
698 sum.set(
699 (row_index + sum_row_offset, column_index + sum_column_offset),
700 matrix[(row_index, column_index)],
701 );
702 }
703 }
704 sum_row_offset += matrix.rowcount();
705 sum_column_offset += matrix.columncount();
706 }
707 sum
708}
709
710fn pivot_of<const WORD_COUNT: usize>(
711 matrix: &BitMatrix<WORD_COUNT>,
712 starting_at: (usize, usize),
713) -> (usize, usize) {
714 let (mut row_index, mut column_index) = starting_at;
715 if row_index >= matrix.rowcount() || column_index >= matrix.columncount() {
716 return (row_index, column_index);
717 }
718 while !matrix.get((row_index, column_index)) {
719 row_index += 1;
720 if row_index == matrix.rowcount() {
721 column_index += 1;
722 row_index = starting_at.0;
723 if column_index == matrix.columncount() {
724 break;
725 }
726 }
727 }
728 (row_index, column_index)
729}
730
731struct ReductionData<const WORD_COUNT: usize> {
732 column_accessor: BitAccessor<WORD_COUNT>,
733 blocks_per_row: usize,
734 rowstride: usize,
735 base_block: *const BitBlock<WORD_COUNT>,
736 from_block: *mut BitBlock<WORD_COUNT>,
737}
738
739impl<const WORD_COUNT: usize> ReductionData<WORD_COUNT> {
740 pub fn for_pivot(pivot: (usize, usize), within: &BitMatrix<WORD_COUNT>) -> Self {
741 let start_block_offset = pivot.1 / BitBlock::<WORD_COUNT>::BITS;
742 let bit_index = pivot.1 % BitBlock::<WORD_COUNT>::BITS;
743 let from_block = unsafe { within.rows.get_unchecked(pivot.0).add(start_block_offset) };
744 let base_block = unsafe { within.blocks.as_ptr().add(start_block_offset) };
745 let rowstride = within.rowstride();
746
747 ReductionData {
748 column_accessor: BitAccessor::for_index(bit_index),
749 blocks_per_row: rowstride - start_block_offset,
750 rowstride,
751 from_block,
752 base_block,
753 }
754 }
755}
756
757fn reduce<const WORD_COUNT: usize>(matrix: &mut BitMatrix<WORD_COUNT>, from: (usize, usize)) {
758 let data = ReductionData::for_pivot(from, matrix);
759 let mut to_block = data.from_block;
760 to_block = reduce_backward_until(data.base_block, to_block, &data);
761 to_block = unsafe { to_block.add(data.rowstride * matrix.rowcount()) };
762 let until_block = unsafe { data.from_block.add(data.rowstride) };
763 reduce_backward_until(until_block, to_block, &data);
764}
765
766fn reduce_backward_until<const WORD_COUNT: usize>(
767 until_block: *const BitBlock<WORD_COUNT>,
768 mut to_block: *mut BitBlock<WORD_COUNT>,
769 data: &ReductionData<WORD_COUNT>,
770) -> *mut BitBlock<WORD_COUNT> {
771 while until_block != to_block {
772 to_block = unsafe { to_block.sub(data.rowstride) };
773 let column_value = unsafe { data.column_accessor.array_value_of((*to_block).array()) };
774 if column_value {
775 add_into_block(to_block, data.from_block, data.blocks_per_row);
776 }
777 }
778 to_block
779}
780
781fn add_into_block<const WORD_COUNT: usize>(
782 mut to_block: *mut BitBlock<WORD_COUNT>,
783 mut from_block: *const BitBlock<WORD_COUNT>,
784 block_count: usize,
785) {
786 for _ in 0..block_count {
787 unsafe {
788 *to_block ^= &*from_block;
789 to_block = to_block.add(1);
790 from_block = from_block.add(1);
791 }
792 }
793}
794
795/// # Returns
796/// Row reduced echelon form R of `matrix` , transformation matrix T and , inverse transpose of T,
797/// and row rank profile.
798/// T * `matrix` equals R
799pub fn rref_with_transforms<const WORD_COUNT: usize>(
800 mut matrix: BitMatrix<WORD_COUNT>,
801) -> (
802 BitMatrix<WORD_COUNT>,
803 BitMatrix<WORD_COUNT>,
804 BitMatrix<WORD_COUNT>,
805 Vec<usize>,
806) {
807 let num_rows = matrix.rowcount();
808 let mut transform = BitMatrix::identity(num_rows);
809 let mut transform_inv_t = BitMatrix::identity(num_rows);
810 let mut pivot = pivot_of(&matrix, (0, 0));
811 let mut rank_profile = Vec::<usize>::with_capacity(matrix.columncount());
812
813 for row_index in 0..matrix.rowcount() {
814 if pivot.1 >= matrix.columncount() {
815 break;
816 }
817
818 matrix.swap_rows(pivot.0, row_index);
819 transform_inv_t.swap_rows(pivot.0, row_index);
820 transform.swap_rows(pivot.0, row_index);
821
822 pivot.0 = row_index;
823 rank_profile.push(pivot.1);
824 reduce_with_transforms(&mut matrix, &mut transform, &mut transform_inv_t, pivot);
825 pivot = pivot_of(&matrix, (pivot.0 + 1, pivot.1 + 1));
826 }
827 (matrix, transform, transform_inv_t, rank_profile)
828}
829
830fn reduce_with_transforms<const WORD_COUNT: usize>(
831 matrix: &mut BitMatrix<WORD_COUNT>,
832 transform: &mut BitMatrix<WORD_COUNT>,
833 transform_inv_t: &mut BitMatrix<WORD_COUNT>,
834 from: (usize, usize),
835) {
836 let rowcount = matrix.rowcount();
837 for row_index in 0..from.0 {
838 xor_if_column_with_transforms(
839 from.1,
840 matrix,
841 transform,
842 transform_inv_t,
843 row_index,
844 from.0,
845 );
846 }
847 for row_index in from.0 + 1..rowcount {
848 xor_if_column_with_transforms(
849 from.1,
850 matrix,
851 transform,
852 transform_inv_t,
853 row_index,
854 from.0,
855 );
856 }
857}
858
859fn xor_if_column_with_transforms<const WORD_COUNT: usize>(
860 column_index: usize,
861 matrix: &mut BitMatrix<WORD_COUNT>,
862 transform: &mut BitMatrix<WORD_COUNT>,
863 transform_inv_t: &mut BitMatrix<WORD_COUNT>,
864 row_index: usize,
865 from_row_index: usize,
866) {
867 if matrix[(row_index, column_index)] {
868 matrix.add_into_row(row_index, from_row_index);
869 transform.add_into_row(row_index, from_row_index);
870 transform_inv_t.add_into_row(from_row_index, row_index);
871 }
872}
873
874pub fn kernel_basis_matrix<const WORD_COUNT: usize>(
875 matrix: &BitMatrix<WORD_COUNT>,
876) -> BitMatrix<WORD_COUNT> {
877 let num_cols = matrix.columncount();
878 let mut rr = matrix.clone();
879 let rank_profile = rr.echelonize();
880 let rank_profile_complement = crate::setwise::complement(&rank_profile, num_cols);
881 let res_row_count = num_cols - rank_profile.len();
882 let mut res = BitMatrix::zeros(res_row_count, num_cols);
883 for (index, elt) in rank_profile.into_iter().enumerate() {
884 for (row_pos, col_src) in rank_profile_complement
885 .iter()
886 .enumerate()
887 .take(res_row_count)
888 {
889 res.set((row_pos, elt), rr[(index, *col_src)]);
890 }
891 }
892 for (index, position) in rank_profile_complement.into_iter().enumerate() {
893 res.set((index, position), true);
894 }
895 res
896}
897
898pub fn full_rank_row_completion_with_inv<const WORD_COUNT: usize>(
899 _matrix: &BitMatrix<WORD_COUNT>,
900) -> (BitMatrix<WORD_COUNT>, BitMatrix<WORD_COUNT>) {
901 // let _num_cols = matrix.columncount();
902 // let rr = matrix.clone();
903 // let rr2 = matrix.clone();
904 // (rr,rr2);
905 todo!()
906}
907
908impl<const WORD_COUNT: usize> Bitwise for Column<'_, WORD_COUNT> {
909 fn weight(&self) -> usize {
910 self.into_iter().filter(|bit| *bit).count()
911 }
912
913 fn support(&self) -> impl SortedIterator<Item = usize> {
914 Box::new(
915 self.into_iter()
916 .enumerate()
917 .filter(|pair| pair.1)
918 .map(|pair| pair.0),
919 )
920 .assume_sorted_by_item()
921 }
922
923 fn index(&self, index: usize) -> bool {
924 let block = unsafe { &*self.rows[index].add(self.block_index) };
925 self.accessor.array_value_of(block.array())
926 }
927}
928
929impl<const WORD_COUNT: usize> Dot for Column<'_, WORD_COUNT> {
930 fn dot(&self, other: &Self) -> bool {
931 assert_eq!(self.rows.len(), other.rows.len());
932 let mut result = false;
933 for index in 0..self.rows.len() {
934 result ^= self.index(index) & other.index(index);
935 }
936 result
937 }
938}
939
940impl<const WORD_COUNT: usize> OverlapWeight for Column<'_, WORD_COUNT> {
941 fn and_weight(&self, other: &Self) -> usize {
942 assert_eq!(self.rows.len(), other.rows.len());
943 let mut result = 0usize;
944 for index in 0..self.rows.len() {
945 if self.index(index) & other.index(index) {
946 result += 1;
947 }
948 }
949 result
950 }
951
952 fn or_weight(&self, other: &Self) -> usize {
953 assert_eq!(self.rows.len(), other.rows.len());
954 let mut result = 0usize;
955 for index in 0..self.rows.len() {
956 if self.index(index) | other.index(index) {
957 result += 1;
958 }
959 }
960 result
961 }
962}
963
964impl<const WORD_COUNT: usize> PartialEq for Column<'_, WORD_COUNT> {
965 fn eq(&self, other: &Self) -> bool {
966 if self.rows.len() != other.rows.len() {
967 return false;
968 }
969 for index in 0..self.rows.len() {
970 if self.index(index) != other.index(index) {
971 return false;
972 }
973 }
974 true
975 }
976}
977
978impl<const WORD_COUNT: usize> Eq for Column<'_, WORD_COUNT> {}
979
980impl<const WORD_COUNT: usize> Column<'_, WORD_COUNT> {
981 #[must_use]
982 pub fn slice(&self, range: Range<usize>) -> Self {
983 Column {
984 rows: &self.rows[range],
985 accessor: self.accessor.clone(),
986 block_index: self.block_index,
987 }
988 }
989
990 #[must_use]
991 pub fn len(&self) -> usize {
992 self.rows.len()
993 }
994
995 #[must_use]
996 pub fn is_empty(&self) -> bool {
997 self.len() == 0
998 }
999}
1000
1001// impl<'life,const WORD_COUNT: usize> IntoIterator for Column<'life,WORD_COUNT> {
1002// type Item = bool;
1003// type IntoIter = ColumnIterator<'life,WORD_COUNT>;
1004// fn into_iter(self) -> Self::IntoIter {
1005// ColumnIterator {
1006// column: self,
1007// row_index: 0,
1008// }
1009// }
1010// }
1011
1012impl<'life, const WORD_COUNT: usize> IntoIterator for &'life Column<'_, WORD_COUNT> {
1013 type Item = bool;
1014 type IntoIter = ColumnIterator<'life, WORD_COUNT>;
1015 fn into_iter(self) -> Self::IntoIter {
1016 ColumnIterator {
1017 column: self,
1018 row_index: 0,
1019 }
1020 }
1021}
1022
1023impl<const WORD_COUNT: usize> Column<'_, WORD_COUNT> {
1024 #[must_use]
1025 pub fn iter(&self) -> ColumnIterator<'_, WORD_COUNT> {
1026 <&Self as IntoIterator>::into_iter(self)
1027 }
1028}
1029
1030pub struct ColumnIterator<'life, const WORD_COUNT: usize = WORD_COUNT_DEFAULT> {
1031 column: &'life Column<'life, WORD_COUNT>,
1032 row_index: usize,
1033}
1034
1035impl<const WORD_COUNT: usize> Iterator for ColumnIterator<'_, WORD_COUNT> {
1036 type Item = bool;
1037
1038 fn next(&mut self) -> Option<Self::Item> {
1039 if self.row_index >= self.column.rows.len() {
1040 return None;
1041 }
1042 let output = self.column.index(self.row_index);
1043 self.row_index += 1;
1044 Some(output)
1045 }
1046}
1047
1048impl<const WORD_COUNT: usize> NeutralElement for Column<'_, WORD_COUNT> {
1049 type NeutralElementType = BitVec<WORD_COUNT>;
1050
1051 fn neutral_element(&self) -> Self::NeutralElementType {
1052 BitVec::<WORD_COUNT>::zeros(self.rows.len())
1053 }
1054
1055 fn default_size_neutral_element() -> Self::NeutralElementType {
1056 Self::NeutralElementType::default_size_neutral_element()
1057 }
1058
1059 fn neutral_element_of_size(size: usize) -> Self::NeutralElementType {
1060 Self::NeutralElementType::neutral_element_of_size(size)
1061 }
1062}
1063
1064impl<const WORD_COUNT: usize> BitwiseNeutralElement for Column<'_, WORD_COUNT> {}
1065
1066impl<'life, const WORD_COUNT: usize> BitwiseBinaryOps<Column<'life, WORD_COUNT>>
1067 for BitVec<WORD_COUNT>
1068{
1069 fn assign(&mut self, other: &Column<'life, WORD_COUNT>) {
1070 for (index, val) in other.into_iter().enumerate() {
1071 self.assign_index(index, val);
1072 }
1073 }
1074
1075 fn bitxor_assign(&mut self, other: &Column<'life, WORD_COUNT>) {
1076 for (index, val) in other.into_iter().enumerate() {
1077 if val {
1078 self.negate_index(index);
1079 }
1080 }
1081 }
1082
1083 fn bitand_assign(&mut self, other: &Column<'life, WORD_COUNT>) {
1084 for (index, val) in other.into_iter().enumerate() {
1085 if !val {
1086 self.assign_index(index, false);
1087 }
1088 }
1089 }
1090}
1091
1092impl<'life1, const WORD_COUNT_1: usize, const WORD_COUNT_2: usize>
1093 BitwiseBinaryOps<Column<'life1, WORD_COUNT_1>> for MutableBitView<'_, WORD_COUNT_2>
1094{
1095 fn assign(&mut self, other: &Column<'life1, WORD_COUNT_1>) {
1096 for (index, val) in other.into_iter().enumerate() {
1097 self.assign_index(index, val);
1098 }
1099 }
1100
1101 fn bitxor_assign(&mut self, other: &Column<'life1, WORD_COUNT_1>) {
1102 for (index, val) in other.into_iter().enumerate() {
1103 if val {
1104 self.negate_index(index);
1105 }
1106 }
1107 }
1108
1109 fn bitand_assign(&mut self, other: &Column<'life1, WORD_COUNT_1>) {
1110 for (index, val) in other.into_iter().enumerate() {
1111 if !val {
1112 self.assign_index(index, false);
1113 }
1114 }
1115 }
1116}
1117
1118pub fn is_zero_padded_identity(row_iterator: impl ExactSizeIterator<Item: Bitwise>) -> bool {
1119 row_iterator
1120 .into_iter()
1121 .enumerate()
1122 .all(|(row_index, row)| row.is_one_bit(row_index))
1123}
1124
1125pub fn is_zero_padded_symmetric<'life, const WORD_COUNT: usize>(
1126 row_iterator: impl ExactSizeIterator<Item = BitView<'life, WORD_COUNT>>,
1127 column_count: usize,
1128) -> bool {
1129 let matrix = BitMatrix::from_row_iter(row_iterator, column_count);
1130 matrix == matrix.transposed()
1131}
1132
1133pub fn are_zero_rows(mut row_iterator: impl Iterator<Item: Bitwise>) -> bool {
1134 row_iterator.all(|row| row.is_zero())
1135}
1136